1/** \file
2 * \brief Regression test for planarity tests and embeddings
3 *
4 * \author Carsten Gutwenger, Tilo Wiedera, Mirko Wagner
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 <random>
33
34#include <ogdf/planarity/BoothLueker.h>
35#include <ogdf/planarity/BoyerMyrvold.h>
36#include <ogdf/basic/extended_graph_alg.h>
37#include <ogdf/planarity/NonPlanarCore.h>
38#include <ogdf/planarity/PlanarizationLayout.h>
39#include <ogdf/planarity/SubgraphPlanarizer.h>
40#include <ogdf/graphalg/MaxFlowSTPlanarItaiShiloach.h>
41#include <ogdf/graphalg/MinSTCutMaxFlow.h>
42
43#include <graphs.h>
44
45using std::minstd_rand;
46using std::uniform_int_distribution;
47using ReturnType = CrossingMinimizationModule::ReturnType;
48
49template<typename T>
50void testNPCWeighted(string description, string alg, bool useDijkstra) {
51 it("recognizes weight in " + description + " with " + alg, [&]() {
52 Graph graph;
53 completeGraph(graph, 5);
54 EdgeArray<T> weight(graph, T(1));
55 edge e = graph.chooseEdge();
56 edge f = graph.newEdge(e->target(), e->source());
57 weight[graph.split(e)] = T(32.32);
58 weight[graph.split(f)] = T(64.64);
59 weight[graph.newEdge(e->target(), f->target())] = T(4.04);
60 weight[e] = T(8.08);
61 weight[f] = T(16.16);
62 NonPlanarCore<T> *npc;
63 if(useDijkstra) {
64 npc = new NonPlanarCore<T>(graph, weight);
65 } else {
66 MinSTCutMaxFlow<T> minSTCutMaxFlow(true, new MaxFlowSTPlanarItaiShiloach<T>());
67 npc = new NonPlanarCore<T>(graph, weight, &minSTCutMaxFlow);
68 }
69 const Graph &core = npc->core();
70 for (edge eCore : core.edges) {
71 if (npc->isVirtual(eCore)) {
72 AssertThat(npc->cost(eCore), Equals(T(28.28)));
73 }
74 }
75 delete npc;
76 });
77}
78
79void randomizeAdjLists(Graph G, minstd_rand &rng){
80 for(node v : G.nodes){
81 List<adjEntry> L;
82 v->allAdjEntries(L);
83 L.permute(rng);
84 G.sort(v, L);
85 }
86}
87
88void describeModule(const std::string &name, PlanarityModule &pm){
89describe(name, [&](){
90 minstd_rand rng(42);
91 srand(4711);
92
93 forEachGraphItWorks({GraphProperty::planar}, [&](Graph G) {
94 randomizeAdjLists(G, rng);
95 AssertThat(pm.isPlanar(G), IsTrue());
96 AssertThat(pm.planarEmbed(G), IsTrue());
97 AssertThat(G.representsCombEmbedding(), IsTrue());
98 });
99
100 forEachGraphItWorks({GraphProperty::nonPlanar}, [&](Graph G) {
101 randomizeAdjLists(G, rng);
102 AssertThat(pm.isPlanar(G), IsFalse());
103 AssertThat(pm.planarEmbed(G), IsFalse());
104 });
105});
106}
107
108void testNonPlanarCore()
109{
110 for_each_graph_it("returns a simple core", {"north/g.41.26.gml", "north/g.73.8.gml"},
111 [&](Graph &graph){
112 makeBiconnected(graph);
113 NonPlanarCore<int> npc(graph);
114 const Graph &core = npc.core();
115 AssertThat(isSimpleUndirected(core), IsTrue());
116
117 for(edge e : core.edges){
118 AssertThat(npc.cost(e), IsGreaterThan(0));
119 if(!npc.isVirtual(e)){
120 AssertThat(npc.realEdge(e), !IsNull());
121 }
122 }
123 });
124
125 it("works on a minimal previously failing instance (2 x K5)", [](){
126 Graph graph;
127 EdgeArray<int> weight(graph);
128
129 node s = graph.newNode();
130 node t = graph.newNode();
131 graph.newEdge(t, s);
132
133 node v = graph.newNode();
134 graph.newEdge(s, v);
135 graph.newEdge(v, t);
136
137 for(int k = 0; k < 2; k++){
138 List<node> nodes;
139 nodes.pushBack(s);
140 nodes.pushBack(t);
141
142 for(int i = 0; i < 3; i++){
143 nodes.pushBack(graph.newNode());
144 }
145
146 for(node x : nodes){
147 for(node w : nodes){
148 if(x->index() < w->index() && (x != s || w != t)){
149 graph.newEdge(x, w);
150 }
151 }
152 }
153 }
154
155 NonPlanarCore<int> npc(graph);
156 const Graph &core = npc.core();
157
158 for(edge e : core.edges) {
159 if(npc.isVirtual(e)) {
160 for(auto eCut : npc.mincut(e)) {
161 if(eCut.e->source() == npc.original(e->source()) || eCut.e->target() == npc.original(e->target())) {
162 AssertThat(eCut.dir, IsTrue());
163 } else {
164 AssertThat(eCut.dir, IsFalse());
165 }
166 }
167 }
168 }
169 AssertThat(isLoopFree(core), IsTrue());
170 AssertThat(isSimpleUndirected(core), IsTrue());
171 AssertThat(core.numberOfNodes(), Equals(graph.numberOfNodes() - 1));
172 AssertThat(core.numberOfEdges(), Equals(graph.numberOfEdges() - 2));
173 });
174
175 testNPCWeighted<int>("int", "Dijkstra", true);
176 testNPCWeighted<int>("int", "ItaiShiloach", false);
177 testNPCWeighted<unsigned int>("unsigned int", "Dijkstra", true);
178 testNPCWeighted<double>("double", "Dijkstra", true);
179 testNPCWeighted<double>("double", "ItaiShiloach", false);
180
181 for_each_graph_it("retransforms while preserving the genus", {"north/g.41.26.gml", "north/g.73.8.gml"}, [&](Graph &graph) {
182 makeBiconnected(graph);
183 List<edge> edges;
184 graph.allEdges(edges);
185 for(edge e : edges) {
186 edge f = graph.newEdge(e->source(), e->target());
187 edge g = graph.split(e);
188 edge h = graph.split(f);
189 graph.newEdge(g->source(), h->source());
190 }
191 NonPlanarCore<int> C(graph);
192 const Graph &core = C.core();
193 AssertThat(isPlanar(core), IsFalse());
194 AssertThat(core.numberOfNodes(), !Equals(0));
195 SubgraphPlanarizer SP;
196 PlanRep planarCore(core);
197 planarCore.initCC(0);
198
199 GraphCopy endGraph(graph);
200
201 C.retransform(planarCore, endGraph, false);
202
203 AssertThat(planarCore.genus(), Equals(endGraph.genus()));
204 });
205
206 for_each_graph_it("retransforms", {"north/g.41.26.gml", "north/g.73.8.gml"}, [&](Graph &graph) {
207 makeBiconnected(graph);
208 NonPlanarCore<int> C(graph);
209 const Graph &core = C.core();
210 AssertThat(isPlanar(core), IsFalse());
211 AssertThat(core.numberOfNodes(), !Equals(0));
212 SubgraphPlanarizer SP;
213 PlanRep planarCore(core);
214
215 GraphCopy endGraph(graph);
216 int crossingNumber = 0;
217 ReturnType ret = SP.call(planarCore, 0, crossingNumber, &C.cost());
218 AssertThat(ret == ReturnType::TimeoutFeasible
219 || ret == ReturnType::Feasible
220 || ret == ReturnType::Optimal, IsTrue());
221 AssertThat(planarEmbed(planarCore), IsTrue());
222 planarCore.removePseudoCrossings();
223
224 C.retransform(planarCore, endGraph);
225
226 AssertThat(isPlanar(endGraph), IsTrue());
227 AssertThat(endGraph.genus(), Equals(0));
228
229 // now the embedding of the endGraph is tested to assert that the embedding of planarCore was
230 // used to embed the endGraph
231 for(node v : planarCore.nodes){
232 if(planarCore.isDummy(v)){
233 continue;
234 }
235 node endNode = endGraph.copy(C.original(planarCore.original(v)));
236 List<adjEntry> adjEntries;
237 endNode->allAdjEntries(adjEntries);
238 int stComponentCounter(0);
239 Array<int> componentList;
240 componentList.grow(adjEntries.size(), -1);
241 for(adjEntry pcAdj : v->adjEntries){
242 edge coreEdge = planarCore.original(pcAdj->theEdge());
243 node stNode = (pcAdj == pcAdj->theEdge()->adjSource() ? C.sNode(coreEdge) : C.tNode(coreEdge));
244 EdgeArray<edge> &mapE = *C.mapE(coreEdge);
245 for(adjEntry stAdj : stNode->adjEntries){
246 List<edge> chain = endGraph.chain(mapE[stAdj->theEdge()]);
247 adjEntry endAdj = nullptr;
248 for(edge e : chain){
249 if(e->source() == endNode){
250 endAdj = e->adjSource();
251 }
252 if(e->target() == endNode){
253 endAdj = e->adjTarget();
254 }
255
256 }
257 auto searchIt = adjEntries.search(endAdj);
258 AssertThat(searchIt.valid(), IsTrue());
259 int position = adjEntries.pos(searchIt);
260 componentList[position] = stComponentCounter;
261 }
262 stComponentCounter++;
263 }
264 int before(*componentList.rbegin());
265 for(int i : componentList){
266 if(i != before){
267 AssertThat((before + 1) % stComponentCounter, Equals(i));
268 before = i;
269 }
270 }
271 }
272 });
273
274 it("contracts chains", [&](){
275 Graph graph;
276 GraphAttributes GA(graph);
277 GA.addAttributes(GraphAttributes::nodeType | GraphAttributes::edgeType | GraphAttributes::nodeLabel |
278 GraphAttributes::nodeStyle | GraphAttributes::edgeLabel | GraphAttributes::edgeStyle | GraphAttributes::edgeArrow);
279 for(int i = 0; i < 13; i++){
280 node curr = graph.newNode();
281 GA.label(curr) = to_string(curr->index());
282 GA.fillColor(curr) = Color::Name::Turquoise;
283 }
284
285 List<node> v;
286 graph.allNodes(v);
287
288 graph.newEdge(*v.get(0), *v.get(1));
289 graph.newEdge(*v.get(1), *v.get(2));
290 graph.newEdge(*v.get(2), *v.get(4));
291 graph.newEdge(*v.get(1), *v.get(3));
292 graph.newEdge(*v.get(4), *v.get(3));
293 graph.newEdge(*v.get(3), *v.get(5));
294 graph.newEdge(*v.get(5), *v.get(6));
295 graph.newEdge(*v.get(5), *v.get(2));
296 graph.newEdge(*v.get(4), *v.get(6));
297 edge e67 = graph.newEdge(*v.get(6), *v.get(7));
298 edge e78 = graph.newEdge(*v.get(7), *v.get(8));
299 graph.newEdge(*v.get(0), *v.get(11));
300 graph.newEdge(*v.get(0), *v.get(10));
301 graph.newEdge(*v.get(11), *v.get(12));
302 graph.newEdge(*v.get(10), *v.get(12));
303 graph.newEdge(*v.get(10), *v.get(9));
304 graph.newEdge(*v.get(9), *v.get(8));
305 graph.newEdge(*v.get(5), *v.get(4));
306 graph.newEdge(*v.get(12), *v.get(8));
307 graph.newEdge(*v.get(11), *v.get(9));
308
309 EdgeArray<int> weight(graph, 1);
310 weight[e67] = 2;
311 weight[e78] = 3;
312 NonPlanarCore<int> C(graph, weight);
313 const Graph &core = C.core();
314 node v6(core.chooseNode()), v8(core.chooseNode());
315 for(node w : core.nodes){
316 if(C.original(w) == *v.get(6)){
317 v6 = w;
318 }
319 if(C.original(w) == *v.get(8)){
320 v8 = w;
321 }
322 }
323 edge virt = nullptr;
324 for(edge e : core.edges){
325 if ((e->source() == v6 && e->target() == v8)
326 || (e->source() == v8 && e->target() == v6)) {
327 virt = e;
328 }
329 }
330 AssertThat(virt, !Equals((void *) nullptr));
331 AssertThat(C.isVirtual(virt), IsTrue());
332 AssertThat(C.cost(virt), Equals(2));
333 });
334
335 it("eliminates multiedges", [](){
336 Graph graph;
337 completeGraph(graph, 5);
338 edge e = graph.chooseEdge();
339 graph.newEdge(e->source(), e->target());
340 e = graph.chooseEdge();
341 graph.newEdge(e->target(), e->source());
342 NonPlanarCore<int> npc(graph);
343 const Graph &core = npc.core();
344 AssertThat(isSimpleUndirected(core), IsTrue());
345 AssertThat(core.numberOfNodes(), Equals(graph.numberOfNodes()));
346 AssertThat(core.numberOfEdges(), Equals(10));
347 });
348
349 it("returns a list of original edges of a core edge", [](){
350 Graph graph;
351 completeGraph(graph, 5);
352 edge e = graph.chooseEdge();
353 edge f = graph.split(e);
354 NonPlanarCore<int> npc(graph);
355 for(edge eCore : npc.core().edges) {
356 List<edge> list = npc.original(eCore);
357 if(npc.isVirtual(eCore)){
358 AssertThat(list.size(), Equals(2));
359 if(list.front() == e) {
360 AssertThat(list.back(), Equals(f));
361 } else {
362 AssertThat(list.front(), Equals(f));
363 AssertThat(list.back(), Equals(e));
364 }
365 } else {
366 AssertThat(list.size(), Equals(1));
367 AssertThat(list.front(), Equals(npc.realEdge(eCore)));
368 }
369 }
370 });
371}
372
373go_bandit([](){
374 describe("Planarity tests", [](){
375 BoothLueker bl;
376 describeModule("Booth-Lueker", bl);
377 BoyerMyrvold bm;
378 describeModule("Boyer-Myrvold", bm);
379
380 it("transforms based on the right graph, when it's a GraphCopySimple", [&](){
381 Graph G;
382 randomRegularGraph(G, 10, 6);
383 GraphCopySimple gcs(G);
384 BoyerMyrvold boyerMyrvold;
385 SList<KuratowskiWrapper> kur_subs;
386 SList<KuratowskiSubdivision> lksGcs;
387 SList<KuratowskiSubdivision> lksG;
388
389 boyerMyrvold.planarEmbed(gcs, kur_subs, BoyerMyrvoldPlanar::EmbeddingGrade::doFindUnlimited);
390 boyerMyrvold.transform(kur_subs,lksGcs,gcs);
391 boyerMyrvold.transform(kur_subs,lksG,G);
392 });
393 });
394
395 describe("NonPlanarCore", [](){
396 testNonPlanarCore();
397 });
398});
399