|
|||
|
|
|
|||
|
|
#include <FaceSinkGraph.h>
Public Member Functions | |
| FaceSinkGraph (const ConstCombinatorialEmbedding &E, node s) | |
| constructor (we assume that the original graph is biconnected!) | |
| FaceSinkGraph () | |
| default constructor (dummy) | |
| void | init (const ConstCombinatorialEmbedding &E, node s) |
| const Graph & | originalGraph () const |
| return a reference to the original graph G | |
| const ConstCombinatorialEmbedding & | originalEmbedding () const |
| returns a reference to the embedding E of the original graph G | |
| node | originalNode (node v) const |
| face | originalFace (node v) const |
| bool | containsSource (node v) const |
| node | checkForest () |
| void | possibleExternalFaces (SList< face > &externalFaces) |
| node | faceNodeOf (edge e) |
| node | faceNodeOf (face f) |
| void | stAugmentation (node h, Graph &G, SList< node > &augmentedNodes, SList< edge > &augmentedEdges) |
| augments G to an st-planar graph (original implementation) | |
| void | stAugmentation (node h, Graph &G, node &superSink, SList< edge > &augmentedEdges) |
| augments G to an st-planar graph | |
Private Member Functions | |
| void | doInit () |
| constructs face-sink graph | |
| bool | dfsCheckForest (node v, node parent, NodeArray< bool > &visited, int &nInternalVertices) |
| performs dfs-traversal and checks for backwards edges | |
| void | gatherExternalFaces (node v, node parent, SList< face > &externalFaces) |
| builds list of possible external faces | |
| node | dfsFaceNodeOf (node v, node parent, face f1, face f2) |
| node | dfsStAugmentation (node v, node parent, Graph &G, SList< node > &augmentedNodes, SList< edge > &augmentedEdges) |
| node | dfsStAugmentation (node v, node parent, Graph &G, SList< edge > &augmentedEdges) |
Private Attributes | |
| const ConstCombinatorialEmbedding * | m_pE |
| associated embedding of graph G | |
| node | m_source |
| the single source | |
| node | m_T |
| representative of unique tree T | |
| NodeArray< node > | m_originalNode |
| original node in G | |
| NodeArray< face > | m_originalFace |
| original face in E | |
| NodeArray< bool > | m_containsSource |
| contains face node the source ? | |
Definition at line 66 of file FaceSinkGraph.h.
| ogdf::FaceSinkGraph::FaceSinkGraph | ( | const ConstCombinatorialEmbedding & | E, | |
| node | s | |||
| ) |
constructor (we assume that the original graph is biconnected!)
| ogdf::FaceSinkGraph::FaceSinkGraph | ( | ) | [inline] |
| void ogdf::FaceSinkGraph::init | ( | const ConstCombinatorialEmbedding & | E, | |
| node | s | |||
| ) |
| const Graph& ogdf::FaceSinkGraph::originalGraph | ( | ) | const [inline] |
| const ConstCombinatorialEmbedding& ogdf::FaceSinkGraph::originalEmbedding | ( | ) | const [inline] |
returns a reference to the embedding E of the original graph G
Definition at line 85 of file FaceSinkGraph.h.
returns the sink-switch in G corresponding to node v in the face-sink graph, 0 if v corresponds to a face
Definition at line 91 of file FaceSinkGraph.h.
returns the face in E corresponding to node v in the face-sink graph, 0 if v corresponds to a sink-switch
Definition at line 97 of file FaceSinkGraph.h.
| bool ogdf::FaceSinkGraph::containsSource | ( | node | v | ) | const [inline] |
Definition at line 103 of file FaceSinkGraph.h.
| node ogdf::FaceSinkGraph::checkForest | ( | ) |
checks if the face-sink graph is a forest with 1) there is exactly one tree T containing no internal vertex of G 2) all other trees contain exactly one internal vertex of G a node in tree T is returned as representative
returns the list of faces f in E such that there exists an upward-planar drawing realizing E with f as external face
Definition at line 116 of file FaceSinkGraph.h.
Definition at line 121 of file FaceSinkGraph.h.
Definition at line 127 of file FaceSinkGraph.h.
| void ogdf::FaceSinkGraph::stAugmentation | ( | node | h, | |
| Graph & | G, | |||
| SList< node > & | augmentedNodes, | |||
| SList< edge > & | augmentedEdges | |||
| ) |
augments G to an st-planar graph (original implementation)
introduces also new nodes into G corresponding to face-nodes in face sink graph)
| void ogdf::FaceSinkGraph::stAugmentation | ( | node | h, | |
| Graph & | G, | |||
| node & | superSink, | |||
| SList< edge > & | augmentedEdges | |||
| ) |
augments G to an st-planar graph
(introduces only one new node as super sink into G)
| void ogdf::FaceSinkGraph::doInit | ( | ) | [private] |
constructs face-sink graph
| bool ogdf::FaceSinkGraph::dfsCheckForest | ( | node | v, | |
| node | parent, | |||
| NodeArray< bool > & | visited, | |||
| int & | nInternalVertices | |||
| ) | [private] |
performs dfs-traversal and checks for backwards edges
| void ogdf::FaceSinkGraph::gatherExternalFaces | ( | node | v, | |
| node | parent, | |||
| SList< face > & | externalFaces | |||
| ) | [private] |
builds list of possible external faces
all faces in tree T containing the single source s) by a dfs traversal of T
| node ogdf::FaceSinkGraph::dfsStAugmentation | ( | node | v, | |
| node | parent, | |||
| Graph & | G, | |||
| SList< node > & | augmentedNodes, | |||
| SList< edge > & | augmentedEdges | |||
| ) | [private] |
| node ogdf::FaceSinkGraph::dfsStAugmentation | ( | node | v, | |
| node | parent, | |||
| Graph & | G, | |||
| SList< edge > & | augmentedEdges | |||
| ) | [private] |
const ConstCombinatorialEmbedding* ogdf::FaceSinkGraph::m_pE [private] |
node ogdf::FaceSinkGraph::m_source [private] |
node ogdf::FaceSinkGraph::m_T [private] |
NodeArray<node> ogdf::FaceSinkGraph::m_originalNode [private] |
NodeArray<face> ogdf::FaceSinkGraph::m_originalFace [private] |
NodeArray<bool> ogdf::FaceSinkGraph::m_containsSource [private] |