Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
PlanarSubgraphBoyerMyrvold.h
Go to the documentation of this file.
1
33#pragma once
34
39
40#include <random>
41
42namespace ogdf {
43
45
52private:
53 int m_runs;
56 std::minstd_rand m_rand;
57
58public:
68 explicit PlanarSubgraphBoyerMyrvold(int runs = 1, double randomness = 0)
69 : m_runs(runs), m_randomness(randomness), m_rand(rand()) {};
70
72
73 virtual PlanarSubgraphBoyerMyrvold* clone() const override {
74 return new PlanarSubgraphBoyerMyrvold(m_runs);
75 };
76
80 void seed(std::minstd_rand rand) { m_rand = rand; }
81
82protected:
92 virtual ReturnType doCall(const Graph& graph, const List<edge>& preferedEdges,
93 List<edge>& delEdges, const EdgeArray<int>* pCost, bool preferedImplyPlanar) override;
94
98 bool isRemoved(const GraphCopy& copy, const edge e) {
99 return copy.copy(e) == nullptr || copy.copy(e)->source() != copy.copy(e->source())
100 || copy.copy(e)->target() != copy.copy(e->target());
101 }
102};
103
104}
Declaration of BoothLueker which implements a planarity test and planar embedding algorithm.
Declaration of the wrapper class of the Boyer-Myrvold planarity test.
Declaration of the class BoyerMyrvoldPlanar.
Declaration of interface for planar subgraph algorithms.
Booth-Lueker planarity test.
Definition BoothLueker.h:51
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
node target() const
Returns the target node of the edge.
Definition Graph_d.h:338
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition GraphCopy.h:338
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
ReturnType
The return type of a module.
Definition Module.h:50
Maximum planar subgraph heuristic based on the Boyer-Myrvold planarity test.
virtual ReturnType doCall(const Graph &graph, const List< edge > &preferedEdges, List< edge > &delEdges, const EdgeArray< int > *pCost, bool preferedImplyPlanar) override
Constructs a planar subgraph according to the options supplied to the constructor.
bool isRemoved(const GraphCopy &copy, const edge e)
Returns true iff this edge could not be embedded.
void seed(std::minstd_rand rand)
Seeds the random generator for performing a random DFS. If this method is never called the random gen...
virtual PlanarSubgraphBoyerMyrvold * clone() const override
Returns a new instance of the planar subgraph module with the same option settings.
PlanarSubgraphBoyerMyrvold(int runs=1, double randomness=0)
Creates a new Boyer-Myrvold subgraph module.
Interface for planar subgraph algorithms.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.