- java.lang.Object
-
- org.jgrapht.alg.planar.BoyerMyrvoldPlanarityInspector<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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 theisPlanar()
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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
BoyerMyrvoldPlanarityInspector.Edge
Internal representation of the edges of the inputgraph
.private class
BoyerMyrvoldPlanarityInspector.MergeInfo
The information needed to merge two consecutive biconnected componentsprivate class
BoyerMyrvoldPlanarityInspector.Node
The internal representation of the vertices of the graph.private class
BoyerMyrvoldPlanarityInspector.OrientDfsStackInfo
Represents information needed to store in the stack during the inputgraph
orientation.private class
BoyerMyrvoldPlanarityInspector.OuterFaceCirculator
A circulator over the nodes on the boundary of the biconnected component.private class
BoyerMyrvoldPlanarityInspector.SearchInfo
Represents information needed to search a path within a biconnected component-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.PlanarityTestingAlgorithm
PlanarityTestingAlgorithm.Embedding<V,E>, PlanarityTestingAlgorithm.EmbeddingImpl<V,E>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.List<BoyerMyrvoldPlanarityInspector.Node>
componentRoots
List of the virtual biconnected component roots.private static boolean
DEBUG
Whether to print debug messagesprivate java.util.List<BoyerMyrvoldPlanarityInspector.Node>
dfsTreeRoots
List of the dfs tree roots of thegraph
.private PlanarityTestingAlgorithm.Embedding<V,E>
embedding
The resulting combinatorial embedding.private BoyerMyrvoldPlanarityInspector.Node
failedV
The node $v$, which has an unembedded back edge incident to it.private Graph<V,E>
graph
The graph we're testing planarity ofprivate Graph<V,E>
kuratowskiSubdivision
The subgraph of thegraph
, which is a Kuratowski subdivision.private int
n
The number of vertices in thegraph
private java.util.List<BoyerMyrvoldPlanarityInspector.Node>
nodes
List of the vertices of thegraph
in their internal representation.private boolean
planar
Whether the graph is planar or not.private static boolean
PRINT_CASES
Whether to print Kuratowski case distinction messagesprivate 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.private boolean
tested
Whether the planarity of thegraph
has been tested already
-
Constructor Summary
Constructors Constructor Description BoyerMyrvoldPlanarityInspector(Graph<V,E> graph)
Creates new instance of the planarity testing algorithm for thegraph
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addBoundaryEdges(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges, BoyerMyrvoldPlanarityInspector.Node componentRoot)
Adds the edges on the outer face of the component rooted atcomponentRoot
to the setedges
private void
addPathEdges(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges, BoyerMyrvoldPlanarityInspector.Edge startEdge, BoyerMyrvoldPlanarityInspector.Node stop)
Adds the edges on the path from thestartEdge
up to the nodestop
to the setedges
private void
addPathEdges(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges, BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node stop)
Adds the edges between thestart
and theend
to the setedges
private BoyerMyrvoldPlanarityInspector.Edge
checkComponentForFailedEdge(BoyerMyrvoldPlanarityInspector.Node componentRoot, BoyerMyrvoldPlanarityInspector.Node v)
Checks whether the biconnected component rooted atcomponentRoot
can be used to extract a Kuratowski subdivision.private void
cleanUpDfs(BoyerMyrvoldPlanarityInspector.Node dfsTreeRoot)
Recursively cleans up the dfs tree rooted at thedfsTreeRoot
my removing all the short-circuit edges and properly orienting other embedded edgesprivate void
clearVisited()
Clears the visited variable of all the nodes and component rootsprivate 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 thegraphVertex
to the internal node representation.private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator
embedBackEdge(BoyerMyrvoldPlanarityInspector.Node root, int entryDir, BoyerMyrvoldPlanarityInspector.Edge edge, BoyerMyrvoldPlanarityInspector.Node childPrev)
Embeds the back edgeedge
into the list of embedded edges of the source and the virtual target of the edge such that thechildPrev
belongs to the new inner face.private void
embedShortCircuit(BoyerMyrvoldPlanarityInspector.Node componentRoot, int entryDir, BoyerMyrvoldPlanarityInspector.OuterFaceCirculator circulator)
Embeds a short-circuit edge from thecomponentRoot
to the current node of thecirculator
.private BoyerMyrvoldPlanarityInspector.Edge
findFailedEdge(BoyerMyrvoldPlanarityInspector.Node v)
Finds an unembedded back edge tov
, which can be used to extract the Kuratowski subdivision.private java.util.List<BoyerMyrvoldPlanarityInspector.Edge>
findHighestObstructingPath(BoyerMyrvoldPlanarityInspector.Node componentRoot, BoyerMyrvoldPlanarityInspector.Node w)
Finds the highest obstructing path in the component rooted atcomponentRoot
.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 thecurrent
node to the first node satisfying theisFinish
predicate consisting of all the nodes satisfying thecanGo
predicate.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 listpath
to the nodev
.private Graph<V,E>
finish(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> subdivision)
Finishes the Kuratowski subdivision extraction by constructing the desired subgraphprivate boolean
firstStrictlyHigher(BoyerMyrvoldPlanarityInspector.Node a, BoyerMyrvoldPlanarityInspector.Node b, BoyerMyrvoldPlanarityInspector.Node c)
Checks whether the first nodea
is strictly higher than nodesb
andc
private void
fixBoundaryOrder(BoyerMyrvoldPlanarityInspector.Node componentRoot)
Orient the connections on the outer face of the component rooted atcomponentRoot
such that they are orderedprivate BoyerMyrvoldPlanarityInspector.OuterFaceCirculator
getActiveSuccessorOnOuterFace(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node v, int dir)
Returns an active node on the outer face in the directiondir
starting from thestart
nodeprivate BoyerMyrvoldPlanarityInspector.Node
getComponentRoot(BoyerMyrvoldPlanarityInspector.Node node)
Returns a component root of component thenode
is contained in.PlanarityTestingAlgorithm.Embedding<V,E>
getEmbedding()
Computes combinatorial embedding of the inputgraph
.private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator
getExternallyActiveSuccessorOnOuterFace(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node stop, BoyerMyrvoldPlanarityInspector.Node v, int dir)
Returns acirculator to the externally active node on the outer face between thestart
andend
nodes in the directiondir
.Graph<V,E>
getKuratowskiSubdivision()
Extracts a Kuratowski subdivision from thegraph
.private BoyerMyrvoldPlanarityInspector.Node
getNextOnPath(BoyerMyrvoldPlanarityInspector.Node w, BoyerMyrvoldPlanarityInspector.Edge backEdge)
Effectively is a method for finding nodez
in the notations of the original paper.private BoyerMyrvoldPlanarityInspector.Node
highest(BoyerMyrvoldPlanarityInspector.Node a, BoyerMyrvoldPlanarityInspector.Node b)
Returns the highest of the two input node, i.e.boolean
isPlanar()
Tests the planarity of thegraph
.private void
kuratowskiCleanUp()
Cleans up the dfs trees before the Kuratowski subdivision extraction phaseprivate PlanarityTestingAlgorithm.Embedding<V,E>
lazyComputeEmbedding()
Lazily computes a combinatorial embedding of thegraph
by removing all the short-circuit edges and properly orienting the edges around the nodes.private Graph<V,E>
lazyExtractKuratowskiSubdivision()
Lazily extracts a Kuratowski subdivision from thegraph
.private boolean
lazyTestPlanarity()
Lazily tests the planarity of the graph.private BoyerMyrvoldPlanarityInspector.Node
lowest(BoyerMyrvoldPlanarityInspector.Node a, BoyerMyrvoldPlanarityInspector.Node b)
Returns the lowest of the two input node, i.e.private void
mergeBiconnectedComponent()
Merges the last two biconnected components using the info stored on top of the stack.private void
orient()
Iteratively start an orienting dfs from everygraph
vertex that hasn't been visited yet.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.private void
printBiconnectedComponent(BoyerMyrvoldPlanarityInspector.Node node)
Method for debug purposes, prints the boundary thenode
belongs toprivate void
printState()
Method for debug purposes, prints the state of the algorithmprivate void
removeUp(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node end, int dir, java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges)
Removes the edges from the outer face from thestart
node to theend
node in the directiondir
from the setedges
private BoyerMyrvoldPlanarityInspector.Edge
searchEdge(BoyerMyrvoldPlanarityInspector.Node current, int heightMax)
Searches a back edge which target has a height smaller thanheightMax
private BoyerMyrvoldPlanarityInspector.Edge
searchEdge(BoyerMyrvoldPlanarityInspector.Node current, int heightMax, BoyerMyrvoldPlanarityInspector.Edge forbiddenEdge)
Searches a back edge which target has a height smaller thanheightMax
private BoyerMyrvoldPlanarityInspector.Edge
searchEdge(BoyerMyrvoldPlanarityInspector.Node current, java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Edge> isNeeded)
Generically searches an edge in the subtree rooted at thecurrent
, which doesn't include the children of thecurrent
that have beem merged to the parent biconnected component.private BoyerMyrvoldPlanarityInspector.Edge
searchSubtreeDfs(BoyerMyrvoldPlanarityInspector.Node start, java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Edge> isNeeded)
Recursively searches all the subtree root at the nodestart
to find an edge satisfying thepredicate
.private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator
selectOnOuterFace(java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Node> predicate, BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node stop, int dir)
Either finds and returns a circulator to the node on the boundary of the component, which satisfies thepredicate
or returns a circulator to thestop
node.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 nodew
.private void
sortVertices()
Performs sorting of the vertices by their lowpoints and adding them to theseparatedDfsChildList
private void
walkDown(BoyerMyrvoldPlanarityInspector.Node componentRoot)
The walkdown procedure from the original paper.private void
walkUp(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node end, BoyerMyrvoldPlanarityInspector.Edge edge)
The walkup procedure from the original paper.
-
-
-
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
-
n
private int n
The number of vertices in thegraph
-
embedding
private PlanarityTestingAlgorithm.Embedding<V,E> embedding
The resulting combinatorial embedding. This value is computed only after the first call to thegetEmbedding()
-
kuratowskiSubdivision
private Graph<V,E> kuratowskiSubdivision
The subgraph of thegraph
, 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 thegraph
in their internal representation. After the orientation of thegraph
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 thegraph
. This list has length more than 1 if the inputgraph
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 thegraph
, except for the dfs roots. These component roots don't belong to thegraph
. 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
-
failedV
private BoyerMyrvoldPlanarityInspector.Node failedV
The node $v$, which has an unembedded back edge incident to it.
-
tested
private boolean tested
Whether the planarity of thegraph
has been tested already
-
planar
private boolean planar
Whether the graph is planar or not. Is valid, iftested
istrue
-
-
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 thegraphVertex
to the internal node representation.- Parameters:
vertexMap
- the map from vertices of thegraph
to their internal representationgraphVertex
- the vertex of thegraph
we're processingedge
- the parent edge of thegraphVertex
, isnull
for dfs tree rootsparent
- the parent node of thegraphVertex
dfsIndex
- the dfs index of thegraphVertex
- 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 fromgraph
vertices to their internal representativesstartGraphVertex
- the node to start the traversal from (this is a dfs tree root).currentDfsIndex
- the dfs index of thestartGraphVertex
- Returns:
- the
currentDfsIndex
+ number of nodes in the traversed subtree
-
orient
private void orient()
Iteratively start an orienting dfs from everygraph
vertex that hasn't been visited yet. After orienting the graph, sorts the nodes by their lowpoints and adds them to theseparatedDfsChildList
-
sortVertices
private void sortVertices()
Performs sorting of the vertices by their lowpoints and adding them to theseparatedDfsChildList
-
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
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator embedBackEdge(BoyerMyrvoldPlanarityInspector.Node root, int entryDir, BoyerMyrvoldPlanarityInspector.Edge edge, BoyerMyrvoldPlanarityInspector.Node childPrev)
Embeds the back edgeedge
into the list of embedded edges of the source and the virtual target of the edge such that thechildPrev
belongs to the new inner face. This method also takes care of modifying the boundary of the outer face accordingly- Parameters:
root
- the component rootentryDir
- the component entry directionedge
- the edge to embedchildPrev
- 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.Node componentRoot, int entryDir, BoyerMyrvoldPlanarityInspector.OuterFaceCirculator circulator)
Embeds a short-circuit edge from thecomponentRoot
to the current node of thecirculator
. Changes the outer face accordingly- Parameters:
componentRoot
- the component rootentryDir
- the direction used to enter the componentcirculator
- 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 thecomponentRoot
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
private void walkUp(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node end, BoyerMyrvoldPlanarityInspector.Edge edge)
The walkup procedure from the original paper. Identifies the pertinent subgraph of the graph by going up the dfs tree from thestart
node to theend
node using the edgeedge
- Parameters:
start
- the node to start the walkup fromend
- the node currently processed by the main loop of the algorithmedge
- a back edge to embed
-
lazyComputeEmbedding
private PlanarityTestingAlgorithm.Embedding<V,E> lazyComputeEmbedding()
Lazily computes a combinatorial embedding of thegraph
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 thenode
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
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator selectOnOuterFace(java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Node> predicate, BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node stop, int dir)
Either finds and returns a circulator to the node on the boundary of the component, which satisfies thepredicate
or returns a circulator to thestop
node.- Parameters:
predicate
- the condition the desired node should satisfystart
- the node to start the search fromstop
- the node to end the search withdir
- the direction to start the traversal in- Returns:
- a circulator to the node satisfying the
predicate
or to thestop
node
-
getActiveSuccessorOnOuterFace
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator getActiveSuccessorOnOuterFace(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node v, int dir)
Returns an active node on the outer face in the directiondir
starting from thestart
node- Parameters:
start
- the node to start the search fromv
- an ancestor of thestart
dir
- the direction of the search- Returns:
- a circulator to the found node
-
getExternallyActiveSuccessorOnOuterFace
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator getExternallyActiveSuccessorOnOuterFace(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node stop, BoyerMyrvoldPlanarityInspector.Node v, int dir)
Returns acirculator to the externally active node on the outer face between thestart
andend
nodes in the directiondir
.- Parameters:
start
- the node to start the search fromstop
- the node to end the search withv
- an ancestor of thestart
and theend
dir
- the direction of the search- Returns:
- a circulator to the found node
-
getComponentRoot
private BoyerMyrvoldPlanarityInspector.Node getComponentRoot(BoyerMyrvoldPlanarityInspector.Node node)
Returns a component root of component thenode
is contained in.- Parameters:
node
- a node in the partially embedded graph- Returns:
- a component root of the component the
node
belongs to
-
addPathEdges
private void addPathEdges(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges, BoyerMyrvoldPlanarityInspector.Edge startEdge, BoyerMyrvoldPlanarityInspector.Node stop)
Adds the edges on the path from thestartEdge
up to the nodestop
to the setedges
- Parameters:
edges
- the set to add the path edges tostartEdge
- the edge to start fromstop
- the last node on the path
-
addPathEdges
private void addPathEdges(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges, BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node stop)
Adds the edges between thestart
and theend
to the setedges
- Parameters:
edges
- the set to add the path edges to tostart
- the node to start fromstop
- the node to end with
-
searchEdge
private BoyerMyrvoldPlanarityInspector.Edge searchEdge(BoyerMyrvoldPlanarityInspector.Node current, int heightMax)
Searches a back edge which target has a height smaller thanheightMax
- Parameters:
current
- the node to start fromheightMax
- 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, int heightMax, BoyerMyrvoldPlanarityInspector.Edge forbiddenEdge)
Searches a back edge which target has a height smaller thanheightMax
- Parameters:
current
- the node to start fromheightMax
- an upper bound on the height of the desired back edgeforbiddenEdge
- an edge the desired edge should not be equal to- 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 thecurrent
, which doesn't include the children of thecurrent
that have beem merged to the parent biconnected component.- Parameters:
current
- the node to start the searh fromisNeeded
- 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
private BoyerMyrvoldPlanarityInspector.Edge searchSubtreeDfs(BoyerMyrvoldPlanarityInspector.Node start, java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Edge> isNeeded)
Recursively searches all the subtree root at the nodestart
to find an edge satisfying thepredicate
.- 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
private BoyerMyrvoldPlanarityInspector.Node highest(BoyerMyrvoldPlanarityInspector.Node a, BoyerMyrvoldPlanarityInspector.Node b)
Returns the highest of the two input node, i.e. the node with the greater height- Parameters:
a
- a node in the dfs treeb
- a node in the dfs tree- Returns:
- the highest of the two nodes
-
lowest
private BoyerMyrvoldPlanarityInspector.Node lowest(BoyerMyrvoldPlanarityInspector.Node a, BoyerMyrvoldPlanarityInspector.Node b)
Returns the lowest of the two input node, i.e. the node with the least height.- Parameters:
a
- a node in the dfs treeb
- a node in the dfs tree- Returns:
- the lowest of the two nodes
-
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 nodew
.- Parameters:
componentRoot
- the root of the componentw
- the end of the outer face branchdir
- the direction to start the traversal indelta
- 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 thecurrent
node to the first node satisfying theisFinish
predicate consisting of all the nodes satisfying thecanGo
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 theedges
.- Parameters:
start
- the start node of the traversalstartPrev
- the previous edge of the start nodecanGo
- specifies where the search can goisFinish
- specifies what nodes are finish nodesedges
- 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 atcomponentRoot
. See the original paper for the definition of the obstructing path. This method heavily relies on the fact that the methodBoyerMyrvoldPlanarityInspector#findPathDfs(Node, Edge, Predicate, Predicate, List)
chooses the edges in the clockwise order.- Parameters:
componentRoot
- the root of the componentw
- the node calledw
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 atcomponentRoot
to the setedges
- Parameters:
edges
- the set to add the edges tocomponentRoot
- 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 thedfsTreeRoot
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 atcomponentRoot
such that they are ordered- Parameters:
componentRoot
- the root of the component to process
-
removeUp
private void removeUp(BoyerMyrvoldPlanarityInspector.Node start, BoyerMyrvoldPlanarityInspector.Node end, int dir, java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges)
Removes the edges from the outer face from thestart
node to theend
node in the directiondir
from the setedges
- Parameters:
start
- the start of the boundary pathend
- the end of the boundary pathdir
- the direction to take from thestart
nodeedges
- the set of edges to modify
-
getNextOnPath
private BoyerMyrvoldPlanarityInspector.Node getNextOnPath(BoyerMyrvoldPlanarityInspector.Node w, BoyerMyrvoldPlanarityInspector.Edge backEdge)
Effectively is a method for finding nodez
in the notations of the original paper. The search proceeds in the reverse order of the path from thebackEdge
to the nodew
- Parameters:
w
- the start of the path downbackEdge
- the last edge on the path- Returns:
- the desired node
z
or null if the source of thebackEdge
is equal tow
-
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 listpath
to the nodev
. The path tov
certainly doesn't exist if the listpath
has size 1, because we're looking for a path from some intermediate node- Parameters:
path
- the path between left and right outer face branchesv
- the parent of the biconnected component- Returns:
- the path edges in a list, which can be empty
-
firstStrictlyHigher
private boolean firstStrictlyHigher(BoyerMyrvoldPlanarityInspector.Node a, BoyerMyrvoldPlanarityInspector.Node b, BoyerMyrvoldPlanarityInspector.Node c)
Checks whether the first nodea
is strictly higher than nodesb
andc
- Parameters:
a
- a node in the dfs treeb
- a node in the dfs treec
- a node in the dfs tree- Returns:
- true if the first node in strictly higher that other node, false otherwise
-
checkComponentForFailedEdge
private BoyerMyrvoldPlanarityInspector.Edge checkComponentForFailedEdge(BoyerMyrvoldPlanarityInspector.Node componentRoot, BoyerMyrvoldPlanarityInspector.Node v)
Checks whether the biconnected component rooted atcomponentRoot
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 componentv
- 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, ornull
is no such edge exist for this biconnected component
-
findFailedEdge
private BoyerMyrvoldPlanarityInspector.Edge findFailedEdge(BoyerMyrvoldPlanarityInspector.Node v)
Finds an unembedded back edge tov
, 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 thegraph
. 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 thegraph
. Returns true if the input graph is planar, false otherwise. If this method returns true, the combinatorial embedding of thegraph
is provided after the call to thePlanarityTestingAlgorithm.getEmbedding()
. Otherwise, a Kuratowski subdivision is provided after the call to thePlanarityTestingAlgorithm.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 interfacePlanarityTestingAlgorithm<V,E>
- Returns:
true
if thegraph
is planar, false otherwise
-
getEmbedding
public PlanarityTestingAlgorithm.Embedding<V,E> getEmbedding()
Computes combinatorial embedding of the inputgraph
. This method will return a valid result only if thegraph
is planar. For more information on the combinatorial embedding, seePlanarityTestingAlgorithm.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 interfacePlanarityTestingAlgorithm<V,E>
- Returns:
- combinatorial embedding of the input
graph
-
getKuratowskiSubdivision
public Graph<V,E> getKuratowskiSubdivision()
Extracts a Kuratowski subdivision from thegraph
. The returned value certifies the nonplanarity of the graph. The returned certificate can be verified through the call to theGraphTests.isKuratowskiSubdivision(Graph)
. This method will return a valid result only if thegraph
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 interfacePlanarityTestingAlgorithm<V,E>
- Returns:
- a Kuratowski subdivision from the
graph
-
-