Class BoyerMyrvoldPlanarityInspector<V,E>

java.lang.Object
org.jgrapht.alg.planar.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 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 Details

    • DEBUG

      private static final boolean DEBUG
      Whether to print debug messages
      See Also:
    • graph

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

      private int n
      The number of vertices in the graph
    • embedding

      The resulting combinatorial embedding. This value is computed only after the first call to the getEmbedding()
    • 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

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

      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
    • failedV

      The node $v$, which has an unembedded back edge incident to it.
    • 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 Details

    • 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 Details

    • createNewNode

      private BoyerMyrvoldPlanarityInspector<V,E>.Node createNewNode(Map<V,BoyerMyrvoldPlanarityInspector<V,E>.Node> vertexMap, V graphVertex, E edge, BoyerMyrvoldPlanarityInspector<V,E>.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(Map<V,BoyerMyrvoldPlanarityInspector<V,E>.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.
    • embedBackEdge

      Embeds the back edge edge into the list of embedded edges of the source and the virtual target of the edge such that the childPrev belongs to the new inner face. This method also takes care of modifying the boundary of the outer face accordingly
      Parameters:
      root - the component root
      entryDir - the component entry direction
      edge - the edge to embed
      childPrev - the neighbor of the source of the edge that should belong to the inner face
      Returns:
      a circulator starting from the edge's source
    • embedShortCircuit

      private void embedShortCircuit(BoyerMyrvoldPlanarityInspector<V,E>.Node componentRoot, int entryDir, BoyerMyrvoldPlanarityInspector<V,E>.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<V,E>.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
    • walkUp

      The walkup procedure from the original paper. Identifies the pertinent subgraph of the graph by going up the dfs tree from the start node to the end node using the edge edge
      Parameters:
      start - the node to start the walkup from
      end - the node currently processed by the main loop of the algorithm
      edge - a back edge to embed
    • 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<V,E>.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
    • selectOnOuterFace

      Either finds and returns a circulator to the node on the boundary of the component, which satisfies the predicate or returns a circulator to the stop node.
      Parameters:
      predicate - the condition the desired node should satisfy
      start - the node to start the search from
      stop - the node to end the search with
      dir - the direction to start the traversal in
      Returns:
      a circulator to the node satisfying the predicate or to the stop node
    • getActiveSuccessorOnOuterFace

      Returns an active node on the outer face in the direction dir starting from the start node
      Parameters:
      start - the node to start the search from
      v - an ancestor of the start
      dir - the direction of the search
      Returns:
      a circulator to the found node
    • getExternallyActiveSuccessorOnOuterFace

      Returns acirculator to the externally active node on the outer face between the start and end nodes in the direction dir.
      Parameters:
      start - the node to start the search from
      stop - the node to end the search with
      v - an ancestor of the start and the end
      dir - the direction of the search
      Returns:
      a circulator to the found node
    • getComponentRoot

      Returns a component root of component the node is contained in.
      Parameters:
      node - a node in the partially embedded graph
      Returns:
      a component root of the component the node belongs to
    • addPathEdges

      Adds the edges on the path from the startEdge up to the node stop to the set edges
      Parameters:
      edges - the set to add the path edges to
      startEdge - the edge to start from
      stop - the last node on the path
    • addPathEdges

      Adds the edges between the start and the end to the set edges
      Parameters:
      edges - the set to add the path edges to to
      start - the node to start from
      stop - the node to end with
    • searchEdge

      private BoyerMyrvoldPlanarityInspector<V,E>.Edge searchEdge(BoyerMyrvoldPlanarityInspector<V,E>.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<V,E>.Edge searchEdge(BoyerMyrvoldPlanarityInspector<V,E>.Node current, int heightMax, BoyerMyrvoldPlanarityInspector<V,E>.Edge forbiddenEdge)
      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
      forbiddenEdge - an edge the desired edge should not be equal to
      Returns:
      the desired back edge or null, if no such edge exist
    • searchEdge

      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
    • searchSubtreeDfs

      Recursively searches all the subtree root at the node start to find an edge satisfying the predicate.
      Parameters:
      start - the node to start the search from.
      isNeeded - a predicate, which the desired edge should satisfy
      Returns:
      a desired edge, or null if no such edge exist.
    • highest

      Returns the highest of the two input node, i.e. the node with the greater height
      Parameters:
      a - a node in the dfs tree
      b - a node in the dfs tree
      Returns:
      the highest of the two nodes
    • lowest

      Returns the lowest of the two input node, i.e. the node with the least height.
      Parameters:
      a - a node in the dfs tree
      b - a node in the dfs tree
      Returns:
      the lowest of the two nodes
    • setBoundaryDepth

      private void setBoundaryDepth(BoyerMyrvoldPlanarityInspector<V,E>.Node componentRoot, BoyerMyrvoldPlanarityInspector<V,E>.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

      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

      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
      invalid reference
      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(Set<BoyerMyrvoldPlanarityInspector<V,E>.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(Set<BoyerMyrvoldPlanarityInspector<V,E>.Edge> edges, BoyerMyrvoldPlanarityInspector<V,E>.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<V,E>.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<V,E>.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
    • removeUp

      Removes the edges from the outer face from the start node to the end node in the direction dir from the set edges
      Parameters:
      start - the start of the boundary path
      end - the end of the boundary path
      dir - the direction to take from the start node
      edges - the set of edges to modify
    • getNextOnPath

      Effectively is a method for finding node z in the notations of the original paper. The search proceeds in the reverse order of the path from the backEdge to the node w
      Parameters:
      w - the start of the path down
      backEdge - the last edge on the path
      Returns:
      the desired node z or null if the source of the backEdge is equal to w
    • findPathToV

      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
    • firstStrictlyHigher

      Checks whether the first node a is strictly higher than nodes b and c
      Parameters:
      a - a node in the dfs tree
      b - a node in the dfs tree
      c - a node in the dfs tree
      Returns:
      true if the first node in strictly higher that other node, false otherwise
    • checkComponentForFailedEdge

      private BoyerMyrvoldPlanarityInspector<V,E>.Edge checkComponentForFailedEdge(BoyerMyrvoldPlanarityInspector<V,E>.Node componentRoot, BoyerMyrvoldPlanarityInspector<V,E>.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

      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
    • getEmbedding

      public PlanarityTestingAlgorithm.Embedding<V,E> getEmbedding()
      Computes combinatorial embedding of the input graph. This method will return a valid result only if the graph is planar. For more information on the combinatorial embedding, see PlanarityTestingAlgorithm.Embedding

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

      Specified by:
      getEmbedding in interface PlanarityTestingAlgorithm<V,E>
      Returns:
      combinatorial embedding of the input graph
    • 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