1/** \file
2 * \brief Simple tests for generating various graphs.
3 *
4 * \author Christoph Schulz, 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 "ogdf/basic/simple_graph_alg.h"
35#include "ogdf/basic/extended_graph_alg.h"
36#include <testing.h>
37
38/**
39 * Checks for a given graph \p G and a given list of
40 * pairs {\a d, \a n} in \p degNumberPairs, that there
41 * are \a n occurrences of degree \a d.
42 */
43static void assertNodeDegrees(const Graph &G, std::vector<std::pair<int,int>> degNumberPairs) {
44 Array<int> degdist;
45 degreeDistribution(G, degdist);
46
47 for (auto degNumberPair : degNumberPairs) {
48 const int d = degNumberPair.first;
49 const int n = degNumberPair.second;
50
51 AssertThat(d, !(IsGreaterThan(degdist.high()) || IsLessThan(degdist.low())));
52 AssertThat(degdist[d], Equals(n));
53 }
54}
55
56/**
57 * Checks if the nodes in a given graph \p G are constructed
58 * in a circulant way, with each node being connected to its
59 * (\a idx &plusmn; \a i) neighbors, for each \a i in \p jumps.
60 */
61static void assertCirculant(Graph &G, Array<int>& jumps) {
62 Array<node> nodes;
63 NodeArray<int> indices = NodeArray<int>(G);
64 G.allNodes(nodes);
65 for (int i = 0; i < nodes.size(); i++) {
66 indices[nodes[i]] = i;
67 }
68
69 // Make sure our nodes are generated in order with our edges being of the requested length
70 for (node v : nodes) {
71 std::vector<node> expected;
72 for (int j : jumps) {
73 expected.push_back(nodes[(indices[v] + j + nodes.size()) % nodes.size()]);
74 expected.push_back(nodes[(indices[v] - j + nodes.size()) % nodes.size()]);
75 }
76
77 List<edge> vEdges;
78 v->adjEdges(vEdges);
79 for (edge e : vEdges) {
80 AssertThat(expected, Contains(e->opposite(v)));
81 auto it = std::find(expected.begin(), expected.end(), e->opposite(v));
82 if (it != expected.end()) {
83 expected.erase(it);
84 }
85 }
86 AssertThat(expected, IsEmpty());
87 }
88}
89
90/**
91 * Checks if \p clearFunction clears the graph
92 */
93static void itClearsGraph(std::function<void(Graph &G)> clearFunction) {
94 it("clears the graph", [&] {
95 Graph G;
96 G.newEdge(G.newNode(), G.newNode());
97 clearFunction(G);
98 AssertThat(G.empty(), IsTrue());
99 });
100}
101
102static void testDeterministicGenerators() {
103 describe("circulantGraph", [] {
104 itClearsGraph([](Graph &G) {
105 circulantGraph(G, 0, Array<int>{});
106 });
107
108 it("generates two circulant graphs",[](){
109 Graph G;
110 circulantGraph(G, 11, Array<int>{1, 2, 4});
111 AssertThat(G.numberOfEdges(), Equals(33));
112 AssertThat(G.numberOfNodes(), Equals(11));
113 AssertThat(isConnected(G),Equals(true));
114
115 circulantGraph(G, 12, Array<int>{2, 4, 6});
116 AssertThat(G.numberOfNodes(), Equals(12));
117 AssertThat(isConnected(G),Equals(false));
118 });
119
120 for (int n = 10; n < 40; n+=3) {
121 Array<int> jumps = Array<int>(3);
122 for (int jumpmod = 1; jumpmod*4+4 < n; jumpmod++) {
123 jumps[0] = jumpmod;
124 jumps[1] = jumpmod*2;
125 jumps[2] = jumpmod*2+2;
126 string jumpstr = "{" + to_string(jumps[0]) + ", " + to_string(jumps[1]) + ", " + to_string(jumps[2]) + "}";
127 it("generates a circulant graphs with " + to_string(n) + " nodes and jumps " + jumpstr, [&](){
128 Graph G;
129 circulantGraph(G, n, jumps);
130 AssertThat(G.numberOfEdges(), Equals(n*3));
131 AssertThat(G.numberOfNodes(), Equals(n));
132 assertCirculant(G, jumps);
133 });
134 }
135 }
136 });
137
138 describe("emptyGraph", [] {
139 itClearsGraph([](Graph &G) {
140 emptyGraph(G, 0);
141 });
142
143 for (int n = 0; n < 20; n++) {
144 it("generates a graph with " + to_string(n) + " isolated nodes", [&] {
145 Graph G;
146 emptyGraph(G, n);
147 AssertThat(G.numberOfNodes(), Equals(n));
148 AssertThat(G.numberOfEdges(), Equals(0));
149 });
150 }
151 });
152
153 describe("completeGraph", [] {
154 itClearsGraph([](Graph &G) {
155 completeGraph(G, 0);
156 });
157
158 for (int n = 0; n < 20; n++) {
159 it("generates K_" + to_string(n), [&] {
160 Graph G;
161 completeGraph(G, n);
162 AssertThat(G.numberOfNodes(), Equals(n));
163 AssertThat(G.numberOfEdges(), Equals(n * (n-1) / 2));
164 AssertThat(isSimpleUndirected(G), IsTrue());
165 });
166 }
167 });
168
169 describe("completeBipartiteGraph", [] {
170 for (int n = 1; n <= 5; n++) {
171 for (int m = 1; m <= 5; m++) {
172 it("generates K_{" + to_string(n) + "," + to_string(m) + "}", [&] {
173 Graph G;
174 completeBipartiteGraph(G, n, m);
175 AssertThat(G.numberOfNodes(), Equals(n + m));
176 AssertThat(G.numberOfEdges(), Equals(n * m));
177 AssertThat(isSimpleUndirected(G), IsTrue());
178 AssertThat(isBipartite(G), IsTrue());
179 });
180 }
181 }
182 });
183
184 describe("completeKPartiteGraph", [] {
185 itClearsGraph([](Graph &G) {
186 completeKPartiteGraph(G, {});
187 });
188
189 it("generates K_{1,1,1}", [] {
190 Graph G;
191 completeKPartiteGraph(G, {1, 1, 1});
192 AssertThat(G.numberOfNodes(), Equals(3));
193 AssertThat(isSimpleUndirected(G), IsTrue());
194 AssertThat(isAcyclicUndirected(G), IsFalse());
195 });
196
197 it("generates K_{4,1,1}", [] {
198 Graph G;
199 completeKPartiteGraph(G, {4, 1, 1});
200 AssertThat(G.numberOfNodes(), Equals(6));
201 AssertThat(G.numberOfEdges(), Equals(9));
202 AssertThat(isConnected(G), IsTrue());
203 AssertThat(isSimpleUndirected(G), IsTrue());
204 assertNodeDegrees(G, {{2, 4}, {5, 2}});
205 });
206
207 it("generates K_{1,2,1,2}", [] {
208 Graph G;
209 completeKPartiteGraph(G, {1, 2, 1, 2});
210 AssertThat(G.numberOfNodes(), Equals(6));
211 AssertThat(G.numberOfEdges(), Equals(13));
212 AssertThat(isConnected(G), IsTrue());
213 AssertThat(isSimpleUndirected(G), IsTrue());
214 assertNodeDegrees(G, {{4, 4}, {5, 2}});
215 });
216 });
217
218 describe("regularLatticeGraph", [] {
219 for (int n = 4; n < 50; n++) {
220 for (int k = 2; k < n-2; k+=2) {
221 it("generates graph with " + to_string(n) + " nodes and " + to_string(k) + " degrees", [&] {
222 Graph G;
223 regularLatticeGraph(G, n, k);
224 AssertThat(G.numberOfNodes(), Equals(n));
225 AssertThat(G.numberOfEdges(), Equals(n*k/2));
226 AssertThat(isConnected(G), IsTrue());
227 AssertThat(isSimple(G), IsTrue());
228 assertNodeDegrees(G, {{k, n}});
229 Array<int> jumps = Array<int>(k/2);
230 for (int i = 0; i < k/2; i++) {
231 jumps[i] = i+1;
232 }
233 assertCirculant(G, jumps);
234 });
235 }
236 }
237 });
238
239 describe("regularTree", [] {
240 for (int n = 1; n < 50; n++) {
241 for (int d = 1; d < n; d++) {
242 it("generates the regular tree with " + to_string(n) + " nodes and " + to_string(d) + " children", [&]() {
243 Graph G;
244 regularTree(G, n, d);
245 AssertThat(G.numberOfNodes(), Equals(n));
246 AssertThat(isTree(G), IsTrue());
247 // Test on k-arity:
248 // Calculate number of expected inner nodes
249 int nodesOnLevel = 1; // Number of nodes on the current level
250 int sumNumberOfNodes = nodesOnLevel; // Total number of nodes up to current level
251 int numberOfNodes = G.numberOfNodes();
252 while (sumNumberOfNodes < numberOfNodes) {
253 nodesOnLevel *= d;
254 sumNumberOfNodes += nodesOnLevel;
255 }
256 sumNumberOfNodes -= nodesOnLevel;
257 nodesOnLevel /= d;
258 sumNumberOfNodes -= nodesOnLevel + 1;
259 /* We now have:
260 - at least 1 node of degree d
261 - at least nodesOnLevel nodes of degree 1 (leaves)
262 - at least sumNumberOfNodes node of degree d+1.
263 */
264 Array<int> degdist;
265 degreeDistribution(G, degdist);
266 AssertThat(degdist[d], IsGreaterThanOrEqualTo(1));
267 // Our array is not initialized if no such nodes exist.
268 if (sumNumberOfNodes > 0) AssertThat(degdist[d+1], IsGreaterThanOrEqualTo(sumNumberOfNodes));
269 AssertThat(degdist[1], IsGreaterThanOrEqualTo(nodesOnLevel));
270 });
271 }
272 }
273 });
274
275 describe("wheelGraph", [] {
276 for (int n = 3; n < 50; n++) {
277 it("generates the wheel graph with " + to_string(n) + " exterior nodes", [&]() {
278 Graph G;
279 wheelGraph(G, n);
280 AssertThat(G.numberOfNodes(), Equals(n+1));
281 AssertThat(G.numberOfEdges(), Equals(n*2));
282 AssertThat(isSimpleUndirected(G), IsTrue());
283 AssertThat(isConnected(G), IsTrue());
284 if (n == 3) {
285 // Special case: complete graph K_4
286 AssertThat(isRegular(G, 3), IsTrue());
287 }
288 else {
289 assertNodeDegrees(G, {{n, 1}, {3, n}});
290 }
291 });
292 }
293 });
294
295 describe("suspension", [] {
296 for (int n = 1; n < 50; n++) {
297 for (int s = 1; s < 5; s++) {
298 string label;
299 if (s == 0) {
300 label = "does not modify a graph with " + to_string(n) + " nodes if no nodes added";
301 }
302 else {
303 label = "adds " + to_string(s) + " suspension nodes to a graph with " + to_string(n) + " nodes";
304 }
305 it(label, [&]() {
306 Graph G;
307 randomSimpleGraph(G, n, n/2);
308 int numberOfNodes = G.numberOfNodes();
309 int numberOfEdges = G.numberOfEdges();
310 bool connected = isConnected(G);
311 suspension(G, s);
312 AssertThat(G.numberOfNodes(), Equals(numberOfNodes + s));
313 AssertThat(G.numberOfEdges(), Equals(numberOfEdges + s*numberOfNodes));
314 if (s == 0) AssertThat(isConnected(G), Equals(connected));
315 else AssertThat(isConnected(G), IsTrue());
316 AssertThat(isSimpleUndirected(G), IsTrue());
317 });
318 }
319 }
320 });
321
322 describe("gridGraph", [] {
323 for (int n = 2; n <= 10; n++) {
324 for (int m = 2; m <= 10; m++) {
325 for (bool loopN : {true, false}) {
326 for (bool loopM : {true, false}) {
327 it("generates a grid of " + to_string(n) + "x" + to_string(m) + " (loop:" + (loopN ? "yes" : " no") + "/" + (loopM ? "yes" : "no ") + ")", [&](){
328 Graph G;
329 gridGraph(G, n, m, loopN, loopM);
330 int expectedEdges = 2*n*m;
331 // Fewer edges if we do not close the torus in either direction.
332 if (!loopN) expectedEdges -= m;
333 if (!loopM) expectedEdges -= n;
334 AssertThat(G.numberOfNodes(), Equals(n*m));
335 AssertThat(G.numberOfEdges(), Equals(expectedEdges));
336 AssertThat(isLoopFree(G), IsTrue());
337 // If the grid is two nodes wide or tall, parallel edges are inserted for the loop.
338 if ( (n > 2 || !loopN) && (m > 2 || !loopM)) {
339 AssertThat(isParallelFreeUndirected(G), IsTrue());
340 }
341 AssertThat(isConnected(G), IsTrue());
342 std::vector<std::pair<int, int>> expectedDegrees;
343 // We expect degree 2 only for the corners if we do not close the torus in either direction.
344 // We expect degree 4 for every node if we loop in all directions. For each direction that we
345 // do not loop in, the sides of that direction are degree 3 instead.
346 int e2 = 0;
347 int e3 = 0;
348 if ( loopN && !loopM) e3 = 2*n;
349 if (!loopN && loopM) e3 = 2*m;
350 if (!loopN && !loopM) {
351 e2 = 4;
352 e3 = 2*(m-2 + n-2); // Do not count corners
353 }
354 int e4 = n*m - (e2 + e3);
355 if (e2 > 0) expectedDegrees.push_back({2, e2});
356 if (e3 > 0) expectedDegrees.push_back({3, e3});
357 if (e4 > 0) expectedDegrees.push_back({4, e4});
358 assertNodeDegrees(G, expectedDegrees);
359 });
360 }
361 }
362 }
363 }
364 });
365
366 describe("petersenGraph", [] {
367 it("generates the standard Petersen graph if no additional arguments are supplied", [&]() {
368 Graph G;
369 petersenGraph(G);
370 AssertThat(G.numberOfNodes(), Equals(10));
371 AssertThat(G.numberOfEdges(), Equals(15));
372 AssertThat(isSimpleUndirected(G), IsTrue());
373 AssertThat(isRegular(G, 3), IsTrue());
374 });
375 for (int n = 3; n <= 10; n++) {
376 for (int d = 1; d < n/2; d++) {
377 it("generates the generalized Petersen graph with " + to_string(n) + " outer nodes and an inner jump width of " + to_string(d), [&](){
378 Graph G;
379 petersenGraph(G, n, d);
380 AssertThat(G.numberOfNodes(), Equals(2 * n));
381 AssertThat(G.numberOfEdges(), Equals(3 * n));
382 AssertThat(isSimpleUndirected(G), IsTrue());
383 AssertThat(isRegular(G, 3), IsTrue());
384 });
385 }
386 }
387 });
388
389 describe("customGraph", [] {
390 itClearsGraph([](Graph &G) {
391 customGraph(G, 0, {});
392 });
393
394 for (int n = 0; n < 50; n++) {
395 int m = randomNumber(0, (n*(n-1))/2);
396 List<std::pair<int,int>> edges;
397
398 for (int i = 0; i < m; i++) {
399 std::pair<int,int> e({randomNumber(0, n-1),
400 randomNumber(0, n-1)});
401 edges.pushBack(e);
402 }
403
404 it("generates a custom graph with " + to_string(n) + " nodes and " + to_string(m) + " edges", [&]() {
405 Graph G;
406 customGraph(G, n, edges);
407 AssertThat(G.numberOfNodes(), Equals(n));
408 AssertThat(G.numberOfEdges(), Equals(m));
409
410 Array<node> nodes(n);
411 int i = 0;
412 for (auto v : G.nodes) {
413 nodes[i++] = v;
414 }
415
416 for (auto e : G.edges) {
417 std::pair<int,int> nodePair = edges.popFrontRet();
418 AssertThat(nodes[std::get<0>(nodePair)], Equals(e->source()));
419 AssertThat(nodes[std::get<1>(nodePair)], Equals(e->target()));
420 }
421 });
422 }
423
424 it("returns a correct mapping", [] {
425 Graph G;
426 Array<node> nodes;
427 customGraph(G, 5, {{0, 2}, {1, 2}, {2, 2}, {3, 2}, {4, 2}}, nodes);
428 AssertThat(G.numberOfNodes(), Equals(5));
429 AssertThat(G.numberOfEdges(), Equals(5));
430 G.delNode(nodes[2]);
431 AssertThat(G.numberOfNodes(), Equals(4));
432 AssertThat(G.numberOfEdges(), Equals(0));
433 });
434 });
435}
436
437static void testRandomGenerators() {
438 describe("randomGraph", [](){
439 itClearsGraph([](Graph &G) {
440 randomGraph(G, 0, 0);
441 });
442
443 for(int n = 0; n < 100; n++) {
444 int m = randomNumber(0, (n*(n-1))/2);
445 it("generates a graph with " + to_string(n) + " nodes and " + to_string(m) + " edges", [&] {
446 Graph G;
447 randomGraph(G, n, m);
448 AssertThat(G.numberOfNodes(), Equals(n));
449 AssertThat(G.numberOfEdges(), Equals(m));
450 });
451 }
452 });
453
454 describe("randomSimpleGraph", [](){
455 itClearsGraph([](Graph &G) {
456 randomSimpleGraph(G, 0, 0);
457 });
458
459 for(int n = 0; n < 100; n++) {
460 int m = randomNumber(0, (n*(n-1))/2);
461 it("generates a graph with " + to_string(n) + " nodes and " + to_string(m) + " edges", [&] {
462 Graph G;
463 randomSimpleGraph(G, n, m);
464 AssertThat(G.numberOfNodes(), Equals(n));
465 AssertThat(G.numberOfEdges(), Equals(m));
466 AssertThat(isSimple(G), Equals(true));
467 });
468 }
469 });
470
471 describe("randomSimpleConnectedGraph", []() {
472 itClearsGraph([](Graph &G) {
473 randomSimpleConnectedGraph(G, 0, 0);
474 });
475
476 it("fails if it cannot be simple", []() {
477 Graph G;
478 AssertThat(randomSimpleConnectedGraph(G, 1, 1), IsFalse());
479 AssertThat(randomSimpleConnectedGraph(G, 2, 2), IsFalse());
480 AssertThat(randomSimpleConnectedGraph(G, 3, 4), IsFalse());
481 });
482
483 it("fails if it cannot be connected", []() {
484 Graph G;
485 AssertThat(randomSimpleConnectedGraph(G, 2, 0), IsFalse());
486 AssertThat(randomSimpleConnectedGraph(G, 3, 1), IsFalse());
487 });
488
489 for (int n = 0; n < 100; n++) {
490 int m = randomNumber(max(0, n-1), (n*(n-1))/2);
491 it("generates a graph with " + to_string(n) + " nodes and " + to_string(m) + " edges", [&]() {
492 Graph G;
493 bool ret = randomSimpleConnectedGraph(G, n, m);
494 AssertThat(ret, IsTrue());
495 AssertThat(G.numberOfNodes(), Equals(n));
496 AssertThat(G.numberOfEdges(), Equals(m));
497 AssertThat(isSimple(G), IsTrue());
498 AssertThat(isConnected(G), IsTrue());
499 });
500 }
501 });
502
503 describe("randomBiconnectedGraph", [](){
504 for(int n = 3; n < 100; n++) {
505 int m = randomNumber(n, (n*(n-1))/2);
506 it("generates a graph with " + to_string(n) + " nodes and " + to_string(m) + " edges", [&] {
507 Graph G;
508 randomBiconnectedGraph(G, n, m);
509 AssertThat(G.numberOfNodes(), Equals(n));
510 AssertThat(G.numberOfEdges(), Equals(m));
511 AssertThat(isBiconnected(G), Equals(true));
512 });
513 }
514 });
515
516 describe("randomTriconnectedGraph", [](){
517 for(int n = 4; n < 100; n++) {
518 it("generates a graph with " + to_string(n) + " nodes", [&] {
519 Graph G;
520 randomTriconnectedGraph(G, n, .5, .5);
521 AssertThat(G.numberOfNodes(), Equals(n));
522 AssertThat(isTriconnected(G), Equals(true));
523 });
524 }
525 });
526
527 describe("randomPlanarBiconnectedGraph", [](){
528 for(int n = 3; n < 100; n++) {
529 int m = randomNumber(n, 3*n-6);
530 it("generates a graph with " + to_string(n) + " nodes and " + to_string(m) + " edges", [&] {
531 Graph G;
532 randomPlanarBiconnectedGraph(G, n, m, false);
533 AssertThat(G.numberOfNodes(), Equals(n));
534 AssertThat(G.numberOfEdges(), Equals(m));
535 AssertThat(isSimple(G), IsTrue());
536 AssertThat(isPlanar(G), IsTrue());
537 AssertThat(isBiconnected(G), IsTrue());
538 });
539 }
540 });
541
542 describe("randomPlanarCNBGraph", [](){
543 for(int b = 2; b < 15; b++) {
544 for(int n = 3; n < 30; n++) {
545 int m = randomNumber(n, 3*n-6);
546 it("generates a graph with " + to_string(b) +
547 " biconnected components and max. " + to_string(n) +
548 " nodes per component", [&] {
549 Graph G;
550 EdgeArray<int> comps(G);
551 randomPlanarCNBGraph(G, n, m, b);
552 AssertThat(G.numberOfNodes(), IsLessThanOrEqualTo(n*b));
553 AssertThat(G.numberOfEdges(), IsLessThanOrEqualTo(m*b));
554 AssertThat(isConnected(G), IsTrue());
555 AssertThat(isSimple(G), IsTrue());
556 AssertThat(isPlanar(G), IsTrue());
557 AssertThat(biconnectedComponents(G, comps), Equals(b));
558 });
559 }
560 }
561 });
562
563
564 describe("randomTree", [](){
565 itClearsGraph([](Graph &G) {
566 randomTree(G, 0);
567 });
568
569 for(int n = 0; n < 100; n++) {
570 it("generates a graph with " + to_string(n) + " nodes", [&] {
571 Graph G;
572 randomTree(G, n);
573 AssertThat(G.numberOfNodes(), Equals(n));
574 AssertThat(isTree(G), Equals(true));
575 });
576 }
577 });
578
579 // TODO: dont skip me
580 describe_skip("randomHierarchy", [](){
581 for(int n = 1; n < 100; n++) {
582 int m = randomNumber(n-1, (n*(n-1))/2);
583 it("generates a graph with " + to_string(n) + " nodes and " + to_string(m) + " edges", [&] {
584 Graph G;
585 randomHierarchy(G, n, m, false, false, true);
586 AssertThat(G.numberOfNodes(), Equals(n));
587 AssertThat(G.numberOfEdges(), Equals(m));
588 });
589 }
590 });
591
592 describe("randomDigraph", [](){
593 for(int n = 1; n < 100; n++) {
594 it("generates a graph with " + to_string(n) + " nodes", [&] {
595 Graph G;
596 randomDigraph(G, n, .5);
597 AssertThat(G.numberOfNodes(), Equals(n));
598 AssertThat(isSimple(G), Equals(true));
599 });
600 }
601 });
602
603 describe("randomRegularGraph", []() {
604 for (int n = 10; n <= 30; n += 5) {
605 for (int d = 2; d <= 6; d += 2) {
606 it("generates a graph with degree " + to_string(d) + " and " + to_string(n) + " nodes", [&] {
607 Graph G;
608 randomRegularGraph(G, n, d);
609 AssertThat(G.numberOfNodes(), Equals(n));
610 AssertThat(isSimple(G), Equals(true));
611 AssertThat(isRegular(G, d), Equals(true));
612 });
613 }
614 }
615 });
616
617 describe("randomGeometricCubeGraph", [](){
618 for(int d = 1; d < 4; d++){
619 for(double t : {0.0, 0.1, 0.5}) {
620 for(int n = 0; n < 100; n++) {
621 it("generates a graph with " + to_string(n) +
622 " nodes in dim " + to_string(d) +
623 " and threshold " + to_string(t), [&] {
624 Graph G;
625 randomGeometricCubeGraph(G,n,t,d);
626 AssertThat(G.numberOfNodes(), Equals(n));
627 AssertThat(isSimple(G), Equals(true));
628 });
629 }
630 }
631 }
632 });
633
634 describe("randomGeographicalThresholdGraph", [](){
635 for (int d = 1; d < 4; d++) {
636 for (double l : {0.5, 1.0, 2.0}) {
637 for (int a = 1; a < 4; a++) {
638 for (double t : {0.0, 0.1, 0.5}) {
639 for (int n = 0; n < 50; n+=10) {
640 it("generates a graph with " + to_string(n) +
641 " nodes in dim " + to_string(d) +
642 " with alpha " + to_string(a) +
643 " and threshold " + to_string(t), [&] {
644 Graph G;
645 Array<int> weights = Array<int>(n);
646 for (int &w : weights) {
647 w = randomNumber(0, n);
648 }
649 std::exponential_distribution<double> dist(l);
650 randomGeographicalThresholdGraph(G, weights, dist, t, a, d);
651 AssertThat(G.numberOfNodes(), Equals(n));
652 AssertThat(isSimple(G), Equals(true));
653 });
654 }
655 }
656 }
657 }
658 }
659 for (int n = 0; n < 100; n+=10) {
660 it("generates a graph with " + to_string(n) + " nodes with custom function", [&] {
661 Graph G;
662 Array<int> weights = Array<int>(n);
663 for (int &w : weights) {
664 w = randomNumber(0, n);
665 }
666 std::uniform_int_distribution<> dist(0, n);
667 randomGeographicalThresholdGraph(G, weights, dist, 0.7, [](double r) { return 1/r; });
668 AssertThat(G.numberOfNodes(), Equals(n));
669 AssertThat(isSimple(G), Equals(true));
670 });
671 }
672 });
673
674 describe("randomEdgesGraph", [](){
675 std::minstd_rand rng(randomSeed());
676 std::uniform_real_distribution<> dist(0, 1);
677 for (int n = 2; n < 50; n++) {
678 it("randomly generates edges in an empty graph with " + to_string(n) + " nodes", [&] {
679 Graph G;
680 emptyGraph(G, n);
681 randomEdgesGraph(G, [&](node, node){ return dist(rng); });
682 AssertThat(G.numberOfNodes(), Equals(n));
683 AssertThat(isSimpleUndirected(G), IsTrue());
684 });
685 }
686 for (int n = 2; n < 50; n++) {
687 it("does not generate edges if probability is 0.0 on a graph with " + to_string(n) + " nodes", [&] {
688 Graph G;
689 emptyGraph(G, n);
690 randomEdgesGraph(G, [](node,node) { return 0.0; });
691 AssertThat(G.numberOfNodes(), Equals(n));
692 AssertThat(G.numberOfEdges(), Equals(0));
693 });
694 }
695 for (int n = 2; n < 50; n++) {
696 int e = n * (n-1) / 2; // probability 1.0 should lead to a complete graph
697 it("generates " + to_string(e) + " edges if probability is 1.0 on a graph with " + to_string(n) + " nodes", [&] {
698 Graph G;
699 emptyGraph(G, n);
700 randomEdgesGraph(G, [](node,node) { return 1.0; });
701 AssertThat(G.numberOfNodes(), Equals(n));
702 AssertThat(G.numberOfEdges(), Equals(e));
703 });
704 }
705 for (int n = 2; n < 50; n++) {
706 it("generates edges on a simple graph with " + to_string(n) + " nodes and keeps it free of self-loops", [&] {
707 Graph G;
708 randomSimpleGraph(G, n, n/2);
709 randomEdgesGraph(G, [&](node,node) { return dist(rng); });
710 AssertThat(G.numberOfNodes(), Equals(n));
711 AssertThat(G.numberOfEdges(), IsGreaterThanOrEqualTo(n/2));
712 AssertThat(isLoopFree(G), IsTrue());
713 });
714 }
715 });
716
717 describe("randomWaxmanGraph", []() {
718 for(int n = 1; n < 100; n+=10) {
719 it("generates a graph with " + to_string(n) + " nodes", [&] {
720 Graph G;
721 randomWaxmanGraph(G, n, 0.5, 0.5);
722 AssertThat(G.numberOfNodes(), Equals(n));
723 AssertThat(isSimpleUndirected(G), IsTrue());
724 });
725 }
726 for(int n = 1; n < 100; n+=10) {
727 it("generates a graph with " + to_string(n) + " nodes", [&] {
728 Graph G;
729 randomWaxmanGraph(G, n, 0.5, 0.5, 10, 10);
730 AssertThat(G.numberOfNodes(), Equals(n));
731 AssertThat(isSimpleUndirected(G), IsTrue());
732 });
733 }
734 });
735
736 describe("preferentialAttachmentGraph", [](){
737 for (int n = 0; n < 100; n+=10) {
738 for (int d = 1; d < 5; d++) {
739 it("generates a graph with " + to_string(n) + " nodes with degree " + to_string(d) + " on an empty input graph", [&] {
740 Graph G;
741 preferentialAttachmentGraph(G, n, d);
742 AssertThat(G.numberOfNodes(), Equals(n));
743 AssertThat(isSimple(G), Equals(true));
744 });
745 }
746 }
747 for (int n = 3; n < 20; n++) {
748 it("fills a tree with " + to_string(n) + " nodes with 50 nodes and stays connected", [&] {
749 Graph G;
750 randomSimpleConnectedGraph(G, n, n-1);
751 preferentialAttachmentGraph(G, 50, 3);
752 AssertThat(isConnected(G), Equals(true));
753 AssertThat(isSimple(G), Equals(true));
754 });
755 }
756 for (int n = 5; n < 20; n++) {
757 it("fills a connected graph with " + to_string(n) + " nodes and " + to_string(n*2) + " edges with 50 nodes and stays connected", [&] {
758 Graph G;
759 randomSimpleConnectedGraph(G, n, n*2);
760 preferentialAttachmentGraph(G, 50, 3);
761 AssertThat(isConnected(G), Equals(true));
762 AssertThat(isSimple(G), Equals(true));
763 });
764 }
765 });
766
767 describe("randomWattsStrogatzGraph", [] {
768 it("does not modify generated lattice graph at 0.0 probability", [] {
769 Graph G;
770 randomWattsStrogatzGraph(G, 20, 4, 0.0);
771 AssertThat(G.numberOfEdges(), Equals(40));
772 AssertThat(G.numberOfNodes(), Equals(20));
773 AssertThat(isConnected(G), IsTrue());
774 AssertThat(isSimple(G), IsTrue());
775 assertNodeDegrees(G, {{4, 20}});
776
777 });
778 for (int n = 4; n <= 50; n+=7) {
779 for (int k = 2; k < n-2; k+=2) {
780 it("generates graph with " + to_string(n) + " nodes and " + to_string(k) + " degrees at 0.5 probability", [&] {
781 Graph G;
782 randomWattsStrogatzGraph(G, n, k, 0.5);
783 AssertThat(G.numberOfNodes(), Equals(n));
784 AssertThat(G.numberOfEdges(), Equals(n*k/2));
785 AssertThat(isSimple(G), IsTrue());
786 for (node v : G.nodes) {
787 AssertThat(v->degree(), IsGreaterThanOrEqualTo(k/2));
788 }
789 });
790 }
791 }
792 });
793
794 describe("randomChungLuGraph", [](){
795 it("generates graph", []() {
796 Graph G;
797 randomChungLuGraph(G, {1, 2, 2, 3, 3, 3});
798 AssertThat(G.numberOfNodes(), Equals(6));
799 AssertThat(isSimpleUndirected(G), Equals(true));
800 });
801 });
802}
803
804// TODO: Test overloaded functions
805
806go_bandit([] {
807 describe("Graph generators", [] {
808 describe("Deterministic graph generators", [] {
809 testDeterministicGenerators();
810 });
811 describe("Random generators", [] {
812 testRandomGenerators();
813 });
814 });
815});
816