Module org.jgrapht.core
Package org.jgrapht.alg.planar

Class BoyerMyrvoldPlanarityInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    PlanarityTestingAlgorithm<V,​E>
    public class BoyerMyrvoldPlanarityInspector<V,​E>
extends java.lang.Object
implements PlanarityTestingAlgorithm<V,​E>
    An implementation of the Boyer-Myrvold planarity testing algorithm. This class determines whether an input graph is planar or not. If the graph is planar, the algorithm provides a combinatorial embedding of the graph, which is represented as a clockwise ordering of the edges of the graph. Otherwise, the algorithm provides a Kuratowski subgraph as a certificate. Both embedding of the graph and Kuratowski subdivision are computed lazily, meaning that the call to the isPlanar() does spend time only on the planarity testing. All of the operations of this algorithm (testing, embedding and Kuratowski subgraph extraction) run in linear time.

    A planar graph is a graph, which can be drawn in two-dimensional space without any of its edges crossing. According to the Kuratowski theorem, a graph is planar if and only if it doesn't contain a subdivision of the $K_{3,3}$ or $K_{5}$ graphs.

    The Boyer-Myrvold planarity testing algorithm was originally described in: Boyer, John amp; Myrvold, Wendy. (2004). On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. J. Graph Algorithms Appl.. 8. 241-273. 10.7155/jgaa.00091. . We refer to this paper for the complete description of the Boyer-Myrvold algorithm

    • Field Detail

      • DEBUG

        private static final boolean DEBUG
        Whether to print debug messages
        See Also:
        Constant Field Values

      • PRINT_CASES

        private static final boolean PRINT_CASES
        Whether to print Kuratowski case distinction messages
        See Also:
        Constant Field Values

      • graph

        private Graph<V,​E> graph
        The graph we're testing planarity of

      • n

        private int n
        The number of vertices in the graph

      • kuratowskiSubdivision

        private Graph<V,​E> kuratowskiSubdivision
        The subgraph of the graph, which is a Kuratowski subdivision. This subgraph certifies the nonplanarity of the graph.

      • nodes

        private java.util.List<BoyerMyrvoldPlanarityInspector.Node> nodes
        List of the vertices of the graph in their internal representation. After the orientation of the graph and edge sorting, nodes in this list are sorted according to their dfs indexes

      • dfsTreeRoots

        private java.util.List<BoyerMyrvoldPlanarityInspector.Node> dfsTreeRoots
        List of the dfs tree roots of the graph. This list has length more than 1 if the input graph isn't connected

      • componentRoots

        private java.util.List<BoyerMyrvoldPlanarityInspector.Node> componentRoots
        List of the virtual biconnected component roots. Initially, a virtual biconnected component root is created for every node in the graph, except for the dfs roots. These component roots don't belong to the graph. At each step of the algorithm, every biconnected component has its own unique component root.

      • stack

        private java.util.List<BoyerMyrvoldPlanarityInspector.MergeInfo> stack
        The stack containing merge information for every consecutive pair of biconnected components on the path to the back edge source. After all the biconnected components are merged, this stack is cleared

      • tested

        private boolean tested
        Whether the planarity of the graph has been tested already

      • planar

        private boolean planar
        Whether the graph is planar or not. Is valid, if tested is true

    • Constructor Detail

      • BoyerMyrvoldPlanarityInspector

        public BoyerMyrvoldPlanarityInspector​(Graph<V,​E> graph)
        Creates new instance of the planarity testing algorithm for the graph. The input graph can't be null.
        Parameters:
        graph - the graph to test the planarity of

    • Method Detail

      • createNewNode

        private BoyerMyrvoldPlanarityInspector.Node createNewNode​(java.util.Map<V,​BoyerMyrvoldPlanarityInspector.Node> vertexMap,
                                                          V graphVertex,
                                                          E edge,
                                                          BoyerMyrvoldPlanarityInspector.Node parent,
                                                          int dfsIndex)
        Creates a new node by converting the graphVertex to the internal node representation.
        Parameters:
        vertexMap - the map from vertices of the graph to their internal representation
        graphVertex - the vertex of the graph we're processing
        edge - the parent edge of the graphVertex, is null for dfs tree roots
        parent - the parent node of the graphVertex
        dfsIndex - the dfs index of the graphVertex
        Returns:
        the newly created node

      • orientDfs

        private int orientDfs​(java.util.Map<V,​BoyerMyrvoldPlanarityInspector.Node> vertexMap,
                      V startGraphVertex,
                      int currentDfsIndex)
        Orients the input graph according to its dfs traversal by creating a dfs tree. Computes the least ancestors and lowpoints of the nodes
        Parameters:
        vertexMap - the map from graph vertices to their internal representatives
        startGraphVertex - the node to start the traversal from (this is a dfs tree root).
        currentDfsIndex - the dfs index of the startGraphVertex
        Returns:
        the currentDfsIndex + number of nodes in the traversed subtree

      • orient

        private void orient()
        Iteratively start an orienting dfs from every graph vertex that hasn't been visited yet. After orienting the graph, sorts the nodes by their lowpoints and adds them to the separatedDfsChildList

      • sortVertices

        private void sortVertices()
        Performs sorting of the vertices by their lowpoints and adding them to the separatedDfsChildList

      • lazyTestPlanarity

        private boolean lazyTestPlanarity()
        Lazily tests the planarity of the graph. The implementation below is close to the code presented in the original paper
        Returns:
        true if the graph is planar, false otherwise

      • mergeBiconnectedComponent

        private void mergeBiconnectedComponent()
        Merges the last two biconnected components using the info stored on top of the stack. The key goal of this method is to merge the outer faces of the two components and to merge the embedded edges of the child component root with the embedded edges of the component parent node.

      • embedShortCircuit

        private void embedShortCircuit​(BoyerMyrvoldPlanarityInspector.Node componentRoot,
                               int entryDir,
                               BoyerMyrvoldPlanarityInspector.OuterFaceCirculator circulator)
        Embeds a short-circuit edge from the componentRoot to the current node of the circulator. Changes the outer face accordingly
        Parameters:
        componentRoot - the component root
        entryDir - the direction used to enter the component
        circulator - a circulator to the source of the new edge

      • walkDown

        private void walkDown​(BoyerMyrvoldPlanarityInspector.Node componentRoot)
        The walkdown procedure from the original paper. Either embeds all of the back edges in the subtree rooted at the child of the componentRoot or identifies the back edges which can be used to extract a Kuratowski subdivision. Iteratively traverses the tree of the biconnected component and descends only to the pertinent components. This procedure is also responsible for embedding short-circuit edges to make the algorithm run in linear time in the worst case.
        Parameters:
        componentRoot - the root of the component to start the walkdown from

      • lazyComputeEmbedding

        private PlanarityTestingAlgorithm.Embedding<V,​E> lazyComputeEmbedding()
        Lazily computes a combinatorial embedding of the graph by removing all the short-circuit edges and properly orienting the edges around the nodes.
        Returns:
        a combinatorial embedding of the graph

      • printBiconnectedComponent

        private void printBiconnectedComponent​(BoyerMyrvoldPlanarityInspector.Node node)
        Method for debug purposes, prints the boundary the node belongs to
        Parameters:
        node - a node on the outer face

      • printState

        private void printState()
        Method for debug purposes, prints the state of the algorithm

      • searchEdge

        private BoyerMyrvoldPlanarityInspector.Edge searchEdge​(BoyerMyrvoldPlanarityInspector.Node current,
                                                       int heightMax)
        Searches a back edge which target has a height smaller than heightMax
        Parameters:
        current - the node to start from
        heightMax - an upper bound on the height of the desired back edge
        Returns:
        the desired back edge or null, if no such edge exist

      • searchEdge

        private BoyerMyrvoldPlanarityInspector.Edge searchEdge​(BoyerMyrvoldPlanarityInspector.Node current,
                                                       java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Edge> isNeeded)
        Generically searches an edge in the subtree rooted at the current, which doesn't include the children of the current that have beem merged to the parent biconnected component.
        Parameters:
        current - the node to start the searh from
        isNeeded - the predicate which the desired edge should satisfy
        Returns:
        an edge which satisfies the predicate, or null if such an edge doesn't exist

      • setBoundaryDepth

        private void setBoundaryDepth​(BoyerMyrvoldPlanarityInspector.Node componentRoot,
                              BoyerMyrvoldPlanarityInspector.Node w,
                              int dir,
                              int delta)
        Iteratively sets a boundary height for the nodes on the outer face branch ending at the node w.
        Parameters:
        componentRoot - the root of the component
        w - the end of the outer face branch
        dir - the direction to start the traversal in
        delta - a value in $\{+1, -1\}$ to set either positive or negative boundary height

      • clearVisited

        private void clearVisited()
        Clears the visited variable of all the nodes and component roots

      • findPathDfs

        private boolean findPathDfs​(BoyerMyrvoldPlanarityInspector.Node start,
                            BoyerMyrvoldPlanarityInspector.Edge startPrev,
                            java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Node> canGo,
                            java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Node> isFinish,
                            java.util.List<BoyerMyrvoldPlanarityInspector.Edge> edges)
        Generically searches a path from the current node to the first node satisfying the isFinish predicate consisting of all the nodes satisfying the canGo predicate. The key property of this method is that it searches the next edge on the path in the clockwise order starting from the previous edge. The edges of the resulting path are added to the edges.
        Parameters:
        start - the start node of the traversal
        startPrev - the previous edge of the start node
        canGo - specifies where the search can go
        isFinish - specifies what nodes are finish nodes
        edges - the list containing the resulting path
        Returns:
        true if the search was successful, false otherwise

      • findHighestObstructingPath

        private java.util.List<BoyerMyrvoldPlanarityInspector.Edge> findHighestObstructingPath​(BoyerMyrvoldPlanarityInspector.Node componentRoot,
                                                                                       BoyerMyrvoldPlanarityInspector.Node w)
        Finds the highest obstructing path in the component rooted at componentRoot. See the original paper for the definition of the obstructing path. This method heavily relies on the fact that the method BoyerMyrvoldPlanarityInspector#findPathDfs(Node, Edge, Predicate, Predicate, List) chooses the edges in the clockwise order.
        Parameters:
        componentRoot - the root of the component
        w - the node called w in the Kuratowski subdivision extraction phase.
        Returns:
        the edges of the desired path as a list

      • finish

        private Graph<V,​E> finish​(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> subdivision)
        Finishes the Kuratowski subdivision extraction by constructing the desired subgraph
        Parameters:
        subdivision - the edges in the Kuratowski subdivision
        Returns:
        the Kuratowski subgraph of the graph

      • addBoundaryEdges

        private void addBoundaryEdges​(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges,
                              BoyerMyrvoldPlanarityInspector.Node componentRoot)
        Adds the edges on the outer face of the component rooted at componentRoot to the set edges
        Parameters:
        edges - the set to add the edges to
        componentRoot - the root of the biconnected component

      • kuratowskiCleanUp

        private void kuratowskiCleanUp()
        Cleans up the dfs trees before the Kuratowski subdivision extraction phase

      • cleanUpDfs

        private void cleanUpDfs​(BoyerMyrvoldPlanarityInspector.Node dfsTreeRoot)
        Recursively cleans up the dfs tree rooted at the dfsTreeRoot my removing all the short-circuit edges and properly orienting other embedded edges
        Parameters:
        dfsTreeRoot - the root of the dfs tree to clean up

      • fixBoundaryOrder

        private void fixBoundaryOrder​(BoyerMyrvoldPlanarityInspector.Node componentRoot)
        Orient the connections on the outer face of the component rooted at componentRoot such that they are ordered
        Parameters:
        componentRoot - the root of the component to process

      • findPathToV

        private java.util.List<BoyerMyrvoldPlanarityInspector.Edge> findPathToV​(java.util.List<BoyerMyrvoldPlanarityInspector.Edge> path,
                                                                        BoyerMyrvoldPlanarityInspector.Node v)
        Finds a path from some intermediate nodes on the path represented by the list path to the node v. The path to v certainly doesn't exist if the list path has size 1, because we're looking for a path from some intermediate node
        Parameters:
        path - the path between left and right outer face branches
        v - the parent of the biconnected component
        Returns:
        the path edges in a list, which can be empty

      • checkComponentForFailedEdge

        private BoyerMyrvoldPlanarityInspector.Edge checkComponentForFailedEdge​(BoyerMyrvoldPlanarityInspector.Node componentRoot,
                                                                        BoyerMyrvoldPlanarityInspector.Node v)
        Checks whether the biconnected component rooted at componentRoot can be used to extract a Kuratowski subdivision. It can be used in the case there is one externally active node on each branch of the outer face and there is a pertinent node on the lower part of the outer face between these two externally active nodes.
        Parameters:
        componentRoot - the root of the biconnected component
        v - an ancestor of the nodes in the biconnected component
        Returns:
        an unembedded back edge, which target is v and which can be used to extract a Kuratowski subdivision, or null is no such edge exist for this biconnected component

      • findFailedEdge

        private BoyerMyrvoldPlanarityInspector.Edge findFailedEdge​(BoyerMyrvoldPlanarityInspector.Node v)
        Finds an unembedded back edge to v, which can be used to extract the Kuratowski subdivision. If the merge stack isn't empty, the last biconnected component processed by the walkdown can be used to find such an edge, because walkdown descended to that component (which means that component is pertinent) and couldn't reach a pertinent node. This can only happen by encountering externally active nodes on both branches of the traversal. Otherwise, be have look in all the child biconnected components to find an unembedded back edge. We're guided by the fact that an edge can not be embedded only in the case both traversals of the walkdown could reach all off the pertinent nodes. This in turn can happen only if both traversals get stuck on externally active nodes.

        Note: not every unembedded back edge can be used to extract a Kuratowski subdivision

        Parameters:
        v - the vertex which has an unembedded back edge incident to it
        Returns:
        the found unembedded back edge which can be used to extract a Kuratowski subdivision

      • lazyExtractKuratowskiSubdivision

        private Graph<V,​E> lazyExtractKuratowskiSubdivision()
        Lazily extracts a Kuratowski subdivision from the graph. The process of adding the edges of the subdivision to the resulting set of edges had been made explicit for every case.
        Returns:
        a Kuratowski subgraph of the graph

      • isPlanar

        public boolean isPlanar()
        Tests the planarity of the graph. Returns true if the input graph is planar, false otherwise. If this method returns true, the combinatorial embedding of the graph is provided after the call to the PlanarityTestingAlgorithm.getEmbedding(). Otherwise, a Kuratowski subdivision is provided after the call to the PlanarityTestingAlgorithm.getKuratowskiSubdivision().

        Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.

        Specified by:
        isPlanar in interface PlanarityTestingAlgorithm<V,​E>
        Returns:
        true if the graph is planar, false otherwise

      • getKuratowskiSubdivision

        public Graph<V,​E> getKuratowskiSubdivision()
        Extracts a Kuratowski subdivision from the graph. The returned value certifies the nonplanarity of the graph. The returned certificate can be verified through the call to the GraphTests.isKuratowskiSubdivision(Graph). This method will return a valid result only if the graph is not planar.

        Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.

        Specified by:
        getKuratowskiSubdivision in interface PlanarityTestingAlgorithm<V,​E>
        Returns:
        a Kuratowski subdivision from the graph