1/** \file
2 * \brief Tests for Max Flow Algorithms
3 *
4 * \author Ivo Hedtke, 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/graphalg/MaxFlowEdmondsKarp.h>
33#include <ogdf/graphalg/MaxFlowGoldbergTarjan.h>
34#include <ogdf/graphalg/MaxFlowSTPlanarDigraph.h>
35#include <ogdf/graphalg/MaxFlowSTPlanarItaiShiloach.h>
36#include <ogdf/graphalg/ConnectivityTester.h>
37#include <ogdf/basic/graph_generators.h>
38
39#include <resources.h>
40
41// if defined will print the first failed instance
42#define PRINT_FIRST_FAIL
43
44using std::string;
45using std::endl;
46
47#ifdef PRINT_FIRST_FAIL
48bool printedFailedInstance = false;
49
50/**
51 * Defines which properties a graph fullfills
52 * or an algorithm requires.
53 */
54enum MaxFlowRequirement {
55 MFR_NONE = 0,
56 MFR_PLANAR = 1,
57 MFR_ST_PLANAR = 2,
58 MFR_CONNECTED = 4,
59 MFR_ST_NON_INCIDENT_FACE = 8,
60};
61
62/**
63 * Used to combine requirements or properties.
64 */
65MaxFlowRequirement operator|(MaxFlowRequirement a, MaxFlowRequirement b)
66{
67 return MaxFlowRequirement(int(a) | int(b));
68}
69
70/**
71 * Establishes the properties of the given graph.
72 *
73 * @param graph The graph to be investigated
74 * @param s source node of the instance
75 * @param t target node of the instance
76 * @return all properties except for \c MFR_ST_NON_INCIDENT_FACE
77 */
78MaxFlowRequirement determineProperties(const Graph &graph, node s, node t)
79{
80 MaxFlowRequirement result = MFR_NONE;
81
82 if(isPlanar(graph)) {
83 result = result | MFR_PLANAR;
84
85 if(isSTPlanar(graph, s, t)) {
86 result = result | MFR_ST_PLANAR;
87 }
88 }
89
90 if(isConnected(graph)) {
91 result = result | MFR_CONNECTED;
92 }
93
94 return result;
95}
96
97/**
98 * Used to print the first encountered failed instance.
99 * Always returns false and can thus be used in an bandit assertion.
100 *
101 * @param graph the graph to be printed
102 * @param caps the capacities
103 * @param node s the source node
104 * @param node t the sink node
105 * @param flow the calculated flow
106 */
107template<typename T>
108bool printInstance(const Graph &graph, const EdgeArray<T> caps, const node s, const node t, const EdgeArray<T> &flows)
109{
110 if(!printedFailedInstance) {
111 printedFailedInstance = true;
112
113 std::cout << std::endl << "Graph consists of " << graph.numberOfNodes() << " nodes:" << std::endl;
114 for(node v : graph.nodes) {
115 std::cout << " " << v;
116 if(v == s) { std::cout << " [source]"; }
117 if(v == t) { std::cout << " [sink]"; }
118 std::cout << std::endl;
119 }
120 std::cout << "Graph has " << graph.numberOfEdges() << " edges:" << std::endl;
121 for(edge e : graph.edges) {
122 std::cout << " " << e << " " << flows[e] << " / " << caps[e] << std::endl;
123 }
124 }
125 return false;
126}
127#endif
128
129/**
130 * Asserts the provided flow is valid.
131 * Utilizes EpsilonTest to check the flow values.
132 *
133 * @param graph the problem instance
134 * @param caps the capacity of each edge
135 * @param s the source node
136 * @param t the sink node
137 * @param flows the flow to be validated
138 * @param the total flow from source to sink
139 * @param computeFlow if true the reference algorithms result is
140 * compared to the given flow
141 */
142template<typename VALUE_TYPE>
143void validateFlow(
144 const Graph &graph,
145 const EdgeArray<VALUE_TYPE> &caps,
146 const node s,
147 const node t,
148 const EdgeArray<VALUE_TYPE> &flows,
149 const VALUE_TYPE flow,
150 bool computeFlow = false)
151{
152 EpsilonTest et;
153 const VALUE_TYPE ZERO(0);
154
155 for(edge e : graph.edges) {
156 AssertThat(et.leq(flows[e], caps[e]) || printInstance(graph, caps, s, t, flows), IsTrue());
157 }
158
159 for(node v : graph.nodes) {
160 VALUE_TYPE income(ZERO);
161 VALUE_TYPE output(ZERO);
162 for(adjEntry adj : v->adjEntries) {
163 edge e = adj->theEdge();
164 if(e->isSelfLoop()) {
165 // self-loop, flow must be 0
166 AssertThat(et.equal(flows[e], ZERO) || printInstance(graph, caps, s, t, flows), IsTrue());
167 } else {
168 if(e->source() == v) {
169 output += flows[e];
170 } else {
171 OGDF_ASSERT(e->target() == v);
172 income += flows[e];
173 }
174 }
175 }
176 if(v == s) {
177 // there are Max-Flow algorithms that allow incoming flow in s
178 AssertThat(et.equal(output, flow+income) || printInstance(graph, caps, s, t, flows), IsTrue());
179 } else if(v == t) {
180 // there are Max-Flow algorithms that allow outgoing flow from t
181 AssertThat(et.equal(income, flow+output) || printInstance(graph, caps, s, t, flows), IsTrue());
182 } else {
183 AssertThat(et.equal(income, output) || printInstance(graph, caps, s, t, flows), IsTrue());
184 }
185 }
186
187 // using Edmonds & Karp algorithm for reference
188 if(computeFlow) {
189 MaxFlowEdmondsKarp<VALUE_TYPE> mfek(graph);
190 VALUE_TYPE refFlow = mfek.computeValue(caps, s, t);
191 AssertThat(et.equal(flow, refFlow) || printInstance(graph, caps, s, t, flows), IsTrue());
192 }
193}
194
195/**
196 * Tests a given maximum flow algorithm.
197 *
198 * @param name the human-readable description of this algorithm
199 * @param the requiremets for this algorithm
200 */
201template<typename MAX_FLOW_ALGO, typename VALUE_TYPE>
202void describeMaxFlowModule(const string &name, const MaxFlowRequirement reqs = MFR_NONE)
203{
204 const int maxCapacity = 100;
205 const int maxNodes = 50;
206
207 describe(name, [&](){
208 // test predefined instances
209 for_each_file("maxflow", [&](const ResourceFile* file){
210 it("works on " + file->fullPath(), [&] {
211 // optimal solution value is extracted from the filename
212 std::string filename = file->name();
213 string tmp = filename.substr(0, filename.length() - 4);
214 tmp = tmp.substr(tmp.find_last_of('.') + 1);
215 std::stringstream ss(tmp);
216 VALUE_TYPE opt = -1;
217 ss >> opt;
218
219 Graph graph;
220 EdgeArray<VALUE_TYPE> caps(graph, 0);
221 node s;
222 node t;
223 std::stringstream is{file->data()};
224 AssertThat(GraphIO::readDMF(graph, caps, s, t, is), IsTrue());
225 MaxFlowRequirement props = determineProperties(graph, s, t);
226
227 // create non s-t-incident face if required
228 if(reqs & MFR_ST_NON_INCIDENT_FACE) {
229 props = props | MFR_ST_NON_INCIDENT_FACE;
230 node v = graph.newNode();
231 graph.newEdge(v, t);
232 graph.newEdge(t, v);
233 }
234
235 if(props & MFR_PLANAR) {
236 planarEmbed(graph);
237 }
238
239 if((reqs & props) == reqs) {
240 MAX_FLOW_ALGO alg(graph);
241
242 VALUE_TYPE value = alg.computeValue(caps, s, t);
243 AssertThat(value, Equals(opt));
244
245 EdgeArray<VALUE_TYPE> flow(graph);
246 alg.computeFlowAfterValue(flow);
247 validateFlow(graph, caps, s, t, flow, value);
248 }
249 });
250 });
251
252 // test random instances
253 for(int n = 2; n < maxNodes; n++) {
254 it("works on a random graph of approximate size " + to_string(n), [&] {
255 Graph graph;
256 EdgeArray<VALUE_TYPE> caps(graph);
257 node s = nullptr;
258 node t = nullptr;
259
260 // generate a connected graph based on the requirements of this algorithm
261 if(reqs & MFR_ST_PLANAR) {
262 if(n % 2) {
263 int r = 1 + (int)sqrt(n);
264 gridGraph(graph, r, r, false, false);
265 List<node> nodes;
266 graph.allNodes(nodes);
267 s = *nodes.get(randomNumber(0, r-1));
268 t = *nodes.get(randomNumber(r*(r-1), r*r-1));
269 } else {
270 int m = randomNumber(n-1, max(n-1, 3*n-6));
271 randomPlanarConnectedGraph(graph, n, m);
272 s = graph.chooseNode();
273 CombinatorialEmbedding ce(graph);
274
275 // select sink with common face
276 for(adjEntry adj = s->firstAdj();
277 t == nullptr || randomNumber(0, s->degree());
278 adj = adj->faceCycleSucc()) {
279 node v = adj->theNode();
280
281 if(s != v) {
282 t = v;
283 }
284 }
285 }
286 } else if(reqs & MFR_PLANAR) {
287 int m = randomNumber(n-1, max(n-1, 3*n-6));
288 randomPlanarConnectedGraph(graph, n, m);
289 } else {
290 int m = randomNumber(n*2, max(n*2, n*(n-1)/2));
291 randomBiconnectedGraph(graph, n, m);
292 }
293
294 // generate capacities
295 caps.init(graph);
296 for (edge e: graph.edges) {
297 caps[e] = (VALUE_TYPE) randomDouble(1, maxCapacity);
298 }
299
300 // choose source and sink
301 if(s == nullptr || s == t) {
302 s = graph.chooseNode([&](node v) { return v != t; });
303 }
304 while(t == nullptr || t == s) {
305 t = graph.chooseNode([&](node v) { return v != s; });
306 }
307
308 // create non s-t-incident face if required
309 if(reqs & MFR_ST_NON_INCIDENT_FACE) {
310 node v = graph.newNode();
311 caps[graph.newEdge(v, t)] = 0;
312 caps[graph.newEdge(t, v)] = 0;
313 }
314
315 // compute flow and validate it
316 MAX_FLOW_ALGO alg(graph);
317 EdgeArray<VALUE_TYPE> algFlows(graph);
318
319 VALUE_TYPE algFlow = alg.computeValue(caps, s, t);
320 alg.computeFlowAfterValue(algFlows);
321
322 validateFlow(graph, caps, s, t, algFlows, algFlow, true);
323 });
324 }
325 });
326}
327
328template<typename T>
329void registerTestSuite(const string typeName)
330{
331 const string suffix = "<" + typeName + ">";
332
333 describeMaxFlowModule<MaxFlowSTPlanarItaiShiloach<T>, T>("MaxFlowSTPlanarItaiShiloach" + suffix,
334 MFR_CONNECTED | MFR_ST_PLANAR);
335 describeMaxFlowModule<MaxFlowSTPlanarDigraph<T>, T>("MaxFlowSTPlanarDigraph" + suffix,
336 MFR_CONNECTED | MFR_ST_PLANAR);
337 describeMaxFlowModule<MaxFlowEdmondsKarp<T>, T>("MaxFlowEdmondsKarp" + suffix);
338 describeMaxFlowModule<MaxFlowGoldbergTarjan<T>, T>("MaxFlowGoldbergTarjan" + suffix);
339}
340
341/**
342 * Tests the ConnectivityTester on the given graphs.
343 * Node and edge connectivity is computed for both directed and undirected (i.e. bi-directed) graphs.
344 * The resulting values are tested for consistency.
345 *
346 * @param title A description of the graphs
347 * @param expected The minimal expected node connectivity
348 * @param initializer A lambda expression used to initialize the test instances.
349 * Each call is provided with the graph to be initialized and a counter.
350 */
351void describeConnectivityTester(
352 string title,
353 int expected,
354 std::function<void (Graph&, int)> initializer)
355{
356describe(title, [&]()
357{
358 const int maxNodes = 50;
359
360 // undirected node connectivity
361 ConnectivityTester nodeAlgo;
362
363 // undirected edge connectivity
364 ConnectivityTester edgeAlgo(false);
365
366 // directed node connectivity
367 ConnectivityTester nodeDirAlgo(true, true);
368
369 // directed edge connectivity
370 ConnectivityTester edgeDirAlgo(false, true);
371
372 for (int n = 3; n < maxNodes / 2; n++) {
373 it("works for " + to_string(n) + " nodes", [&] {
374 Graph graph;
375 initializer(graph, n);
376
377 NodeArray<NodeArray<int>> edgeCon(graph, NodeArray<int>(graph));
378 NodeArray<NodeArray<int>> nodeCon(graph, NodeArray<int>(graph));
379 NodeArray<NodeArray<int>> edgeDirCon(graph, NodeArray<int>(graph));
380 NodeArray<NodeArray<int>> nodeDirCon(graph, NodeArray<int>(graph));
381
382 // compute the connectivity
383 edgeAlgo.computeConnectivity(graph, edgeCon);
384 int minConnectivity = nodeAlgo.computeConnectivity(graph, nodeCon);
385 nodeDirAlgo.computeConnectivity(graph, nodeDirCon);
386 edgeDirAlgo.computeConnectivity(graph, edgeDirCon);
387
388 AssertThat(minConnectivity, IsGreaterThan(expected - 1));
389
390 // assert consistency with existing tests
391 if(n > 3 && isTriconnected(graph)) {
392 AssertThat(minConnectivity, IsGreaterThan(2));
393 } else if(n > 2 && isBiconnected(graph)) {
394 AssertThat(minConnectivity, IsGreaterThan(1));
395 } else if(n > 1 && isConnected(graph)) {
396 AssertThat(minConnectivity, IsGreaterThan(0));
397 }
398
399 // check consistency of connectivity variants
400 for (node v : graph.nodes) {
401 for (node w : graph.nodes) {
402 if (v == w) {
403 AssertThat(nodeCon[v][w], Equals(0));
404 } else {
405 // compare with expected values
406 AssertThat(nodeCon[v][w], IsGreaterThan(expected - 1));
407 AssertThat(nodeCon[v][w], IsGreaterThan(minConnectivity - 1));
408
409 // edge connectivity is least restrictive
410 AssertThat(edgeCon[v][w], IsGreaterThan(nodeCon[v][w] - 1));
411 AssertThat(edgeCon[v][w], IsGreaterThan(edgeDirCon[v][w] - 1));
412
413 // (node) connectivity might never be greater than edge connectivity
414 AssertThat(edgeCon[v][w], IsGreaterThan(edgeDirCon[v][w] - 1));
415
416 // directed connectivity is most restrictive
417 AssertThat(nodeCon[v][w], IsGreaterThan(nodeDirCon[v][w] - 1));
418 AssertThat(edgeDirCon[v][w], IsGreaterThan(nodeDirCon[v][w] - 1));
419 }
420 }
421 }
422
423 // create a new node with some edges
424 // thus reducing the overall connectivity
425 if(minConnectivity > 0) {
426 node w = graph.firstNode();
427 node v = graph.newNode();
428 int modifiedExpected = randomNumber(0, minConnectivity - 1);
429 for (int i = 0; i < modifiedExpected; i++) {
430 OGDF_ASSERT(w != v);
431 graph.newEdge(w, v);
432 w = w->succ();
433 }
434
435 AssertThat(nodeAlgo.computeConnectivity(graph, nodeCon), Equals(modifiedExpected));
436 }
437 });
438 }
439});
440}
441
442go_bandit([]() {
443 describe("Maximum flow algorithms", [](){
444 registerTestSuite<int>("int");
445 registerTestSuite<double>("double");
446 registerTestSuite<unsigned long long int>("unsigned long long int");
447 });
448
449 describe("Connectivity Tester", [](){
450 describeConnectivityTester("random graphs", 0, [](Graph &graph, int n) {
451 randomGraph(graph, n, randomNumber(n, (n*(n-1))/2));
452 });
453
454 describeConnectivityTester("planar connected graphs", 1, [](Graph &graph, int n) {
455 randomPlanarConnectedGraph(graph, n, randomNumber(n, (n*(n-1))/2));
456 });
457
458 describeConnectivityTester("biconnected graphs", 2, [](Graph &graph, int n) {
459 randomBiconnectedGraph(graph, n, randomNumber(n, (n*(n-1))/2));
460 });
461
462 describeConnectivityTester("triconnected graphs", 3, [](Graph &graph, int n) {
463 randomTriconnectedGraph(graph, n, randomDouble(0, 1), randomDouble(0, 1));
464 });
465 });
466});
467