1/** \file
2 * \brief Tests for ogdf::ConstCombinatorialEmbedding and ogdf::CombinatorialEmbedding.
3 *
4 * \author Mirko Wagner, 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 <ogdf/basic/CombinatorialEmbedding.h>
33#include <ogdf/basic/graph_generators.h>
34#include <ogdf/basic/extended_graph_alg.h>
35#include <ogdf/basic/Math.h>
36#include <ogdf/basic/FaceArray.h>
37
38#include <testing.h>
39
40constexpr int NUMBER_OF_ITERATIONS = 17;
41constexpr int NUMBER_OF_NODES = 100;
42constexpr int NUMBER_OF_EDGES = 200;
43
44//! Runs a single iteration of generic tests that do not modify the \c graph.
45template<typename T>
46void testConstCombinatorialEmbedding(Graph &graph) {
47 OGDF_ASSERT(graph.representsCombEmbedding());
48
49 T emb(graph);
50
51 it("returns its graph", [&] {
52 AssertThat(emb.valid(), IsTrue());
53 AssertThat(&emb.getGraph(), Equals(&graph));
54 AssertThat(&((const Graph&)(emb)), Equals(&graph));
55 });
56
57 it("iterates faces", [&] {
58 face f = emb.firstFace();
59 AssertThat(f->index(), Equals(0));
60 AssertThat(f->pred(), IsNull());
61
62 int counter = 0;
63 for(; f != nullptr; f = f->succ()) {
64 counter++;
65 }
66
67 AssertThat(counter, Equals(emb.numberOfFaces()));
68 });
69
70 it("iterates faces in reverse", [&] {
71 face f = emb.lastFace();
72 AssertThat(f->index(), Equals(emb.maxFaceIndex()));
73 AssertThat(f->succ(), IsNull());
74
75 int counter = 0;
76 for(; f != nullptr; f = f->pred()) {
77 counter++;
78 }
79
80 AssertThat(counter, Equals(emb.numberOfFaces()));
81 });
82
83 it("returns a maximal face", [&] {
84 int maxSize = -1;
85 for(face f : emb.faces) {
86 Math::updateMax(maxSize, f->size());
87 }
88
89 AssertThat(emb.maximalFace()->size(), Equals(maxSize));
90 });
91
92 it("chooses a random face", [&] {
93 for(int i = 0; i < 20; i++) {
94 AssertThat(emb.chooseFace(), !Equals(nullptr));
95 }
96 });
97
98 it("supports setting an external face", [&] {
99 AssertThat(emb.externalFace(), Equals(nullptr));
100 face f = emb.chooseFace();
101 emb.setExternalFace(f);
102 AssertThat(emb.externalFace(), Equals(f));
103 });
104
105 it("creates faces with correct size", [&] {
106 int sizesSum = 0;
107 for(face f : emb.faces) {
108 sizesSum += f->size();
109 }
110
111 AssertThat(sizesSum, Equals(graph.numberOfEdges() * 2));
112 });
113
114 it("returns all left and right faces", [&] {
115 FaceArray<bool> visited(emb, false);
116
117 for(edge e : graph.edges) {
118 adjEntry adj = e->adjSource();
119 visited[emb.leftFace(adj)] = true;
120 visited[emb.rightFace(adj)] = true;
121 }
122
123 for(face f : emb.faces) {
124 AssertThat(visited[f], IsTrue());
125 }
126 });
127}
128
129//! Create K4 rotation system with a single crossing
130void createBadK4(Graph &graph) {
131 completeGraph(graph, 4);
132 planarEmbed(graph);
133 adjEntry adj = graph.chooseNode()->firstAdj();
134 graph.moveAdjAfter(adj, adj->succ());
135}
136
137//! Runs tests that apply for ogdf::ConstCombinatorialEmbedding and ogdf::CombinatorialEmbedding.
138//! Also executes several iterations of generic tests.
139template<typename T>
140void testConstCombinatorialEmbedding() {
141 Graph planarGraph;
142 randomPlanarConnectedGraph(planarGraph, NUMBER_OF_NODES, NUMBER_OF_EDGES);
143 Graph K5;
144 completeGraph(K5, 5);
145 Graph badK4;
146 createBadK4(badK4);
147
148 describe("initialization",[&] {
149 it("works", [&] {
150 T emb(planarGraph);
151 AssertThat(emb.valid(), IsTrue());
152 AssertThat(&emb.getGraph(), Equals(&planarGraph));
153 });
154
155 it("works w/o a graph", [&] {
156 T emb;
157 AssertThat(emb.valid(), IsFalse());
158 });
159
160#ifdef OGDF_USE_ASSERT_EXCEPTIONS
161 it("rejects graphs that are not embedded", [&] {
162 AssertThrows(AssertionFailed, CombinatorialEmbedding(K5));
163 AssertThrows(AssertionFailed, CombinatorialEmbedding(badK4));
164 });
165#endif
166
167 it("works using init()", [&] {
168 T emb;
169 emb.init(planarGraph);
170 AssertThat(emb.valid(), IsTrue());
171 AssertThat(&emb.getGraph(), Equals(&planarGraph));
172 });
173
174#ifdef OGDF_USE_ASSERT_EXCEPTIONS
175 it("rejects graphs that are not embedded using init()", [&] {
176 T emb;
177 AssertThrows(AssertionFailed, emb.init(K5));
178 AssertThrows(AssertionFailed, emb.init(badK4));
179 });
180#endif
181 });
182
183 it("works on a single loop", [&] {
184 Graph graph;
185 node v = graph.newNode();
186 graph.newEdge(v, v);
187 T emb(graph);
188
189 AssertThat(emb.numberOfFaces(), Equals(2));
190 adjEntry adj = v->firstAdj();
191 AssertThat(emb.leftFace(adj), !Equals(emb.rightFace(adj)));
192 adj = v->lastAdj();
193 AssertThat(emb.leftFace(adj), !Equals(emb.rightFace(adj)));
194 });
195
196 it("works on a K3 with a dangling node", [&] {
197 Graph graph;
198 completeGraph(graph, 3);
199 node w = graph.chooseNode();
200 node v = graph.newNode();
201 edge e = graph.newEdge(v, w);
202 T emb(graph);
203
204 AssertThat(emb.numberOfFaces(), Equals(2));
205 adjEntry adj = v->firstAdj();
206 AssertThat(emb.leftFace(adj), Equals(emb.rightFace(adj)));
207
208 for(edge f : graph.edges) {
209 AssertThat(emb.isBridge(f), Equals(f == e));
210 }
211 });
212
213 it("works on a triconnected graph", [&] {
214 Graph graph;
215 randomPlanarTriconnectedGraph(graph, NUMBER_OF_NODES, NUMBER_OF_EDGES);
216 T emb(graph);
217
218 int counter = 0;
219 int size = 0;
220 for(face f : emb.faces){
221 counter++;
222 size += f->size();
223 }
224
225 AssertThat(size, Equals(graph.numberOfEdges()*2));
226 AssertThat(counter, Equals(emb.numberOfFaces()));
227 });
228
229 it("knows which faces are incident to a node or edge on a K3", [&] {
230 Graph graph;
231 node u = graph.newNode();
232 node v = graph.newNode();
233 node w = graph.newNode();
234 edge e = graph.newEdge(u, v);
235 edge f = graph.newEdge(v, w);
236 edge g = graph.newEdge(w, u);
237 T emb(graph);
238 AssertThat(u->firstAdj()->theEdge(), Equals(e));
239 face rightFace = emb.rightFace(e->adjSource());
240 AssertThat(emb.rightFace(f->adjSource()), Equals(rightFace));
241 AssertThat(emb.rightFace(g->adjSource()), Equals(rightFace));
242 face leftFace = emb.leftFace(e->adjSource());
243 AssertThat(emb.leftFace(f->adjSource()), Equals(leftFace));
244 AssertThat(emb.leftFace(g->adjSource()), Equals(leftFace));
245 AssertThat(emb.numberOfFaces(), Equals(2));
246 });
247
248 it("detects bridges on a tree", [&] {
249 Graph graph;
250 randomTree(graph, NUMBER_OF_NODES);
251 T emb(graph);
252
253 AssertThat(emb.numberOfFaces(), Equals(1));
254
255 for(edge e : graph.edges){
256 AssertThat(emb.isBridge(e), IsTrue());
257 }
258 });
259
260 it("detects bridges", [&] {
261 Graph graph;
262 randomPlanarBiconnectedGraph(graph, NUMBER_OF_NODES, NUMBER_OF_EDGES);
263
264 EdgeArray<bool> isBridge(graph, false);
265 node chosenNode = graph.chooseNode();
266 node v = chosenNode;
267 for(int i = 0; i < NUMBER_OF_NODES; i++) {
268 node u = graph.newNode();
269 edge e = graph.newEdge(v, u);
270 v = u;
271 isBridge[e] = true;
272 }
273
274 T emb(graph);
275
276 for(edge e : graph.edges) {
277 AssertThat(emb.isBridge(e), Equals(isBridge[e]));
278 }
279
280 graph.newEdge(v, chosenNode);
281 planarEmbed(graph);
282
283 emb.computeFaces();
284
285 for(edge e : graph.edges) {
286 AssertThat(emb.isBridge(e), IsFalse());
287 }
288 });
289
290 it("returns a sane size of its face array", [&] {
291 Graph graph;
292 randomPlanarTriconnectedGraph(graph, NUMBER_OF_NODES*10, NUMBER_OF_EDGES*10);
293 T emb(graph);
294 AssertThat(emb.faceArrayTableSize(), IsGreaterThan(emb.numberOfFaces() - 1));
295 });
296
297 for(int i = 1; i <= NUMBER_OF_ITERATIONS; i++) {
298 describe("iteration #" + to_string(i), [&] {
299 Graph graph;
300 randomPlanarConnectedGraph(graph, NUMBER_OF_NODES, NUMBER_OF_EDGES);
301 testConstCombinatorialEmbedding<T>(graph);
302 });
303 }
304}
305
306//! Performs single iteration of generic tests that modify the \c graph.
307void testCombinatorialEmbedding(Graph &graph) {
308 CombinatorialEmbedding emb(graph);
309 int numberOfNodes;
310 int numberOfEdges;
311 int numberOfFaces;
312
313 before_each([&] {
314 emb.computeFaces();
315 numberOfNodes = graph.numberOfNodes();
316 numberOfEdges = graph.numberOfEdges();
317 numberOfFaces = emb.numberOfFaces();
318 });
319
320 describe("updating", [&] {
321 it("clears itself",[&] {
322 emb.clear();
323
324 AssertThat(graph.numberOfNodes(), Equals(0));
325 AssertThat(graph.numberOfEdges(), Equals(0));
326 AssertThat(emb.numberOfFaces(), Equals(0));
327 });
328
329 it("adds edges to isolated nodes", [&] {
330 adjEntry adj = graph.chooseNode()->firstAdj();
331
332 face f = emb.rightFace(adj);
333 int size = f->size();
334
335 edge e = emb.addEdgeToIsolatedNode(graph.newNode(), adj);
336
337 AssertThat(emb.numberOfFaces(), Equals(numberOfFaces));
338 AssertThat(emb.rightFace(e->adjSource()), Equals(f));
339 AssertThat(emb.leftFace(e->adjSource()), Equals(f));
340 AssertThat(f->size(), Equals(size + 2));
341 });
342
343 it("splits an edge", [&] {
344 edge splitEdgeBeginning = graph.chooseEdge();
345 face leftFace = emb.leftFace(splitEdgeBeginning->adjSource());
346 int leftFaceSize = leftFace->size();
347 face rightFace = emb.rightFace(splitEdgeBeginning->adjSource());
348 int rightFaceSize = rightFace->size();
349
350 edge splitEdgeEnd = emb.split(splitEdgeBeginning);
351
352 AssertThat(graph.numberOfNodes(), Equals(numberOfNodes + 1));
353 AssertThat(graph.numberOfEdges(), Equals(numberOfEdges + 1));
354 AssertThat(emb.numberOfFaces(), Equals(numberOfFaces));
355 AssertThat(emb.leftFace(splitEdgeBeginning->adjSource()), Equals(leftFace));
356 AssertThat(emb.rightFace(splitEdgeBeginning->adjSource()), Equals(rightFace));
357 AssertThat(emb.leftFace(splitEdgeEnd->adjSource()), Equals(leftFace));
358 AssertThat(emb.rightFace(splitEdgeEnd->adjSource()), Equals(rightFace));
359
360 if(leftFace == rightFace) {
361 AssertThat(leftFace->size(), Equals(leftFaceSize + 2));
362 } else {
363 AssertThat(leftFace->size(), Equals(leftFaceSize + 1));
364 AssertThat(rightFace->size(), Equals(rightFaceSize + 1));
365 }
366 });
367
368 it("unsplits an edge", [&] {
369 edge splitEdgeBeginning = graph.chooseEdge();
370 face leftFace = emb.leftFace(splitEdgeBeginning->adjSource());
371 int leftFaceSize = leftFace->size();
372 face rightFace = emb.rightFace(splitEdgeBeginning->adjSource());
373 int rightFaceSize = rightFace->size();
374
375 edge splitEdgeEnd = emb.split(splitEdgeBeginning);
376 emb.unsplit(splitEdgeBeginning, splitEdgeEnd);
377
378 AssertThat(graph.numberOfNodes(), Equals(numberOfNodes));
379 AssertThat(graph.numberOfEdges(), Equals(numberOfEdges));
380 AssertThat(emb.numberOfFaces(), Equals(numberOfFaces));
381 AssertThat(leftFace->size(), Equals(leftFaceSize));
382 AssertThat(rightFace->size(), Equals(rightFaceSize));
383 });
384
385 auto pickNode = [&] {
386 for(node v : graph.nodes) {
387 if(v->degree() > 1) {
388 return v;
389 }
390 }
391 OGDF_ASSERT(false); // there should be a node with degree > 1
392 return node(nullptr);
393 };
394
395 it("splits a node", [&] {
396 node vl = pickNode();
397 int degree = vl->degree();
398 adjEntry adjStartLeft = vl->firstAdj();
399 adjEntry adjStartRight = vl->lastAdj();
400
401 node vr = emb.splitNode(adjStartLeft, adjStartRight);
402
403 AssertThat(graph.numberOfNodes(), Equals(numberOfNodes + 1));
404 AssertThat(graph.numberOfEdges(), Equals(numberOfEdges + 1));
405 AssertThat(vl->degree(), Equals(degree));
406 AssertThat(vr->degree(), Equals(2));
407 AssertThat(graph.searchEdge(vl, vr), !Equals(nullptr));
408 AssertThat(vl->firstAdj()->theEdge(), Equals(vr->firstAdj()->theEdge()));
409 });
410
411 it("contracts a node", [&] {
412 node vl = pickNode();
413 int degree = vl->degree();
414 adjEntry adjStartLeft = vl->firstAdj();
415 adjEntry adjStartRight = vl->lastAdj();
416 node vr = emb.splitNode(adjStartLeft, adjStartRight);
417
418 node contractedNode = emb.contract(graph.searchEdge(vl, vr));
419
420 AssertThat(graph.numberOfNodes(), Equals(numberOfNodes));
421 AssertThat(graph.numberOfEdges(), Equals(numberOfEdges));
422 AssertThat(contractedNode->degree(), Equals(degree));
423 });
424
425 it("reverses an edge", [&] {
426 edge e = graph.chooseEdge();
427 node src = e->source();
428 node tgt = e->target();
429 adjEntry adjSrc = e->adjSource();
430 face rightFace = emb.rightFace(adjSrc);
431 face leftFace = emb.leftFace(adjSrc);
432
433 emb.reverseEdge(e);
434
435 AssertThat(e->source(), Equals(tgt));
436 AssertThat(e->target(), Equals(src));
437 adjSrc = e->adjSource();
438 AssertThat(emb.rightFace(adjSrc), Equals(leftFace));
439 AssertThat(emb.leftFace(adjSrc), Equals(rightFace));
440 });
441
442 it("removes a degree-1 node", [&] {
443 node v = graph.newNode();
444 node w = graph.chooseNode([&](node u) { return u != v; });
445
446 graph.newEdge(w, v);
447 emb.computeFaces();
448
449 face f = emb.rightFace(v->firstAdj());
450 int size = f->size();
451
452 AssertThat(emb.leftFace(v->firstAdj()), Equals(f));
453
454 emb.removeDeg1(v);
455
456 AssertThat(emb.numberOfFaces(), Equals(numberOfFaces));
457 AssertThat(f->size(), Equals(size - 2));
458 });
459 });
460
461 describe("splitting faces", [&] {
462 int sizeOfFace;
463 face fSplitMe;
464 adjEntry adjFirst;
465 adjEntry adjSecond;
466
467 before_each([&](){
468 fSplitMe = emb.chooseFace([](face f) { return f->size() > 4; });
469 adjFirst = fSplitMe->firstAdj();
470 adjSecond = adjFirst->faceCycleSucc()->faceCycleSucc();
471 sizeOfFace = fSplitMe->size();
472 });
473
474 it("works given two adjacency entries", [&] {
475 edge e = emb.splitFace(adjFirst, adjSecond);
476
477 AssertThat(e, !Equals(nullptr));
478 AssertThat(e->source(), Equals(adjFirst->theNode()));
479 AssertThat(e->target(), Equals(adjSecond->theNode()));
480
481 face f = emb.leftFace(e->adjSource());
482 face g = emb.rightFace(e->adjSource());
483
484 AssertThat(f, !Equals(g));
485 AssertThat(fSplitMe, Equals(f) || Equals(g));
486
487 AssertThat(f->size(), Equals(3));
488 AssertThat(g->size(), Equals(sizeOfFace - 1));
489
490 AssertThat(emb.rightFace(adjFirst), Equals(f));
491 AssertThat(emb.rightFace(adjSecond), Equals(g));
492 });
493
494 it("works given a deg-0 node and an adjacency entry as target", [&] {
495 node v = graph.newNode();
496
497 edge e = emb.addEdgeToIsolatedNode(v, adjFirst);
498
499 AssertThat(e, !Equals(nullptr));
500 AssertThat(e->source(), Equals(v));
501 AssertThat(e->target(), Equals(adjFirst->theNode()));
502
503 AssertThat(fSplitMe->size(), Equals(sizeOfFace + 2));
504 AssertThat(emb.rightFace(e->adjSource()), Equals(fSplitMe));
505 AssertThat(emb.leftFace(e->adjSource()), Equals(fSplitMe));
506 });
507
508 it("works given an adjacency entry as source and a deg-0 node", [&] {
509 node v = graph.newNode();
510
511 edge e = emb.addEdgeToIsolatedNode(adjFirst, v);
512
513 AssertThat(e, !Equals(nullptr));
514 AssertThat(e->source(), Equals(adjFirst->theNode()));
515 AssertThat(e->target(), Equals(v));
516
517 AssertThat(fSplitMe->size(), Equals(sizeOfFace + 2));
518 AssertThat(emb.rightFace(e->adjSource()), Equals(fSplitMe));
519 AssertThat(emb.leftFace(e->adjSource()), Equals(fSplitMe));
520 });
521
522#ifdef OGDF_USE_ASSERT_EXCEPTIONS
523 it("rejects splitting given adjacency entries from different faces", [&] {
524 adjEntry v = graph.chooseEdge()->adjSource();
525 adjEntry w;
526
527 do {
528 w = graph.chooseEdge()->adjSource();
529 } while(emb.rightFace(v) == emb.rightFace(w) ||
530 emb.rightFace(v) == emb.leftFace(w) ||
531 emb.leftFace(v) == emb.rightFace(w) ||
532 emb.leftFace(v) == emb.leftFace(w));
533
534 AssertThrows(AssertionFailed, emb.splitFace(v, w));
535 });
536#endif
537
538 it("removes the edge when joining two faces", [&] {
539 int embNumberOfFaces = emb.numberOfFaces();
540 edge nonBridgeEdge = graph.chooseEdge([&](edge e) { return !emb.isBridge(e); });
541
542 face faceLeft = emb.leftFace(nonBridgeEdge->adjSource());
543 face faceRight = emb.rightFace(nonBridgeEdge->adjSource());
544
545 int sizeLeft = faceLeft->size();
546 int sizeRight = faceRight->size();
547
548 face jointFace = emb.joinFaces(nonBridgeEdge);
549
550 AssertThat(jointFace->size(), Equals(sizeLeft + sizeRight - 2));
551 AssertThat(emb.numberOfFaces(), Equals(embNumberOfFaces - 1));
552 });
553 });
554}
555
556go_bandit([] {
557 describe("ConstCombinatorialEmbedding", [&] {
558 testConstCombinatorialEmbedding<ConstCombinatorialEmbedding>();
559 });
560
561 describe("CombinatorialEmbedding", [&] {
562 for(int i = 1; i <= NUMBER_OF_ITERATIONS; i++) {
563 describe("iteration #" + to_string(i), [&] {
564 Graph graph;
565
566 before_each([&] {
567 randomPlanarConnectedGraph(graph, NUMBER_OF_NODES, NUMBER_OF_EDGES);
568 });
569
570 testCombinatorialEmbedding(graph);
571 });
572 }
573
574 testConstCombinatorialEmbedding<CombinatorialEmbedding>();
575 });
576});
577