java.lang.Object
org.jgrapht.alg.planar.BoyerMyrvoldPlanarityInspector.Node
- Enclosing class:
BoyerMyrvoldPlanarityInspector<V,
E>
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
FieldsModifier and TypeFieldDescription(package private) int
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) List
<BoyerMyrvoldPlanarityInspector<V, E>.Edge> The list of back edges incident to this node.(package private) int
The height of this node on the boundary of the biconnected component, which is used to extract the Kuratowski subdivision.(package private) int
The dfs index of this node in the graph.(package private) List
<BoyerMyrvoldPlanarityInspector<V, E>.Edge> The list containing the edges from descendants of this node in the dfs tree.(package private) BoyerMyrvoldPlanarityInspector<V,
E>.Edge If this node has a back edge incident to the currently processed node $v$, then this variable stores this edge(package private) DoublyLinkedList
<BoyerMyrvoldPlanarityInspector<V, E>.Edge> The list of the embedded edges incident to this node in a clockwise or a counterclockwise order.(package private) V
The counterpart of this node in thegraph
.(package private) int
The height of the node in the created dfs tree.(package private) BoyerMyrvoldPlanarityInspector<V,
E>.Node The component root the node is created in.(package private) int
The least dfs index of the nodes adjacent to this node.(package private) DoublyLinkedList.ListNode
<BoyerMyrvoldPlanarityInspector<V, E>.Node> Stores the list node from theseparatedDfsChildList
of the parent node this node is stored in.(package private) int
The least dfs index of the nodes' least ancestors in the subtree rooted at this node.(package private) boolean
Used to mark the boundary nodes of the biconnected(package private) BoyerMyrvoldPlanarityInspector<V,
E>.Node[] Two neighbors on the outer face of the biconnected component.(package private) BoyerMyrvoldPlanarityInspector<V,
E>.Edge Edge to the parent node of this node in the dfs tree.(package private) DoublyLinkedList
<BoyerMyrvoldPlanarityInspector<V, E>.Node> The roots of the pertinent components during the processing of the node $v$.(package private) boolean
Whether this node is a root of the biconnected component or not.(package private) DoublyLinkedList
<BoyerMyrvoldPlanarityInspector<V, E>.Node> The list containing the dfs children of this node, which are in the different child biconnected component, i.e.(package private) List
<BoyerMyrvoldPlanarityInspector<V, E>.Edge> The list of tree edges incident to this node in the dfs tree.(package private) int
Stores some value to indicate whether this node is visited in the current context or not. -
Constructor Summary
ConstructorsConstructorDescriptionNode
(int dfsIndex, BoyerMyrvoldPlanarityInspector<V, E>.Edge parentEdge) Creates a new component root.Node
(V graphVertex, int dfsIndex, int height, BoyerMyrvoldPlanarityInspector<V, E>.Node initialComponentRoot, BoyerMyrvoldPlanarityInspector<V, E>.Edge parentEdge) Creates a new real node with the specified parameters.Node
(V graphVertex, int dfsIndex, BoyerMyrvoldPlanarityInspector<V, E>.Edge parentEdge, boolean rootVertex) Creates a new node with the specified parameters -
Method Summary
Modifier and TypeMethodDescription(package private) void
Checks whether this node has a neighbornode
on the boundary of the biconnected component(package private) void
embedBackEdge
(BoyerMyrvoldPlanarityInspector<V, E>.Edge edge, BoyerMyrvoldPlanarityInspector<V, E>.Node prev) Addsedge
to the list of the embedded edges such that theprev
node becomes an inner node.(package private) BoyerMyrvoldPlanarityInspector<V,
E>.Node Returns the parent of this node in the dfs tree.(package private) boolean
Checks whether this node has a back edge to thenode
.(package private) boolean
Checks whether this node has a neighbor, which is a root of a biconnected component(package private) boolean
Check whether this node is active.(package private) boolean
Checks whether this node is externally active with respect to thenode
.(package private) boolean
Check whether this node is inactive.(package private) boolean
Check whether this node is internally active.(package private) boolean
Checks whether this node is pertinent in the context of processing the nodenode
.(package private) boolean
Returns true if the node is a component root, false otherwise(package private) boolean
Checks whether this node is visited in the context of processing the nodenode
(package private) BoyerMyrvoldPlanarityInspector<V,
E>.OuterFaceCirculator iterator
(int direction) Returns a circulator, that moves in the directiondirection
.(package private) void
mergeChildEdges
(DoublyLinkedList<BoyerMyrvoldPlanarityInspector<V, E>.Edge> edges, int vIn, int vOut, BoyerMyrvoldPlanarityInspector<V, E>.Node parentNext, BoyerMyrvoldPlanarityInspector<V, E>.Edge parentEdge) Merges the embedded edges of the child component root into this node's embedded edges.(package private) BoyerMyrvoldPlanarityInspector<V,
E>.Node Returns a neighbor of this node which is not equal to theprev
(package private) void
(package private) void
substitute
(BoyerMyrvoldPlanarityInspector<V, E>.Node node, BoyerMyrvoldPlanarityInspector<V, E>.Node newNeighbor) Substitutes the neighbornode
with anewNeighbor
(package private) void
substituteAnother
(BoyerMyrvoldPlanarityInspector<V, E>.Node node, BoyerMyrvoldPlanarityInspector<V, E>.Node newNeighbor) Substitutes a neighbor of this node, which is not equal to thenode
, with thenewNeighbor
(package private) void
Swaps the outer face neighbors of this nodetoString()
toString
(boolean full) Returns a full or a partial string representation of this node
-
Field Details
-
graphVertex
V graphVertexThe counterpart of this node in thegraph
. For the component roots this value isnull
. -
rootVertex
boolean rootVertexWhether this node is a root of the biconnected component or not. -
dfsIndex
int dfsIndexThe 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 heightThe 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 lowpointThe 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 leastAncestorThe 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 visitedStores 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 backEdgeFlagDuring 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 boundaryHeightThe 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 markedUsed to mark the boundary nodes of the biconnected -
parentEdge
BoyerMyrvoldPlanarityInspector<V,E>.Edge parentEdgeEdge to the parent node of this node in the dfs tree. For tree roots this value isnull
-
edgeToEmbed
BoyerMyrvoldPlanarityInspector<V,E>.Edge edgeToEmbedIf this node has a back edge incident to the currently processed node $v$, then this variable stores this edge -
initialComponentRoot
BoyerMyrvoldPlanarityInspector<V,E>.Node initialComponentRootThe component root the node is created in. For dfs tree roots this value isnull
-
outerFaceNeighbors
BoyerMyrvoldPlanarityInspector<V,E>.Node[] outerFaceNeighborsTwo 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<V,E>.Node> separatedDfsChildListThe 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<V,E>.Node> pertinentRootsThe 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
List<BoyerMyrvoldPlanarityInspector<V,E>.Edge> treeEdgesThe list of tree edges incident to this node in the dfs tree. This list doesn't contain a parent edge of this node -
downEdges
List<BoyerMyrvoldPlanarityInspector<V,E>.Edge> downEdgesThe 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
List<BoyerMyrvoldPlanarityInspector<V,E>.Edge> backEdgesThe list of back edges incident to this 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<V,E>.Edge> embeddedThe 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 Details
-
Node
Node(V graphVertex, int dfsIndex, int height, BoyerMyrvoldPlanarityInspector<V, E>.Node initialComponentRoot, BoyerMyrvoldPlanarityInspector<V, E>.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<V, E>.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<V, E>.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 Details
-
isVisitedWrtTo
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
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
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
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
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
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
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
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<V,E>.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
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<V, E>.Node node, BoyerMyrvoldPlanarityInspector<V, E>.Node newNeighbor) Substitutes the neighbornode
with anewNeighbor
- Parameters:
node
- an old neighbornewNeighbor
- a new neighbor
-
substituteAnother
void substituteAnother(BoyerMyrvoldPlanarityInspector<V, E>.Node node, BoyerMyrvoldPlanarityInspector<V, E>.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<V,E>.Node nextOnOuterFace(BoyerMyrvoldPlanarityInspector<V, E>.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<V, E>.Edge edge, BoyerMyrvoldPlanarityInspector<V, E>.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<V, E>.Edge> edges, int vIn, int vOut, BoyerMyrvoldPlanarityInspector<V, E>.Node parentNext, BoyerMyrvoldPlanarityInspector<V, E>.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
-
toString
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
-