Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ExtractKuratowskis.h
Go to the documentation of this file.
1 
33 #pragma once
34 
37 
38 namespace ogdf {
39 
42 public:
45 
47  inline bool isK33() const { return subdivisionType != SubdivisionType::E5; }
49  inline bool isK5() const { return subdivisionType == SubdivisionType::E5; }
50 
52  enum class SubdivisionType {
53  A=0,
54  AB=1,
55  AC=2,
56  AD=3,
57  AE1=4,
58  AE2=5,
59  AE3=6,
60  AE4=7,
61  B=8,
62  C=9,
63  D=10,
64  E1=11,
65  E2=12,
66  E3=13,
67  E4=14,
68  E5=15
69  };
72 
75 
78 };
79 
80 OGDF_EXPORT std::ostream &operator<<(std::ostream &os, const KuratowskiWrapper::SubdivisionType &obj);
81 
83 
89 public:
94 
96  void extract(
97  const SListPure<KuratowskiStructure>& allKuratowskis,
98  SList<KuratowskiWrapper>& output);
99 
101  void extractBundles(
102  const SListPure<KuratowskiStructure>& allKuratowskis,
103  SList<KuratowskiWrapper>& output);
104 
106  enum class KuratowskiType {
107  none = 0,
108  K33 = 1,
109  K5 = 2
110  };
111 
113 
120  const Graph& m_g,
121  const NodeArray<int>& dfi,
122  const SListPure<edge>& list);
123 
125 
133  const Graph& g,
134 #if 0
135  const NodeArray<int>& m_dfi,
136 #endif
137  EdgeArray<int>& edgenumber);
138 
140  static bool isANewKuratowski(
141  const Graph& g,
142  const SListPure<edge>& kuratowski,
143  const SList<KuratowskiWrapper>& output);
145 
147  static bool isANewKuratowski(
148 #if 0
149  const Graph& g,
150 #endif
151  const EdgeArray<int>& test,
152  const SList<KuratowskiWrapper>& output);
153 
154  // avoid automatic creation of assignment operator
157 
158 protected:
161 
163  const Graph& m_g;
164 
168  const bool m_avoidE2Minors;
169 
171 
176 
179 
182 
185 
187  inline void addExternalFacePath(
188  SListPure<edge>& list,
189  const SListPure<adjEntry>& externPath) {
191  for (itExtern = externPath.begin(); itExtern.valid(); ++itExtern) {
192  list.pushBack((*itExtern)->theEdge());
193  }
194  }
195 
197 
199  inline adjEntry adjToLowestNodeBelow(node high, int low);
200 
202 
204  inline void addDFSPath(SListPure<edge>& list, node bottom, node top);
206 
208  inline void addDFSPathReverse(SListPure<edge>& list, node bottom, node top);
209 
211  inline void truncateEdgelist(SListPure<edge>& list1, const SListPure<edge>& list2);
212 
214  void extractMinorA(
215  SList<KuratowskiWrapper>& output,
216  const KuratowskiStructure& k,
217 #if 0
218  const WInfo& info,
219 #endif
220  const SListPure<edge>& pathX,
221  const node endnodeX,
222  const SListPure<edge>& pathY,
223  const node endnodeY,
224  const SListPure<edge>& pathW);
226  void extractMinorB(
227  SList<KuratowskiWrapper>& output,
228  //NodeArray<int>& nodeflags,
229  //const int nodemarker,
230  const KuratowskiStructure& k,
231  const WInfo& info,
232  const SListPure<edge>& pathX,
233  const node endnodeX,
234  const SListPure<edge>& pathY,
235  const node endnodeY,
236  const SListPure<edge>& pathW);
239  SList<KuratowskiWrapper>& output,
240  NodeArray<int>& nodeflags,
241  const int nodemarker,
242  const KuratowskiStructure& k,
243  EdgeArray<int>& flags,
244  const WInfo& info,
245  const SListPure<edge>& pathX,
246  const node endnodeX,
247  const SListPure<edge>& pathY,
248  const node endnodeY,
249  const SListPure<edge>& pathW);
251  void extractMinorC(
252  SList<KuratowskiWrapper>& output,
253  const KuratowskiStructure& k,
254  const WInfo& info,
255  const SListPure<edge>& pathX,
256  const node endnodeX,
257  const SListPure<edge>& pathY,
258  const node endnodeY,
259  const SListPure<edge>& pathW);
261  void extractMinorD(
262  SList<KuratowskiWrapper>& output,
263  const KuratowskiStructure& k,
264  const WInfo& info,
265  const SListPure<edge>& pathX,
266  const node endnodeX,
267  const SListPure<edge>& pathY,
268  const node endnodeY,
269  const SListPure<edge>& pathW);
271  void extractMinorE(
272  SList<KuratowskiWrapper>& output,
273  bool firstXPath,
274  bool firstPath,
275  bool firstWPath,
276  bool firstWOnHighestXY,
277  const KuratowskiStructure& k,
278  const WInfo& info,
279  const SListPure<edge>& pathX,
280  const node endnodeX,
281  const SListPure<edge>& pathY,
282  const node endnodeY,
283  const SListPure<edge>& pathW);
286  SList<KuratowskiWrapper>& output,
287  bool firstXPath,
288  bool firstPath,
289  bool firstWPath,
290  bool firstWOnHighestXY,
291  NodeArray<int>& nodeflags,
292  const int nodemarker,
293  const KuratowskiStructure& k,
294  EdgeArray<int>& flags,
295  const WInfo& info,
296  const SListPure<edge>& pathX,
297  const node endnodeX,
298  const SListPure<edge>& pathY,
299  const node endnodeY,
300  const SListPure<edge>& pathW);
302  inline bool isMinorE1(
303  int before,
304  bool firstXPath,
305  bool firstYPath) const
306  {
307  return (before == -1 && firstXPath)
308  || (before == 1 && firstYPath);
309  }
311  void extractMinorE1(
312  SList<KuratowskiWrapper>& output,
313  int before,
314 #if 0
315  const node z,
316 #endif
317  const node px,
318  const node py,
319  const KuratowskiStructure& k,
320  const WInfo& info,
321  const SListPure<edge>& pathX,
322  const node endnodeX,
323  const SListPure<edge>& pathY,
324  const node endnodeY,
325  const SListPure<edge>& pathW,
326  const SListPure<edge>& pathZ,
327  const node endnodeZ);
329  inline bool checkMinorE2(
330  bool firstWPath,
331  bool firstWOnHighestXY) const
332  {
333  return !m_avoidE2Minors
334  && firstWPath
335  && firstWOnHighestXY;
336  }
338  inline bool isMinorE2(
339  const node endnodeX,
340  const node endnodeY,
341  const node endnodeZ) const
342  {
343  return m_dfi[endnodeZ] > m_dfi[endnodeX]
344  && m_dfi[endnodeZ] > m_dfi[endnodeY];
345  }
347  void extractMinorE2(
348  SList<KuratowskiWrapper>& output,
349 #if 0
350  int before,
351  const node z,
352  const node px,
353  const node py,
354 #endif
355  const KuratowskiStructure& k,
356  const WInfo& info,
357  const SListPure<edge>& pathX,
358  const node endnodeX,
359  const SListPure<edge>& pathY,
360  const node endnodeY,
361 #if 0
362  const SListPure<edge>& pathW,
363 #endif
364  const SListPure<edge>& pathZ
365 #if 0
366  , const node endnodeZ
367 #endif
368  );
370  inline bool isMinorE3(
371  const node endnodeX,
372  const node endnodeY,
373  const node endnodeZ) const
374  {
375  return endnodeX != endnodeY
376  && (m_dfi[endnodeX] > m_dfi[endnodeZ]
377  || m_dfi[endnodeY] > m_dfi[endnodeZ]);
378  }
380  void extractMinorE3(
381  SList<KuratowskiWrapper>& output,
382  int before,
383  const node z,
384  const node px,
385  const node py,
386  const KuratowskiStructure& k,
387  const WInfo& info,
388  const SListPure<edge>& pathX,
389  const node endnodeX,
390  const SListPure<edge>& pathY,
391  const node endnodeY,
392  const SListPure<edge>& pathW,
393  const SListPure<edge>& pathZ,
394  const node endnodeZ);
396  inline bool isMinorE4(
397  const node px,
398  const node py,
399  const KuratowskiStructure& k,
400  const WInfo& info) const
401  {
402  return (px != k.stopX && !info.pxAboveStopX)
403  || (py != k.stopY && !info.pyAboveStopY);
404  }
406  void extractMinorE4(
407  SList<KuratowskiWrapper>& output,
408  int before,
409  const node z,
410  const node px,
411  const node py,
412  const KuratowskiStructure& k,
413  const WInfo& info,
414  const SListPure<edge>& pathX,
415  const node endnodeX,
416  const SListPure<edge>& pathY,
417  const node endnodeY,
418  const SListPure<edge>& pathW,
419  const SListPure<edge>& pathZ,
420  const node endnodeZ);
422  inline bool isMinorE5(
423  const node px,
424  const node py,
425  const KuratowskiStructure& k,
426  const node endnodeX,
427  const node endnodeY,
428  const node endnodeZ) const
429  {
430  return px == k.stopX
431  && py == k.stopY
432  && k.V == k.RReal
433  && ((endnodeX == endnodeY
434  && m_dfi[endnodeZ] <= m_dfi[endnodeX])
435  || (endnodeX == endnodeZ
436  && m_dfi[endnodeY] <= m_dfi[endnodeX])
437  || (endnodeY == endnodeZ
438  && m_dfi[endnodeX] <= m_dfi[endnodeY]));
439  }
441  void extractMinorE5(
442  SList<KuratowskiWrapper>& output,
443 #if 0
444  int before,
445  const node z,
446  const node px,
447  const node py,
448 #endif
449  const KuratowskiStructure& k,
450  const WInfo& info,
451  const SListPure<edge>& pathX,
452  const node endnodeX,
453  const SListPure<edge>& pathY,
454  const node endnodeY,
455  const SListPure<edge>& pathW,
456  const SListPure<edge>& pathZ,
457  const node endnodeZ);
458 };
459 
460 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::KuratowskiStructure
A Kuratowski Structure is a special graph structure containing severals subdivisions.
Definition: FindKuratowskis.h:92
ogdf::ExtractKuratowskis::checkMinorE2
bool checkMinorE2(bool firstWPath, bool firstWOnHighestXY) const
Checks for minortype E2 preconditions.
Definition: ExtractKuratowskis.h:329
ogdf::ExtractKuratowskis::isMinorE3
bool isMinorE3(const node endnodeX, const node endnodeY, const node endnodeZ) const
Checks for minortype E3.
Definition: ExtractKuratowskis.h:370
BoyerMyrvoldPlanar.h
Declaration of the class BoyerMyrvoldPlanar.
ogdf::KuratowskiStructure::stopY
node stopY
Second stopping node.
Definition: FindKuratowskis.h:129
ogdf::KuratowskiStructure::stopX
node stopX
First stopping node.
Definition: FindKuratowskis.h:127
ogdf::KuratowskiWrapper
Wrapper-class for Kuratowski Subdivisions containing the minortype and edgelist.
Definition: ExtractKuratowskis.h:41
ogdf::whaType::A
@ A
ogdf::SListIteratorBase
Encapsulates a pointer to an ogdf::SList element.
Definition: SList.h:39
FindKuratowskis.h
Declaration of the class FindKuratowskis.
ogdf::KuratowskiWrapper::isK33
bool isK33() const
Returns true, iff subdivision is a K3,3-minor.
Definition: ExtractKuratowskis.h:47
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::WInfo::pxAboveStopX
bool pxAboveStopX
Definition: FindKuratowskis.h:72
ogdf::ExtractKuratowskis::m_avoidE2Minors
const bool m_avoidE2Minors
Some parameters, see BoyerMyrvold for further instructions.
Definition: ExtractKuratowskis.h:168
ogdf::Direction::before
@ before
ogdf::SListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: SList.h:115
ogdf::WInfo::pyAboveStopY
bool pyAboveStopY
Definition: FindKuratowskis.h:73
ogdf::ExtractKuratowskis::extractMinorE3
void extractMinorE3(SList< KuratowskiWrapper > &output, int before, const node z, const node px, const node py, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
Extracts minorsubtype E3 and adds it to list output.
ogdf::NodeArray< int >
ogdf::ExtractKuratowskis::KuratowskiType
KuratowskiType
Enumeration over Kuratowski Type none, K33, K5.
Definition: ExtractKuratowskis.h:106
ogdf::EdgeArray< int >
ogdf::ExtractKuratowskis::m_adjParent
const NodeArray< adjEntry > & m_adjParent
The adjEntry which goes from DFS-parent to current vertex.
Definition: ExtractKuratowskis.h:184
ogdf::ExtractKuratowskis::extractMinorE5
void extractMinorE5(SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
Extracts minorsubtype E5 and adds it to list output.
ogdf::ExtractKuratowskis::m_wasHere
NodeArray< int > m_wasHere
Array maintaining visited bits on each node.
Definition: ExtractKuratowskis.h:175
ogdf::SListPure::begin
iterator begin()
Returns an iterator to the first element of the list.
Definition: SList.h:318
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::ExtractKuratowskis::extractMinorA
void extractMinorA(SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
Extracts minortype A and adds it to list output.
ogdf::ExtractKuratowskis::extractMinorBBundles
void extractMinorBBundles(SList< KuratowskiWrapper > &output, NodeArray< int > &nodeflags, const int nodemarker, const KuratowskiStructure &k, EdgeArray< int > &flags, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
Extracts minortype B and adds it to list output (with bundles)
ogdf::ExtractKuratowskis::whichKuratowskiArray
static KuratowskiType whichKuratowskiArray(const Graph &g, EdgeArray< int > &edgenumber)
Checks, if edges in Array edgenumber form a valid Kuratowski Subdivision and returns the type.
ogdf::ExtractKuratowskis::isMinorE2
bool isMinorE2(const node endnodeX, const node endnodeY, const node endnodeZ) const
Checks for minortype E2.
Definition: ExtractKuratowskis.h:338
ogdf::KuratowskiWrapper::isK5
bool isK5() const
Returns true, iff subdivision is a K5-minor.
Definition: ExtractKuratowskis.h:49
ogdf::ExtractKuratowskis::isANewKuratowski
static bool isANewKuratowski(const Graph &g, const SListPure< edge > &kuratowski, const SList< KuratowskiWrapper > &output)
Returns true, iff the Kuratowski is not already contained in output.
ogdf::ExtractKuratowskis::extractMinorB
void extractMinorB(SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
Extracts minortype B and adds it to list output (no bundles)
ogdf::ExtractKuratowskis::extractBundles
void extractBundles(const SListPure< KuratowskiStructure > &allKuratowskis, SList< KuratowskiWrapper > &output)
Extracts all Kuratowski Subdivisions and adds them to output (with bundles)
ogdf::ExtractKuratowskis::extract
void extract(const SListPure< KuratowskiStructure > &allKuratowskis, SList< KuratowskiWrapper > &output)
Extracts all Kuratowski Subdivisions and adds them to output (without bundles)
ogdf::ExtractKuratowskis::KuratowskiType::K5
@ K5
a K5 subdivision exists
ogdf::ExtractKuratowskis::extractMinorE2
void extractMinorE2(SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathZ)
Extracts minorsubtype E2 and adds it to list output.
ogdf::ExtractKuratowskis::ExtractKuratowskis
ExtractKuratowskis(BoyerMyrvoldPlanar &bm)
Constructor.
ogdf::Array< node >
ogdf::KuratowskiWrapper::SubdivisionType
SubdivisionType
Possible minortypes of a Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:52
ogdf::KuratowskiWrapper::edgeList
SListPure< edge > edgeList
Contains the edges of the Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:77
ogdf::ExtractKuratowskis::extractMinorC
void extractMinorC(SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
Extracts minortype C and adds it to list output.
ogdf::ExtractKuratowskis::extractMinorE
void extractMinorE(SList< KuratowskiWrapper > &output, bool firstXPath, bool firstPath, bool firstWPath, bool firstWOnHighestXY, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
Extracts minortype E and adds it to list output (no bundles)
ogdf::ExtractKuratowskis::extractMinorE4
void extractMinorE4(SList< KuratowskiWrapper > &output, int before, const node z, const node px, const node py, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
Extracts minorsubtype E4 and adds it to list output.
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::ExtractKuratowskis::extractMinorD
void extractMinorD(SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
Extracts minortype D and adds it to list output.
ogdf::ExtractKuratowskis::m_nodeFromDFI
const Array< node > & m_nodeFromDFI
Returns appropriate node from given DFI.
Definition: ExtractKuratowskis.h:181
ogdf::ExtractKuratowskis::isMinorE1
bool isMinorE1(int before, bool firstXPath, bool firstYPath) const
Checks for minortype E1.
Definition: ExtractKuratowskis.h:302
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:949
ogdf::ExtractKuratowskis::m_embeddingGrade
int m_embeddingGrade
Some parameters, see BoyerMyrvold for further instructions.
Definition: ExtractKuratowskis.h:166
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::ExtractKuratowskis::operator=
ExtractKuratowskis & operator=(const ExtractKuratowskis &)
Assignment operator is undefined!
ogdf::KuratowskiWrapper::V
node V
The node which was embedded while the Kuratowski Subdivision was found.
Definition: ExtractKuratowskis.h:74
ogdf::ExtractKuratowskis::extractMinorEBundles
void extractMinorEBundles(SList< KuratowskiWrapper > &output, bool firstXPath, bool firstPath, bool firstWPath, bool firstWOnHighestXY, NodeArray< int > &nodeflags, const int nodemarker, const KuratowskiStructure &k, EdgeArray< int > &flags, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
Extracts minortype E and adds it to list output (bundles)
ogdf::ExtractKuratowskis::isMinorE4
bool isMinorE4(const node px, const node py, const KuratowskiStructure &k, const WInfo &info) const
Checks for minortype E4.
Definition: ExtractKuratowskis.h:396
ogdf::KuratowskiWrapper::KuratowskiWrapper
KuratowskiWrapper()
Constructor.
Definition: ExtractKuratowskis.h:44
ogdf::ExtractKuratowskis::KuratowskiType::K33
@ K33
a K3,3 subdivision exists
ogdf::ExtractKuratowskis::addDFSPathReverse
void addDFSPathReverse(SListPure< edge > &list, node bottom, node top)
Adds DFS-path from node top to node bottom to list.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::BoyerMyrvoldPlanar
This class implements the extended BoyerMyrvold planarity embedding algorithm.
Definition: BoyerMyrvoldPlanar.h:60
ogdf::ExtractKuratowskis::BMP
BoyerMyrvoldPlanar & BMP
Link to class BoyerMyrvoldPlanar.
Definition: ExtractKuratowskis.h:160
ogdf::KuratowskiStructure::RReal
node RReal
Real node of virtual node R.
Definition: FindKuratowskis.h:125
ogdf::ExtractKuratowskis::extractMinorE1
void extractMinorE1(SList< KuratowskiWrapper > &output, int before, const node px, const node py, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
Extracts minorsubtype E1 and adds it to list output.
ogdf::ExtractKuratowskis::m_g
const Graph & m_g
Input graph.
Definition: ExtractKuratowskis.h:163
ogdf::ExtractKuratowskis::m_nodeMarker
int m_nodeMarker
Value used as marker for visited nodes etc.
Definition: ExtractKuratowskis.h:173
ogdf::ExtractKuratowskis::isMinorE5
bool isMinorE5(const node px, const node py, const KuratowskiStructure &k, const node endnodeX, const node endnodeY, const node endnodeZ) const
Checks for minortype E5 (K5)
Definition: ExtractKuratowskis.h:422
ogdf::KuratowskiStructure::V
node V
The current node to embed.
Definition: FindKuratowskis.h:116
ogdf::ExtractKuratowskis::addDFSPath
void addDFSPath(SListPure< edge > &list, node bottom, node top)
Adds DFS-path from node bottom to node top to list.
ogdf::SListPure::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:451
ogdf::ExtractKuratowskis::m_dfi
const NodeArray< int > & m_dfi
The one and only DFI-NodeArray.
Definition: ExtractKuratowskis.h:178
ogdf::ExtractKuratowskis::~ExtractKuratowskis
~ExtractKuratowskis()
Destructor.
Definition: ExtractKuratowskis.h:93
ogdf::ExtractKuratowskis::KuratowskiType::none
@ none
no kuratowski subdivision exists
ogdf::ExtractKuratowskis::truncateEdgelist
void truncateEdgelist(SListPure< edge > &list1, const SListPure< edge > &list2)
Separates list1 from edges already contained in list2.
ogdf::ExtractKuratowskis::adjToLowestNodeBelow
adjEntry adjToLowestNodeBelow(node high, int low)
Returns adjEntry of the edge between node high and a special node.
ogdf::ExtractKuratowskis::addExternalFacePath
void addExternalFacePath(SListPure< edge > &list, const SListPure< adjEntry > &externPath)
Adds external face edges to list.
Definition: ExtractKuratowskis.h:187
ogdf::ExtractKuratowskis
Extracts multiple Kuratowski Subdivisions.
Definition: ExtractKuratowskis.h:88
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::WInfo
Saves information about a pertinent node w between two stopping vertices.
Definition: FindKuratowskis.h:56
ogdf::KuratowskiWrapper::subdivisionType
SubdivisionType subdivisionType
Minortype of the Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:71
ogdf::ExtractKuratowskis::whichKuratowski
static KuratowskiType whichKuratowski(const Graph &m_g, const NodeArray< int > &dfi, const SListPure< edge > &list)
Checks, if list forms a valid Kuratowski Subdivision and returns the type.