Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

BoyerMyrvold.h
Go to the documentation of this file.
1 
33 #pragma once
34 
38 #include <ogdf/basic/GraphCopy.h>
40 
41 namespace ogdf {
42 
43 class KuratowskiWrapper;
44 
46 
139 {
140 protected:
143 
145  void clear() {
146  delete pBMP;
147  pBMP = nullptr;
148  }
149 
152 
153 public:
155  BoyerMyrvold() { pBMP = nullptr; nOfStructures = 0; }
157  ~BoyerMyrvold() { clear(); }
158 
160  int numberOfStructures() { return nOfStructures; }
161 
163 
166  virtual bool isPlanarDestructive(Graph& g) override;
167 
169 
171  virtual bool isPlanar(const Graph& g) override;
172 
174  virtual bool planarEmbed(Graph &G) override {
176  return planarEmbed(G,list);
177  }
178 
180 
188  virtual bool planarEmbedPlanarGraph(Graph &G) override {
190  return planarEmbedDestructive(G,list);
191  }
192 
193 
195  void transform(
196  const KuratowskiWrapper& source,
197  KuratowskiSubdivision& target,
198  NodeArray<int>& count,
199  EdgeArray<int>& countEdge);
200 
202 
205  void transform(
206  const SList<KuratowskiWrapper>& sourceList,
207  SList<KuratowskiSubdivision>& targetList,
208  const Graph& g,
209  const bool onlyDifferent = false);
210 
211 
213 
216  void transform(
217  const SList<KuratowskiWrapper>& sourceList,
218  SList<KuratowskiSubdivision>& targetList,
219  const GraphCopySimple& h,
220  const bool onlyDifferent = false)
221  {
222  transform(sourceList, targetList, h.original(), onlyDifferent);
223  }
224 
225 
227 
237  bool planarEmbedDestructive(
238  Graph& g,
239  SList<KuratowskiWrapper>& output,
240  int embeddingGrade,
241  bool bundles = false,
242  bool limitStructures = false,
243  bool randomDFSTree = false,
244  bool avoidE2Minors = true);
245 
248  Graph& g,
249  SList<KuratowskiWrapper>& output,
251  bool bundles = false,
252  bool limitStructures = false,
253  bool randomDFSTree = false,
254  bool avoidE2Minors = true)
255  {
256  return planarEmbedDestructive(g, output, static_cast<int>(embeddingGrade), bundles, limitStructures, randomDFSTree, avoidE2Minors);
257  }
258 
260 
271  bool planarEmbed(
272  Graph& g,
273  SList<KuratowskiWrapper>& output,
274  int embeddingGrade,
275  bool bundles = false,
276  bool limitStructures = false,
277  bool randomDFSTree = false,
278  bool avoidE2Minors = true);
279 
282  Graph& g,
283  SList<KuratowskiWrapper>& output,
285  bool bundles = false,
286  bool limitStructures = false,
287  bool randomDFSTree = false,
288  bool avoidE2Minors = true)
289  {
290  return planarEmbed(g, output, static_cast<int>(embeddingGrade), bundles, limitStructures, randomDFSTree, avoidE2Minors);
291  }
292 
294 
304  bool planarEmbed(
305  GraphCopySimple& h,
306  SList<KuratowskiWrapper>& output,
307  int embeddingGrade,
308  bool bundles = false,
309  bool limitStructures = false,
310  bool randomDFSTree = false,
311  bool avoidE2Minors = true);
312 
315  GraphCopySimple& h,
316  SList<KuratowskiWrapper>& output,
318  bool bundles = false,
319  bool limitStructures = false,
320  bool randomDFSTree = false,
321  bool avoidE2Minors = true)
322  {
323  return planarEmbed(h, output, static_cast<int>(embeddingGrade), bundles, limitStructures, randomDFSTree, avoidE2Minors);
324  }
325 };
326 
327 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::BoyerMyrvold::planarEmbed
virtual bool planarEmbed(Graph &G) override
Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
Definition: BoyerMyrvold.h:174
BoyerMyrvoldPlanar.h
Declaration of the class BoyerMyrvoldPlanar.
ogdf::KuratowskiWrapper
Wrapper-class for Kuratowski Subdivisions containing the minortype and edgelist.
Definition: ExtractKuratowskis.h:41
ogdf::BoyerMyrvold::planarEmbedPlanarGraph
virtual bool planarEmbedPlanarGraph(Graph &G) override
Constructs a planar embedding of G. G has to be planar!
Definition: BoyerMyrvold.h:188
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::GraphCopySimple::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:87
ogdf::BoyerMyrvold::pBMP
BoyerMyrvoldPlanar * pBMP
Class BoyerMyrvoldPlanar on heap.
Definition: BoyerMyrvold.h:142
ogdf::isPlanar
bool isPlanar(const Graph &G)
Returns true, if G is planar, false otherwise.
Definition: extended_graph_alg.h:441
ogdf::BoyerMyrvold::BoyerMyrvold
BoyerMyrvold()
Constructor.
Definition: BoyerMyrvold.h:155
ogdf::GraphCopySimple
Copies of graphs with mapping between nodes and edges.
Definition: GraphCopy.h:60
ogdf::NodeArray< int >
ogdf::EdgeArray< int >
ExtractKuratowskis.h
Declaration of the class ExtractKuratowskis.
ogdf::KuratowskiSubdivision
Definition: KuratowskiSubdivision.h:40
ogdf::BoyerMyrvold::clear
void clear()
Deletes BoyerMyrvoldPlanar on heap.
Definition: BoyerMyrvold.h:145
PlanarityModule.h
Declaration of PlanarityModule.
ogdf::BoyerMyrvoldPlanar::EmbeddingGrade
EmbeddingGrade
Denotes the different embedding options.
Definition: BoyerMyrvoldPlanar.h:75
ogdf::BoyerMyrvold::numberOfStructures
int numberOfStructures()
The number of extracted Structures for statistical purposes.
Definition: BoyerMyrvold.h:160
ogdf::planarEmbed
bool planarEmbed(Graph &G)
Returns true, if G is planar, false otherwise. If true is returned, G will be planarly embedded.
Definition: extended_graph_alg.h:481
ogdf::BoyerMyrvold::~BoyerMyrvold
~BoyerMyrvold()
Destructor.
Definition: BoyerMyrvold.h:157
GraphCopy.h
Declaration of graph copy classes.
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::BoyerMyrvold
Wrapper class used for preprocessing and valid invocation of the planarity test.
Definition: BoyerMyrvold.h:138
ogdf::BoyerMyrvold::transform
void transform(const SList< KuratowskiWrapper > &sourceList, SList< KuratowskiSubdivision > &targetList, const GraphCopySimple &h, const bool onlyDifferent=false)
Transforms KuratowskiWrapper-List in KuratowskiSubdivision-List with respect to sieving constraints.
Definition: BoyerMyrvold.h:216
KuratowskiSubdivision.h
Declaration of KuratowskiSubdivion class.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind
@ doNotFind
ogdf::BoyerMyrvoldPlanar
This class implements the extended BoyerMyrvold planarity embedding algorithm.
Definition: BoyerMyrvoldPlanar.h:60
ogdf::PlanarityModule
Module for planarity testing and planar embeddings.
Definition: PlanarityModule.h:48
ogdf::BoyerMyrvold::planarEmbedDestructive
bool planarEmbedDestructive(Graph &g, SList< KuratowskiWrapper > &output, BoyerMyrvoldPlanar::EmbeddingGrade embeddingGrade=BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.
Definition: BoyerMyrvold.h:247
ogdf::BoyerMyrvold::planarEmbed
bool planarEmbed(GraphCopySimple &h, SList< KuratowskiWrapper > &output, BoyerMyrvoldPlanar::EmbeddingGrade embeddingGrade=BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
Returns an embedding, if graph copy h is planar and Kuratowski Subdivisions otherwise.
Definition: BoyerMyrvold.h:314
ogdf::BoyerMyrvold::planarEmbed
bool planarEmbed(Graph &g, SList< KuratowskiWrapper > &output, BoyerMyrvoldPlanar::EmbeddingGrade embeddingGrade=BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.
Definition: BoyerMyrvold.h:281
ogdf::BoyerMyrvold::nOfStructures
int nOfStructures
The number of extracted Structures for statistical purposes.
Definition: BoyerMyrvold.h:151