Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

FaceSinkGraph.h
Go to the documentation of this file.
1 
32 #pragma once
33 
35 #include <ogdf/basic/NodeArray.h>
36 #include <ogdf/basic/FaceArray.h>
37 #include <ogdf/basic/SList.h>
38 
39 
40 namespace ogdf {
41 
42 
44 {
45 public:
48 
50  FaceSinkGraph() : m_pE(nullptr) { }
51 
52 
53  void init(const ConstCombinatorialEmbedding &E, node s);
54 
55 
57  const Graph &originalGraph() const {
58  return *m_pE;
59  }
60 
63  return *m_pE;
64  }
65 
68  node originalNode(node v) const {
69  return m_originalNode[v];
70  }
71 
74  face originalFace(node v) const {
75  return m_originalFace[v];
76  }
77 
78  // returns true iff node v in the face-sink graph corresponds to a
79  // face in E containing the source
80  bool containsSource(node v) const {
81  return m_containsSource[v];
82  }
83 
88  node v_T = checkForest();
89  if (v_T != nullptr)
90  gatherExternalFaces(m_T,nullptr,externalFaces);
91  return v_T;
92  }
93 
94 
96  return dfsFaceNodeOf(m_T,nullptr,
97  m_pE->rightFace(e->adjSource()),m_pE->rightFace(e->adjTarget()));
98  }
99 
100 
102  return dfsFaceNodeOf(m_T,nullptr,f,nullptr);
103  }
104 
105 
107 
109  void stAugmentation(
110  node h, // node corresponding to external face
111  Graph &G, // original graph (not const)
112  SList<node> &augmentedNodes, // list of augmented nodes
113  SList<edge> &augmentedEdges); // list of augmented edges
114 
116 
118  void stAugmentation(
119  node h, // node corresponding to external face
120  Graph &G, // original graph (not const)
121  node &superSink, // super sink
122  SList<edge> &augmentedEdges); // list of augmented edges
123 
125  // the ext. face muss be set
126  void sinkSwitches(FaceArray< List<adjEntry> > &faceSwitches);
127 
128 private:
130  void doInit();
131 
133  bool dfsCheckForest(
134  node v, // current node
135  node parent, // its parent in tree
136  NodeArray<bool> &visited, // not already visited ?
137  // number of internal vertices of G in current tree
138  int &nInternalVertices);
139 
141 
144  void gatherExternalFaces(
145  node v, // current node
146  node parent, // its parent
147  SList<face> &externalFaces); // returns list of possible external faces
148 
149  node dfsFaceNodeOf(node v, node parent,face f1, face f2);
150 
151  node dfsStAugmentation(
152  node v, // current node
153  node parent, // its parent
154  Graph &G, // original graph (not const)
155  SList<node> &augmentedNodes, // list of augmented nodes
156  SList<edge> &augmentedEdges); // list of augmented edges
157 
158  node dfsStAugmentation(
159  node v, // current node
160  node parent, // its parent
161  Graph &G, // original graph (not const)
162  SList<edge> &augmentedEdges); // list of augmented edges
163 
164 
169 
173 
174 #if 0
175  void dfsFST(node v, //current node
177  node parent, //parent of v
178  FaceArray< List<adjEntry> > &faceSwitches,
179  NodeArray<bool> &visited);
180 #endif
181 
186  node checkForest();
187 };
188 
189 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::FaceSinkGraph::originalGraph
const Graph & originalGraph() const
return a reference to the original graph G
Definition: FaceSinkGraph.h:57
ogdf::FaceSinkGraph::m_T
node m_T
representative of unique tree T
Definition: FaceSinkGraph.h:168
ogdf::FaceSinkGraph::originalFace
face originalFace(node v) const
returns the face in E corresponding to node v in the face-sink graph, 0 if v corresponds to a sink-sw...
Definition: FaceSinkGraph.h:74
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
FaceArray.h
declaration and implementation of FaceArray class
ogdf::NodeArray< bool >
ogdf::FaceSinkGraph::faceNodeOf
node faceNodeOf(edge e)
Definition: FaceSinkGraph.h:95
ogdf::FaceSinkGraph::m_originalNode
NodeArray< node > m_originalNode
original node in G
Definition: FaceSinkGraph.h:170
ogdf::FaceSinkGraph::m_containsSource
NodeArray< bool > m_containsSource
contains face node the source ?
Definition: FaceSinkGraph.h:172
ogdf::FaceSinkGraph::possibleExternalFaces
node possibleExternalFaces(SList< face > &externalFaces)
returns the list of faces f in E such that there exists an upward-planar drawing realizing E with f a...
Definition: FaceSinkGraph.h:87
SList.h
Declaration of singly linked lists and iterators.
ogdf::FaceArray
Dynamic arrays indexed with faces of a combinatorial embedding.
Definition: CombinatorialEmbedding.h:174
ogdf::FaceSinkGraph::m_source
node m_source
the single source
Definition: FaceSinkGraph.h:167
ogdf::FaceSinkGraph::m_originalFace
NodeArray< face > m_originalFace
original face in E
Definition: FaceSinkGraph.h:171
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::EdgeElement::adjSource
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition: Graph_d.h:333
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::FaceSinkGraph::m_pE
const ConstCombinatorialEmbedding * m_pE
associated embedding of graph G
Definition: FaceSinkGraph.h:166
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::ConstCombinatorialEmbedding
Combinatorial embeddings of planar graphs.
Definition: CombinatorialEmbedding.h:198
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::FaceSinkGraph::originalNode
node originalNode(node v) const
returns the sink-switch in G corresponding to node v in the face-sink graph, 0 if v corresponds to a ...
Definition: FaceSinkGraph.h:68
ogdf::FaceSinkGraph
Definition: FaceSinkGraph.h:43
CombinatorialEmbedding.h
Declaration of CombinatorialEmbedding and face.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::FaceSinkGraph::containsSource
bool containsSource(node v) const
Definition: FaceSinkGraph.h:80
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::FaceSinkGraph::originalEmbedding
const ConstCombinatorialEmbedding & originalEmbedding() const
returns a reference to the embedding E of the original graph G
Definition: FaceSinkGraph.h:62
ogdf::FaceSinkGraph::faceNodeOf
node faceNodeOf(face f)
Definition: FaceSinkGraph.h:101
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::FaceElement
Faces in a combinatorial embedding.
Definition: CombinatorialEmbedding.h:111
ogdf::FaceSinkGraph::FaceSinkGraph
FaceSinkGraph()
default constructor (dummy)
Definition: FaceSinkGraph.h:50