private void |
BoyerMyrvoldPlanarityInspector.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
|
private void |
BoyerMyrvoldPlanarityInspector.addPathEdges(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges,
BoyerMyrvoldPlanarityInspector.Edge startEdge,
BoyerMyrvoldPlanarityInspector.Node stop) |
Adds the edges on the path from the startEdge up to the node stop to the set
edges
|
private void |
BoyerMyrvoldPlanarityInspector.addPathEdges(java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges,
BoyerMyrvoldPlanarityInspector.Node start,
BoyerMyrvoldPlanarityInspector.Node stop) |
Adds the edges between the start and the end to the set edges
|
private BoyerMyrvoldPlanarityInspector.Edge |
BoyerMyrvoldPlanarityInspector.checkComponentForFailedEdge(BoyerMyrvoldPlanarityInspector.Node componentRoot,
BoyerMyrvoldPlanarityInspector.Node v) |
Checks whether the biconnected component rooted at componentRoot can be used to
extract a Kuratowski subdivision.
|
(package private) void |
BoyerMyrvoldPlanarityInspector.Node.checkIsAdjacent(BoyerMyrvoldPlanarityInspector.Node node) |
Checks whether this node has a neighbor node on the boundary of the biconnected
component
|
private void |
BoyerMyrvoldPlanarityInspector.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
|
private BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.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.
|
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator |
BoyerMyrvoldPlanarityInspector.embedBackEdge(BoyerMyrvoldPlanarityInspector.Node root,
int entryDir,
BoyerMyrvoldPlanarityInspector.Edge edge,
BoyerMyrvoldPlanarityInspector.Node childPrev) |
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.
|
(package private) void |
BoyerMyrvoldPlanarityInspector.Node.embedBackEdge(BoyerMyrvoldPlanarityInspector.Edge edge,
BoyerMyrvoldPlanarityInspector.Node prev) |
Adds edge to the list of the embedded edges such that the prev node
becomes an inner node.
|
private void |
BoyerMyrvoldPlanarityInspector.embedShortCircuit(BoyerMyrvoldPlanarityInspector.Node componentRoot,
int entryDir,
BoyerMyrvoldPlanarityInspector.OuterFaceCirculator circulator) |
Embeds a short-circuit edge from the componentRoot to the current node of the
circulator .
|
private BoyerMyrvoldPlanarityInspector.Edge |
BoyerMyrvoldPlanarityInspector.findFailedEdge(BoyerMyrvoldPlanarityInspector.Node v) |
Finds an unembedded back edge to v , which can be used to extract the Kuratowski
subdivision.
|
private java.util.List<BoyerMyrvoldPlanarityInspector.Edge> |
BoyerMyrvoldPlanarityInspector.findHighestObstructingPath(BoyerMyrvoldPlanarityInspector.Node componentRoot,
BoyerMyrvoldPlanarityInspector.Node w) |
Finds the highest obstructing path in the component rooted at componentRoot .
|
private boolean |
BoyerMyrvoldPlanarityInspector.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.
|
private java.util.List<BoyerMyrvoldPlanarityInspector.Edge> |
BoyerMyrvoldPlanarityInspector.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 .
|
private boolean |
BoyerMyrvoldPlanarityInspector.firstStrictlyHigher(BoyerMyrvoldPlanarityInspector.Node a,
BoyerMyrvoldPlanarityInspector.Node b,
BoyerMyrvoldPlanarityInspector.Node c) |
Checks whether the first node a is strictly higher than nodes b and c
|
private void |
BoyerMyrvoldPlanarityInspector.fixBoundaryOrder(BoyerMyrvoldPlanarityInspector.Node componentRoot) |
Orient the connections on the outer face of the component rooted at componentRoot
such that they are ordered
|
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator |
BoyerMyrvoldPlanarityInspector.getActiveSuccessorOnOuterFace(BoyerMyrvoldPlanarityInspector.Node start,
BoyerMyrvoldPlanarityInspector.Node v,
int dir) |
Returns an active node on the outer face in the direction dir starting from the
start node
|
private BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.getComponentRoot(BoyerMyrvoldPlanarityInspector.Node node) |
Returns a component root of component the node is contained in.
|
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator |
BoyerMyrvoldPlanarityInspector.getExternallyActiveSuccessorOnOuterFace(BoyerMyrvoldPlanarityInspector.Node start,
BoyerMyrvoldPlanarityInspector.Node stop,
BoyerMyrvoldPlanarityInspector.Node v,
int dir) |
Returns acirculator to the externally active node on the outer face between the start
and end nodes in the direction dir .
|
private BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.getNextOnPath(BoyerMyrvoldPlanarityInspector.Node w,
BoyerMyrvoldPlanarityInspector.Edge backEdge) |
Effectively is a method for finding node z in the notations of the original paper.
|
(package private) BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.Edge.getOpposite(BoyerMyrvoldPlanarityInspector.Node node) |
Returns the opposite node of the node
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Node.hasBackEdgeWrtTo(BoyerMyrvoldPlanarityInspector.Node node) |
Checks whether this node has a back edge to the node .
|
private BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.highest(BoyerMyrvoldPlanarityInspector.Node a,
BoyerMyrvoldPlanarityInspector.Node b) |
Returns the highest of the two input node, i.e.
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Node.isActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node) |
Check whether this node is active.
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Node.isExternallyActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node) |
Checks whether this node is externally active with respect to the node .
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Node.isInactiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node) |
Check whether this node is inactive.
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Edge.isIncidentTo(BoyerMyrvoldPlanarityInspector.Node node) |
True if this edge is incident to the node node , false otherwise
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Node.isInternallyActiveWrtTo(BoyerMyrvoldPlanarityInspector.Node node) |
Check whether this node is internally active.
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Node.isPertinentWrtTo(BoyerMyrvoldPlanarityInspector.Node node) |
Checks whether this node is pertinent in the context of processing the node node .
|
(package private) boolean |
BoyerMyrvoldPlanarityInspector.Node.isVisitedWrtTo(BoyerMyrvoldPlanarityInspector.Node node) |
Checks whether this node is visited in the context of processing the node node
|
private BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.lowest(BoyerMyrvoldPlanarityInspector.Node a,
BoyerMyrvoldPlanarityInspector.Node b) |
Returns the lowest of the two input node, i.e.
|
(package private) void |
BoyerMyrvoldPlanarityInspector.Node.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.
|
(package private) BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.Node.nextOnOuterFace(BoyerMyrvoldPlanarityInspector.Node prev) |
Returns a neighbor of this node which is not equal to the prev
|
private void |
BoyerMyrvoldPlanarityInspector.printBiconnectedComponent(BoyerMyrvoldPlanarityInspector.Node node) |
Method for debug purposes, prints the boundary the node belongs to
|
private void |
BoyerMyrvoldPlanarityInspector.removeUp(BoyerMyrvoldPlanarityInspector.Node start,
BoyerMyrvoldPlanarityInspector.Node end,
int dir,
java.util.Set<BoyerMyrvoldPlanarityInspector.Edge> edges) |
Removes the edges from the outer face from the start node to the end node in
the direction dir from the set edges
|
private BoyerMyrvoldPlanarityInspector.Edge |
BoyerMyrvoldPlanarityInspector.searchEdge(BoyerMyrvoldPlanarityInspector.Node current,
int heightMax) |
Searches a back edge which target has a height smaller than heightMax
|
private BoyerMyrvoldPlanarityInspector.Edge |
BoyerMyrvoldPlanarityInspector.searchEdge(BoyerMyrvoldPlanarityInspector.Node current,
int heightMax,
BoyerMyrvoldPlanarityInspector.Edge forbiddenEdge) |
Searches a back edge which target has a height smaller than heightMax
|
private BoyerMyrvoldPlanarityInspector.Edge |
BoyerMyrvoldPlanarityInspector.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.
|
private BoyerMyrvoldPlanarityInspector.Edge |
BoyerMyrvoldPlanarityInspector.searchSubtreeDfs(BoyerMyrvoldPlanarityInspector.Node start,
java.util.function.Predicate<BoyerMyrvoldPlanarityInspector.Edge> isNeeded) |
Recursively searches all the subtree root at the node start to find an edge
satisfying the predicate .
|
private BoyerMyrvoldPlanarityInspector.OuterFaceCirculator |
BoyerMyrvoldPlanarityInspector.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 the predicate or returns a circulator to the stop node.
|
private void |
BoyerMyrvoldPlanarityInspector.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 .
|
(package private) void |
BoyerMyrvoldPlanarityInspector.Node.substitute(BoyerMyrvoldPlanarityInspector.Node node,
BoyerMyrvoldPlanarityInspector.Node newNeighbor) |
Substitutes the neighbor node with a newNeighbor
|
(package private) void |
BoyerMyrvoldPlanarityInspector.Node.substituteAnother(BoyerMyrvoldPlanarityInspector.Node node,
BoyerMyrvoldPlanarityInspector.Node newNeighbor) |
Substitutes a neighbor of this node, which is not equal to the node , with the
newNeighbor
|
private BoyerMyrvoldPlanarityInspector.Node |
BoyerMyrvoldPlanarityInspector.OuterFaceCirculator.toExistingNode(BoyerMyrvoldPlanarityInspector.Node node) |
Returns either node or its real counterpart in the case the node is a
component root.
|
private void |
BoyerMyrvoldPlanarityInspector.walkDown(BoyerMyrvoldPlanarityInspector.Node componentRoot) |
The walkdown procedure from the original paper.
|
private void |
BoyerMyrvoldPlanarityInspector.walkUp(BoyerMyrvoldPlanarityInspector.Node start,
BoyerMyrvoldPlanarityInspector.Node end,
BoyerMyrvoldPlanarityInspector.Edge edge) |
The walkup procedure from the original paper.
|