Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
BoyerMyrvoldPlanar.h
Go to the documentation of this file.
1
33#pragma once
34
36#include <ogdf/basic/List.h>
38#include <ogdf/basic/SList.h>
39
40#include <random>
41
42namespace ogdf {
43
46 Undefined = 0,
47 Selfloop = 1,
48 Back = 2,
49 Dfs = 3,
50 DfsParallel = 4,
51 BackDeleted = 5
52};
53
54class KuratowskiStructure;
55class FindKuratowskis;
56
57namespace boyer_myrvold {
58class BoyerMyrvoldInit;
59}
60
63 friend class BoyerMyrvold;
65 friend class FindKuratowskis;
66 friend class ExtractKuratowskis;
67
68public:
70 const static int DirectionCCW;
71
73 const static int DirectionCW;
74
76 enum class EmbeddingGrade {
77 doNotEmbed = -3, // and not find any kuratowski subdivisions
78 doNotFind = -2, // but embed
79 doFindUnlimited = -1, // and embed
80 doFindZero = 0 // and embed
81 };
82
86 bool extractSubgraph, const EdgeArray<int>* edgeCosts = nullptr);
87
94
96 bool start();
97
99
105 void flipBicomp(int c, int marker, NodeArray<int>& visited, bool wholeGraph,
106 bool deleteFlipFlags);
107
108 // avoid automatic creation of assignment operator
111
115 void seed(const std::minstd_rand rand) { m_rand = rand; }
116
117protected:
120
122 inline bool pertinent(node w) const {
123 OGDF_ASSERT(w != nullptr);
124 return m_dfi[w] > 0 && (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty());
125 }
126
128 inline bool internallyActive(node w, int v) const {
129 OGDF_ASSERT(w != nullptr);
130 return m_dfi[w] > 0 && pertinent(w) && !externallyActive(w, v);
131 }
132
134 inline bool externallyActive(node w, int v) const {
135 OGDF_ASSERT(w != nullptr);
136 if (m_dfi[w] <= 0) {
137 return false;
138 }
139 if (m_leastAncestor[w] < v) {
140 return true;
141 }
142 return !m_separatedDFSChildList[w].empty()
143 && m_lowPoint[m_separatedDFSChildList[w].front()] < v;
144 }
145
147 inline bool inactive(node w, int v) {
148 OGDF_ASSERT(w != nullptr);
149 if (m_dfi[w] <= 0) {
150 return true;
151 }
152 if (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty() || m_leastAncestor[w] < v) {
153 return false;
154 }
155 return m_separatedDFSChildList[w].empty()
156 || m_lowPoint[m_separatedDFSChildList[w].front()] >= v;
157 }
158
160
167 inline int infoAboutNode(node w, int v) const {
168 OGDF_ASSERT(w != nullptr);
169 if (m_dfi[w] <= 0) {
170 return 0;
171 }
172 if (!m_pertinentRoots[w].empty() || !m_backedgeFlags[w].empty()) {
173 // pertinent
174 if (m_leastAncestor[w] < v) {
175 return 2;
176 }
177 if (m_separatedDFSChildList[w].empty()) {
178 return 1;
179 }
180 return m_lowPoint[m_separatedDFSChildList[w].front()] < v ? 2 : 1;
181 } else {
182 // not pertinent
183 if (m_leastAncestor[w] < v) {
184 return 3;
185 }
186 if (m_separatedDFSChildList[w].empty()) {
187 return 0;
188 }
189 return m_lowPoint[m_separatedDFSChildList[w].front()] < v ? 3 : 0;
190 }
191 }
192
194
199 inline node successorOnExternalFace(node w, int& direction) const {
200 OGDF_ASSERT(w != nullptr);
201 OGDF_ASSERT(w->degree() > 0);
204 adjEntry adj = m_link[direction][w];
205 OGDF_ASSERT(adj->theNode() != nullptr);
206
207 if (w->degree() > 1) {
208 direction = adj
210 }
211 OGDF_ASSERT(direction
213 return adj->theNode();
214 }
215
217 inline node successorWithoutShortCircuit(node w, int& direction) {
218 OGDF_ASSERT(w != nullptr);
219 OGDF_ASSERT(w->degree() > 0);
222 adjEntry adj = beforeShortCircuitEdge(w, direction);
223 OGDF_ASSERT(adj->theNode() != nullptr);
224
225 if (w->degree() > 1) {
226 direction = adj
228 }
229 OGDF_ASSERT(direction
231 return adj->theNode();
232 }
233
235
237 inline node constSuccessorOnExternalFace(node v, int direction) {
238 OGDF_ASSERT(v != nullptr);
239 OGDF_ASSERT(v->degree() > 0);
240 return m_link[direction][v]->theNode();
241 }
242
244
246 inline node constSuccessorWithoutShortCircuit(node v, int direction) const {
247 OGDF_ASSERT(v != nullptr);
248 OGDF_ASSERT(v->degree() > 0);
249 return beforeShortCircuitEdge(v, direction)->theNode();
250 }
251
253
256 inline adjEntry beforeShortCircuitEdge(node v, int direction) const {
257 OGDF_ASSERT(v != nullptr);
258 return (m_beforeSCE[direction][v] == nullptr) ? m_link[direction][v]
259 : m_beforeSCE[direction][v];
260 }
261
263
265 node activeSuccessor(node w, int& direction, int v, int& info) const;
266
268
270 inline node constActiveSuccessor(node w, int direction, int v, int& info) const {
271 return activeSuccessor(w, direction, v, info);
272 }
273
275
277 inline bool wNodesExist(node root, node stopx, node stopy) const {
278 OGDF_ASSERT(root != stopx);
279 OGDF_ASSERT(root != stopy);
282 bool between = false;
283 while (root != nullptr) {
284 root = successorOnExternalFace(root, dir);
285 if (between && pertinent(root)) {
286 return true;
287 }
288 if (root == stopx || root == stopy) {
289 if (between) {
290 return false;
291 }
292 between = true;
293 }
294 }
295 return false;
296 }
297
299 inline void printNodeInfo(node v) {
300 std::cout
301 << "\nprintNodeInfo(" << m_dfi[v] << "): "
304 << "\tCCWBefore="
306 << ",CWBefore="
308 << "\tadjList: ";
309 adjEntry adj;
310 for (adj = v->firstAdj(); adj; adj = adj->succ()) {
311 std::cout << adj->twinNode() << " ";
312 }
313 }
314
318
321 void embedBackedges(const node v, const int v_dir, const node w, const int w_dir);
322
324 void createShortCircuitEdge(const node v, const int v_dir, const node w, const int w_dir);
325
327
330 node walkup(const node v, const node w, const int marker, const edge back);
331
333
339 int walkdown(const int i, const node v, FindKuratowskis* findKuratowskis);
340
343
345
348
350
352 bool embed();
353
355
358
361 const bool m_bundles;
364 const double m_randomness;
365 const bool m_avoidE2Minors;
367 std::minstd_rand m_rand;
369
371 bool m_extractSubgraph = true;
372
375
378
380
383
386
389
391
394
396
401
404
406
409
412
415
418
420
423
425
428
432
435
438
445
452
454
459
461
465
468
471
473};
474
476 return lhs > static_cast<int>(rhs);
477}
478
480 return lhs == static_cast<int>(rhs);
481}
482
484 return lhs != static_cast<int>(rhs);
485}
486
488 return lhs <= static_cast<int>(rhs);
489}
490
491}
Declaration and implementation of EdgeArray class.
Declaration of doubly linked lists and iterators.
Declaration and implementation of NodeArray class.
Declaration of singly linked lists and iterators.
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry twin() const
Returns the corresponding adjacency element associated with the same edge.
Definition Graph_d.h:109
adjEntry succ() const
Returns the successor in the adjacency list.
Definition Graph_d.h:155
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition Graph_d.h:112
node theNode() const
Returns the node whose adjacency list contains this element.
Definition Graph_d.h:103
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Wrapper class used for preprocessing and valid invocation of the planarity test.
This class implements the extended BoyerMyrvold planarity embedding algorithm.
BoyerMyrvoldPlanar(Graph &g, bool bundles, EmbeddingGrade embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > *edgeCosts=nullptr)
Constructor, for parameters see BoyerMyrvold.
NodeArray< SListPure< node > > m_pertinentRoots
List of virtual bicomp roots, that are pertinent to the current embedded node.
adjEntry beforeShortCircuitEdge(node v, int direction) const
Returns underlying former adjEntry, if a short circuit edge in direction of v exists.
Graph & m_g
Input graph, which can be altered.
static const int DirectionCW
Direction for clockwise traversal.
NodeArray< SListPure< adjEntry > > m_backedgeFlags
Holds information, if node is the source of a backedge.
NodeArray< ListIterator< node > > m_pNodeInParent
Pointer to node contained in the DFSChildList of his parent, if exists.
NodeArray< edge > m_visitedWithBackedge
Stores for each (real) non-root vertex v with which backedge it was visited during the walkup.
node successorOnExternalFace(node w, int &direction) const
Walks upon external face in the given direction starting at w.
bool externallyActive(node w, int v) const
Checks whether real node w is externally active while embedding node with DFI v.
int infoAboutNode(node w, int v) const
Checks all dynamic information about a node w while embedding node with DFI v.
BoyerMyrvoldPlanar(Graph &g, bool bundles, int embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > *edgeCosts=nullptr)
Constructor, for parameters see BoyerMyrvold.
Array< node > m_nodeFromDFI
Returns appropriate node from given DFI.
bool pertinent(node w) const
Checks whether node w is pertinent. w has to be non-virtual.
NodeArray< int > m_numUnembeddedBackedgesInBicomp
Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded.
node constSuccessorWithoutShortCircuit(node v, int direction) const
Walks upon external face in direction avoiding short circuit edges.
NodeArray< int > m_dfi
The one and only DFI-NodeArray.
NodeArray< int > m_leastAncestor
The DFI of the least ancestor node over all backedges.
int walkdown(const int i, const node v, FindKuratowskis *findKuratowskis)
Walkdown: Embeds all backedges with DFI i as targetnode to node v.
node constSuccessorOnExternalFace(node v, int direction)
Returns the successornode on the external face in given direction.
bool inactive(node w, int v)
Checks whether real node w is inactive while embedding node with DFI v.
NodeArray< int > m_lowPoint
The lowpoint of each node.
node successorWithoutShortCircuit(node w, int &direction)
Walks upon external face in given direction avoiding short circuit edges.
void seed(const std::minstd_rand rand)
Seeds the random generator for performing a random DFS. If this method is never called the random gen...
NodeArray< bool > m_flipped
Iff true, the node is the root of a bicomp which has to be flipped.
NodeArray< int > m_visited
This Array keeps track of all vertices that are visited by current walkup.
SListPure< KuratowskiStructure > & m_output
Data structure for the Kuratowski subdivisions, which will be returned.
bool wNodesExist(node root, node stopx, node stopy) const
Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.
node activeSuccessor(node w, int &direction, int v, int &info) const
Walks upon external face in the given direction starting at w until an active vertex is reached.
NodeArray< adjEntry > m_link[2]
Links to opposite adjacency entries on external face in clockwise resp. ccw order.
bool start()
Starts the embedding algorithm.
NodeArray< node > m_realVertex
Link to non-virtual vertex of a virtual Vertex.
const EdgeArray< int > * m_edgeCosts
NodeArray< adjEntry > m_adjParent
The adjEntry which goes from DFS-parent to current vertex.
void mergeBiconnectedComponent(ArrayBuffer< int > &stack)
Merges the last two biconnected components saved in stack. Embeds them iff m_embeddingGrade !...
static const int DirectionCCW
Direction for counterclockwise traversal.
EdgeArray< node > m_pointsToRoot
Identifies the rootnode of the child bicomp the given backedge points to.
BoyerMyrvoldPlanar & operator=(const BoyerMyrvoldPlanar &)
Assignment operator is undefined!
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.
EmbeddingGrade
Denotes the different embedding options.
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.
EdgeArray< BoyerMyrvoldEdgeType > m_edgeType
Contains the type of each edge.
NodeArray< adjEntry > m_beforeSCE[2]
Links for short circuit edges.
void mergeUnprocessedNodes()
Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.
int m_flippedNodes
The whole number of bicomps, which have to be flipped.
bool m_extractSubgraph
Flag for extracting a planar subgraph instead of testing for planarity.
void postProcessEmbedding()
Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.
bool internallyActive(node w, int v) const
Checks whether real node w is internally active while embedding node with DFI v.
void printNodeInfo(node v)
Prints informations about node v.
void embedBackedges(const node v, const int v_dir, const node w, const int w_dir)
Links (and embeds iff m_embeddingGrade != EmbeddingGrade::doNotEmbed) backedges from node v with dire...
node walkup(const node v, const node w, const int marker, const edge back)
Walkup: Builds the pertinent subgraph for the backedge back.
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.
node constActiveSuccessor(node w, int direction, int v, int &info) const
Walks upon external face in the given direction (without changing it) until an active vertex is reach...
bool embed()
Starts the embedding phase, which embeds m_g node by node in descending DFI-order.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Extracts multiple Kuratowski Subdivisions.
This class collects information about Kuratowski Subdivisions which is used for extraction later.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition Graph_d.h:220
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition Graph_d.h:223
Singly linked lists.
Definition SList.h:179
This class is used in the Boyer-Myrvold planarity test for preprocessing purposes.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
BoyerMyrvoldEdgeType
Type of edge.
@ DfsParallel
parallel DFS-edge
@ BackDeleted
deleted backedge
bool operator>(int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs)
bool operator!=(const Tuple2< E1, E2 > &t1, const Tuple2< E1, E2 > &t2)
Inequality operator for 2-tuples.
Definition tuples.h:86
bool operator<=(int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs)
bool operator==(const Tuple2< E1, E2 > &t1, const Tuple2< E1, E2 > &t2)
Equality operator for 2-tuples.
Definition tuples.h:80