1/** \file
2 * \brief Tests for the basic graph class
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 <ogdf/basic/Graph.h>
33#include <ogdf/basic/graph_generators.h>
34#include <resources.h>
35
36/**
37 * Returns an arbitrary edge where both nodes have at least \c minDegree incident edges.
38 * Requires the graph to contain at least one such edge.
39 *
40 * @param graph graph to investigate
41 * @param minDegree minimal number of incident edges
42 * @return the chosen edge
43 */
44edge chooseEdge(const Graph &graph, int minDegree) {
45 return graph.chooseEdge([&](edge e) { return e->source()->degree() >= minDegree && e->target()->degree() >= minDegree; });
46}
47
48/**
49 * Returns an arbitrary node with at least \c minDegree incident edges.
50 * Requires the graph to contain at least one such node.
51 *
52 * @param graph graph to investigate
53 * @param minDegree minimal number of incident edges
54 * @return the chosen node
55 */
56node chooseNode(const Graph &graph, int minDegree) {
57 return graph.chooseNode([&](node v) { return v->degree() >= minDegree; });
58}
59
60/**
61 * Returns an arbitrary node which does not equal \c v.
62 * Requires the graph to contain at least one such node.
63 *
64 * @param graph graph to investigate
65 * @param v the node to exclude from selection
66 * @return the chosen node
67 */
68node chooseNode(const Graph &graph, node v) {
69 return graph.chooseNode([&](node w) { return w != v; });
70}
71
72go_bandit([](){
73describe("Graph Class", [](){
74 std::vector<std::string> files = {"rome/grafo3703.45.lgr.gml.pun", "rome/grafo5745.50.lgr.gml.pun", "north/g.41.26.gml", "north/g.61.11.gml", "north/g.73.8.gml"};
75
76 it("is initialized correctly", [](){
77 Graph graph;
78
79 AssertThat(graph.empty(), IsTrue());
80 AssertThat(graph.numberOfNodes(), Equals(0));
81 AssertThat(graph.numberOfEdges(), Equals(0));
82 AssertThat(graph.maxNodeIndex(), IsLessThan(0));
83 AssertThat(graph.maxEdgeIndex(), IsLessThan(0));
84 AssertThat(graph.maxAdjEntryIndex(), IsLessThan(0));
85 AssertThat(graph.nodeArrayTableSize(), IsGreaterThan(0));
86 AssertThat(graph.edgeArrayTableSize(), IsGreaterThan(0));
87 AssertThat(graph.adjEntryArrayTableSize(), IsGreaterThan(0));
88 AssertThat(graph.firstNode(), IsNull());
89 AssertThat(graph.lastNode(), IsNull());
90 AssertThat(graph.firstEdge(), IsNull());
91 AssertThat(graph.lastEdge(), IsNull());
92 });
93
94 for_each_graph_it("finds an existing edge", files, [](Graph &graph){
95 edge e = graph.chooseEdge();
96 AssertThat(graph.searchEdge(e->source(), e->target()), Equals(e));
97 });
98
99 for_each_graph_it("returns the adjacency entries of an edge", files, [](Graph &graph){
100 edge e = graph.chooseEdge();
101 adjEntry adjSrc = e->adjSource();
102 adjEntry adjTgt = e->adjTarget();
103
104 AssertThat(adjSrc == adjTgt, IsFalse());
105 AssertThat(adjSrc->isSource(), IsTrue());
106 AssertThat(adjTgt->isSource(), IsFalse());
107 });
108
109 for_each_graph_it("finds a reverse edge", files, [](Graph &graph){
110 edge e = graph.chooseEdge();
111 AssertThat(graph.searchEdge(e->target(), e->source()), Equals(e));
112 });
113
114 for_each_graph_it("does not find non-existent edges", files, [](Graph &graph){
115 edge e = graph.chooseEdge();
116 node s = e->source();
117 node t = e->target();
118 graph.delEdge(e);
119 AssertThat(graph.searchEdge(s, t), IsNull());
120 });
121
122 for_each_graph_it("can be assigned", files, [](Graph &graph){
123 int m = graph.numberOfEdges();
124
125 int *degreeCounter = new int[m];
126
127 for(int i = 0; i < m; i++) {
128 degreeCounter[i] = 0;
129 }
130
131 for(node v : graph.nodes) {
132 degreeCounter[v->degree()]++;
133 }
134
135 Graph copy = graph;
136
137 AssertThat(copy.numberOfNodes(), Equals(graph.numberOfNodes()));
138 AssertThat(copy.numberOfEdges(), Equals(m));
139
140 for(node v : copy.nodes) {
141 degreeCounter[v->degree()]--;
142 }
143
144 for(node v : graph.nodes) {
145 AssertThat(degreeCounter[v->degree()], Equals(0));
146 }
147
148 delete[] degreeCounter;
149 });
150
151 it("maintains the adjacency order at nodes with self-loops", [] {
152 Graph graph;
153 node v = graph.newNode();
154 List<adjEntry> entries;
155
156 for(int i = 0; i < 2; i++) {
157 edge e = graph.newEdge(v, v);
158 entries.pushBack(e->adjTarget());
159 entries.pushBack(e->adjSource());
160 }
161
162 graph.sort(v, entries);
163 Graph copy(graph);
164
165 for (adjEntry adj : copy.firstNode()->adjEntries) {
166 edge e = adj->theEdge();
167 adjEntry succ = adj->cyclicSucc();
168 edge eSucc = succ->theEdge();
169
170 bool isSourceAdj = adj == e->adjSource();
171
172 AssertThat(e != eSucc, Equals(isSourceAdj));
173
174 if (isSourceAdj) {
175 AssertThat(succ == eSucc->adjTarget(), IsTrue());
176 } else {
177 AssertThat(succ == e->adjSource(), IsTrue());
178 }
179 }
180 });
181
182 it("adds nodes", [](){
183 Graph graph;
184 const int numberOfNodes = 100;
185 emptyGraph(graph,numberOfNodes);
186
187 AssertThat(graph.empty(), IsFalse());
188 AssertThat(graph.numberOfNodes(), Equals(numberOfNodes));
189 AssertThat(graph.numberOfEdges(), Equals(0));
190 AssertThat(graph.maxNodeIndex(), IsGreaterThan(numberOfNodes - 2));
191 AssertThat(graph.firstNode(), !IsNull());
192 AssertThat(graph.lastNode(), !IsNull());
193
194 int maxIndex = graph.maxNodeIndex();
195 bool *visited = new bool[maxIndex + 1];
196
197 for(int i = 0; i <= maxIndex; i++) {
198 visited[i] = false;
199 }
200
201 int count = 0;
202
203 for(node v : graph.nodes) {
204 int index = v->index();
205 AssertThat(index, IsGreaterThan(-1));
206 AssertThat(index, IsLessThan(maxIndex + 1));
207 AssertThat(visited[index], IsFalse());
208 visited[index] = true;
209 count++;
210 }
211
212 AssertThat(count, Equals(numberOfNodes));
213
214 delete[] visited;
215 });
216
217 it("adds edges", [](){
218 Graph graph;
219 emptyGraph(graph, 100);
220
221 int count = 0;
222
223 for(node v : graph.nodes) {
224 for(node w : graph.nodes) {
225 if((v->index() + w->index()) % 3 == 0) {
226 graph.newEdge(v, w);
227 count++;
228 }
229 }
230 }
231
232 AssertThat(graph.numberOfEdges(), Equals(count));
233 AssertThat(graph.maxEdgeIndex(), IsGreaterThan(count - 2));
234 AssertThat(graph.maxAdjEntryIndex(), IsGreaterThan(count - 2));
235 AssertThat(graph.firstEdge(), !IsNull());
236 AssertThat(graph.lastEdge(), !IsNull());
237
238 int maxIndex = graph.maxEdgeIndex();
239 bool *visited = new bool[maxIndex + 1];
240
241 for(int i = 0; i <= maxIndex; i++) {
242 visited[i] = false;
243 }
244
245 int iterCount = 0;
246
247 for(edge e : graph.edges) {
248 int index = e->index();
249 AssertThat(index, IsGreaterThan(-1));
250 AssertThat(index, IsLessThan(maxIndex + 1));
251 AssertThat(visited[index], IsFalse());
252 visited[index] = true;
253 iterCount++;
254 }
255
256 AssertThat(iterCount, Equals(count));
257
258 delete[] visited;
259 });
260
261 it("doesn't duplicate self-loops", [](){
262 Graph graph;
263
264 node v = graph.newNode();
265 graph.newEdge(v, v);
266
267 List<edge> edges;
268 v->adjEdges(edges);
269 AssertThat(edges.size(), Equals(2));
270 v->inEdges(edges);
271 AssertThat(edges.size(), Equals(1));
272 v->outEdges(edges);
273 AssertThat(edges.size(), Equals(1));
274 });
275
276 for_each_graph_it("removes a node", files, [](Graph &graph){
277 int n = graph.numberOfNodes();
278 int m = graph.numberOfEdges();
279
280 node v = graph.chooseNode();
281 int deg = v->degree();
282
283 graph.delNode(v);
284
285 AssertThat(graph.numberOfNodes(), Equals(n - 1));
286 AssertThat(graph.numberOfEdges(), Equals(m - deg));
287 });
288
289 for_each_graph_it("removes an edge", files, [](Graph &graph){
290 int n = graph.numberOfNodes();
291 int m = graph.numberOfEdges();
292
293 edge e = graph.chooseEdge();
294 node s = e->source();
295 node t = e->target();
296
297 graph.delEdge(e);
298
299 AssertThat(graph.searchEdge(s, t), IsNull());
300 AssertThat(graph.numberOfNodes(), Equals(n));
301 AssertThat(graph.numberOfEdges(), Equals(m - 1));
302 });
303
304 for_each_graph_it("can be cleared", files, [](Graph &graph){
305 graph.clear();
306
307 AssertThat(graph.empty(), IsTrue());
308 AssertThat(graph.numberOfNodes(), Equals(0));
309 AssertThat(graph.numberOfEdges(), Equals(0));
310 });
311
312 for_each_graph_it("hides an edge and restores it", files, [](Graph &graph){
313 int n = graph.numberOfNodes();
314 int m = graph.numberOfEdges();
315
316 edge e = graph.chooseEdge();
317 Graph::HiddenEdgeSet set(graph);
318 set.hide(e);
319
320 AssertThat(set.size(), Equals(1));
321 AssertThat(graph.numberOfNodes(), Equals(n));
322 AssertThat(graph.numberOfEdges(), Equals(m - 1));
323 AssertThat(graph.searchEdge(e->source(), e->target()), IsNull());
324
325 set.restore(e);
326
327 AssertThat(set.size(), Equals(0));
328 AssertThat(graph.numberOfEdges(), Equals(m));
329 AssertThat(graph.searchEdge(e->source(), e->target()), Equals(e));
330 });
331
332 for_each_graph_it("restores all hidden edges", files, [](Graph &graph){
333 int m = graph.numberOfEdges();
334 Graph::HiddenEdgeSet set(graph);
335
336 // this should not change anything
337 set.restore();
338
339 for(int i = 0; i < m / 2; i++) {
340 set.hide(graph.chooseEdge());
341 }
342
343 AssertThat(set.size(), Equals(m / 2));
344 AssertThat(graph.numberOfEdges(), Equals(m - m / 2));
345 set.restore();
346 AssertThat(set.size(), Equals(0));
347 AssertThat(graph.numberOfEdges(), Equals(m));
348 });
349
350 for_each_graph_it("hides all edges across 10 sets", files, [](Graph &graph){
351 int m = graph.numberOfEdges();
352 int maxIndex = graph.maxNodeIndex();
353
354 int *inDeg = new int[maxIndex + 1];
355 int *outDeg = new int[maxIndex + 1];
356
357 for(node v : graph.nodes) {
358 inDeg[v->index()] = v->indeg();
359 outDeg[v->index()] = v->outdeg();
360 }
361
362 List<Graph::HiddenEdgeSet*> sets;
363
364 for(int i = 0; i < 10; i++) {
365 sets.pushFront(new Graph::HiddenEdgeSet(graph));
366
367 for(int k = 0; k < m / 10; k++) {
368 sets.front()->hide(graph.chooseEdge());
369 }
370 }
371
372 sets.permute();
373
374 while(graph.numberOfEdges() > 0) {
375 sets.front()->hide(graph.chooseEdge());
376 }
377
378 for(node v : graph.nodes) {
379 AssertThat(v->indeg(), Equals(0));
380 AssertThat(v->outdeg(), Equals(0));
381 }
382
383 for(Graph::HiddenEdgeSet *set : sets) {
384 // restore edges by deleting the set
385 delete set;
386 }
387
388 AssertThat(graph.numberOfEdges(), Equals(m));
389
390 for(node v : graph.nodes) {
391 AssertThat(v->indeg(), Equals(inDeg[v->index()]));
392 AssertThat(v->outdeg(), Equals(outDeg[v->index()]));
393 }
394
395 delete[] inDeg;
396 delete[] outDeg;
397 });
398
399 for_each_graph_it("restores edges upon graph destruction", files, [](Graph &graph) {
400 GraphCopy *copy = new GraphCopy(graph);
401 Graph::HiddenEdgeSet set(*copy);
402 set.hide(copy->chooseEdge());
403 delete copy;
404 AssertThat(set.size(), Equals(0));
405 });
406
407#ifdef OGDF_USE_ASSERT_EXCEPTIONS
408 for_each_graph_it("doesn't hide edges of other graphs", files, [](Graph &graph) {
409 GraphCopy copy(graph);
410 Graph::HiddenEdgeSet set(copy);
411 AssertThrows(AssertionFailed, set.hide(graph.chooseEdge()));
412
413 });
414
415 for_each_graph_it("doesn't restore a non-hidden edge", files, [](Graph &graph) {
416 Graph::HiddenEdgeSet set(graph);
417 AssertThrows(AssertionFailed, set.restore(graph.chooseEdge()));
418 });
419
420 for_each_graph_it("doesn't hide an edge twice", files, [](Graph &graph) {
421 Graph::HiddenEdgeSet set(graph);
422 edge e = graph.chooseEdge();
423 set.hide(e);
424 AssertThrows(AssertionFailed, set.hide(e));
425 });
426
427 for_each_graph_it("doesn't restore an edge twice", files, [](Graph &graph) {
428 Graph::HiddenEdgeSet set(graph);
429 edge e = graph.chooseEdge();
430 set.hide(e);
431 set.restore(e);
432 AssertThrows(AssertionFailed, set.restore(e));
433 });
434#endif
435
436 for_each_graph_it("reverses an edge", files, [](Graph &graph){
437 edge e = chooseEdge(graph, 5);
438 node s = e->source();
439 node t = e->target();
440
441 int inT = t->indeg();
442 int outT = t->outdeg();
443
444 int inS = s->indeg();
445 int outS = s->outdeg();
446
447 graph.reverseEdge(e);
448
449 AssertThat(e->source(), Equals(t));
450 AssertThat(e->target(), Equals(s));
451 AssertThat(e->source()->degree(), Equals(inT + outT));
452 AssertThat(e->target()->degree(), Equals(inS + outS));
453 AssertThat(e->source()->indeg(), Equals(inT - 1));
454 AssertThat(e->source()->outdeg(), Equals(outT + 1));
455 });
456
457 for_each_graph_it("reverses all edges", files, [](Graph &graph){
458 int maxIndex = graph.maxEdgeIndex();
459 node *sources = new node[maxIndex + 1];
460 node *targets = new node[maxIndex + 1];
461
462 for(int i = 0; i <= maxIndex; i++) {
463 sources[i] = targets[i] = nullptr;
464 }
465
466 for(edge e : graph.edges) {
467 sources[e->index()] = e->source();
468 targets[e->index()] = e->target();
469 }
470
471 graph.reverseAllEdges();
472
473 for(edge e : graph.edges) {
474 AssertThat(e->source(), Equals(targets[e->index()]));
475 AssertThat(e->target(), Equals(sources[e->index()]));
476 }
477
478 delete[] sources;
479 delete[] targets;
480 });
481
482 for_each_graph_it("moves an adjacency entry", files, [](Graph &graph){
483 adjEntry adj = chooseEdge(graph, 5)->adjSource();
484 adjEntry adjSucc = adj->cyclicSucc();
485
486 graph.moveAdj(adj, Direction::after, adjSucc);
487
488 AssertThat(adjSucc->cyclicSucc(), Equals(adj));
489 AssertThat(adj->cyclicSucc(), Is().Not().EqualTo(adjSucc));
490
491 graph.moveAdj(adj, Direction::before, adjSucc);
492
493 AssertThat(adj->cyclicSucc(), Equals(adjSucc));
494 AssertThat(adjSucc->cyclicSucc(), Is().Not().EqualTo(adj));
495 });
496
497 for_each_graph_it("swaps the target of an edge", files, [](Graph &graph){
498 edge e = graph.chooseEdge();
499 node s = e->source();
500 node t = e->target();
501
502 node v = chooseNode(graph, t);
503
504 graph.moveTarget(e, v);
505
506 AssertThat(e->source(), Equals(s));
507 AssertThat(e->target(), Equals(v));
508 });
509
510 for_each_graph_it("swaps the source of an edge", files, [](Graph &graph){
511 edge e = graph.chooseEdge();
512 node s = e->source();
513 node t = e->target();
514
515 node v = chooseNode(graph, s);
516
517 graph.moveSource(e, v);
518
519 AssertThat(e->source(), Equals(v));
520 AssertThat(e->target(), Equals(t));
521 });
522
523 for_each_graph_it("splits an edge", files, [](Graph &graph){
524 int n = graph.numberOfNodes();
525 int m = graph.numberOfEdges();
526
527 edge e = graph.chooseEdge();
528 node v = e->target();
529
530 edge f = graph.split(e);
531
532 AssertThat(f->source(), Equals(e->target()));
533 AssertThat(f->target(), Equals(v));
534 AssertThat(f->source()->degree(), Equals(2));
535 AssertThat(graph.numberOfNodes(), Equals(n + 1));
536 AssertThat(graph.numberOfEdges(), Equals(m + 1));
537 });
538
539 for_each_graph_it("un-splits an edge by dummy-node", files, [](Graph &graph){
540 int n = graph.numberOfNodes();
541 int m = graph.numberOfEdges();
542
543 edge e = graph.chooseEdge();
544 node s = e->source();
545 node t = e->target();
546
547 graph.split(e);
548
549 node v = e->target();
550
551 graph.unsplit(v);
552
553 AssertThat(graph.numberOfNodes(), Equals(n));
554 AssertThat(graph.numberOfEdges(), Equals(m));
555 AssertThat(e->source(), Equals(s));
556 AssertThat(e->target(), Equals(t));
557 AssertThat(graph.searchEdge(s, t), Equals(e));
558 });
559
560 for_each_graph_it("un-splits an edge by dummy-edge", files, [](Graph &graph){
561 int n = graph.numberOfNodes();
562 int m = graph.numberOfEdges();
563
564 edge e = graph.chooseEdge();
565 node s = e->source();
566 node t = e->target();
567
568 edge f = graph.split(e);
569 graph.unsplit(e, f);
570
571 AssertThat(graph.numberOfNodes(), Equals(n));
572 AssertThat(graph.numberOfEdges(), Equals(m));
573 AssertThat(e->source(), Equals(s));
574 AssertThat(e->target(), Equals(t));
575 AssertThat(graph.searchEdge(s, t), Equals(e));
576 });
577
578 for_each_graph_it("splits nodes", files, [](Graph &graph){
579 node vLeft = chooseNode(graph, 6);
580
581 int degree = vLeft->degree();
582 List<adjEntry> entries;
583 vLeft->allAdjEntries(entries);
584 adjEntry adjFirstRight = *entries.get(degree / 2);
585 node vRight = graph.splitNode(vLeft->firstAdj(), adjFirstRight);
586 int count = 0;
587
588 for(adjEntry adj = vLeft->firstAdj()->succ(); adj != nullptr; adj = adj->succ()) {
589 AssertThat(adj, Equals(*entries.get(count++)));
590 }
591
592 for(adjEntry adj = vRight->firstAdj()->succ(); adj != nullptr; adj = adj->succ()) {
593 AssertThat(adj, Equals(*entries.get(count++)));
594 }
595
596 AssertThat(count, Equals(degree));
597 AssertThat(vLeft->degree() + vRight->degree(), Equals(degree + 2));
598 });
599
600 for_each_graph_it("contracts an edge", files, [](Graph &graph){
601 edge e = chooseEdge(graph, 5);
602 node s = e->source();
603 node t = e->target();
604
605 // create the list of expected adjacency order
606 List<node> nodes;
607 List<edge> edges;
608 s->adjEdges(edges);
609
610 for(edge f : edges) {
611 nodes.pushBack(f->opposite(s));
612 }
613
614 // to prevent ambiguity, delete would-be multi-edges
615 List<edge> deleteMe;
616 t->adjEdges(edges);
617 ListIterator<node> it = nodes.search(t);
618
619 while(edges.front() != e) {
620 edges.moveToBack(edges.begin());
621 }
622
623 edges.del(edges.begin());
624
625 for(edge f : edges) {
626 if(nodes.search(f->opposite(t)).valid()) {
627 deleteMe.pushBack(f);
628 } else {
629 nodes.insertBefore(f->opposite(t), it);
630 }
631 }
632
633 nodes.del(it);
634
635 for(edge f : deleteMe) {
636 graph.delEdge(f);
637 }
638
639 node v = graph.contract(e);
640 edge f = graph.searchEdge(v, nodes.front());
641
642 AssertThat(v == t || v == s, IsTrue());
643 AssertThat(v->degree(), Equals(nodes.size()));
644 AssertThat(f, !IsNull());
645
646 adjEntry adj = f->source() == v ? f->adjSource() : f->adjTarget();
647 for(node w : nodes) {
648 AssertThat(adj->twinNode(), Equals(w));
649 adj = adj->cyclicSucc();
650 }
651
652 });
653
654 for_each_graph_it("collapses half of all nodes", files, [](Graph &graph){
655 int m = graph.numberOfEdges();
656
657 List<node> nodes;
658 int maxIndex = graph.maxNodeIndex();
659 bool *adjacent = new bool[maxIndex + 1];
660
661 for(int i = 0; i <= maxIndex; i++) {
662 adjacent[i] = false;
663 }
664
665 for(node v : graph.nodes) {
666 if(v->index() % 2) {
667 nodes.pushBack(v);
668 }
669 }
670
671 int minRemoved = 0;
672 for(edge e : graph.edges) {
673 int target = e->target()->index();
674 int source = e->source()->index();
675
676 if(source % 2 && target % 2 == 0) {
677 adjacent[target] = true;
678 }
679
680 if(source % 2 == 0 && target % 2) {
681 adjacent[source] = true;
682 }
683
684 minRemoved += source % 2 && target % 2;
685 }
686
687 node v = nodes.front();
688 graph.collapse(nodes);
689
690 AssertThat(nodes.empty(), IsTrue());
691 AssertThat(graph.numberOfEdges(), IsLessThan(1 + m - minRemoved));
692
693 for(adjEntry adj = v->firstAdj(); adj != nullptr; adj = adj->succ()) {
694 adjacent[adj->twinNode()->index()] = false;
695 }
696
697 for(int i = 0; i <= maxIndex; i++) {
698 AssertThat(adjacent[i], IsFalse());
699 }
700
701 delete[] adjacent;
702 });
703
704 for_each_graph_it("sorts adjacency lists", files, [](Graph &graph){
705 node v = chooseNode(graph, 6);
706
707 List<adjEntry> entries;
708 v->allAdjEntries(entries);
709
710 entries.permute();
711
712 graph.sort(v, entries);
713
714 AssertThat(v->firstAdj(), Equals(entries.front()));
715 AssertThat(v->lastAdj(), Equals(entries.back()));
716
717 adjEntry adjBefore = nullptr;
718 for(adjEntry adj : entries) {
719 if(adjBefore != nullptr) {
720 AssertThat(adjBefore->succ(), Equals(adj));
721 AssertThat(adj->pred(), Equals(adjBefore));
722 }
723
724 adjBefore = adj;
725 }
726 });
727
728 for_each_graph_it("reverses the order of all edges adjacent to a given node", files, [](Graph &graph){
729 node v = chooseNode(graph, 6);
730 List<edge> edges;
731 v->adjEdges(edges);
732
733 graph.reverseAdjEdges(v);
734 edges.reverse();
735
736 adjEntry adj = v->firstAdj();
737 for(edge e : edges) {
738 AssertThat(adj, !IsNull());
739 AssertThat(adj->theEdge(), Equals(e));
740
741 adj = adj->succ();
742 }
743 });
744
745 for_each_graph_it("swaps adjacency entries", files, [](Graph &graph){
746 edge e = chooseEdge(graph, 5);
747 adjEntry adj = e->adjSource()->cyclicSucc()->cyclicSucc();
748
749 graph.swapAdjEdges(e->adjSource(), adj);
750
751 AssertThat(adj->cyclicSucc()->cyclicSucc(), Equals(e->adjSource()));
752 AssertThat(e->adjSource()->cyclicSucc()->cyclicSucc(), Is().Not().EqualTo(adj));
753 });
754
755 for_each_graph_it("does not return a negative genus", files, [](Graph &graph){
756 AssertThat(graph.genus(), IsGreaterThan(-1));
757 });
758
759 for_each_graph_it("detects a combinatorial embedding", files, [](Graph &graph){
760 AssertThat(graph.representsCombEmbedding(), Equals(graph.genus() == 0));
761 });
762
763 for_each_graph_it("returns wether an adjacency entry lies between two others", files, [](Graph &graph) {
764 node v = graph.newNode();
765
766 while(graph.numberOfNodes() < 12) {
767 graph.newNode();
768 }
769
770 int n = graph.numberOfNodes();
771 int count = 0;
772 adjEntry adjs[3];
773
774 // Add new edge for every third node.
775 // Pick 3 adjacency entries from the first, second, and last third.
776 for(node w : graph.nodes) {
777 if (count % 3 == 0) {
778 adjs[(count*3)/n] = graph.newEdge(v, w)->adjSource();
779 }
780
781 count++;
782 }
783
784 AssertThat(adjs[0]->isBetween(adjs[2], adjs[1]), IsTrue());
785 AssertThat(adjs[0]->isBetween(adjs[1], adjs[2]), IsFalse());
786
787 AssertThat(adjs[1]->isBetween(adjs[0], adjs[2]), IsTrue());
788 AssertThat(adjs[1]->isBetween(adjs[2], adjs[0]), IsFalse());
789
790 AssertThat(adjs[2]->isBetween(adjs[1], adjs[0]), IsTrue());
791 AssertThat(adjs[2]->isBetween(adjs[0], adjs[1]), IsFalse());
792 });
793
794 for_each_graph_it("returns the adjacency entry of an edge", files, [](Graph &graph) {
795 node v = graph.chooseNode();
796
797 for(adjEntry adj : v->adjEntries) {
798 edge e = adj->theEdge();
799
800 adjEntry adj2 = e->getAdj(v);
801
802 AssertThat(adj2->theNode(), Equals(v));
803 AssertThat(adj2->theEdge(), Equals(e));
804
805 if(!e->isSelfLoop()) {
806 AssertThat(adj2, Equals(adj));
807 }
808 }
809 });
810});
811});
812