Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
BoyerMyrvold.h
Go to the documentation of this file.
1
33#pragma once
34
40
41namespace ogdf {
42
43class KuratowskiWrapper;
44
46
139protected:
142
144 void clear() {
145 delete pBMP;
146 pBMP = nullptr;
147 }
148
151
152public:
155 pBMP = nullptr;
156 nOfStructures = 0;
157 }
158
160 ~BoyerMyrvold() { clear(); }
161
163 int numberOfStructures() { return nOfStructures; }
164
166
169 virtual bool isPlanarDestructive(Graph& g) override;
170
172
174 virtual bool isPlanar(const Graph& g) override;
175
177 virtual bool planarEmbed(Graph& G) override {
179 return planarEmbed(G, list);
180 }
181
183
191 virtual bool planarEmbedPlanarGraph(Graph& G) override {
193 return planarEmbedDestructive(G, list);
194 }
195
199
201
206 const bool onlyDifferent = false);
207
209
214 const bool onlyDifferent = false) {
215 transform(sourceList, targetList, h.original(), onlyDifferent);
216 }
217
219
230 bool bundles = false, bool limitStructures = false, bool randomDFSTree = false,
231 bool avoidE2Minors = true);
232
236 BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind,
237 bool bundles = false, bool limitStructures = false, bool randomDFSTree = false,
238 bool avoidE2Minors = true) {
239 return planarEmbedDestructive(g, output, static_cast<int>(embeddingGrade), bundles,
241 }
242
244
256 bool bundles = false, bool limitStructures = false, bool randomDFSTree = false,
257 bool avoidE2Minors = true);
258
262 BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind,
263 bool bundles = false, bool limitStructures = false, bool randomDFSTree = false,
264 bool avoidE2Minors = true) {
265 return planarEmbed(g, output, static_cast<int>(embeddingGrade), bundles, limitStructures,
267 }
268
270
281 bool bundles = false, bool limitStructures = false, bool randomDFSTree = false,
282 bool avoidE2Minors = true);
283
287 BoyerMyrvoldPlanar::EmbeddingGrade::doNotFind,
288 bool bundles = false, bool limitStructures = false, bool randomDFSTree = false,
289 bool avoidE2Minors = true) {
290 return planarEmbed(h, output, static_cast<int>(embeddingGrade), bundles, limitStructures,
292 }
293};
294
295}
Declaration of the class BoyerMyrvoldPlanar.
Declaration of the class ExtractKuratowskis.
Declaration of graph copy classes.
Declaration of KuratowskiSubdivion class.
Declaration of PlanarityModule.
Wrapper class used for preprocessing and valid invocation of the planarity test.
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.
BoyerMyrvold()
Constructor.
bool planarEmbed(GraphCopySimple &h, SList< KuratowskiWrapper > &output, int embeddingGrade, 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.
void transform(const KuratowskiWrapper &source, KuratowskiSubdivision &target, NodeArray< int > &count, EdgeArray< int > &countEdge)
Transforms KuratowskiWrapper in KuratowskiSubdivision.
bool planarEmbedDestructive(Graph &g, SList< KuratowskiWrapper > &output, int embeddingGrade, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.
void clear()
Deletes BoyerMyrvoldPlanar on heap.
virtual bool isPlanarDestructive(Graph &g) override
Returns true, iff g is planar.
~BoyerMyrvold()
Destructor.
int nOfStructures
The number of extracted Structures for statistical purposes.
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.
BoyerMyrvoldPlanar * pBMP
Class BoyerMyrvoldPlanar on heap.
virtual bool planarEmbed(Graph &G) override
Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
bool planarEmbed(Graph &g, SList< KuratowskiWrapper > &output, int embeddingGrade, bool bundles=false, bool limitStructures=false, bool randomDFSTree=false, bool avoidE2Minors=true)
Returns an embedding, if g is planar and Kuratowski Subdivisions otherwise.
int numberOfStructures()
The number of extracted Structures for statistical purposes.
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.
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.
virtual bool isPlanar(const Graph &g) override
Returns true, iff a copy of the constant graph g is planar.
void transform(const SList< KuratowskiWrapper > &sourceList, SList< KuratowskiSubdivision > &targetList, const Graph &g, const bool onlyDifferent=false)
Transforms KuratowskiWrapper-List in KuratowskiSubdivision-List with respect to sieving constraints.
virtual bool planarEmbedPlanarGraph(Graph &G) override
Constructs a planar embedding of G. G has to be planar!
This class implements the extended BoyerMyrvold planarity embedding algorithm.
EmbeddingGrade
Denotes the different embedding options.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Copies of graphs with mapping between nodes and edges.
Definition GraphCopy.h:59
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Wrapper-class for Kuratowski Subdivisions containing the minortype and edgelist.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Module for planarity testing and planar embeddings.
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
bool planarEmbed(Graph &G)
Returns true, if G is planar, false otherwise. If true is returned, G will be planarly embedded.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.