Class BoyerMyrvoldPlanarityInspector.Node

java.lang.Object
org.jgrapht.alg.planar.BoyerMyrvoldPlanarityInspector.Node
Enclosing class:
BoyerMyrvoldPlanarityInspector<V,E>

private class BoyerMyrvoldPlanarityInspector.Node extends 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 Details

    • graphVertex

      V graphVertex
      The counterpart of this node in the graph. For the component roots this value is null.
    • 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

      Edge to the parent node of this node in the dfs tree. For tree roots this value is null
    • edgeToEmbed

      If this node has a back edge incident to the currently processed node $v$, then this variable stores this edge
    • initialComponentRoot

      BoyerMyrvoldPlanarityInspector<V,E>.Node initialComponentRoot
      The component root the node is created in. For dfs tree roots this value is null
    • outerFaceNeighbors

      BoyerMyrvoldPlanarityInspector<V,E>.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

      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

      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

      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

      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

      The list of back edges incident to this node.
    • listNode

      Stores the list node from the separatedDfsChildList of the parent node this node is stored in. This enable deleting of this node from the separatedDfsChildList list in $\mathcal{O}(1)$ time
    • 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 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 the graph
      dfsIndex - the dfs index of this node
      height - the height of this node in the dfs tree
      initialComponentRoot - 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 node
      parentEdge - 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 the graph corresponding to this node
      dfsIndex - the dfs index of this node
      parentEdge - the parent edge of this node
      rootVertex - whether this is real or virtual node
  • Method Details

    • isVisitedWrtTo

      boolean isVisitedWrtTo(BoyerMyrvoldPlanarityInspector<V,E>.Node node)
      Checks whether this node is visited in the context of processing the node node
      Parameters:
      node - the node that is currently been processed
      Returns:
      true if this node is visited, false otherwise
    • isPertinentWrtTo

      boolean isPertinentWrtTo(BoyerMyrvoldPlanarityInspector<V,E>.Node node)
      Checks whether this node is pertinent in the context of processing the node node. During the processing of the node node, a node is pertinent if it has a back edge to node 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<V,E>.Node node)
      Checks whether this node has a back edge to the node.
      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<V,E>.Node node)
      Checks whether this node is externally active with respect to the node. A node is externally active, if it is incident to the edge ending higher than node, 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<V,E>.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<V,E>.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<V,E>.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

      Returns a circulator, that moves in the direction direction. The next node along the traversal will be this.outerFaceNeighbor[direction].
      Parameters:
      direction - the direction to move in
      Returns:
      an iterator over the boundary nodes in the direction direction
    • removeShortCircuitEdges

      void removeShortCircuitEdges()
    • getParent

      Returns the parent of this node in the dfs tree. Tree parent of the dfs root node is null
      Returns:
      the parent of this node in the dfs tree
    • checkIsAdjacent

      void checkIsAdjacent(BoyerMyrvoldPlanarityInspector<V,E>.Node node)
      Checks whether this node has a neighbor node 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

      Substitutes the neighbor node with a newNeighbor
      Parameters:
      node - an old neighbor
      newNeighbor - 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 the node, with the newNeighbor
      Parameters:
      node - the remaining neighbor
      newNeighbor - 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

      Returns a neighbor of this node which is not equal to the prev
      Parameters:
      prev - a neighbor of this node
      Returns:
      a neightbor, which is not equal to the prev
    • embedBackEdge

      Adds edge to the list of the embedded edges such that the prev node becomes an inner node.
      Parameters:
      edge - an edge to embed
      prev - 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 the edges list are always in the clockwise order. There are 3 parameters which determine how the edges list is merged: the vIn direction, the vOut direction and the orientation of the edges around this node (clockwise or counterclockwise). The edges in the edges list should have the same orientation. If this list is inverted, the sign of the parentEdge is set to $-1$.
      Parameters:
      edges - the edges from the child component root
      vIn - the direction used to enter the parent component
      vOut - the direction used to enter the child component
      parentNext - the next node along the traversal of the parent biconnected component
      parentEdge - the parent edge if the child component
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • toString

      public 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