1/** \file
2 * \brief Tests for various crossing minimization modules.
3 *
4 * \author Tilo Wiedera
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <set>
33
34#include <ogdf/basic/graph_generators.h>
35#include <ogdf/basic/simple_graph_alg.h>
36#include <ogdf/basic/extended_graph_alg.h>
37#include <ogdf/planarity/SubgraphPlanarizer.h>
38#include <ogdf/planarity/FixedEmbeddingInserter.h>
39#include <ogdf/planarity/MultiEdgeApproxInserter.h>
40#include <ogdf/planarity/VariableEmbeddingInserter.h>
41#include <ogdf/planarity/VariableEmbeddingInserterDyn.h>
42#include <ogdf/energybased/FMMMLayout.h>
43
44#include <resources.h>
45
46constexpr edge none = nullptr;
47
48/**
49 * Verifies that \p graph resembles a planarization of the original graph.
50 *
51 * \param graph a supposed planarization to be verified
52 * \param cost a pointer to the cost of each edge in the original graph
53 * \return the weighted crossing number of the given planarization
54 */
55int verifyCrossings(const GraphCopy &graph, const EdgeArray<int> *cost) {
56 int result = 0;
57
58 const Graph &original = graph.original();
59 int numberOfDummies = graph.numberOfNodes() - original.numberOfNodes();
60 AssertThat(graph.numberOfEdges() - original.numberOfEdges(), Equals(2*numberOfDummies));
61
62 int dummyCounter = 0;
63 for(node v : graph.nodes) {
64 if(graph.isDummy(v)) {
65 dummyCounter++;
66
67 AssertThat(v->degree(), Equals(4));
68 AssertThat(v->indeg(), Equals(2));
69
70 std::set<edge> set;
71 edge e = graph.original(v->firstAdj()->theEdge());
72 edge f = graph.original(v->lastAdj()->theEdge());
73 set.insert(e);
74 set.insert(f);
75 set.insert(graph.original(v->firstAdj()->cyclicSucc()->theEdge()));
76 set.insert(graph.original(v->lastAdj()->cyclicPred()->theEdge()));
77 AssertThat(set.size(), Equals(2u));
78
79 List<edge> inEdges;
80 v->inEdges(inEdges);
81 AssertThat(graph.original(inEdges.front()), !Equals(graph.original(inEdges.back())));
82
83 AssertThat(e, !Equals(none));
84 AssertThat(f, !Equals(none));
85 result += cost ? (*cost)[*set.begin()] * (*cost)[*set.rbegin()] : 1;
86 }
87 }
88
89 AssertThat(dummyCounter, Equals(numberOfDummies));
90
91 for(edge e : graph.edges) {
92 node s = e->source();
93 node t = e->target();
94
95 AssertThat(graph.isDummy(e), IsFalse());
96
97 if(!graph.isDummy(s)) {
98 AssertThat(s, Equals(graph.copy(graph.original(e)->source())));
99 }
100
101 if(!graph.isDummy(t)) {
102 AssertThat(t, Equals(graph.copy(graph.original(e)->target())));
103 }
104 }
105
106 return result;
107}
108
109/**
110 * Tests a planarization algorithm on a single instance.
111 *
112 * \param cmm an algorithm to be tested
113 * \param graph a graph that should be planarized
114 * \param expected the crossing number of the input graph
115 * \param isOptimal whether the algorithm is supposed to yield an optimal solution for this instance
116 * \param cost costs of all edges. If \c nullptr is given each edge is assumed to have cost 1
117 */
118void testComputation(CrossingMinimizationModule &cmm, const Graph &graph, int expected, bool isOptimal, const EdgeArray<int> *cost = nullptr) {
119 using ReturnType = CrossingMinimizationModule::ReturnType;
120
121 PlanRep planRep(graph);
122 planRep.initCC(0);
123 int actual(17); // an arbitrary nonzero number
124 ReturnType result = cmm.call(planRep, 0, actual, cost);
125 if(isOptimal) {
126 AssertThat(result, Equals(ReturnType::Optimal));
127 } else {
128 AssertThat(result, Equals(ReturnType::Optimal) || Equals(ReturnType::Feasible) || Equals(ReturnType::TimeoutFeasible));
129 }
130
131 if(isOptimal) {
132 AssertThat(actual, Equals(expected));
133 } else {
134 AssertThat(actual, !IsLessThan(expected));
135 }
136
137 bool planar = planarEmbed(planRep);
138
139 // optimal algorithms don't need to return planarizations
140 if(!isOptimal) {
141 AssertThat(planar, IsTrue());
142 }
143
144 if(planar) {
145 AssertThat(verifyCrossings(planRep, cost), Equals(actual));
146 }
147 if(planar && isLoopFree(graph)) {
148 AssertThat(isLoopFree(planRep), IsTrue());
149 }
150}
151
152/**
153 * Tests a ::CrossingMinimizationModule \p cmm for correctness.
154 *
155 * \param cmm an algorithm to be tested
156 * \param title a human-readable title of the algorithm
157 * \param isOptimal whether the algorithm is optimal
158 */
159void testModule(CrossingMinimizationModule &cmm, const std::string title, bool isOptimal) {
160 describe(title, [&]() {
161 Graph graph;
162
163 it("works on a K4", [&]() {
164 completeGraph(graph, 4);
165 testComputation(cmm, graph, 0, isOptimal);
166 });
167
168 it("works on a K5", [&]() {
169 completeGraph(graph, 5);
170 testComputation(cmm, graph, 1, isOptimal);
171 });
172
173 it("works on a K6", [&]() {
174 completeGraph(graph, 6);
175 testComputation(cmm, graph, 3, isOptimal);
176 });
177
178 it("works on a K3,3", [&]() {
179 completeBipartiteGraph(graph, 3, 3);
180 testComputation(cmm, graph, 1, isOptimal);
181 });
182
183 it("works on a K4,3", [&]() {
184 completeBipartiteGraph(graph, 4, 3);
185 testComputation(cmm, graph, 2, isOptimal);
186 });
187
188 it("works on a K4,4", [&]() {
189 completeBipartiteGraph(graph, 4, 4);
190 testComputation(cmm, graph, 4, isOptimal);
191 });
192
193 it("works on a petersen graph", [&]() {
194 petersenGraph(graph, 5, 2);
195 testComputation(cmm, graph, 2, isOptimal);
196 });
197
198 it("works on a generalized petersen graph (9,2)", [&]() {
199 petersenGraph(graph, 9, 2);
200 testComputation(cmm, graph, 3, isOptimal);
201 });
202
203 it("works on a weighted K3,3", [&]() {
204 completeBipartiteGraph(graph, 3, 3);
205
206 EdgeArray<int> cost(graph, 2);
207 testComputation(cmm, graph, 4, isOptimal, &cost);
208
209 cost[graph.chooseEdge()] = 1;
210 testComputation(cmm, graph, 2, isOptimal, &cost);
211 });
212
213 // TODO test forbidden edges ?
214
215 if(isOptimal) {
216#ifdef OGDF_USE_ASSERT_EXCEPTIONS
217 // optimal algorithms should throw exceptions on non-pre-processed instances
218
219 it("aborts if the graph contains self-loops", [&](){
220 completeGraph(graph, 5);
221 node v = graph.chooseNode();
222 graph.newEdge(v, v);
223 AssertThrows(AssertionFailed, testComputation(cmm, graph, 1, true));
224 });
225
226 it("aborts if the graph contains parallel edges", [&](){
227 completeGraph(graph, 5);
228 graph.newEdge(graph.firstNode(), graph.lastNode());
229 AssertThrows(AssertionFailed, testComputation(cmm, graph, 1, true));
230 });
231
232 it("aborts if the graph contains nodes with degree 2", [&](){
233 completeGraph(graph, 5);
234 node v = graph.newNode();
235 graph.newEdge(graph.chooseNode(), v);
236 graph.newEdge(graph.chooseNode(), v);
237 AssertThrows(AssertionFailed, testComputation(cmm, graph, 1, true));
238 });
239
240 it("aborts if the graph isn't biconnected", [&](){
241 completeGraph(graph, 5);
242 List<node> nodes = { graph.chooseNode() };
243
244 for(int i = 0; i < 4; i++) {
245 nodes.pushBack(graph.newNode());
246 }
247
248 for(node v : nodes) {
249 for(node w : nodes) {
250 if(w->index() < v->index()) {
251 graph.newEdge(v, w);
252 }
253 }
254 }
255
256 AssertThrows(AssertionFailed, testComputation(cmm, graph, 1, true));
257 });
258#endif
259 } else {
260 // we assume non-optimal algorithms to be faster
261
262 it("works on a generalized petersen graph (15,3)", [&]() {
263 petersenGraph(graph, 15, 3);
264 testComputation(cmm, graph, 5, isOptimal);
265 });
266
267 it("works on a K10", [&]() {
268 completeGraph(graph, 10);
269 testComputation(cmm, graph, 60, false);
270 });
271
272 std::vector<string> instances = {
273 "rome/grafo3703.45.lgr.gml.pun",
274 "rome/grafo5745.50.lgr.gml.pun"
275 };
276
277 for_each_graph_it("works", instances,
278 [&](Graph &gr) {
279 testComputation(cmm, gr, -1, false);
280 });
281 }
282 });
283}
284
285template<typename EdgeInserter>
286void setRemoveReinsert(EdgeInserter &edgeInserter, RemoveReinsertType rrType) {
287 edgeInserter.removeReinsert(rrType);
288}
289
290template<>
291void setRemoveReinsert(MultiEdgeApproxInserter &edgeInserter, RemoveReinsertType rrType) {
292 edgeInserter.removeReinsertVar(rrType);
293 edgeInserter.removeReinsertFix(rrType);
294}
295
296/**
297 * Test the ::SubgraphPlanarizer with a specific type of edge remove-reinsert post-processing.
298 */
299template<typename EdgeInserter>
300void testSPRRType(SubgraphPlanarizer &heuristic, EdgeInserter *edgeInserter, RemoveReinsertType rrType, const std::string name, bool skipMe) {
301 auto performTest = [&]() {
302 setRemoveReinsert(*edgeInserter, rrType);
303 heuristic.permutations(1);
304 testModule(heuristic, "single run", false);
305 heuristic.permutations(4);
306 testModule(heuristic, "4 permutations", false);
307 };
308
309 string title = "remove-reinsert: " + name;
310
311 if(skipMe) {
312 describe_skip(title, performTest);
313 } else {
314 describe(title, performTest);
315 }
316}
317
318/**
319 * Test the ::SubgraphPlanarizer with a specific ::EdgeInsertionModule .
320 */
321template<typename EdgeInserter>
322void testSPEdgeInserter(EdgeInserter *edgeInserter, const std::string name, bool skipMe = false) {
323 describe("edge insertion: " + name, [&]() {
324 SubgraphPlanarizer heuristic;
325 heuristic.setInserter(edgeInserter);
326
327 testSPRRType(heuristic, edgeInserter, RemoveReinsertType::None, "none", skipMe);
328 testSPRRType(heuristic, edgeInserter, RemoveReinsertType::Inserted, "inserted", skipMe);
329 testSPRRType(heuristic, edgeInserter, RemoveReinsertType::MostCrossed, "most-crossed", skipMe);
330 testSPRRType(heuristic, edgeInserter, RemoveReinsertType::All, "all", skipMe);
331 testSPRRType(heuristic, edgeInserter, RemoveReinsertType::Incremental, "incremental", skipMe);
332 testSPRRType(heuristic, edgeInserter, RemoveReinsertType::IncInserted, "inc-inserted", skipMe);
333 });
334}
335
336/**
337 * Test variants of the ::SubgraphPlanarizer .
338 */
339void testSubgraphPlanarizer() {
340 describe("SubgraphPlanarizer", []() {
341 testSPEdgeInserter(new FixedEmbeddingInserter, "FixedEmbedding");
342 testSPEdgeInserter(new MultiEdgeApproxInserter, "MultiEdgeApprox");
343 testSPEdgeInserter(new VariableEmbeddingInserter, "VariableEmbedding");
344 testSPEdgeInserter(new VariableEmbeddingInserterDyn, "VariableEmbeddingDyn");
345 });
346}
347
348go_bandit([]() {
349 testSubgraphPlanarizer();
350});
351