# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
MaximumPlanarSubgraph.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Module.h>
42
43namespace ogdf {
44
46
49template<typename TCost>
51public:
52 // Construction
54
55 // Destruction
57
58 virtual MaximumPlanarSubgraph* clone() const override { return new MaximumPlanarSubgraph(); }
59
60protected:
61 // Implements the Planar Subgraph interface.
62 // For the given graph \p G, a clustered graph with only
63 // a single root cluster is generated.
64 // Computes set of edges delEdges, which have to be deleted
65 // in order to get a planar subgraph; edges in preferredEdges
66 // should be contained in planar subgraph.
67 // Status: pCost and preferredEdges are ignored in current implementation.
69 List<edge>& delEdges, const EdgeArray<TCost>* pCost, bool preferredImplyPlanar) override {
70 if (G.numberOfEdges() < 9) {
72 }
73
74 //if the graph is planar, we don't have to do anything
75 if (isPlanar(G)) {
77 }
78
79 //Exact ILP
81
82 delEdges.clear();
83
84 NodeArray<node> tableNodes(G, nullptr);
85 EdgeArray<edge> tableEdges(G, nullptr);
86 NodeArray<bool> mark(G, 0);
87
89
90 // Determine biconnected components
92 OGDF_ASSERT(bcCount >= 1);
93
94 // Determine edges per biconnected component
96 for (edge e : G.edges) {
97 if (!e->isSelfLoop()) {
98 blockEdges[componentID[e]].pushFront(e);
99 }
100 }
101
102 // Determine nodes per biconnected component.
104 int i;
105 for (i = 0; i < bcCount; i++) {
106 for (edge e : blockEdges[i]) {
107 if (!mark[e->source()]) {
108 blockNodes[i].pushBack(e->source());
109 mark[e->source()] = true;
110 }
111 if (!mark[e->target()]) {
112 blockNodes[i].pushBack(e->target());
113 mark[e->target()] = true;
114 }
115 }
116 for (node v : blockNodes[i]) {
117 mark[v] = false;
118 }
119 }
120
121
122 // Perform computation for every biconnected component
124 if (bcCount == 1) {
125 mr = callWithDouble(mc, G, pCost, delEdges);
126 } else {
127 for (i = 0; i < bcCount; i++) {
128 Graph C;
129
130 for (node v : blockNodes[i]) {
131 node w = C.newNode();
132 tableNodes[v] = w;
133 }
134
135 EdgeArray<double> cost(C);
136
137 for (edge e : blockEdges[i]) {
138 edge f = C.newEdge(tableNodes[e->source()], tableNodes[e->target()]);
139 tableEdges[e] = f;
140 if (pCost != nullptr) {
141 cost[tableEdges[e]] = (*pCost)[e];
142 }
143 }
144
145 // Construct a translation table for the edges.
146 // Necessary, since edges are deleted in a new graph
147 // that represents the current biconnected component
148 // of the original graph.
150 for (edge e : blockEdges[i]) {
152 }
153
154 // The deleted edges of the biconnected component
156
157 ClusterGraph CG(C);
158 mr = mc.call(CG, pCost == nullptr ? nullptr : &cost, delEdgesOfBC);
159
160 // Abort if no optimal solution found, i.e., feasible is also not allowed
162 break;
163 }
164
165 // Get the original edges that are deleted and
166 // put them on the list delEdges.
167 while (!delEdgesOfBC.empty()) {
168 delEdges.pushBack(backTableEdges[delEdgesOfBC.popFrontRet()]);
169 }
170 }
171 }
172 return mr;
173 }
174
175
176private:
177 // Call algorithm with costs as double. All underlying algorithms cast the costs to double on use eventually.
178 // However, only convert the costs if they are not given as double already.
179 template<typename U = TCost>
181 const EdgeArray<U>* pCost, List<edge>& delEdges) {
182 if (pCost == nullptr) {
183 return callWithDouble(mc, G, nullptr, delEdges);
184 } else {
186 for (auto it = pCost->begin(); it != pCost->end(); ++it) {
187 dCost[it.key()] = it.value();
188 }
189 return callWithDouble(mc, G, &dCost, delEdges);
190 }
191 }
192
194 const EdgeArray<double>* pCost, List<edge>& delEdges) {
195 ClusterGraph CG(G);
196 return mc.call(CG, pCost, delEdges);
197 }
198};
199
200}
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
Declaration of an exact c-planar subgraph algorithm, i.e., a maximum c-planar subgraph is computed us...
Declares base class for all module types.
Declaration of interface for planar subgraph algorithms.
Declares base class for modules with timeout functionality.
Includes Abacus.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Representation of clustered graphs.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
node newNode()
Creates a new node and returns it.
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
void clear()
Removes all elements from the list.
Definition List.h:1610
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
Exact computation of a maximum c-planar subgraph.
Exact computation of a maximum planar subgraph.
virtual MaximumPlanarSubgraph * clone() const override
Returns a new instance of the planar subgraph module with the same option settings.
virtual Module::ReturnType doCall(const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar) override
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
Module::ReturnType callWithDouble(MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< U > *pCost, List< edge > &delEdges)
Module::ReturnType callWithDouble(MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< double > *pCost, List< edge > &delEdges)
ReturnType
The return type of a module.
Definition Module.h:50
@ Optimal
The solution is optimal.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Interface for planar subgraph algorithms.
Declaration of extended graph algorithms.
int biconnectedComponents(const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents)
Computes the biconnected components of G.
bool isPlanar(const Graph &G)
Returns true, if G is planar, false otherwise.
#define OGDF_ASSERT(expr)