|
|||
|
|
|
|||
|
|
#include <BoyerMyrvoldPlanar.h>
Public Types | |
| enum | enumEmbeddingGrade { doNotEmbed = -3, doNotFind = -2, doFindUnlimited = -1, doFindZero = 0 } |
| Denotes the different embedding options. More... | |
Public Member Functions | |
| BoyerMyrvoldPlanar (Graph &g, bool bundles, int m_embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, bool randomDFSTree, bool avoidE2Minors) | |
| Constructor, for parameters see BoyerMyrvold. | |
| ~BoyerMyrvoldPlanar () | |
| Destructor. | |
| bool | start () |
| Starts the embedding algorithm. | |
| void | flipBicomp (int c, int marker, NodeArray< int > &visited, bool wholeGraph, bool deleteFlipFlags) |
| Flips all nodes of the bicomp with unique, real, rootchild c as necessary. | |
| void | mergeWholeNonPlanarGraph () |
| Flips the whole graph and merges virtual with real nodes, if not already done. | |
Protected Member Functions | |
| bool | pertinent (const node &w) |
| Checks whether node w is pertinent. w has to be non-virtual. | |
| bool | internallyActive (const node &w, const int &v) |
| Checks whether real node w is internally active while embedding node with DFI v. | |
| bool | externallyActive (const node &w, const int &v) |
| Checks whether real node w is externally active while embedding node with DFI v. | |
| bool | inactive (const node &w, const int &v) |
| Checks whether real node w is inactive while embedding node with DFI v. | |
| int | infoAboutNode (const node &w, const int &v) |
| Checks all dynamic information about a node w while embedding node with DFI v. | |
| node | successorOnExternalFace (const node &w, int &direction) |
| Walks upon external face in the given direction starting at w. | |
| node | successorWithoutShortCircuit (const node &w, int &direction) |
| Walks upon external face in given direction avoiding short circuit edges. | |
| node | constSuccessorOnExternalFace (const node &v, const int &direction) |
| Returns the successornode on the external face in given direction. | |
| node | constSuccessorWithoutShortCircuit (const node &v, const int &direction) |
| Walks upon external face in direction avoiding short circuit edges. | |
| adjEntry | beforeShortCircuitEdge (const node &v, const int &direction) |
| Returns underlying former adjEntry, if a short circuit edge in direction of v exists. | |
| node | activeSuccessor (node w, int &direction, const int &v, int &info) |
| Walks upon external face in the given direction starting at w until an active vertex is reached. | |
| node | constActiveSuccessor (node w, int direction, const int &v, int &info) |
| Walks upon external face in the given direction (without changing it) until an active vertex is reached. | |
| bool | wNodesExist (node root, const node &stopx, const node &stopy) |
| Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy. | |
| void | printNodeInfo (node v) |
| Prints informations about node v. | |
| void | mergeBiconnectedComponent (StackPure< int > &stack, const int j) |
| Merges the last two biconnected components saved in stack while embedding them. | |
| void | mergeBiconnectedComponentOnlyPlanar (StackPure< int > &stack, const int j) |
| Merges the last two biconnected components saved in stack without embedding them. | |
| void | embedBackedges (const node v, const int v_dir, const node w, const int w_dir, const int i) |
| Embeds backedges from node v with direction v_dir to node w with direction w_dir. | |
| void | embedBackedgesOnlyPlanar (const node v, const int v_dir, const node w, const int w_dir, const int i) |
| Links (not embed) backedges from node v with direction v_dir to node w with direction w_dir. | |
| void | createShortCircuitEdge (const node v, const int v_dir, const node w, const int w_dir) |
| Creates a short circuit edge from node v with direction v_dir to node w with direction w_dir. | |
| node | walkup (const node v, const node w, const int marker, const edge back) |
| Walkup: Builds the pertinent subgraph for the backedge back. | |
| int | walkdown (const int i, const node v, FindKuratowskis &findKuratowskis) |
| Walkdown: Embeds all backedges with DFI i as targetnode to node v. | |
| void | mergeUnprocessedNodes () |
| Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart. | |
| void | postProcessEmbedding () |
| Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped. | |
| bool | embed () |
| Starts the embedding phase, which embeds m_g node by node in descending DFI-order. | |
Protected Attributes | |
| Graph & | m_g |
| Input graph, which can be altered. | |
| const bool | m_bundles |
| Some parameters... see BoyerMyrvold for further options. | |
| const int | m_embeddingGrade |
| const bool | m_limitStructures |
| const bool | m_randomDFSTree |
| const bool | m_avoidE2Minors |
| int | m_flippedNodes |
| The whole number of bicomps, which have to be flipped. | |
| NodeArray< node > | m_realVertex |
| Link to non-virtual vertex of a virtual Vertex. | |
| NodeArray< int > | m_dfi |
| The one and only DFI-NodeArray. | |
| Array< node > | m_nodeFromDFI |
| Returns appropriate node from given DFI. | |
| NodeArray< adjEntry > | m_link [2] |
| Links to opposite adjacency entries on external face in clockwise resp. ccw order. | |
| NodeArray< adjEntry > | m_beforeSCE [2] |
| Links for short circuit edges. | |
| NodeArray< adjEntry > | m_adjParent |
| The adjEntry which goes from DFS-parent to current vertex. | |
| NodeArray< int > | m_leastAncestor |
| The DFI of the least ancestor node over all backedges. | |
| EdgeArray< int > | m_edgeType |
| Contains the type of each edge. | |
| NodeArray< int > | m_lowPoint |
| The lowpoint of each node. | |
| NodeArray< int > | m_highestSubtreeDFI |
| The highest DFI in a subtree with node as root. | |
| NodeArray< ListPure< node > > | m_separatedDFSChildList |
| A list to all separated DFS-children of node. | |
| NodeArray< ListIterator< node > > | m_pNodeInParent |
| Pointer to node contained in the DFSChildList of his parent, if exists. | |
| NodeArray< int > | m_visited |
| This Array keeps track of all vertices that are visited by current walkup. | |
| EdgeArray< node > | m_pointsToRoot |
| Identifies the rootnode of the child bicomp the given backedge points to. | |
| NodeArray< int > | m_visitedWithBackedge |
| Keeps track of all vertices that are visited by the walkup through a specific backedge. | |
| NodeArray< bool > | m_flipped |
| Iff true, the node is the root of a bicomp which has to be flipped. | |
| NodeArray< SListPure< adjEntry > > | m_backedgeFlags |
| Holds information, if node is the source of a backedge. | |
| NodeArray< SListPure< node > > | m_pertinentRoots |
| List of virtual bicomp roots, that are pertinent to the current embedded node. | |
| SListPure< KuratowskiStructure > & | m_output |
| Data structure for the kuratowski subdivisions, which will be returned. | |
Friends | |
| class | BoyerMyrvold |
| class | BoyerMyrvoldInit |
| class | FindKuratowskis |
| class | ExtractKuratowskis |
Definition at line 112 of file BoyerMyrvoldPlanar.h.
| ogdf::BoyerMyrvoldPlanar::BoyerMyrvoldPlanar | ( | Graph & | g, | |
| bool | bundles, | |||
| int | m_embeddingGrade, | |||
| bool | limitStructures, | |||
| SListPure< KuratowskiStructure > & | output, | |||
| bool | randomDFSTree, | |||
| bool | avoidE2Minors | |||
| ) |
Constructor, for parameters see BoyerMyrvold.
| ogdf::BoyerMyrvoldPlanar::~BoyerMyrvoldPlanar | ( | ) | [inline] |
| bool ogdf::BoyerMyrvoldPlanar::start | ( | ) |
Starts the embedding algorithm.
| void ogdf::BoyerMyrvoldPlanar::flipBicomp | ( | int | c, | |
| int | marker, | |||
| NodeArray< int > & | visited, | |||
| bool | wholeGraph, | |||
| bool | deleteFlipFlags | |||
| ) |
Flips all nodes of the bicomp with unique, real, rootchild c as necessary.
| c | is the unique rootchild of the bicomp | |
| marker | is the value which marks nodes as visited | |
| visited | is the array containing visiting information | |
| wholeGraph | Iff true, all bicomps of all connected components will be traversed | |
| deleteFlipFlags | Iff true, the flipping flags will be deleted after flipping |
| void ogdf::BoyerMyrvoldPlanar::mergeWholeNonPlanarGraph | ( | ) |
Flips the whole graph and merges virtual with real nodes, if not already done.
| bool ogdf::BoyerMyrvoldPlanar::pertinent | ( | const node & | w | ) | [inline, protected] |
Checks whether node w is pertinent. w has to be non-virtual.
Definition at line 174 of file BoyerMyrvoldPlanar.h.
| bool ogdf::BoyerMyrvoldPlanar::internallyActive | ( | const node & | w, | |
| const int & | v | |||
| ) | [inline, protected] |
Checks whether real node w is internally active while embedding node with DFI v.
Definition at line 181 of file BoyerMyrvoldPlanar.h.
| bool ogdf::BoyerMyrvoldPlanar::externallyActive | ( | const node & | w, | |
| const int & | v | |||
| ) | [inline, protected] |
Checks whether real node w is externally active while embedding node with DFI v.
Definition at line 188 of file BoyerMyrvoldPlanar.h.
| bool ogdf::BoyerMyrvoldPlanar::inactive | ( | const node & | w, | |
| const int & | v | |||
| ) | [inline, protected] |
Checks whether real node w is inactive while embedding node with DFI v.
Definition at line 197 of file BoyerMyrvoldPlanar.h.
| int ogdf::BoyerMyrvoldPlanar::infoAboutNode | ( | const node & | w, | |
| const int & | v | |||
| ) | [inline, protected] |
Checks all dynamic information about a node w while embedding node with DFI v.
| [out] | 0 | = inactive |
| [out] | 1 | = internallyActive |
| [out] | 2 | = pertinent and externallyActive |
| [out] | 3 | = externallyActive and not pertinent |
Definition at line 212 of file BoyerMyrvoldPlanar.h.
| node ogdf::BoyerMyrvoldPlanar::successorOnExternalFace | ( | const node & | w, | |
| int & | direction | |||
| ) | [inline, protected] |
Walks upon external face in the given direction starting at w.
If none of the bicomps has been flipped then CW = clockwise and CCW = counterclockwise holds. In general, the traversaldirection could have been changed due to flipped components. If this occurs, the traversaldirection is flipped.
Definition at line 236 of file BoyerMyrvoldPlanar.h.
| node ogdf::BoyerMyrvoldPlanar::successorWithoutShortCircuit | ( | const node & | w, | |
| int & | direction | |||
| ) | [inline, protected] |
Walks upon external face in given direction avoiding short circuit edges.
Definition at line 250 of file BoyerMyrvoldPlanar.h.
| node ogdf::BoyerMyrvoldPlanar::constSuccessorOnExternalFace | ( | const node & | v, | |
| const int & | direction | |||
| ) | [inline, protected] |
Returns the successornode on the external face in given direction.
direction is not changed.
Definition at line 266 of file BoyerMyrvoldPlanar.h.
| node ogdf::BoyerMyrvoldPlanar::constSuccessorWithoutShortCircuit | ( | const node & | v, | |
| const int & | direction | |||
| ) | [inline, protected] |
Walks upon external face in direction avoiding short circuit edges.
direction is not changed.
Definition at line 275 of file BoyerMyrvoldPlanar.h.
| adjEntry ogdf::BoyerMyrvoldPlanar::beforeShortCircuitEdge | ( | const node & | v, | |
| const int & | direction | |||
| ) | [inline, protected] |
Returns underlying former adjEntry, if a short circuit edge in direction of v exists.
Otherwise the common edge is returned. In every case the returned adjEntry points to the targetnode.
Definition at line 285 of file BoyerMyrvoldPlanar.h.
| node ogdf::BoyerMyrvoldPlanar::activeSuccessor | ( | node | w, | |
| int & | direction, | |||
| const int & | v, | |||
| int & | info | |||
| ) | [protected] |
Walks upon external face in the given direction starting at w until an active vertex is reached.
Returns dynamical typeinformation info of that endvertex.
| node ogdf::BoyerMyrvoldPlanar::constActiveSuccessor | ( | node | w, | |
| int | direction, | |||
| const int & | v, | |||
| int & | info | |||
| ) | [inline, protected] |
Walks upon external face in the given direction (without changing it) until an active vertex is reached.
Returns dynamical typeinformation info of that endvertex. But does not change the direction.
Definition at line 308 of file BoyerMyrvoldPlanar.h.
| bool ogdf::BoyerMyrvoldPlanar::wNodesExist | ( | node | root, | |
| const node & | stopx, | |||
| const node & | stopy | |||
| ) | [inline, protected] |
Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.
The node root is root of the bicomp containing the stopping vertices
Definition at line 315 of file BoyerMyrvoldPlanar.h.
| void ogdf::BoyerMyrvoldPlanar::printNodeInfo | ( | node | v | ) | [inline, protected] |
| void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponent | ( | StackPure< int > & | stack, | |
| const int | j | |||
| ) | [protected] |
Merges the last two biconnected components saved in stack while embedding them.
j is the outgoing traversal direction of the current node to embed
| void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponentOnlyPlanar | ( | StackPure< int > & | stack, | |
| const int | j | |||
| ) | [protected] |
Merges the last two biconnected components saved in stack without embedding them.
j is the outgoing traversal direction of the current node to embed
| void ogdf::BoyerMyrvoldPlanar::embedBackedges | ( | const node | v, | |
| const int | v_dir, | |||
| const node | w, | |||
| const int | w_dir, | |||
| const int | i | |||
| ) | [protected] |
Embeds backedges from node v with direction v_dir to node w with direction w_dir.
i is the DFI of current embedded node.
| void ogdf::BoyerMyrvoldPlanar::embedBackedgesOnlyPlanar | ( | const node | v, | |
| const int | v_dir, | |||
| const node | w, | |||
| const int | w_dir, | |||
| const int | i | |||
| ) | [protected] |
Links (not embed) backedges from node v with direction v_dir to node w with direction w_dir.
i is the DFI of current embedded node.
| void ogdf::BoyerMyrvoldPlanar::createShortCircuitEdge | ( | const node | v, | |
| const int | v_dir, | |||
| const node | w, | |||
| const int | w_dir | |||
| ) | [protected] |
Creates a short circuit edge from node v with direction v_dir to node w with direction w_dir.
| node ogdf::BoyerMyrvoldPlanar::walkup | ( | const node | v, | |
| const node | w, | |||
| const int | marker, | |||
| const edge | back | |||
| ) | [protected] |
Walkup: Builds the pertinent subgraph for the backedge back.
back is the backedge between nodes v and w. v is the current node to embed. All visited nodes are marked with value marker. The Function returns the last traversed node.
| int ogdf::BoyerMyrvoldPlanar::walkdown | ( | const int | i, | |
| const node | v, | |||
| FindKuratowskis & | findKuratowskis | |||
| ) | [protected] |
Walkdown: Embeds all backedges with DFI i as targetnode to node v.
| i | is the DFI of the current vertex to embed | |
| v | is the virtual node being the root of the bicomp attached to i | |
| findKuratowskis | collects information in order to extract Kuratowski Subdivisions later | |
| [out] | 1,iff | the embedding process found a stopping configuration |
| void ogdf::BoyerMyrvoldPlanar::mergeUnprocessedNodes | ( | ) | [protected] |
Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.
| void ogdf::BoyerMyrvoldPlanar::postProcessEmbedding | ( | ) | [protected] |
Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.
In addition, embedding steps for parallel edges and self-loops are implemented.
| bool ogdf::BoyerMyrvoldPlanar::embed | ( | ) | [protected] |
Starts the embedding phase, which embeds m_g node by node in descending DFI-order.
Returns true, if graph is planar, false otherwise.
friend class BoyerMyrvold [friend] |
Definition at line 113 of file BoyerMyrvoldPlanar.h.
friend class BoyerMyrvoldInit [friend] |
Definition at line 114 of file BoyerMyrvoldPlanar.h.
friend class FindKuratowskis [friend] |
Definition at line 115 of file BoyerMyrvoldPlanar.h.
friend class ExtractKuratowskis [friend] |
Definition at line 116 of file BoyerMyrvoldPlanar.h.
Graph& ogdf::BoyerMyrvoldPlanar::m_g [protected] |
const bool ogdf::BoyerMyrvoldPlanar::m_bundles [protected] |
Some parameters... see BoyerMyrvold for further options.
Definition at line 422 of file BoyerMyrvoldPlanar.h.
const int ogdf::BoyerMyrvoldPlanar::m_embeddingGrade [protected] |
Definition at line 423 of file BoyerMyrvoldPlanar.h.
const bool ogdf::BoyerMyrvoldPlanar::m_limitStructures [protected] |
Definition at line 424 of file BoyerMyrvoldPlanar.h.
const bool ogdf::BoyerMyrvoldPlanar::m_randomDFSTree [protected] |
Definition at line 425 of file BoyerMyrvoldPlanar.h.
const bool ogdf::BoyerMyrvoldPlanar::m_avoidE2Minors [protected] |
Definition at line 426 of file BoyerMyrvoldPlanar.h.
int ogdf::BoyerMyrvoldPlanar::m_flippedNodes [protected] |
The whole number of bicomps, which have to be flipped.
Definition at line 429 of file BoyerMyrvoldPlanar.h.
NodeArray<node> ogdf::BoyerMyrvoldPlanar::m_realVertex [protected] |
Link to non-virtual vertex of a virtual Vertex.
A virtual vertex has negative DFI of the DFS-Child of related non-virtual Vertex
Definition at line 440 of file BoyerMyrvoldPlanar.h.
NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_dfi [protected] |
Array<node> ogdf::BoyerMyrvoldPlanar::m_nodeFromDFI [protected] |
NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_link[2] [protected] |
Links to opposite adjacency entries on external face in clockwise resp. ccw order.
m_link[0]=CCW, m_link[1]=CW
Definition at line 451 of file BoyerMyrvoldPlanar.h.
NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_beforeSCE[2] [protected] |
Links for short circuit edges.
If short circuit edges are introduced, the former adjEntries to the neighbors have to be saved here for embedding and merging purposes. If there is no short circuit edge, this adjEntry is NULL.
Definition at line 458 of file BoyerMyrvoldPlanar.h.
NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_adjParent [protected] |
The adjEntry which goes from DFS-parent to current vertex.
Definition at line 461 of file BoyerMyrvoldPlanar.h.
NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_leastAncestor [protected] |
The DFI of the least ancestor node over all backedges.
If no backedge exists, the least ancestor is the DFI of that node itself
Definition at line 466 of file BoyerMyrvoldPlanar.h.
EdgeArray<int> ogdf::BoyerMyrvoldPlanar::m_edgeType [protected] |
Contains the type of each edge.
| 0 | = EDGE_UNDEFINED | |
| 1 | = EDGE_SELFLOOP | |
| 2 | = EDGE_BACK | |
| 3 | = EDGE_DFS | |
| 4 | = EDGE_DFS_PARALLEL | |
| 5 | = EDGE_BACK_DELETED |
Definition at line 476 of file BoyerMyrvoldPlanar.h.
NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_lowPoint [protected] |
NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_highestSubtreeDFI [protected] |
The highest DFI in a subtree with node as root.
Definition at line 482 of file BoyerMyrvoldPlanar.h.
NodeArray<ListPure<node> > ogdf::BoyerMyrvoldPlanar::m_separatedDFSChildList [protected] |
A list to all separated DFS-children of node.
The list is sorted by lowpoint values (in linear time)
Definition at line 487 of file BoyerMyrvoldPlanar.h.
NodeArray<ListIterator<node> > ogdf::BoyerMyrvoldPlanar::m_pNodeInParent [protected] |
Pointer to node contained in the DFSChildList of his parent, if exists.
If node isn't in list or list doesn't exist, the pointer is set to NULL.
Definition at line 492 of file BoyerMyrvoldPlanar.h.
NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_visited [protected] |
This Array keeps track of all vertices that are visited by current walkup.
Definition at line 496 of file BoyerMyrvoldPlanar.h.
EdgeArray<node> ogdf::BoyerMyrvoldPlanar::m_pointsToRoot [protected] |
Identifies the rootnode of the child bicomp the given backedge points to.
Definition at line 499 of file BoyerMyrvoldPlanar.h.
NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_visitedWithBackedge [protected] |
Keeps track of all vertices that are visited by the walkup through a specific backedge.
This is done in order to refer to the unique child-bicomp of v.
Definition at line 504 of file BoyerMyrvoldPlanar.h.
NodeArray<bool> ogdf::BoyerMyrvoldPlanar::m_flipped [protected] |
Iff true, the node is the root of a bicomp which has to be flipped.
The DFS-child of every bicomp root vertex is unique. if a bicomp is flipped, this DFS-child is marked to check whether the bicomp has to be flipped or not.
Definition at line 511 of file BoyerMyrvoldPlanar.h.
NodeArray<SListPure<adjEntry> > ogdf::BoyerMyrvoldPlanar::m_backedgeFlags [protected] |
Holds information, if node is the source of a backedge.
This information refers to the adjEntries on the targetnode and is used during the walkdown
Definition at line 517 of file BoyerMyrvoldPlanar.h.
NodeArray<SListPure<node> > ogdf::BoyerMyrvoldPlanar::m_pertinentRoots [protected] |
List of virtual bicomp roots, that are pertinent to the current embedded node.
Definition at line 520 of file BoyerMyrvoldPlanar.h.
SListPure<KuratowskiStructure>& ogdf::BoyerMyrvoldPlanar::m_output [protected] |
Data structure for the kuratowski subdivisions, which will be returned.
Definition at line 523 of file BoyerMyrvoldPlanar.h.
