- java.lang.Object
-
- org.jgrapht.alg.planar.BoyerMyrvoldPlanarityInspector.Node
-
- Enclosing class:
- BoyerMyrvoldPlanarityInspector<V,E>
private class BoyerMyrvoldPlanarityInspector.Node extends java.lang.Object
The internal representation of the vertices of the graph. Contains necessary information to perform dfs traversals, biconnected component boundary traversals, to embed edges, etc.
-
-
Field Summary
Fields Modifier and Type Field Description (package private) int
backEdgeFlag
During the process of embedding of the down edges of the node $v$, this variable is set to the dfs index of $v$ to indicate that this node has a back edge incident to $v$, which needs to be embedded.(package private) java.util.List<BoyerMyrvoldPlanarityInspector.Edge>
backEdges
The list of back edges incident to this node.(package private) int
boundaryHeight
The height of this node on the boundary of the biconnected component, which is used to extract the Kuratowski subdivision.(package private) int
dfsIndex
The dfs index of this node in the graph.(package private) java.util.List<BoyerMyrvoldPlanarityInspector.Edge>
downEdges
The list containing the edges from descendants of this node in the dfs tree.(package private) BoyerMyrvoldPlanarityInspector.Edge
edgeToEmbed
If this node has a back edge incident to the currently processed node $v$, then this variable stores this edge(package private) DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Edge>
embedded
The list of the embedded edges incident to this node in a clockwise or a counterclockwise order.(package private) V
graphVertex
The counterpart of this node in thegraph
.(package private) int
height
The height of the node in the created dfs tree.(package private) BoyerMyrvoldPlanarityInspector.Node
initialComponentRoot
The component root the node is created in.(package private) int
leastAncestor
The least dfs index of the nodes adjacent to this node.(package private) DoublyLinkedList.ListNode<BoyerMyrvoldPlanarityInspector.Node>
listNode
Stores the list node from theseparatedDfsChildList
of the parent node this node is stored in.(package private) int
lowpoint
The least dfs index of the nodes' least ancestors in the subtree rooted at this node.(package private) boolean
marked
Used to mark the boundary nodes of the biconnected(package private) BoyerMyrvoldPlanarityInspector.Node[]
outerFaceNeighbors
Two neighbors on the outer face of the biconnected component.(package private) BoyerMyrvoldPlanarityInspector.Edge
parentEdge
Edge to the parent node of this node in the dfs tree.(package private) DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Node>
pertinentRoots
The roots of the pertinent components during the processing of the node $v$.(package private) boolean
rootVertex
Whether this node is a root of the biconnected component or not.(package private) DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Node>
separatedDfsChildList
The list containing the dfs children of this node, which are in the different child biconnected component, i.e.(package private) java.util.List<BoyerMyrvoldPlanarityInspector.Edge>
treeEdges
The list of tree edges incident to this node in the dfs tree.(package private) int
visited
Stores some value to indicate whether this node is visited in the current context or not.
-
Constructor Summary
Constructors Constructor Description Node(int dfsIndex, BoyerMyrvoldPlanarityInspector.Edge parentEdge)
Creates a new component root.Node(V graphVertex, int dfsIndex, int height, BoyerMyrvoldPlanarityInspector.Node initialComponentRoot, BoyerMyrvoldPlanarityInspector.Edge parentEdge)
Creates a new real node with the specified parameters.Node(V graphVertex, int dfsIndex, BoyerMyrvoldPlanarityInspector.Edge parentEdge, boolean rootVertex)
Creates a new node with the specified parameters
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) void
checkIsAdjacent(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node has a neighbornode
on the boundary of the biconnected component(package private) void
embedBackEdge(BoyerMyrvoldPlanarityInspector.Edge edge, BoyerMyrvoldPlanarityInspector.Node prev)
Addsedge
to the list of the embedded edges such that theprev
node becomes an inner node.(package private) BoyerMyrvoldPlanarityInspector.Node
getParent()
Returns the parent of this node in the dfs tree.(package private) boolean
hasBackEdgeWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node has a back edge to thenode
.(package private) boolean
hasRootNeighbor()
Checks whether this node has a neighbor, which is a root of a biconnected component(package private) boolean
isActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Check whether this node is active.(package private) boolean
isExternallyActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node is externally active with respect to thenode
.(package private) boolean
isInactiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Check whether this node is inactive.(package private) boolean
isInternallyActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Check whether this node is internally active.(package private) boolean
isPertinentWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node is pertinent in the context of processing the nodenode
.(package private) boolean
isRootVertex()
Returns true if the node is a component root, false otherwise(package private) boolean
isVisitedWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node is visited in the context of processing the nodenode
(package private) BoyerMyrvoldPlanarityInspector.OuterFaceCirculator
iterator(int direction)
Returns a circulator, that moves in the directiondirection
.(package private) void
mergeChildEdges(DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Edge> edges, int vIn, int vOut, BoyerMyrvoldPlanarityInspector.Node parentNext, BoyerMyrvoldPlanarityInspector.Edge parentEdge)
Merges the embedded edges of the child component root into this node's embedded edges.(package private) BoyerMyrvoldPlanarityInspector.Node
nextOnOuterFace(BoyerMyrvoldPlanarityInspector.Node prev)
Returns a neighbor of this node which is not equal to theprev
(package private) void
removeShortCircuitEdges()
(package private) void
substitute(BoyerMyrvoldPlanarityInspector.Node node, BoyerMyrvoldPlanarityInspector.Node newNeighbor)
Substitutes the neighbornode
with anewNeighbor
(package private) void
substituteAnother(BoyerMyrvoldPlanarityInspector.Node node, BoyerMyrvoldPlanarityInspector.Node newNeighbor)
Substitutes a neighbor of this node, which is not equal to thenode
, with thenewNeighbor
(package private) void
swapNeighbors()
Swaps the outer face neighbors of this nodejava.lang.String
toString()
java.lang.String
toString(boolean full)
Returns a full or a partial string representation of this node
-
-
-
Field Detail
-
graphVertex
V graphVertex
The counterpart of this node in thegraph
. For the component roots this value isnull
.
-
rootVertex
boolean rootVertex
Whether this node is a root of the biconnected component or not.
-
dfsIndex
int dfsIndex
The dfs index of this node in the graph. Every node has a unique dfs index in the range $[0,|V| - 1]$. This value is used to order the nodes for the embedding of the edges incident to them. The index of the first dfs root is $1$
-
height
int height
The height of the node in the created dfs tree. The root of the tree has height $0$. The smaller this value is, the lower the node is considered to be.
-
lowpoint
int lowpoint
The least dfs index of the nodes' least ancestors in the subtree rooted at this node. If the subtree doesn't contain a node with a back edge, that ends lower that this node, this value is equal to the dfs index of this node.
-
leastAncestor
int leastAncestor
The least dfs index of the nodes adjacent to this node. If the node doesn't have incident back edges, this value is equal to the dfs index of the node itself.
-
visited
int visited
Stores some value to indicate whether this node is visited in the current context or not. During the testing phase, if this value if equal to the dfs index of the currently processed node $v$, then this node is visited, otherwise not. During the Kuratowski subdivision extraction phase, the value of $0$ indicates that the node isn't visited, otherwise, the node is considered to be visited.
-
backEdgeFlag
int backEdgeFlag
During the process of embedding of the down edges of the node $v$, this variable is set to the dfs index of $v$ to indicate that this node has a back edge incident to $v$, which needs to be embedded.
-
boundaryHeight
int boundaryHeight
The height of this node on the boundary of the biconnected component, which is used to extract the Kuratowski subdivision. The height of the component root is $0$, the heights on the left side are positive, on the right side - negative. This value is used to quickly determine for two nodes on the same boundary branch which one is higher (closer to the component root).
-
marked
boolean marked
Used to mark the boundary nodes of the biconnected
-
parentEdge
BoyerMyrvoldPlanarityInspector.Edge parentEdge
Edge to the parent node of this node in the dfs tree. For tree roots this value isnull
-
edgeToEmbed
BoyerMyrvoldPlanarityInspector.Edge edgeToEmbed
If this node has a back edge incident to the currently processed node $v$, then this variable stores this edge
-
initialComponentRoot
BoyerMyrvoldPlanarityInspector.Node initialComponentRoot
The component root the node is created in. For dfs tree roots this value isnull
-
outerFaceNeighbors
BoyerMyrvoldPlanarityInspector.Node[] outerFaceNeighbors
Two neighbors on the outer face of the biconnected component. Their order is completely irrelevant for the algorithm to traverse the outer face.
-
separatedDfsChildList
DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Node> separatedDfsChildList
The list containing the dfs children of this node, which are in the different child biconnected component, i.e. their weren't merged in the parent component.
-
pertinentRoots
DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Node> pertinentRoots
The roots of the pertinent components during the processing of the node $v$. These are the components that have pertinent descendant nodes, i.e. nodes incident to the node $v$ via a back edge
-
treeEdges
java.util.List<BoyerMyrvoldPlanarityInspector.Edge> treeEdges
The list of tree edges incident to this node in the dfs tree. This list doesn't contain a parent edge of this node
-
downEdges
java.util.List<BoyerMyrvoldPlanarityInspector.Edge> downEdges
The list containing the edges from descendants of this node in the dfs tree. For each such descendant the corresponding edge is a back edge.
-
backEdges
java.util.List<BoyerMyrvoldPlanarityInspector.Edge> backEdges
The list of back edges incident to this node.
-
listNode
DoublyLinkedList.ListNode<BoyerMyrvoldPlanarityInspector.Node> listNode
Stores the list node from theseparatedDfsChildList
of the parent node this node is stored in. This enable deleting of this node from theseparatedDfsChildList
list in $\mathcal{O}(1)$ time
-
embedded
DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Edge> embedded
The list of the embedded edges incident to this node in a clockwise or a counterclockwise order. The order is counterclockwise if the product of the signs of the parent edges along the path from the root of the component this node is contained in to this node is equal to $-1$. Otherwise, the order is clockwise.
-
-
Constructor Detail
-
Node
Node(V graphVertex, int dfsIndex, int height, BoyerMyrvoldPlanarityInspector.Node initialComponentRoot, BoyerMyrvoldPlanarityInspector.Edge parentEdge)
Creates a new real node with the specified parameters.- Parameters:
graphVertex
- the counterpart of this node in thegraph
dfsIndex
- the dfs index of this nodeheight
- the height of this node in the dfs treeinitialComponentRoot
- the component root of this node.parentEdge
- the parent edge of this node
-
Node
Node(int dfsIndex, BoyerMyrvoldPlanarityInspector.Edge parentEdge)
Creates a new component root. Dfs index of the component root is equal to dfs index of its parent.- Parameters:
dfsIndex
- the dfs index of this nodeparentEdge
- the parent edge of this component root
-
Node
Node(V graphVertex, int dfsIndex, BoyerMyrvoldPlanarityInspector.Edge parentEdge, boolean rootVertex)
Creates a new node with the specified parameters- Parameters:
graphVertex
- the vertex in thegraph
corresponding to this nodedfsIndex
- the dfs index of this nodeparentEdge
- the parent edge of this noderootVertex
- whether this is real or virtual node
-
-
Method Detail
-
isVisitedWrtTo
boolean isVisitedWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node is visited in the context of processing the nodenode
- Parameters:
node
- the node that is currently been processed- Returns:
- true if this node is visited, false otherwise
-
isPertinentWrtTo
boolean isPertinentWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node is pertinent in the context of processing the nodenode
. During the processing of the nodenode
, a node is pertinent if it has a back edge tonode
or it has a child biconnected component, which has a pertinent node.- Parameters:
node
- the node that is currently been processed- Returns:
- true if this node is pertinent, false otherwise
-
hasBackEdgeWrtTo
boolean hasBackEdgeWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node has a back edge to thenode
.- Parameters:
node
- the other endpoint of the edge we're looking for- Returns:
- true if the edge between this node and
node
exists, false otherwise
-
isExternallyActiveWrtTo
boolean isExternallyActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node is externally active with respect to thenode
. A node is externally active, if it is incident to the edge ending higher thannode
, or it has a child biconnected component with a pertinent node- Parameters:
node
- an ancestor of this node- Returns:
- true if this node is externally active with respect to the
node
, false otherwise
-
isRootVertex
boolean isRootVertex()
Returns true if the node is a component root, false otherwise- Returns:
- true if the node is a component root, false otherwise
-
isInternallyActiveWrtTo
boolean isInternallyActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Check whether this node is internally active. A node is internally active if it's pertinent and not externally active- Parameters:
node
- an ancestor of this node- Returns:
- true if this node is internally active, false otherwise
-
isInactiveWrtTo
boolean isInactiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Check whether this node is inactive. A node is inactive it is neither pertinent nor externally active- Parameters:
node
- an ancestor of this node- Returns:
- true if this node is inactive, false otherwise
-
isActiveWrtTo
boolean isActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node)
Check whether this node is active. A node is active it is either pertinent or externally active- Parameters:
node
- an ancestor of this node- Returns:
- true if this node is active, false otherwise
-
iterator
BoyerMyrvoldPlanarityInspector.OuterFaceCirculator iterator(int direction)
Returns a circulator, that moves in the directiondirection
. The next node along the traversal will bethis.outerFaceNeighbor[direction]
.- Parameters:
direction
- the direction to move in- Returns:
- an iterator over the boundary nodes in the direction
direction
-
removeShortCircuitEdges
void removeShortCircuitEdges()
-
getParent
BoyerMyrvoldPlanarityInspector.Node getParent()
Returns the parent of this node in the dfs tree. Tree parent of the dfs root node isnull
- Returns:
- the parent of this node in the dfs tree
-
checkIsAdjacent
void checkIsAdjacent(BoyerMyrvoldPlanarityInspector.Node node)
Checks whether this node has a neighbornode
on the boundary of the biconnected component- Parameters:
node
- a possible neighbor of this node
-
swapNeighbors
void swapNeighbors()
Swaps the outer face neighbors of this node
-
substitute
void substitute(BoyerMyrvoldPlanarityInspector.Node node, BoyerMyrvoldPlanarityInspector.Node newNeighbor)
Substitutes the neighbornode
with anewNeighbor
- Parameters:
node
- an old neighbornewNeighbor
- a new neighbor
-
substituteAnother
void substituteAnother(BoyerMyrvoldPlanarityInspector.Node node, BoyerMyrvoldPlanarityInspector.Node newNeighbor)
Substitutes a neighbor of this node, which is not equal to thenode
, with thenewNeighbor
- Parameters:
node
- the remaining neighbornewNeighbor
- a new neighbor
-
hasRootNeighbor
boolean hasRootNeighbor()
Checks whether this node has a neighbor, which is a root of a biconnected component- Returns:
- true, if this node has a root node neighbor, false otherwise
-
nextOnOuterFace
BoyerMyrvoldPlanarityInspector.Node nextOnOuterFace(BoyerMyrvoldPlanarityInspector.Node prev)
Returns a neighbor of this node which is not equal to theprev
- Parameters:
prev
- a neighbor of this node- Returns:
- a neightbor, which is not equal to the
prev
-
embedBackEdge
void embedBackEdge(BoyerMyrvoldPlanarityInspector.Edge edge, BoyerMyrvoldPlanarityInspector.Node prev)
Addsedge
to the list of the embedded edges such that theprev
node becomes an inner node.- Parameters:
edge
- an edge to embedprev
- the node which should be on the new inner face
-
mergeChildEdges
void mergeChildEdges(DoublyLinkedList<BoyerMyrvoldPlanarityInspector.Edge> edges, int vIn, int vOut, BoyerMyrvoldPlanarityInspector.Node parentNext, BoyerMyrvoldPlanarityInspector.Edge parentEdge)
Merges the embedded edges of the child component root into this node's embedded edges. Note, that the edges in theedges
list are always in the clockwise order. There are 3 parameters which determine how theedges
list is merged: thevIn
direction, thevOut
direction and the orientation of the edges around this node (clockwise or counterclockwise). The edges in theedges
list should have the same orientation. If this list is inverted, the sign of theparentEdge
is set to $-1$.- Parameters:
edges
- the edges from the child component rootvIn
- the direction used to enter the parent componentvOut
- the direction used to enter the child componentparentNext
- the next node along the traversal of the parent biconnected componentparentEdge
- the parent edge if the child component
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
toString
public java.lang.String toString(boolean full)
Returns a full or a partial string representation of this node- Parameters:
full
- whether to return full or partial string representation of this node- Returns:
- either full or partial string representation of this node
-
-