Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MaximumPlanarSubgraph.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Array.h>
35#include <ogdf/basic/Graph.h>
37#include <ogdf/basic/List.h>
38#include <ogdf/basic/Module.h>
39#include <ogdf/basic/SList.h>
40#include <ogdf/basic/basic.h>
46
48
49namespace ogdf {
50
52
55template<typename TCost>
57public:
58 // Construction
60
61 // Destruction
63
64 virtual MaximumPlanarSubgraph* clone() const override { return new MaximumPlanarSubgraph(); }
65
66protected:
67 // Implements the Planar Subgraph interface.
68 // For the given graph \p G, a clustered graph with only
69 // a single root cluster is generated.
70 // Computes set of edges delEdges, which have to be deleted
71 // in order to get a planar subgraph; edges in preferredEdges
72 // should be contained in planar subgraph.
73 // Status: pCost and preferredEdges are ignored in current implementation.
74 virtual Module::ReturnType doCall(const Graph& G, const List<edge>& preferredEdges,
75 List<edge>& delEdges, const EdgeArray<TCost>* pCost, bool preferredImplyPlanar) override {
76 if (G.numberOfEdges() < 9) {
78 }
79
80 //if the graph is planar, we don't have to do anything
81 if (isPlanar(G)) {
83 }
84
85 //Exact ILP
87
88 delEdges.clear();
89
90 NodeArray<node> tableNodes(G, nullptr);
91 EdgeArray<edge> tableEdges(G, nullptr);
92 NodeArray<bool> mark(G, 0);
93
94 EdgeArray<int> componentID(G);
95
96 // Determine biconnected components
97 int bcCount = biconnectedComponents(G, componentID);
98 OGDF_ASSERT(bcCount >= 1);
99
100 // Determine edges per biconnected component
101 Array<SList<edge>> blockEdges(0, bcCount - 1);
102 for (edge e : G.edges) {
103 if (!e->isSelfLoop()) {
104 blockEdges[componentID[e]].pushFront(e);
105 }
106 }
107
108 // Determine nodes per biconnected component.
109 Array<SList<node>> blockNodes(0, bcCount - 1);
110 int i;
111 for (i = 0; i < bcCount; i++) {
112 for (edge e : blockEdges[i]) {
113 if (!mark[e->source()]) {
114 blockNodes[i].pushBack(e->source());
115 mark[e->source()] = true;
116 }
117 if (!mark[e->target()]) {
118 blockNodes[i].pushBack(e->target());
119 mark[e->target()] = true;
120 }
121 }
122 for (node v : blockNodes[i]) {
123 mark[v] = false;
124 }
125 }
126
127
128 // Perform computation for every biconnected component
130 if (bcCount == 1) {
131 mr = callWithDouble(mc, G, pCost, delEdges);
132 } else {
133 for (i = 0; i < bcCount; i++) {
134 Graph C;
135
136 for (node v : blockNodes[i]) {
137 node w = C.newNode();
138 tableNodes[v] = w;
139 }
140
141 EdgeArray<double> cost(C);
142
143 for (edge e : blockEdges[i]) {
144 edge f = C.newEdge(tableNodes[e->source()], tableNodes[e->target()]);
145 tableEdges[e] = f;
146 if (pCost != nullptr) {
147 cost[tableEdges[e]] = (*pCost)[e];
148 }
149 }
150
151 // Construct a translation table for the edges.
152 // Necessary, since edges are deleted in a new graph
153 // that represents the current biconnected component
154 // of the original graph.
155 EdgeArray<edge> backTableEdges(C, nullptr);
156 for (edge e : blockEdges[i]) {
157 backTableEdges[tableEdges[e]] = e;
158 }
159
160 // The deleted edges of the biconnected component
161 List<edge> delEdgesOfBC;
162
163 ClusterGraph CG(C);
164 mr = mc.call(CG, pCost == nullptr ? nullptr : &cost, delEdgesOfBC);
165
166 // Abort if no optimal solution found, i.e., feasible is also not allowed
167 if (mr != Module::ReturnType::Optimal) {
168 break;
169 }
170
171 // Get the original edges that are deleted and
172 // put them on the list delEdges.
173 while (!delEdgesOfBC.empty()) {
174 delEdges.pushBack(backTableEdges[delEdgesOfBC.popFrontRet()]);
175 }
176 }
177 }
178 return mr;
179 }
180
181
182private:
183 // Call algorithm with costs as double. All underlying algorithms cast the costs to double on use eventually.
184 // However, only convert the costs if they are not given as double already.
185 template<typename U = TCost>
187 const EdgeArray<U>* pCost, List<edge>& delEdges) {
188 if (pCost == nullptr) {
189 return callWithDouble(mc, G, nullptr, delEdges);
190 } else {
191 EdgeArray<double> dCost(G);
192 for (auto it = pCost->begin(); it != pCost->end(); ++it) {
193 dCost[it.key()] = it.value();
194 }
195 return callWithDouble(mc, G, &dCost, delEdges);
196 }
197 }
198
200 const EdgeArray<double>* pCost, List<edge>& delEdges) {
201 ClusterGraph CG(G);
202 return mc.call(CG, pCost, delEdges);
203 }
204};
205
206}
Declaration and implementation of Array class and Array algorithms.
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
Includes declaration of graph class.
Decralation of GraphElement and GraphList classes.
Declaration of doubly linked lists and iterators.
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.
Declaration of singly linked lists and iterators.
Includes Abacus.
Basic declarations, included by all source files.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:219
ReturnType call(const ClusterGraph &G, List< edge > &delEdges)
Computes set of edges delEdges, which have to be deleted in order to get a c-planar subgraph.
Representation of clustered graphs.
Class for the representation of edges.
Definition Graph_d.h:364
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:866
node newNode(int index=-1)
Creates a new node and returns it.
Definition Graph_d.h:1061
edge newEdge(node v, node w, int index=-1)
Creates a new edge (v,w) and returns it.
Definition Graph_d.h:1080
Doubly linked lists (maintaining the length of the list).
Definition List.h:1451
void clear()
Removes all elements from the list.
Definition List.h:1626
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1547
E popFrontRet()
Removes the first element from the list and returns it.
Definition List.h:1591
bool empty() const
Returns true iff the list is empty.
Definition List.h:286
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:52
@ Optimal
The solution is optimal.
Class for the representation of nodes.
Definition Graph_d.h:241
Interface for planar subgraph algorithms.
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition Graph_d.h:717
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition Graph_d.h:659
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)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:52
The namespace for all OGDF objects.
Declaration of simple graph algorithms.