1#include <set>
2#include <ogdf/basic/Array.h>
3#include <ogdf/basic/Graph.h>
4#include <ogdf/basic/graph_generators.h>
5#include <ogdf/basic/simple_graph_alg.h>
6
7#include <testing.h>
8
9/**
10 * Assert that there is a one-to-one mapping of values in assignedVals to values
11 * in expectedVals, e.g. [3,1,1,2,0,3,1] <=> [2,0,0,3,1,2,0].
12 * @tparam ArrayType is the type of assignedVals.
13 *
14 * @param assignedVals is the first array.
15 * @param expVals is an initializer list with values for the second array.
16 */
17template<template<typename> class ArrayType>
18void bijectiveMappingAssert(ArrayType<int> assignedVals, std::initializer_list<int> expVals)
19{
20 std::set<int> expSet(expVals);
21 int size = expSet.size();
22 Array<int> expectedVals(expVals);
23
24 Array<int> expToAssign(0, size-1, -1);
25 Array<int> assignToExp(0, size-1, -1);
26
27 int i = 0;
28 for (int assigned : assignedVals) {
29 int expected = expectedVals[i++];
30
31 AssertThat(assigned, IsGreaterThan(-1));
32
33 if (expToAssign[expected] == -1) {
34 AssertThat(assignToExp[assigned], Equals(-1));
35 expToAssign[expected] = assigned;
36 assignToExp[assigned] = expected;
37 } else {
38 AssertThat(assigned, Equals(expToAssign[expected]));
39 AssertThat(expected, Equals(assignToExp[assigned]));
40 }
41 }
42}
43
44/**
45 * Assert that calling biconnectedComponents() on G returns the correct number
46 * of biconnected components and assigns the edges the correct biconnected
47 * component ids. The exptected ids can differ from the assigned ids in value as
48 * long as there is a one-to-one mapping of expected ids to assigned ids.
49 *
50 * @param G is the graph to be tested.
51 * @param expCount is the expected number of biconnected components.
52 * @param expectedComps is the expected biconnected component id for each edge.
53 */
54void biconnectedComponentsAssert(Graph &G, int expCount, std::initializer_list<int> expectedComps)
55{
56 EdgeArray<int> comps(G,-1);
57 int nonEmptyBiComps;
58 AssertThat(biconnectedComponents(G, comps, nonEmptyBiComps), Equals(expCount));
59
60 bijectiveMappingAssert(comps, expectedComps);
61
62 // nonEmptyBiComps-1 should be equal to max(component).
63 int maxUsedIndex = 0;
64 for (int c: comps) {
65 maxUsedIndex = std::max(maxUsedIndex, c);
66 }
67 AssertThat(maxUsedIndex, Equals(nonEmptyBiComps - 1));
68}
69
70/**
71 * Assert that calling strongComponents() on G returns the correct number
72 * of strong components and assigns the nodes the correct strong component ids.
73 * The exptected ids can differ from the assigned ids in value as long as there
74 * is a one-to-one mapping of expected ids to assigned ids.
75 *
76 * @param G is the graph to be tested.
77 * @param expectedComps is the expected strong component id for each node.
78 */
79void strongComponentsAssert(Graph &G, std::initializer_list<int> expectedComps)
80{
81 std::set<int> expSet(expectedComps);
82 int expCount = expSet.size();
83 NodeArray<int> comps(G,-1);
84 AssertThat(strongComponents(G, comps), Equals(expCount));
85 bijectiveMappingAssert(comps, expectedComps);
86}
87
88/**
89 * Assert that isAcylic()/isAcyclicUndirected() returns the correct value and
90 * that the list of collected backedges is filled correctly. For cyclic graphs
91 * assert that removing all backedges makes the graph acyclic but maintains
92 * connectivity.
93 *
94 * @param G is the graph to be tested.
95 * @param directed sets whether isAcyclic() or isAcyclicUndirected() is tested.
96 * @param expected is the expected result of the function call.
97 */
98void isAcyclicAssert(Graph &G, bool directed, bool expected)
99{
100 List<edge> backedges;
101 bool result = directed ?
102 isAcyclic(G, backedges) : isAcyclicUndirected(G, backedges);
103
104 if (expected) {
105 AssertThat(result, IsTrue());
106 AssertThat(backedges.empty(), IsTrue());
107 } else {
108 AssertThat(result, IsFalse());
109 AssertThat(backedges.size(), IsGreaterThan(0));
110 AssertThat(backedges.size(), IsLessThan(G.numberOfEdges() + 1));
111
112 bool connected = isConnected(G);
113
114 for (edge e : backedges) {
115 G.delEdge(e);
116 }
117
118 result = directed ?
119 isAcyclic(G, backedges) : isAcyclicUndirected(G, backedges);
120 AssertThat(result, IsTrue());
121 AssertThat(backedges.empty(), IsTrue());
122 AssertThat(isConnected(G), Equals(connected));
123 }
124}
125
126/**
127 * Perform tests for isAcylic() or isAcyclicUndirected().
128 *
129 * @param directed sets whether isAcyclic() or isAcyclicUndirected() is tested.
130 */
131void describeIsAcyclic(bool directed)
132{
133 Graph G;
134
135 before_each([&](){
136 G.clear();
137 });
138
139 it("works on an empty graph", [&](){
140 emptyGraph(G, 0);
141 isAcyclicAssert(G, directed, true);
142 });
143
144 it("works on a graph with a single node", [&](){
145 G.newNode();
146 isAcyclicAssert(G, directed, true);
147 });
148
149 it("works on a graph with a self-loop", [&](){
150 customGraph(G, 1, {{0,0}});
151 isAcyclicAssert(G, directed, false);
152 });
153
154 it("works on a graph with parallel edges", [&](){
155 customGraph(G, 2, {{0,1}, {1,0}});
156 isAcyclicAssert(G, directed, false);
157 });
158
159 it("works on an acylic graph", [&](){
160 customGraph(G, 3, {{0,1}, {0,2}});
161 isAcyclicAssert(G, directed, true);
162 });
163
164 it("works on a cyclic graph", [&](){
165 customGraph(G, 3, {{0,1}, {1,2}, {2,1}});
166 isAcyclicAssert(G, directed, false);
167 });
168
169 it("works on a disconnected acyclic graph", [&](){
170 customGraph(G, 4, {{1,2}, {1,3}});
171 isAcyclicAssert(G, directed, true);
172 });
173
174 it("works on a disconnected cyclic graph", [&](){
175 customGraph(G, 4, {{1,2}, {2,3}, {3,1}});
176 isAcyclicAssert(G, directed, false);
177 });
178
179 it("works on an acyclic graph requiring multiple dfs starts if directed", [&](){
180 customGraph(G, 4, {{0,1}, {1,2}, {3,1}});
181 isAcyclicAssert(G, directed, true);
182 });
183
184 it("works on a cyclic graph requiring multiple dfs starts if directed", [&](){
185 customGraph(G, 4, {{0,1}, {1,2}, {2,0}, {3,1}});
186 isAcyclicAssert(G, directed, false);
187 });
188
189 it("works on a directed acyclic but undirected cyclic graph", [&](){
190 customGraph(G, 3, {{0,1}, {0,2}, {1,2}});
191 isAcyclicAssert(G, directed, directed);
192 });
193
194 it("works on an extremely large acyclic graph", [&](){
195 randomTree(G, 125000, 1, 0);
196 isAcyclicAssert(G, directed, true);
197 });
198
199 it("works on an extremely large cyclic graph", [&](){
200 randomBiconnectedGraph(G, 125000, 250000);
201 isAcyclicAssert(G, directed, false);
202 });
203}
204
205go_bandit([]() {
206 describe("Simple Graph Algorithms", [](){
207 describe("isTwoEdgeConnected", [](){
208 it("works on an empty graph", [&](){
209 Graph G;
210 AssertThat(isTwoEdgeConnected(G), IsTrue());
211 });
212
213 it("works on a graph with one node", [&](){
214 Graph G;
215 G.newNode();
216 AssertThat(isTwoEdgeConnected(G), IsTrue());
217 });
218
219 it("works on a graph with two nodes", [&](){
220 Graph G;
221 customGraph(G, 2, {{0,1}});
222 AssertThat(isTwoEdgeConnected(G), IsFalse());
223 });
224
225 it("works on a disconnected graph", [&](){
226 Graph G;
227 customGraph(G, 5, {{0,1},{0,2},{1,2},{3,4}});
228 edge bridge = G.chooseEdge();
229 AssertThat(isTwoEdgeConnected(G, bridge), IsFalse());
230 AssertThat(bridge, Equals(nullptr));
231 });
232
233 it("works on a tree", [&](){
234 Graph G;
235 customGraph(G, 5, {{0,1},{1,2},{1,3},{3,4}});
236 edge bridge = nullptr;
237 AssertThat(isTwoEdgeConnected(G, bridge), IsFalse());
238 AssertThat(bridge, !Equals(nullptr));
239 });
240
241 it("works on a connected but not two-edge-connected graph", [&](){
242 Graph G;
243 Array<node> nodes;
244 customGraph(G, 7, {
245 {0,1},{0,2},{1,2},{3,4},{4,5},{5,6},{6,2},{6,3}
246 }, nodes);
247 node v = nodes[6];
248 node u = nodes[2];
249 edge e = G.searchEdge(u,v);
250 edge bridge = nullptr;
251 AssertThat(isTwoEdgeConnected(G, bridge), IsFalse());
252 AssertThat(bridge, Equals(e));
253 });
254
255 it("works on a triangle", [&](){
256 Graph G;
257 customGraph(G, 3, {{0,1},{1,2},{2,0}});
258 edge bridge = G.chooseEdge();
259 AssertThat(isTwoEdgeConnected(G, bridge), IsTrue());
260 AssertThat(bridge, Equals(nullptr));
261 });
262
263 it("works on an extremely large tree", [&](){
264 Graph G;
265 randomTree(G, 250000);
266 AssertThat(isTwoEdgeConnected(G), IsFalse());
267 });
268
269 it("works on an extremely large 2-edge-connected graph", [&](){
270 Graph G;
271 randomBiconnectedGraph(G, 250000, 500000);
272 AssertThat(isTwoEdgeConnected(G), IsTrue());
273 });
274
275 it("works with selfloops", [&](){
276 Graph G;
277 customGraph(G, 1, {{0,0}});
278 AssertThat(isTwoEdgeConnected(G), IsTrue());
279 });
280
281 it("works with multiedges", [&](){
282 Graph G;
283 customGraph(G, 2, {{0,1},{0,1}});
284 AssertThat(isTwoEdgeConnected(G), IsTrue());
285 });
286 });
287
288 describe("isBiconnected", [](){
289 Graph G;
290 node cutVertex;
291
292 before_each([&](){
293 G.clear();
294 cutVertex = nullptr;
295 });
296
297 it("works on an empty graph", [&](){
298 AssertThat(isBiconnected(G), IsTrue());
299 });
300
301 it("works on a graph with one node", [&](){
302 G.newNode();
303 AssertThat(isBiconnected(G), IsTrue());
304 });
305
306 it("works on a path of two nodes", [&](){
307 customGraph(G, 2, {{0,1}});
308 AssertThat(isBiconnected(G), IsTrue());
309 });
310
311 it("works on a disconnected graph", [&](){
312 customGraph(G, 3, {{0,1}});
313 AssertThat(isBiconnected(G, cutVertex), IsFalse());
314 AssertThat(cutVertex, Equals(nullptr));
315 });
316
317 it("works on a connected but not biconnected graph", [&](){
318 customGraph(G, 3, {{0,1}, {0,2}});
319 AssertThat(isBiconnected(G, cutVertex), IsFalse());
320 AssertThat(cutVertex, Equals(G.firstNode()));
321 });
322
323 it("works on a simple biconnected graph", [&](){
324 completeGraph(G, 3);
325 AssertThat(isBiconnected(G, cutVertex), IsTrue());
326 AssertThat(cutVertex, Equals(nullptr));
327 });
328
329 it("works on an extremely large tree", [&](){
330 randomTree(G, 250000);
331 AssertThat(isBiconnected(G), IsFalse());
332 });
333
334 it("works on an extremely large biconnected graph", [&](){
335 randomBiconnectedGraph(G, 250000, 500000);
336 AssertThat(isBiconnected(G), IsTrue());
337 });
338 });
339
340 describe("makeBiconnected", [](){
341 Graph G;
342 List<edge> added;
343
344 before_each([&](){
345 G.clear();
346 added.clear();
347 });
348
349 it("works on a disconnected graph", [&](){
350 customGraph(G, 3, {{0,1}});
351 makeBiconnected(G, added);
352 AssertThat(isBiconnected(G), IsTrue());
353 AssertThat(added.size(), Equals(2));
354 });
355
356 it("works on a connected but not biconnected graph", [&](){
357 customGraph(G, 3, {{0,1}, {0,2}});
358 makeBiconnected(G, added);
359 AssertThat(isBiconnected(G), IsTrue());
360 AssertThat(added.size(), Equals(1));
361 });
362
363 it("works on a simple biconnected graph", [&](){
364 randomBiconnectedGraph(G, 10, 20);
365 AssertThat(isBiconnected(G), IsTrue());
366
367 makeBiconnected(G, added);
368 AssertThat(isBiconnected(G), IsTrue());
369 AssertThat(added.empty(), IsTrue());
370 });
371
372 it("works on an extremely large graph", [&](){
373 emptyGraph(G, 250000);
374 AssertThat(isBiconnected(G), IsFalse());
375
376 // A graph with n nodes needs at least n edges to be biconnected
377 makeBiconnected(G, added);
378 AssertThat(isBiconnected(G), IsTrue());
379 AssertThat(added.size(), IsGreaterThan(250000));
380 });
381 });
382
383 describe("biconnectedComponents", [](){
384 Graph G;
385
386 before_each([&](){
387 G.clear();
388 });
389
390 it("works on an empty graph", [&](){
391 EdgeArray<int> component(G,-1);
392 emptyGraph(G, 0);
393 AssertThat(biconnectedComponents(G, component), Equals(0));
394 });
395
396 it("works on a graph with a self-loop", [&](){
397 customGraph(G, 2, {{0,0}, {0,1}});
398 auto expectedComps = {0,1};
399 biconnectedComponentsAssert(G, 2, expectedComps);
400 });
401
402 it("works on a disconnected graph", [&](){
403 customGraph(G, 3, {{0,1}});
404 auto expectedComps = {0};
405 biconnectedComponentsAssert(G, 2, expectedComps);
406 });
407
408 it("works on a connected but not biconnected graph", [&](){
409 customGraph(G, 3, {{0,1}, {0,2}});
410 auto expectedComps = {0,1};
411 biconnectedComponentsAssert(G, 2, expectedComps);
412 });
413
414 it("works on a biconnected graph", [&](){
415 completeGraph(G, 3);
416 auto expectedComps = {0,0,0};
417 biconnectedComponentsAssert(G, 1, expectedComps);
418 });
419
420 it("works on a graph with 2 biconnected components", [&](){
421 customGraph(G, 4, {{0,1}, {0,2}, {1,2}, {0,3}});
422 auto expectedComps = {0,0,0,1};
423 biconnectedComponentsAssert(G, 2, expectedComps);
424 });
425
426 it("works on a graph with 4 biconnected components", [&](){
427 customGraph(G, 10, {{0,1}, {1,2}, {2,3}, {3,1}, {3,4}, {4,1}, {1,5}, {5,6}, {6,0}, {0,7}, {7,8}, {8,9}, {9,7}});
428 auto expectedComps = {0,1,1,1,1,1,0,0,0,2,3,3,3};
429 biconnectedComponentsAssert(G, 4, expectedComps);
430 });
431
432 it("works on a graph with 5 biconnected components", [&](){
433 customGraph(G, 12, {{0,1}, {1,2}, {2,3}, {3,4}, {4,2}, {3,1}, {1,5}, {5,6}, {6,0}, {5,7}, {7,8}, {5,8}, {8,9}, {10,11}});
434 auto expectedComps = {0,1,1,1,1,1,0,0,0,2,2,2,3,4};
435 biconnectedComponentsAssert(G, 5, expectedComps);
436 });
437
438 it("works on an extremely large graph", [&](){
439 randomGraph(G, 250000, 500000);
440
441 EdgeArray<int> component(G,-1);
442 NodeArray<int> conComp(G);
443 int result = biconnectedComponents(G,component);
444
445 AssertThat(result, IsGreaterThan(0));
446 AssertThat(result, !IsLessThan(connectedComponents(G,conComp)));
447 for (edge e : G.edges) {
448 AssertThat(component[e], IsGreaterThan(-1));
449 }
450 });
451
452 it("works on an extremely large biconnected graph", [&](){
453 randomBiconnectedGraph(G, 250000, 500000);
454
455 EdgeArray<int> component(G,-1);
456 AssertThat(biconnectedComponents(G,component), Equals(1));
457 for (edge e : G.edges) {
458 AssertThat(component[e], Equals(0));
459 }
460 });
461 });
462
463 describe("strongComponents", [](){
464 Graph G;
465
466 before_each([&](){
467 G.clear();
468 });
469
470 it("works on an empty graph", [&](){
471 NodeArray<int> component(G,-1);
472 emptyGraph(G, 0);
473 AssertThat(strongComponents(G, component), Equals(0));
474 });
475
476 it("works on a graph with a self-loop", [&](){
477 customGraph(G, 2, {{0,0}, {0,1}});
478 auto expectedComps = {0,1};
479 strongComponentsAssert(G, expectedComps);
480 });
481
482 it("works on a disconnected graph", [&](){
483 customGraph(G, 3, {{0,1}});
484 auto expectedComps = {0,1,2};
485 strongComponentsAssert(G, expectedComps);
486 });
487
488 it("works on a connected but not strongly connected graph", [&](){
489 customGraph(G, 3, {{0,1}, {0,2}});
490 auto expectedComps = {0,1,2};
491 strongComponentsAssert(G, expectedComps);
492 });
493
494 it("works on a strongly connected graph", [&](){
495 customGraph(G, 3, {{0,1}, {1,2}, {2,0}});
496 auto expectedComps = {0,0,0};
497 strongComponentsAssert(G, expectedComps);
498 });
499
500 it("works on a graph with 2 strongly connected components", [&](){
501 customGraph(G, 4, {{0,1}, {1,2}, {2,0}, {0,3}});
502 auto expectedComps = {0,0,0,1};
503 strongComponentsAssert(G, expectedComps);
504 });
505
506 it("works on a graph with 3 strongly connected components", [&](){
507 customGraph(G, 10, {{0,1}, {1,2}, {2,3}, {3,1}, {3,4}, {4,1}, {0,5}, {5,6}, {6,0}, {0,7}, {7,8}, {8,9}, {9,7}});
508 auto expectedComps = {0,1,1,1,1,0,0,2,2,2};
509 strongComponentsAssert(G, expectedComps);
510 });
511
512 it("works on a graph with 5 strongly connected components", [&](){
513 customGraph(G, 12, {{0,1}, {1,2}, {2,3}, {3,4}, {4,2}, {1,3}, {1,5}, {5,6}, {6,0}, {5,7}, {7,8}, {8,5}, {8,9}, {10,11}});
514 auto expectedComps = {0,0,1,1,1,0,0,0,0,2,3,4};
515 strongComponentsAssert(G, expectedComps);
516 });
517
518 it("works on an extremely large graph", [&](){
519 randomGraph(G, 250000, 500000);
520
521 NodeArray<int> component(G,-1);
522 NodeArray<int> conComp(G);
523 int result = strongComponents(G,component);
524
525 AssertThat(result, IsGreaterThan(0));
526 AssertThat(result, !IsLessThan(connectedComponents(G,conComp)));
527 for (node v : G.nodes) {
528 AssertThat(component[v], IsGreaterThan(-1));
529 }
530 });
531
532 it("works on an extremely large strongly connected graph", [&](){
533 randomBiconnectedGraph(G, 250000, 250000);
534
535 // Ensure that G is strongly connected.
536 List<edge> edges;
537 G.allEdges(edges);
538 for (edge e : edges) {
539 G.newEdge(e->target(), e->source());
540 }
541
542 NodeArray<int> component(G,-1);
543 AssertThat(strongComponents(G,component), Equals(1));
544 for (node v : G.nodes) {
545 AssertThat(component[v], Equals(0));
546 }
547 });
548 });
549
550 describe("isAcyclic", [](){
551 describeIsAcyclic(true);
552 });
553
554 describe("isAcyclicUndirected", [](){
555 describeIsAcyclic(false);
556 });
557
558 describe("isArborescenceForest", [](){
559 Graph G;
560 List<node> roots;
561
562 before_each([&](){
563 G.clear();
564 roots.clear();
565 });
566
567 it("works on an empty graph", [&](){
568 emptyGraph(G, 0);
569 AssertThat(isArborescenceForest(G, roots), IsTrue());
570 AssertThat(roots.empty(), IsTrue());
571 });
572
573 it("works on a graph with a single node", [&](){
574 G.newNode();
575 AssertThat(isArborescenceForest(G, roots), IsTrue());
576 AssertThat(roots.size(), Equals(1));
577 AssertThat(roots.front(), Equals(G.firstNode()));
578 });
579
580 it("works on a graph with a self-loop", [&](){
581 customGraph(G, 2, {{0,1}, {1,1}});
582 AssertThat(isArborescenceForest(G, roots), IsFalse());
583 });
584
585 it("works on a graph with parallel edges", [&](){
586 customGraph(G, 2, {{0,1}, {0,1}});
587 AssertThat(isArborescenceForest(G, roots), IsFalse());
588 });
589
590 it("works on a graph without a source", [&](){
591 customGraph(G, 2, {{0,0}, {0,1}});
592 AssertThat(isArborescenceForest(G, roots), IsFalse());
593 });
594
595 it("works on a cyclic graph", [&](){
596 customGraph(G, 3, {{0,1}, {0,2}, {1,2}});
597 AssertThat(isArborescenceForest(G, roots), IsFalse());
598 });
599
600 it("works on a cyclic graph with different edge order", [&](){
601 customGraph(G, 3, {{0,2}, {0,1}, {1,2}});
602 AssertThat(isArborescenceForest(G, roots), IsFalse());
603 });
604
605 it("works on an arborescence", [&](){
606 customGraph(G, 4, {{0,1}, {0,2}, {1,3}});
607 AssertThat(isArborescenceForest(G, roots), IsTrue());
608 AssertThat(roots.size(), Equals(1));
609 AssertThat(roots.front(), Equals(G.firstNode()));
610 });
611
612 it("works on a disconnected forest", [&](){
613 customGraph(G, 3, {{0,1}});
614 AssertThat(isArborescenceForest(G, roots), IsTrue());
615 AssertThat(roots.size(), Equals(2));
616 });
617
618 it("works on a graph with one tree and one cyclic subgraph", [&](){
619 customGraph(G, 5, {{0,1}, {2,3}, {3,4}, {4,2}});
620 AssertThat(isArborescenceForest(G, roots), IsFalse());
621 });
622
623 it("works on a directed tree that is not an arborescence", [&](){
624 customGraph(G, 4, {{0,1}, {1,2}, {3,1}});
625 AssertThat(isArborescenceForest(G, roots), IsFalse());
626 });
627
628 it("works on an extremely large biconnected graph", [&](){
629 randomBiconnectedGraph(G, 250000, 500000);
630 AssertThat(isArborescenceForest(G, roots), IsFalse());
631 });
632
633 it("works on an extremely large arborescence", [&](){
634 constexpr int n = 125000;
635 node nodes[n];
636 nodes[0] = G.newNode();
637
638 for (int i = 1; i < n; i++) {
639 nodes[i] = G.newNode();
640 G.newEdge(nodes[randomNumber(0, i-1)], nodes[i]);
641 }
642 AssertThat(isArborescenceForest(G, roots), IsTrue());
643 AssertThat(roots.size(), Equals(1));
644 AssertThat(roots.front(), Equals(G.firstNode()));
645 });
646
647 it("works on an extremely large path", [&](){
648 node v = G.newNode();
649 for (int i = 0; i < 125000; i++) {
650 node w = G.newNode();
651 G.newEdge(v, w);
652 v = w;
653 }
654 AssertThat(isArborescenceForest(G, roots), IsTrue());
655 AssertThat(roots.size(), Equals(1));
656 AssertThat(roots.front(), Equals(G.firstNode()));
657 });
658 });
659
660 describe("degreeDistribution", [] {
661 it("works on an empty graph", [] {
662 Graph G;
663 Array<int> dist;
664 degreeDistribution(G, dist);
665 AssertThat(dist.empty(), IsTrue());
666 });
667
668 it("works on isolated nodes", [] {
669 Graph G;
670 emptyGraph(G, 100);
671 Array<int> dist;
672 degreeDistribution(G, dist);
673 AssertThat(dist.low(), Equals(0));
674 AssertThat(dist.size(), Equals(1));
675 AssertThat(dist[0], Equals(100));
676 });
677
678 it("works on a complete graph", [] {
679 Graph G;
680 const int n = 12;
681 completeGraph(G, n);
682 Array<int> dist;
683 degreeDistribution(G, dist);
684 AssertThat(dist.low(), Equals(n-1));
685 AssertThat(dist.size(), Equals(1));
686 AssertThat(dist[n-1], Equals(n));
687 });
688
689 it("works on an isolated node with a lot of self-loops", [] {
690 Graph G;
691 node v = G.newNode();
692 const int n = 42;
693 for (int i = 0; i < n; ++i) {
694 G.newEdge(v, v);
695 }
696 Array<int> dist;
697 degreeDistribution(G, dist);
698 AssertThat(dist.low(), Equals(2*n));
699 AssertThat(dist.size(), Equals(1));
700 AssertThat(dist[2*n], Equals(1));
701 });
702
703 it("works with a very untypical distribution", [] {
704 Graph G;
705 const int n = 30;
706 completeGraph(G, n);
707 for (int i = 0; i < n; ++i) {
708 node u = G.newNode();
709 node v = G.newNode();
710 G.newEdge(u, v);
711 }
712 Array<int> dist;
713 degreeDistribution(G, dist);
714 AssertThat(dist.low(), Equals(1));
715 AssertThat(dist.high(), Equals(n-1));
716 AssertThat(dist[dist.low()], Equals(2*n));
717 for (int i = dist.low() + 1; i < dist.high(); ++i) {
718 AssertThat(dist[i], Equals(0));
719 }
720 AssertThat(dist[dist.high()], Equals(n));
721 });
722
723 it("works with a multigraph", [] {
724 Graph G;
725 customGraph(G, 7,
726 {{0, 1}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {3, 4}, {3, 5}, {4, 5}, {4, 5}, {5, 5}});
727 Array<int> dist;
728 degreeDistribution(G, dist);
729 AssertThat(dist.low(), Equals(0));
730 AssertThat(dist.high(), Equals(5));
731 for (int i = dist.low(); i < dist.high(); ++i) {
732 AssertThat(dist[i], Equals(1));
733 }
734 AssertThat(dist[dist.high()], Equals(2));
735 });
736 });
737
738 describe("isBipartite", [](){
739 it("works on an empty graph", [&](){
740 Graph G;
741 AssertThat(isBipartite(G), IsTrue());
742 });
743
744 it("works on a graph with one node", [&](){
745 Graph G;
746 G.newNode();
747 AssertThat(isBipartite(G), IsTrue());
748 });
749
750 it("works on a path of two nodes", [&](){
751 Graph G;
752 NodeArray<bool> color(G, false);
753 customGraph(G, 2, {{0,1}});
754 AssertThat(isBipartite(G, color), IsTrue());
755 AssertThat(color[G.firstNode()], !Equals(color[G.lastNode()]));
756 });
757
758 it("works on a disconnected bipartite graph", [&](){
759 Graph G;
760 NodeArray<bool> color(G, false);
761 Array<node> nodes;
762 customGraph(G, 3, {{0,1}}, nodes);
763 AssertThat(isBipartite(G, color), IsTrue());
764 AssertThat(color[nodes[0]], !Equals(color[nodes[1]]));
765 });
766
767 it("works on a disconnected non-bipartite graph", [&](){
768 Graph G;
769 customGraph(G, 4, {{1,2}, {2,3}, {3,1}});
770 AssertThat(isBipartite(G), IsFalse());
771 });
772
773 it("works on a bipartite graph with multi-edges", [&](){
774 Graph G;
775 NodeArray<bool> color(G, false);
776 Array<node> nodes;
777 customGraph(G, 3, {{0,1}, {1,0}, {1,2}}, nodes);
778 AssertThat(isBipartite(G, color), IsTrue());
779 AssertThat(color[nodes[0]], !Equals(color[nodes[1]]));
780 AssertThat(color[nodes[1]], !Equals(color[nodes[2]]));
781 AssertThat(color[nodes[0]], Equals(color[nodes[2]]));
782 });
783
784 it("works on a non-bipartite graph with multi-edges", [&](){
785 Graph G;
786 customGraph(G, 4, {{1,2}, {2,3}, {3,1}});
787 AssertThat(isBipartite(G), IsFalse());
788 });
789
790 it("works on a graph with a self-loop", [&](){
791 Graph G;
792 customGraph(G, 2, {{0,1}, {1,1}});
793 AssertThat(isBipartite(G), IsFalse());
794 });
795
796 it("works on an extremely large tree", [&](){
797 Graph G;
798 randomTree(G, 250000);
799 AssertThat(isBipartite(G), IsTrue());
800 });
801
802 it("works on an extremely large non-bipartite graph", [&](){
803 Graph G;
804 randomTree(G, 250000);
805 node u = G.chooseNode();
806 node v = G.chooseNode();
807 node w = G.chooseNode();
808 G.newEdge(u, v);
809 G.newEdge(u, w);
810 G.newEdge(v, w);
811 AssertThat(isBipartite(G), IsFalse());
812 });
813 });
814
815 describe("nodeDistribution", [] {
816 it("can compute an indegree distribution", [] {
817 Graph G;
818 customGraph(G, 3, {{0, 1}, {1, 2}, {2, 0}});
819 Array<int> dist;
820 nodeDistribution(G, dist, [](node v) {
821 return v->indeg();
822 });
823 AssertThat(dist.low(), Equals(1));
824 AssertThat(dist.size(), Equals(1));
825 AssertThat(dist[1], Equals(3));
826 });
827
828 it("can compute the number of nodes that belong to connected components", [] {
829 Graph G;
830 customGraph(G, 4, {{0, 0}, {1, 2}});
831 NodeArray<int> comp(G);
832 Array<int> dist;
833 connectedComponents(G, comp);
834 nodeDistribution(G, dist, comp);
835 AssertThat(dist.low(), Equals(0));
836 AssertThat(dist.size(), Equals(3));
837 AssertThat(dist[0] + dist[1] + dist[2], Equals(G.numberOfNodes()));
838 });
839 });
840 });
841});
842