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/planarity/boyer_myrvold/BoyerMyrvoldPlanar.h>
36 #include <ogdf/planarity/boyer_myrvold/FindKuratowskis.h>
37 
38 namespace ogdf {
39 
41 class OGDF_EXPORT KuratowskiWrapper {
42 public:
44  KuratowskiWrapper() { }
45 
47  inline bool isK33() const { return subdivisionType != SubdivisionType::E5; }
48 
50  inline bool isK5() const { return subdivisionType == SubdivisionType::E5; }
51 
53  enum class SubdivisionType {
54  A = 0,
55  AB = 1,
56  AC = 2,
57  AD = 3,
58  AE1 = 4,
59  AE2 = 5,
60  AE3 = 6,
61  AE4 = 7,
62  B = 8,
63  C = 9,
64  D = 10,
65  E1 = 11,
66  E2 = 12,
67  E3 = 13,
68  E4 = 14,
69  E5 = 15
70  };
72  SubdivisionType subdivisionType;
73 
75  node V;
76 
78  SListPure<edge> edgeList;
79 };
80 
81 OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const KuratowskiWrapper::SubdivisionType& obj);
82 
84 
89 class ExtractKuratowskis {
90 public:
92  explicit ExtractKuratowskis(BoyerMyrvoldPlanar& bm);
93 
95  ~ExtractKuratowskis() { }
96 
98  void extract(const SListPure<KuratowskiStructure>& allKuratowskis,
99  SList<KuratowskiWrapper>& output);
100 
102  void extractBundles(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 
119  static KuratowskiType whichKuratowski(const Graph& m_g, const NodeArray<int>& dfi,
120  const SListPure<edge>& list);
121 
123 
130  static KuratowskiType whichKuratowskiArray(const Graph& g,
131 #if 0
132  const NodeArray<int>& m_dfi,
133 #endif
134  EdgeArray<int>& edgenumber);
135 
137  static bool isANewKuratowski(const Graph& g, const SListPure<edge>& kuratowski,
138  const SList<KuratowskiWrapper>& output);
140 
142  static bool isANewKuratowski(
143 #if 0
144  const Graph& g,
145 #endif
146  const EdgeArray<int>& test, const SList<KuratowskiWrapper>& output);
147 
148  // avoid automatic creation of assignment operator
150  ExtractKuratowskis& operator=(const ExtractKuratowskis&);
151 
152 protected:
154  BoyerMyrvoldPlanar& BMP;
155 
157  const Graph& m_g;
158 
160  int m_embeddingGrade;
162  const bool m_avoidE2Minors;
163 
165 
167  int m_nodeMarker;
169  NodeArray<int> m_wasHere;
170 
172  const NodeArray<int>& m_dfi;
173 
175  const Array<node>& m_nodeFromDFI;
176 
178  const NodeArray<adjEntry>& m_adjParent;
179 
181  inline void addExternalFacePath(SListPure<edge>& list, const SListPure<adjEntry>& externPath) {
182  SListConstIterator<adjEntry> itExtern;
183  for (itExtern = externPath.begin(); itExtern.valid(); ++itExtern) {
184  list.pushBack((*itExtern)->theEdge());
185  }
186  }
187 
189 
191  inline adjEntry adjToLowestNodeBelow(node high, int low);
192 
194 
196  inline void addDFSPath(SListPure<edge>& list, node bottom, node top);
198 
200  inline void addDFSPathReverse(SListPure<edge>& list, node bottom, node top);
201 
203  inline void truncateEdgelist(SListPure<edge>& list1, const SListPure<edge>& list2);
204 
206  void extractMinorA(SList<KuratowskiWrapper>& output, const KuratowskiStructure& k,
207 #if 0
208  const WInfo& info,
209 #endif
210  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
211  const node endnodeY, const SListPure<edge>& pathW);
213  void extractMinorB(SList<KuratowskiWrapper>& output,
214  //NodeArray<int>& nodeflags,
215  //const int nodemarker,
216  const KuratowskiStructure& k, const WInfo& info, const SListPure<edge>& pathX,
217  const node endnodeX, const SListPure<edge>& pathY, const node endnodeY,
218  const SListPure<edge>& pathW);
220  void extractMinorBBundles(SList<KuratowskiWrapper>& output, NodeArray<int>& nodeflags,
221  const int nodemarker, const KuratowskiStructure& k, EdgeArray<int>& flags,
222  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
223  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
225  void extractMinorC(SList<KuratowskiWrapper>& output, const KuratowskiStructure& k,
226  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
227  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
229  void extractMinorD(SList<KuratowskiWrapper>& output, const KuratowskiStructure& k,
230  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
231  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
233  void extractMinorE(SList<KuratowskiWrapper>& output, bool firstXPath, bool firstPath,
234  bool firstWPath, bool firstWOnHighestXY, const KuratowskiStructure& k,
235  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
236  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
238  void extractMinorEBundles(SList<KuratowskiWrapper>& output, bool firstXPath, bool firstPath,
239  bool firstWPath, bool firstWOnHighestXY, NodeArray<int>& nodeflags,
240  const int nodemarker, const KuratowskiStructure& k, EdgeArray<int>& flags,
241  const WInfo& info, const SListPure<edge>& pathX, const node endnodeX,
242  const SListPure<edge>& pathY, const node endnodeY, const SListPure<edge>& pathW);
243 
245  inline bool isMinorE1(int before, bool firstXPath, bool firstYPath) const {
246  return (before == -1 && firstXPath) || (before == 1 && firstYPath);
247  }
248 
250  void extractMinorE1(SList<KuratowskiWrapper>& output, int before,
251 #if 0
252  const node z,
253 #endif
254  const node px, const node py, const KuratowskiStructure& k, const WInfo& info,
255  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
256  const node endnodeY, const SListPure<edge>& pathW, const SListPure<edge>& pathZ,
257  const node endnodeZ);
259  inline bool checkMinorE2(bool firstWPath, bool firstWOnHighestXY) const {
260  return !m_avoidE2Minors && firstWPath && firstWOnHighestXY;
261  }
262 
264  inline bool isMinorE2(const node endnodeX, const node endnodeY, const node endnodeZ) const {
265  return m_dfi[endnodeZ] > m_dfi[endnodeX] && m_dfi[endnodeZ] > m_dfi[endnodeY];
266  }
267 
269  void extractMinorE2(SList<KuratowskiWrapper>& output,
270 #if 0
271  int before,
272  const node z,
273  const node px,
274  const node py,
275 #endif
276  const KuratowskiStructure& k, const WInfo& info, const SListPure<edge>& pathX,
277  const node endnodeX, const SListPure<edge>& pathY, const node endnodeY,
278 #if 0
279  const SListPure<edge>& pathW,
280 #endif
281  const SListPure<edge>& pathZ
282 #if 0
283  , const node endnodeZ
284 #endif
285  );
287  inline bool isMinorE3(const node endnodeX, const node endnodeY, const node endnodeZ) const {
288  return endnodeX != endnodeY
289  && (m_dfi[endnodeX] > m_dfi[endnodeZ] || m_dfi[endnodeY] > m_dfi[endnodeZ]);
290  }
291 
293  void extractMinorE3(SList<KuratowskiWrapper>& output, int before, const node z, const node px,
294  const node py, const KuratowskiStructure& k, const WInfo& info,
295  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
296  const node endnodeY, const SListPure<edge>& pathW, const SListPure<edge>& pathZ,
297  const node endnodeZ);
298 
300  inline bool isMinorE4(const node px, const node py, const KuratowskiStructure& k,
301  const WInfo& info) const {
302  return (px != k.stopX && !info.pxAboveStopX) || (py != k.stopY && !info.pyAboveStopY);
303  }
304 
306  void extractMinorE4(SList<KuratowskiWrapper>& output, int before, const node z, const node px,
307  const node py, const KuratowskiStructure& k, const WInfo& info,
308  const SListPure<edge>& pathX, const node endnodeX, const SListPure<edge>& pathY,
309  const node endnodeY, const SListPure<edge>& pathW, const SListPure<edge>& pathZ,
310  const node endnodeZ);
311 
313  inline bool isMinorE5(const node px, const node py, const KuratowskiStructure& k,
314  const node endnodeX, const node endnodeY, const node endnodeZ) const {
315  return px == k.stopX && py == k.stopY && k.V == k.RReal
316  && ((endnodeX == endnodeY && m_dfi[endnodeZ] <= m_dfi[endnodeX])
317  || (endnodeX == endnodeZ && m_dfi[endnodeY] <= m_dfi[endnodeX])
318  || (endnodeY == endnodeZ && m_dfi[endnodeX] <= m_dfi[endnodeY]));
319  }
320 
322  void extractMinorE5(SList<KuratowskiWrapper>& output,
323 #if 0
324  int before,
325  const node z,
326  const node px,
327  const node py,
328 #endif
329  const KuratowskiStructure& k, const WInfo& info, const SListPure<edge>& pathX,
330  const node endnodeX, const SListPure<edge>& pathY, const node endnodeY,
331  const SListPure<edge>& pathW, const SListPure<edge>& pathZ, const node endnodeZ);
332 };
333 
334 }
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:89
ogdf::ExtractKuratowskis::checkMinorE2
bool checkMinorE2(bool firstWPath, bool firstWOnHighestXY) const
Checks for minortype E2 preconditions.
Definition: ExtractKuratowskis.h:259
ogdf::ExtractKuratowskis::isMinorE3
bool isMinorE3(const node endnodeX, const node endnodeY, const node endnodeZ) const
Checks for minortype E3.
Definition: ExtractKuratowskis.h:287
BoyerMyrvoldPlanar.h
Declaration of the class BoyerMyrvoldPlanar.
ogdf::KuratowskiStructure::stopY
node stopY
Second stopping node.
Definition: FindKuratowskis.h:126
ogdf::KuratowskiStructure::stopX
node stopX
First stopping node.
Definition: FindKuratowskis.h:124
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:41
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:833
ogdf::WInfo::pxAboveStopX
bool pxAboveStopX
Definition: FindKuratowskis.h:71
ogdf::ExtractKuratowskis::m_avoidE2Minors
const bool m_avoidE2Minors
Some parameters, see BoyerMyrvold for further instructions.
Definition: ExtractKuratowskis.h:162
ogdf::Direction::before
@ before
ogdf::SListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: SList.h:122
ogdf::WInfo::pyAboveStopY
bool pyAboveStopY
Definition: FindKuratowskis.h:72
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:106
ogdf::ExtractKuratowskis::m_adjParent
const NodeArray< adjEntry > & m_adjParent
The adjEntry which goes from DFS-parent to current vertex.
Definition: ExtractKuratowskis.h:178
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:169
ogdf::SListPure::begin
iterator begin()
Returns an iterator to the first element of the list.
Definition: SList.h:332
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:135
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:264
ogdf::KuratowskiWrapper::isK5
bool isK5() const
Returns true, iff subdivision is a K5-minor.
Definition: ExtractKuratowskis.h:50
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:53
ogdf::KuratowskiWrapper::edgeList
SListPure< edge > edgeList
Contains the edges of the Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:78
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:39
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:175
ogdf::ExtractKuratowskis::isMinorE1
bool isMinorE1(int before, bool firstXPath, bool firstYPath) const
Checks for minortype E1.
Definition: ExtractKuratowskis.h:245
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:978
ogdf::internal::GraphRegisteredArray
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition: Graph_d.h:651
ogdf::ExtractKuratowskis::m_embeddingGrade
int m_embeddingGrade
Some parameters, see BoyerMyrvold for further instructions.
Definition: ExtractKuratowskis.h:160
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:862
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:75
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:300
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:101
ogdf::BoyerMyrvoldPlanar
This class implements the extended BoyerMyrvold planarity embedding algorithm.
Definition: BoyerMyrvoldPlanar.h:62
ogdf::ExtractKuratowskis::BMP
BoyerMyrvoldPlanar & BMP
Link to class BoyerMyrvoldPlanar.
Definition: ExtractKuratowskis.h:154
ogdf::KuratowskiStructure::RReal
node RReal
Real node of virtual node R.
Definition: FindKuratowskis.h:122
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:157
ogdf::ExtractKuratowskis::m_nodeMarker
int m_nodeMarker
Value used as marker for visited nodes etc.
Definition: ExtractKuratowskis.h:167
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:313
ogdf::KuratowskiStructure::V
node V
The current node to embed.
Definition: FindKuratowskis.h:113
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:469
ogdf::ExtractKuratowskis::m_dfi
const NodeArray< int > & m_dfi
The one and only DFI-NodeArray.
Definition: ExtractKuratowskis.h:172
ogdf::ExtractKuratowskis::~ExtractKuratowskis
~ExtractKuratowskis()
Destructor.
Definition: ExtractKuratowskis.h:95
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:181
ogdf::ExtractKuratowskis
Extracts multiple Kuratowski Subdivisions.
Definition: ExtractKuratowskis.h:89
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:233
ogdf::WInfo
Saves information about a pertinent node w between two stopping vertices.
Definition: FindKuratowskis.h:55
ogdf::KuratowskiWrapper::subdivisionType
SubdivisionType subdivisionType
Minortype of the Kuratowski Subdivision.
Definition: ExtractKuratowskis.h:72
ogdf::internal::EdgeArrayBase2
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition: Graph_d.h:709
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.