Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

ExtractKuratowskis.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/basic/Array.h>
36 #include <ogdf/basic/Graph.h>
37 #include <ogdf/basic/SList.h>
38 #include <ogdf/basic/basic.h>
39 #include <ogdf/planarity/boyer_myrvold/FindKuratowskis.h>
40 
41 #include <iosfwd>
42 
43 namespace ogdf {
44 class BoyerMyrvoldPlanar;
45 
47 class OGDF_EXPORT KuratowskiWrapper {
48 public:
50  KuratowskiWrapper() { }
51 
53  inline bool isK33() const { return subdivisionType != SubdivisionType::E5; }
54 
56  inline bool isK5() const { return subdivisionType == SubdivisionType::E5; }
57 
59  enum class SubdivisionType {
60  A = 0,
61  AB = 1,
62  AC = 2,
63  AD = 3,
64  AE1 = 4,
65  AE2 = 5,
66  AE3 = 6,
67  AE4 = 7,
68  B = 8,
69  C = 9,
70  D = 10,
71  E1 = 11,
72  E2 = 12,
73  E3 = 13,
74  E4 = 14,
75  E5 = 15
76  };
78  SubdivisionType subdivisionType;
79 
81  node V;
82 
84  SListPure<edge> edgeList;
85 };
86 
87 OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const KuratowskiWrapper::SubdivisionType& obj);
88 
90 
95 class ExtractKuratowskis {
96 public:
98  explicit ExtractKuratowskis(BoyerMyrvoldPlanar& bm);
99 
101  ~ExtractKuratowskis() { }
102 
104  void extract(const SListPure<KuratowskiStructure>& allKuratowskis,
105  SList<KuratowskiWrapper>& output);
106 
108  void extractBundles(const SListPure<KuratowskiStructure>& allKuratowskis,
109  SList<KuratowskiWrapper>& output);
110 
112  enum class KuratowskiType {
113  none = 0,
114  K33 = 1,
115  K5 = 2
116  };
117 
119 
125  static KuratowskiType whichKuratowski(const Graph& m_g, const NodeArray<int>& dfi,
126  const SListPure<edge>& list);
127 
129 
136  static KuratowskiType whichKuratowskiArray(const Graph& g,
137 #if 0
138  const NodeArray<int>& m_dfi,
139 #endif
140  EdgeArray<int>& edgenumber);
141 
143  static bool isANewKuratowski(const Graph& g, const SListPure<edge>& kuratowski,
144  const SList<KuratowskiWrapper>& output);
146 
148  static bool isANewKuratowski(
149 #if 0
150  const Graph& g,
151 #endif
152  const EdgeArray<int>& test, const SList<KuratowskiWrapper>& output);
153 
154  // avoid automatic creation of assignment operator
156  ExtractKuratowskis& operator=(const ExtractKuratowskis&);
157 
158 protected:
160  BoyerMyrvoldPlanar& BMP;
161 
163  const Graph& m_g;
164 
166  int m_embeddingGrade;
168  const bool m_avoidE2Minors;
169 
171 
173  int m_nodeMarker;
175  NodeArray<int> m_wasHere;
176 
178  const NodeArray<int>& m_dfi;
179 
181  const Array<node>& m_nodeFromDFI;
182 
184  const NodeArray<adjEntry>& m_adjParent;
185 
187  inline void addExternalFacePath(SListPure<edge>& list, const SListPure<adjEntry>& externPath) {
188  SListConstIterator<adjEntry> itExtern;
189  for (itExtern = externPath.begin(); itExtern.valid(); ++itExtern) {
190  list.pushBack((*itExtern)->theEdge());
191  }
192  }
193 
195 
197  inline adjEntry adjToLowestNodeBelow(node high, int low);
198 
200 
202  inline void addDFSPath(SListPure<edge>& list, node bottom, node top);
204 
206  inline void addDFSPathReverse(SListPure<edge>& list, node bottom, node top);
207 
209  inline void truncateEdgelist(SListPure<edge>& list1, const SListPure<edge>& list2);
210 
212  void extractMinorA(SList<KuratowskiWrapper>& output, const KuratowskiStructure& k,
213 #if 0
214  const WInfo& info,
215 #endif
216  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
217  const node endnodeY, const SListPure<edge>& pathW);
219  void extractMinorB(SList<KuratowskiWrapper>& output,
220  //NodeArray<int>& nodeflags,
221  //const int nodemarker,
222  const KuratowskiStructure& k, const WInfo& info, const SListPure<edge>& pathX,
223  const node endnodeX, const SListPure<edge>& pathY, const node endnodeY,
224  const SListPure<edge>& pathW);
226  void extractMinorBBundles(SList<KuratowskiWrapper>& output, NodeArray<int>& nodeflags,
227  const int nodemarker, const KuratowskiStructure& k, EdgeArray<int>& flags,
228  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
229  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
231  void extractMinorC(SList<KuratowskiWrapper>& output, const KuratowskiStructure& k,
232  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
233  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
235  void extractMinorD(SList<KuratowskiWrapper>& output, const KuratowskiStructure& k,
236  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
237  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
239  void extractMinorE(SList<KuratowskiWrapper>& output, bool firstXPath, bool firstPath,
240  bool firstWPath, bool firstWOnHighestXY, const KuratowskiStructure& k,
241  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
242  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
244  void extractMinorEBundles(SList<KuratowskiWrapper>& output, bool firstXPath, bool firstPath,
245  bool firstWPath, bool firstWOnHighestXY, NodeArray<int>& nodeflags,
246  const int nodemarker, const KuratowskiStructure& k, EdgeArray<int>& flags,
247  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
248  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
249 
251  inline bool isMinorE1(int before, bool firstXPath, bool firstYPath) const {
252  return (before == -1 && firstXPath) || (before == 1 && firstYPath);
253  }
254 
256  void extractMinorE1(SList<KuratowskiWrapper>& output, int before,
257 #if 0
258  const node z,
259 #endif
260  const node px, const node py, const KuratowskiStructure& k, const WInfo& info,
261  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
262  const node endnodeY, const SListPure<edge>& pathW, const SListPure<edge>& pathZ,
263  const node endnodeZ);
265  inline bool checkMinorE2(bool firstWPath, bool firstWOnHighestXY) const {
266  return !m_avoidE2Minors && firstWPath && firstWOnHighestXY;
267  }
268 
270  inline bool isMinorE2(const node endnodeX, const node endnodeY, const node endnodeZ) const {
271  return m_dfi[endnodeZ] > m_dfi[endnodeX] && m_dfi[endnodeZ] > m_dfi[endnodeY];
272  }
273 
275  void extractMinorE2(SList<KuratowskiWrapper>& output,
276 #if 0
277  int before,
278  const node z,
279  const node px,
280  const node py,
281 #endif
282  const KuratowskiStructure& k, const WInfo& info, const SListPure<edge>& pathX,
283  const node endnodeX, const SListPure<edge>& pathY, const node endnodeY,
284 #if 0
285  const SListPure<edge>& pathW,
286 #endif
287  const SListPure<edge>& pathZ
288 #if 0
289  , const node endnodeZ
290 #endif
291  );
293  inline bool isMinorE3(const node endnodeX, const node endnodeY, const node endnodeZ) const {
294  return endnodeX != endnodeY
295  && (m_dfi[endnodeX] > m_dfi[endnodeZ] || m_dfi[endnodeY] > m_dfi[endnodeZ]);
296  }
297 
299  void extractMinorE3(SList<KuratowskiWrapper>& output, int before, const node z, const node px,
300  const node py, const KuratowskiStructure& k, const WInfo& info,
301  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
302  const node endnodeY, const SListPure<edge>& pathW, const SListPure<edge>& pathZ,
303  const node endnodeZ);
304 
306  inline bool isMinorE4(const node px, const node py, const KuratowskiStructure& k,
307  const WInfo& info) const {
308  return (px != k.stopX && !info.pxAboveStopX) || (py != k.stopY && !info.pyAboveStopY);
309  }
310 
312  void extractMinorE4(SList<KuratowskiWrapper>& output, int before, const node z, const node px,
313  const node py, const KuratowskiStructure& k, const WInfo& info,
314  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
315  const node endnodeY, const SListPure<edge>& pathW, const SListPure<edge>& pathZ,
316  const node endnodeZ);
317 
319  inline bool isMinorE5(const node px, const node py, const KuratowskiStructure& k,
320  const node endnodeX, const node endnodeY, const node endnodeZ) const {
321  return px == k.stopX && py == k.stopY && k.V == k.RReal
322  && ((endnodeX == endnodeY && m_dfi[endnodeZ] <= m_dfi[endnodeX])
323  || (endnodeX == endnodeZ && m_dfi[endnodeY] <= m_dfi[endnodeX])
324  || (endnodeY == endnodeZ && m_dfi[endnodeX] <= m_dfi[endnodeY]));
325  }
326 
328  void extractMinorE5(SList<KuratowskiWrapper>& output,
329 #if 0
330  int before,
331  const node z,
332  const node px,
333  const node py,
334 #endif
335  const KuratowskiStructure& k, const WInfo& info, const SListPure<edge>& pathX,
336  const node endnodeX, const SListPure<edge>& pathY, const node endnodeY,
337  const SListPure<edge>& pathW, const SListPure<edge>& pathZ, const node endnodeZ);
338 };
339 
340 }
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::KuratowskiStructure
A Kuratowski Structure is a special graph structure containing severals subdivisions.
Definition: FindKuratowskis.h:96
ogdf::ExtractKuratowskis::checkMinorE2
bool checkMinorE2(bool firstWPath, bool firstWOnHighestXY) const
Checks for minortype E2 preconditions.
Definition: ExtractKuratowskis.h:265
Graph.h
Includes declaration of graph class.
ogdf::ExtractKuratowskis::isMinorE3
bool isMinorE3(const node endnodeX, const node endnodeY, const node endnodeZ) const
Checks for minortype E3.
Definition: ExtractKuratowskis.h:293
ogdf::KuratowskiStructure::stopY
node stopY
Second stopping node.
Definition: FindKuratowskis.h:133
ogdf::KuratowskiStructure::stopX
node stopX
First stopping node.
Definition: FindKuratowskis.h:131
ogdf::KuratowskiWrapper
Wrapper-class for Kuratowski Subdivisions containing the minortype and edgelist.
Definition: ExtractKuratowskis.h:47
ogdf::whaType::A
@ A
ogdf::SListIteratorBase
Encapsulates a pointer to an ogdf::SList element.
Definition: SList.h:50
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:53
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:845
ogdf::WInfo::pxAboveStopX
bool pxAboveStopX
Definition: FindKuratowskis.h:78
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:134
ogdf::WInfo::pyAboveStopY
bool pyAboveStopY
Definition: FindKuratowskis.h:79
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::ExtractKuratowskis::KuratowskiType
KuratowskiType
Enumeration over Kuratowski Type none, K33, K5.
Definition: ExtractKuratowskis.h:112
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:344
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:142
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:270
ogdf::KuratowskiWrapper::isK5
bool isK5() const
Returns true, iff subdivision is a K5-minor.
Definition: ExtractKuratowskis.h:56
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.
SList.h
Declaration of singly linked lists and iterators.
ogdf::Array< node >
ogdf::KuratowskiWrapper::SubdivisionType
SubdivisionType
Possible minortypes of a Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:59
ogdf::KuratowskiWrapper::edgeList
SListPure< edge > edgeList
Contains the edges of the Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:84
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:52
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:251
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:983
ogdf::internal::GraphRegisteredArray
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition: Graph_d.h:658
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:869
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:81
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:306
ogdf::KuratowskiWrapper::KuratowskiWrapper
KuratowskiWrapper()
Constructor.
Definition: ExtractKuratowskis.h:50
ogdf::ExtractKuratowskis::KuratowskiType::K33
@ K33
a K3,3 subdivision exists
basic.h
Basic declarations, included by all source files.
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:101
Array.h
Declaration and implementation of Array class and Array algorithms.
ogdf::BoyerMyrvoldPlanar
This class implements the extended BoyerMyrvold planarity embedding algorithm.
Definition: BoyerMyrvoldPlanar.h:66
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:129
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:319
ogdf::KuratowskiStructure::V
node V
The current node to embed.
Definition: FindKuratowskis.h:120
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:481
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:101
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:95
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:240
ogdf::WInfo
Saves information about a pertinent node w between two stopping vertices.
Definition: FindKuratowskis.h:62
ogdf::KuratowskiWrapper::subdivisionType
SubdivisionType subdivisionType
Minortype of the Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:78
ogdf::internal::EdgeArrayBase2
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition: Graph_d.h:716
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.