1/** \file
2 * \brief Bandit tests for strong component algorithms
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/simple_graph_alg.h>
34#include <ogdf/basic/graph_generators.h>
35
36#include <testing.h>
37
38/** Checks wheter a path from source to target
39 * does exist by traversing the graph.
40 */
41bool pathExists(const Graph &graph, const node source, const node target)
42{
43 OGDF_ASSERT(source != target);
44 OGDF_ASSERT(source->graphOf() == &graph);
45 OGDF_ASSERT(target->graphOf() == &graph);
46
47 List<node> queue;
48 NodeArray<bool> visited(graph, false);
49 visited[source] = true;
50 queue.pushBack(source);
51
52 bool result = false;
53 while(!queue.empty() && !result) {
54 node v = queue.popFrontRet();
55 for(adjEntry adj : v->adjEntries) {
56 node w = adj->theEdge()->target();
57 if(!visited[w]) {
58 result |= w == target;
59 visited[w] = true;
60 queue.pushBack(w);
61 }
62 }
63 }
64
65 return result;
66}
67
68go_bandit([](){
69 describe("strong components", [](){
70 for(int n = 0; n < 75; n++) {
71 it("works on a random graph of size " + to_string(n), [&](){
72 Graph graph;
73 randomDigraph(graph, n, randomDouble(0, 1));
74
75 NodeArray<int> components(graph);
76 int nComponents = strongComponents(graph, components);
77 List<node> nodes;
78 graph.allNodes(nodes);
79 for(node v = graph.firstNode(); v; v = v->succ()) {
80 for(node w = v->succ(); w; w = w->succ()) {
81 AssertThat(components[v], IsGreaterThan(-1) && IsLessThan(nComponents));
82 AssertThat(components[w], IsGreaterThan(-1) && IsLessThan(nComponents));
83 if(components[v] == components[w]) {
84 AssertThat(pathExists(graph, v, w), IsTrue());
85 AssertThat(pathExists(graph, w, v), IsTrue());
86 } else {
87 AssertThat(pathExists(graph, w, v) && pathExists(graph, v, w), IsFalse());
88 }
89 }
90 }
91 });
92 }
93
94 it("works on a predefined graph with overlapping circles", [](){
95 Graph graph;
96 emptyGraph(graph, 8);
97 List<node> nodes;
98 graph.allNodes(nodes);
99 graph.newEdge(*nodes.get(2), *nodes.get(5));
100 graph.newEdge(*nodes.get(3), *nodes.get(6));
101 graph.newEdge(*nodes.get(4), *nodes.get(7));
102 graph.newEdge(*nodes.get(5), *nodes.get(4));
103 graph.newEdge(*nodes.get(6), *nodes.get(5));
104 graph.newEdge(*nodes.get(6), *nodes.get(1));
105 graph.newEdge(*nodes.get(7), *nodes.get(2));
106 graph.newEdge(*nodes.get(7), *nodes.get(3));
107 graph.newEdge(*nodes.get(7), *nodes.get(6));
108
109 NodeArray<int> components(graph);
110 int nComponents = strongComponents(graph, components);
111 AssertThat(nComponents, Equals(3));
112 AssertThat(components[*nodes.get(0)], !Equals(components[*nodes.get(1)]));
113 AssertThat(components[*nodes.get(0)], !Equals(components[*nodes.get(2)]));
114 AssertThat(components[*nodes.get(1)], !Equals(components[*nodes.get(2)]));
115 AssertThat(components[*nodes.get(2)], Equals(components[*nodes.get(7)]));
116 AssertThat(components[*nodes.get(3)], Equals(components[*nodes.get(7)]));
117 AssertThat(components[*nodes.get(4)], Equals(components[*nodes.get(7)]));
118 AssertThat(components[*nodes.get(5)], Equals(components[*nodes.get(7)]));
119 AssertThat(components[*nodes.get(6)], Equals(components[*nodes.get(7)]));
120
121
122 });
123 });
124});
125