Class 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 Detail

      • 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
      • 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.
      • 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 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.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.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 Detail

      • isVisitedWrtTo

        boolean isVisitedWrtTo​(BoyerMyrvoldPlanarityInspector.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.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.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.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.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 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

        BoyerMyrvoldPlanarityInspector.Node 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.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
      • 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
      • 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 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 java.lang.String toString()
        Overrides:
        toString in class java.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