Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
UpwardPlanRep.h
Go to the documentation of this file.
1
33#pragma once
34
36
37namespace ogdf {
38
39
51public:
53
54#if 0
55 //debug only
57#endif
58
59 /* @{
60 * \brief Creates a planarized representation with respect to \p Gamma.
61 * Gamma muss be an upward planar embedding with a fixed ext. face
62 * Precondition: the graph is a single source graph
63 */
64
65 explicit UpwardPlanRep(
66 const CombinatorialEmbedding& Gamma); //upward planar embedding with a fixed ext. face
67
68 UpwardPlanRep(const GraphCopy& GC, // must be upward embedded and single source
69 adjEntry adj_ext); // the right face of this adjEntry is the external face
70
73
76 : GraphCopy()
77 , isAugmented(false)
78 , t_hat(nullptr)
79 , s_hat(nullptr)
80 , extFaceHandle(nullptr)
81 , crossings(0)
82 // multisources(false)
83 {
84 m_Gamma.init(*this);
85 m_isSinkArc.init(*this, false);
86 m_isSourceArc.init(*this, false);
87 }
88
89 virtual ~UpwardPlanRep() { }
90
93
95 // pred. the graph muss be a sinlge source graph
96 // We construct node t and connect the sink-switches with t. The new arcs are sSinkArc.
97 // For simplicity we construct an additional edge (t,t_hat) (the extFaceArc), where t_hat is the super sink.
98 void augment();
99
101 bool augmented() const { return isAugmented; }
102
104 const CombinatorialEmbedding& getEmbedding() const { return m_Gamma; }
105
107
108 node getSuperSink() const { return t_hat; }
109
110 node getSuperSource() const { return s_hat; }
111
112 int numberOfCrossings() const { return crossings; }
113
116
117 bool isSinkArc(edge e) const { return m_isSinkArc[e]; }
118
119 bool isSourceArc(edge e) const { return m_isSourceArc[e]; }
120
123 adjEntry sinkSwitchOf(node v) { return m_sinkSwitchOf[v]; }
124
127
128 //return the left in edge of node v.
130 if (v->indeg() == 0) {
131 return nullptr;
132 }
133
134 adjEntry adjFound = nullptr;
135 for (adjEntry adj : v->adjEntries) {
136 if (adj->theEdge()->target() == v && adj->cyclicSucc()->theEdge()->source() == v) {
137 adjFound = adj;
138 break;
139 }
140 }
141 return adjFound;
142 }
143
144 // debug
145 void outputFaces(const CombinatorialEmbedding& embedding) const {
146 std::cout << std::endl << "Face UPR " << std::endl;
147 for (face f : embedding.faces) {
148 std::cout << "face " << f->index() << ": ";
149 adjEntry adjNext = f->firstAdj();
150 do {
151 std::cout << adjNext->theEdge() << "; ";
152 adjNext = adjNext->faceCycleSucc();
153 } while (adjNext != f->firstAdj());
154 std::cout << std::endl;
155 }
156 if (embedding.externalFace() != nullptr) {
157 std::cout << "ext. face of the graph is: " << embedding.externalFace()->index()
158 << std::endl;
159 } else {
160 std::cout << "no ext. face set." << std::endl;
161 }
162 }
163
164
165protected:
167
169
171
173
174 // sinkArk are edges which are added to transform the original graph to single sink graph.
175 // note: the extFaceHandle is a sink arc.
177
178 // source arc are edges which are added to transform the original graph to a single source graph
180
181 // 0 if node v is not a non-top-sink-switch of a internal face.
182 // else v is (non-top) sink-switch of f (= right face of adjEntry).
184
185 adjEntry extFaceHandle; // the right face of this adjEntry is always the ext. face
186
188
189
190private:
192
194 void initMe();
195
197
199
201};
202
203}
Declaration of graph copy classes.
Class for adjacency list elements.
Definition Graph_d.h:79
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
Combinatorial embeddings of planar graphs with modification functionality.
face externalFace() const
Returns the external face.
internal::GraphObjectContainer< FaceElement > faces
The container containing all face objects.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Faces in a combinatorial embedding.
int index() const
Returns the index of the face.
Edge insertion module that inserts each edge optimally into a fixed embedding.
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
void init(const Graph &G)
Re-initializes the copy using the graph G.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
int indeg() const
Returns the indegree of the node.
Definition Graph_d.h:214
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
Takes an acyclic connected non-upward-planar graph and planarizes it, i.e., we obtain an upward-plana...
Upward planarized representations (of a connected component) of a graph.
void copyMe(const UpwardPlanRep &UPR)
UpwardPlanRep(const GraphCopy &GC, adjEntry adj_ext)
EdgeArray< bool > m_isSourceArc
void removeSinkArcs(SList< adjEntry > &crossedEdges)
NodeArray< adjEntry > m_sinkSwitchOf
CombinatorialEmbedding m_Gamma
bool augmented() const
return true if graph is augmented to a single source single sink graph
CombinatorialEmbedding & getEmbedding()
void augment()
convert to a single source single sink graph (result is not necessary a st-graph!).
node s_hat
the super source
UpwardPlanRep(const CombinatorialEmbedding &Gamma)
UpwardPlanRep()
standart constructor
UpwardPlanRep(const UpwardPlanRep &UPR)
copy constructor
void outputFaces(const CombinatorialEmbedding &embedding) const
bool isSourceArc(edge e) const
adjEntry getAdjEntry(const CombinatorialEmbedding &Gamma, node v, face f) const
return the adjEntry of v which right face is f.
bool isAugmented
the UpwardPlanRep is augmented to a single source and single sink graph
int numberOfCrossings() const
EdgeArray< bool > m_isSinkArc
const CombinatorialEmbedding & getEmbedding() const
return the upward planar embedding
void constructSinkArcs(face f, node t)
void insertEdgePathEmbedded(edge eOrig, SList< adjEntry > crossedEdges, EdgeArray< int > &cost)
same as insertEdgePath, but assumes that the graph is embedded
node getSuperSource() const
node getSuperSink() const
UpwardPlanRep & operator=(const UpwardPlanRep &copy)
Assignment operator.
bool isSinkArc(edge e) const
adjEntry leftInEdge(node v) const
void initMe()
only for planarizer !!!
adjEntry sinkSwitchOf(node v)
0 if node v is not a sink switch (not the top sink switch !!) of an internal face....
node t_hat
< embedding og this UpwardPlanRep
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.