Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
PlanarSubgraphModule.h
Go to the documentation of this file.
1
32#pragma once
33
35#include <ogdf/basic/Logger.h>
36#include <ogdf/basic/Module.h>
37#include <ogdf/basic/Thread.h>
39
40namespace ogdf {
41
47template<typename TCost>
48class PlanarSubgraphModule : public Module, public Timeouter {
49 unsigned int m_maxThreads;
50
51public:
54#ifdef OGDF_MEMORY_POOL_NTS
55 m_maxThreads = 1;
56#else
57 m_maxThreads = max(1u, Thread::hardware_concurrency());
58#endif
59 }
60
70 List<edge>& delEdges, bool preferredImplyPlanar = false) {
71 return doCall(G, preferredEdges, delEdges, &cost, preferredImplyPlanar);
72 }
73
82 bool preferredImplyPlanar = false) {
83 return doCall(G, preferredEdges, delEdges, nullptr, preferredImplyPlanar);
84 }
85
92 ReturnType call(const Graph& G, const EdgeArray<TCost>& cost, List<edge>& delEdges) {
94 return doCall(G, preferredEdges, delEdges, &cost);
95 }
96
102 ReturnType call(const Graph& G, List<edge>& delEdges) {
104 return doCall(G, preferredEdges, delEdges);
105 }
106
109 bool preferredImplyPlanar = false) {
110 return call(G, preferredEdges, delEdges, preferredImplyPlanar);
111 }
112
114 ReturnType operator()(const Graph& G, List<edge>& delEdges) { return call(G, delEdges); }
115
125 List<edge> delEdges;
127 if (isSolution(retValue)) {
128 for (edge eCopy : delEdges) {
129 delOrigEdges.pushBack(GC.original(eCopy));
130 GC.delEdge(eCopy);
131 }
132 }
133 return retValue;
134 }
135
145
147 virtual PlanarSubgraphModule* clone() const = 0;
148
150 unsigned int maxThreads() const { return m_maxThreads; }
151
153 void maxThreads(unsigned int n) {
154#ifndef OGDF_MEMORY_POOL_NTS
155 m_maxThreads = n;
156#endif
157 }
158
159protected:
160 // computes set of edges delEdges, which have to be deleted
161 // in order to get a planar subgraph; edges in preferredEdges
162 // should be contained in planar subgraph
163 // must be implemented by derived classes!
176 virtual ReturnType doCall(const Graph& G, const List<edge>& preferredEdges, List<edge>& delEdges,
177 const EdgeArray<TCost>* pCost = nullptr, bool preferredImplyPlanar = false) = 0;
178
180};
181
182}
Declaration of graph copy classes.
Contains logging functionality.
Declares base class for all module types.
Declaration of Thread class representing threads.
Declares base class for modules with timeout functionality.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
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
Base class for modules.
Definition Module.h:47
ReturnType
The return type of a module.
Definition Module.h:50
static bool isSolution(ReturnType ret)
Returns true iff ret indicates that the module returned a feasible solution.
Definition Module.h:65
Interface for planar subgraph algorithms.
ReturnType call(const Graph &G, const EdgeArray< TCost > &cost, List< edge > &delEdges)
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
unsigned int maxThreads() const
Returns the maximal number of used threads.
ReturnType call(const Graph &G, const EdgeArray< TCost > &cost, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
virtual ReturnType doCall(const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost=nullptr, bool preferredImplyPlanar=false)=0
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
void maxThreads(unsigned int n)
Sets the maximal number of used threads to n.
ReturnType callAndDelete(GraphCopy &GC, List< edge > &delOrigEdges)
Makes G planar by deleting edges.
ReturnType operator()(const Graph &G, List< edge > &delEdges)
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
unsigned int m_maxThreads
The maximal number of used threads.
ReturnType call(const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
PlanarSubgraphModule()
Initializes a planar subgraph module (default constructor).
ReturnType operator()(const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
virtual PlanarSubgraphModule * clone() const =0
Returns a new instance of the planar subgraph module with the same option settings.
ReturnType callAndDelete(GraphCopy &GC, const List< edge > &preferredEdges, List< edge > &delOrigEdges, bool preferredImplyPlanar=false)
Makes GC planar by deleting edges.
ReturnType call(const Graph &G, List< edge > &delEdges)
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
class for timeout funtionality.
Definition Timeouter.h:46
#define OGDF_MALLOC_NEW_DELETE
Makes the class use malloc for memory allocation.
Definition memory.h:91
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.