1/** \file
2 * \brief Tests for Steiner Tree approximation algorithm helpers
3 *
4 * \author Stephan Beyer
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 <set>
33#include <ogdf/basic/EpsilonTest.h>
34#include <ogdf/module/MinSteinerTreeModule.h>
35#include <ogdf/graphalg/steiner_tree/FullComponentStore.h>
36#include <ogdf/graphalg/steiner_tree/Full2ComponentGenerator.h>
37#include <ogdf/graphalg/steiner_tree/Full3ComponentGeneratorVoronoi.h>
38#include <ogdf/graphalg/steiner_tree/Full3ComponentGeneratorEnumeration.h>
39#include <ogdf/graphalg/steiner_tree/FullComponentGeneratorDreyfusWagner.h>
40#include <testing.h>
41
42using namespace std::placeholders;
43
44static EpsilonTest et(1e-6);
45
46template<typename T>
47struct EdgeData {
48 int source;
49 int target;
50 T cost;
51};
52
53//! Predefined instances that can be used by using their index
54template<typename T>
55static std::pair<std::vector<int>, std::vector<EdgeData<T>>> predefinedInstanceData(int i) {
56 switch (i) {
57 case 1:
58 // an instance with two terminal nodes
59 return {{0, 3},
60 {{0, 2, 3},
61 {1, 0, 1},
62 {3, 2, 4},
63 {2, 1, 1},
64 {1, 3, 6}}};
65 case 2:
66 // a simple instance with all nodes being terminals
67 return {{0, 1, 2}, {{0, 1, 2}, {0, 2, 2}}};
68 case 3:
69 // an instance to check heuristics avoiding terminals
70 return {{0, 1, 2},
71 {{0, 3, 1},
72 {0, 1, 2},
73 {1, 3, 1},
74 {2, 3, 5},
75 {2, 1, 2}}};
76 case 4:
77 // an instance to check heuristics preferring terminals
78 return {{0, 1, 2},
79 {{0, 3, 1},
80 {0, 1, 2},
81 {1, 3, 1},
82 {2, 5, 1},
83 {5, 4, 1},
84 {4, 3, 1},
85 {2, 1, 2}}};
86 }
87 return {{}, {}};
88};
89
90//! An auxiliary class for nicer tests
91template<typename T>
92struct Instance {
93 EdgeWeightedGraph<T> graph;
94 List<node> terminals;
95 NodeArray<bool> isTerminal;
96 Array<node> v;
97
98 //! Constructs a custom instance
99 Instance(std::vector<int> terminalList, std::vector<EdgeData<T>> edges) {
100 int n = 0;
101 for (auto e : edges) {
102 Math::updateMax(n, e.source + 1);
103 Math::updateMax(n, e.target + 1);
104 }
105
106 v.init(n);
107 for (int i = 0; i < n; ++i) {
108 v[i] = graph.newNode();
109 }
110
111 for (auto e : edges) {
112 graph.newEdge(v[e.source], v[e.target], e.cost);
113 }
114
115 setTerminals(terminalList);
116 }
117
118 //! Constructs a predefined instance with index \p i
119 explicit Instance(int i)
120 : Instance(predefinedInstanceData<T>(i).first, predefinedInstanceData<T>(i).second)
121 {}
122
123 void setTerminals(std::vector<int> terminalList) {
124 isTerminal.init(graph, false);
125 for (auto t : terminalList) {
126 OGDF_ASSERT(t <= v.high());
127 isTerminal[v[t]] = true;
128 }
129 terminals.clear();
130 MinSteinerTreeModule<T>::getTerminals(terminals, graph, isTerminal);
131 }
132};
133
134template<typename T>
135struct Arguments {
136 NodeArray<NodeArray<T>> distance;
137 NodeArray<NodeArray<edge>> pred;
138};
139
140template<typename T>
141struct ModifiedShortestPathAlgorithmsTest {
142 //! Assert something when considering a shortest path tree from a start node
143 struct AssertFrom {
144 int start;
145 std::function<void(const Instance<T> &, const NodeArray<T> &, const NodeArray<edge> &)> doAssert;
146 };
147
148 //! Test a predefined instance
149 static void testIt(std::string &&title, int instance,
150 std::function<void(const Instance<T> &, Arguments<T> &)> doAPSP,
151 std::initializer_list<AssertFrom> list) {
152 it(title, [&] {
153 Instance<T> S(instance);
154 Arguments<T> arg;
155
156 doAPSP(S, arg);
157
158 for (auto af : list) {
159 af.doAssert(S, arg.distance[S.v[af.start]], arg.pred[S.v[af.start]]);
160 }
161 });
162 }
163
164 //! Assert that \p nodes have no predecessor
165 static void assertHasNoPred(const Instance<T> &S, const NodeArray<edge> &pred, std::initializer_list<int> nodes) {
166 for (int i : nodes) {
167 AssertThat(pred[S.v[i]], IsNull());
168 }
169 }
170
171 //! For each pair (\a u, \a d) in \p nodeDistancePairs, assert that
172 //! the distance to \a u equals \a d.
173 static void assertDistanceTo(const Instance<T> &S, const NodeArray<T> &distance, std::initializer_list<std::pair<int, T>> nodeDistancePairs) {
174 for (auto p : nodeDistancePairs) {
175 AssertThat(et.equal(distance[S.v[p.first]], T(p.second)), IsTrue());
176 }
177 }
178
179 //! For each pair (\a u, \a v) in \p nodePredPairs, assert that the predecessor of \a u is \a v
180 //! if \a v is nonnegative. Otherwise just make sure \a u has a predecessor.
181 static void assertPred(const Instance<T> &S, const NodeArray<edge> &pred, std::initializer_list<std::pair<int, int>> nodePredPairs) {
182 for (auto p : nodePredPairs) {
183 AssertThat(pred[S.v[p.first]], !IsNull());
184 if (p.second >= 0) {
185 AssertThat(pred[S.v[p.first]]->opposite(S.v[p.first]), Equals(S.v[p.second]));
186 }
187 }
188 }
189
190 //! Assert for predefined instance 2, that the third terminal is unreachable...
191 //! If \p byDistance is true, it expects the terminal to be unreachable by
192 //! distance, too, that is, the distance is \c std::numeric_limits<T>::max().
193 static void assertThirdUnreachable(const Instance<T> &S, const NodeArray<T> &distance, const NodeArray<edge> &pred, bool byDistance) {
194 assertHasNoPred(S, pred, {1, 2});
195 assertPred(S, pred, {{0, -1}});
196 assertDistanceTo(S, distance, {{0, 2}, {2, 0}});
197 if (byDistance) {
198 AssertThat(distance[S.v[1]], Equals(std::numeric_limits<T>::max()));
199 } else {
200 AssertThat(distance[S.v[1]], IsGreaterThan(3));
201 AssertThat(distance[S.v[1]], IsLessThan(5));
202 }
203 }
204
205 static void itMimicsOrdinaryShortestPath(const std::string spName,
206 std::function<void(const Instance<T> &S, Arguments<T> &arg)> spAlg) {
207 testIt("mimics ordinary " + spName + " when terminals are not in between",
208 1, spAlg, {{0, [&](const Instance<T> &S, const NodeArray<T> &distance, const NodeArray<edge> &pred) {
209 assertHasNoPred(S, pred, {0});
210 assertDistanceTo(S, distance, {{0, 0}, {1, 1}, {2, 2}, {3, 6}});
211 assertPred(S, pred, {{1, 0}, {2, 1}, {3, 2}});
212 }}, {3, [&](const Instance<T> &S, const NodeArray<T> &distance, const NodeArray<edge> &pred) {
213 assertHasNoPred(S, pred, {3});
214 assertDistanceTo(S, distance, {{3, 0}, {1, 5}, {2, 4}, {0, 6}});
215 assertPred(S, pred, {{0, 1}, {1, 2}, {2, 3}});
216 }}});
217 }
218
219 //! The test for the algorithm variants preferring paths over terminals
220 static void callExpectPreferTerminals(const std::string spName,
221 std::function<void(const Instance<T> &S, Arguments<T> &arg)> spAlg) {
222 describe(spName + " preferring terminals heuristic", [&] {
223 itMimicsOrdinaryShortestPath(spName, spAlg);
224
225 testIt("marks the third terminal on a path of three terminals as unreachable (by predecessor only)",
226 2, spAlg, {{2, std::bind(assertThirdUnreachable, _1, _2, _3, false)}});
227
228 testIt("prefers terminals in shortest paths",
229 4, spAlg, {{0, [&](const Instance<T> &S, const NodeArray<T> &distance, const NodeArray<edge> &pred) {
230 assertHasNoPred(S, pred, {0, 2});
231 assertPred(S, pred, {{1, -1}, {3, 0}, {4, 3}, {5, 4}});
232 AssertThat(pred[S.v[1]]->opposite(S.v[1]), Equals(S.v[0]) || Equals(S.v[3]));
233 assertDistanceTo(S, distance, {{0, 0}, {3, 1}, {4, 2}, {5, 3}, {1, 2}, {2, 4}});
234 }}, {2, [&](const Instance<T> &S, const NodeArray<T> &distance, const NodeArray<edge> &pred) {
235 assertHasNoPred(S, pred, {2, 0, 3});
236 assertPred(S, pred, {{1, 2}, {4, 5}, {5, 2}});
237 assertDistanceTo(S, distance, {{2, 0}, {3, 3}, {4, 2}, {5, 1}, {0, 4}, {1, 2}});
238 }}});
239 });
240 }
241
242 //! The test for the algorithm variants avoiding paths over terminals
243 static void callExpectForbidTerminals(const std::string spName,
244 std::function<void(const Instance<T> &S, Arguments<T> &arg)> spAlg) {
245 describe(spName +" avoiding terminals heuristic", [&] {
246 itMimicsOrdinaryShortestPath(spName, spAlg);
247
248 testIt("marks the third terminal on a path of three terminals as unreachable (by predecessor and distance)",
249 2, spAlg, {{2, std::bind(assertThirdUnreachable, _1, _2, _3, true)}});
250
251 testIt("uses a detour as shortest path over nonterminals",
252 3, spAlg, {{0, [&](const Instance<T> &S, const NodeArray<T> &distance, const NodeArray<edge> &pred) {
253 assertHasNoPred(S, pred, {0});
254 assertPred(S, pred, {{1, -1}, {2, 3}, {3, 0}});
255 AssertThat(pred[S.v[1]]->opposite(S.v[1]), Equals(S.v[0]) || Equals(S.v[3]));
256 assertDistanceTo(S, distance, {{0, 0}, {3, 1}, {1, 2}, {2, 6}});
257 }}});
258 });
259 }
260};
261
262template<typename T>
263static void ssspDetour(const Instance<T> &S, Arguments<T> &arg) {
264 MinSteinerTreeModule<T>::allTerminalShortestPathsDetour(S.graph, S.terminals, S.isTerminal, arg.distance, arg.pred);
265}
266
267template<typename T>
268static void ssspStrict(const Instance<T> &S, Arguments<T> &arg) {
269 MinSteinerTreeModule<T>::allTerminalShortestPathsStrict(S.graph, S.terminals, S.isTerminal, arg.distance, arg.pred);
270}
271
272template<typename T>
273static void apspDetour(const Instance<T> &S, Arguments<T> &arg) {
274 ArrayBuffer<node> nonterminals;
275 MinSteinerTreeModule<T>::getNonterminals(nonterminals, S.graph, S.isTerminal);
276 MinSteinerTreeModule<T>::allPairShortestPathsDetour(S.graph, nonterminals, arg.distance, arg.pred);
277}
278
279template<typename T>
280static void apspStrict(const Instance<T> &S, Arguments<T> &arg) {
281 MinSteinerTreeModule<T>::allPairShortestPathsStrict(S.graph, S.isTerminal, arg.distance, arg.pred);
282}
283
284//! Tests for shortest path algorithms (SSSP and APSP variants)
285template<typename T>
286static void testShortestPathAlgorithms() {
287 ModifiedShortestPathAlgorithmsTest<T>::callExpectForbidTerminals("SSSP", ssspDetour<T>);
288 ModifiedShortestPathAlgorithmsTest<T>::callExpectPreferTerminals("SSSP", ssspStrict<T>);
289 ModifiedShortestPathAlgorithmsTest<T>::callExpectForbidTerminals("APSP", apspDetour<T>);
290 ModifiedShortestPathAlgorithmsTest<T>::callExpectPreferTerminals("APSP", apspStrict<T>);
291}
292
293//! Test MinSteinerTreeModule<T>::isSteinerTree()
294template<typename T>
295static void testIsSteinerTree() {
296 std::unique_ptr<Instance<T>> S;
297 std::unique_ptr<EdgeWeightedGraphCopy<T>> tree;
298
299 before_each([&] {
300 S.reset(new Instance<T>({0, 2}, {{0, 1, 2}, {1, 2, 3}, {2, 0, 7}}));
301 edge eCycle = S->graph.lastEdge();
302 OGDF_ASSERT(eCycle->source() == S->v[2]);
303 OGDF_ASSERT(eCycle->target() == S->v[0]);
304
305 tree.reset(new EdgeWeightedGraphCopy<T>(S->graph));
306 tree->delEdge(tree->copy(eCycle));
307 });
308
309 it("recognizes a valid Steiner tree", [&] {
310 AssertThat(MinSteinerTreeModule<T>::isSteinerTree(S->graph, S->terminals, S->isTerminal, *tree), IsTrue());
311 });
312
313 it("recognizes a disconnected Steiner tree", [&] {
314 tree->delEdge(tree->chooseEdge());
315
316 AssertThat(MinSteinerTreeModule<T>::isSteinerTree(S->graph, S->terminals, S->isTerminal, *tree), IsFalse());
317 });
318
319 it("recognizes a Steiner tree with extra nodes", [&] {
320 node v = S->graph.newNode();
321 S->isTerminal[v] = true;
322 S->terminals.pushFront(v);
323
324 AssertThat(MinSteinerTreeModule<T>::isSteinerTree(S->graph, S->terminals, S->isTerminal, *tree), IsFalse());
325 });
326
327 it("recognizes a Steiner tree with redundant Steiner node", [&] {
328 node u = S->terminals.front();
329 node v = S->graph.newNode();
330 edge e = S->graph.newEdge(u, v, 1);
331 tree->newNode(v);
332 tree->newEdge(e, 1);
333
334 AssertThat(MinSteinerTreeModule<T>::isSteinerTree(S->graph, S->terminals, S->isTerminal, *tree), IsFalse());
335 });
336}
337
338//! Test that the module handles calls on trivial instances
339template<typename T>
340static void testCallTrivial() {
341 class MinSteinerTreeDummy : public MinSteinerTreeModule<T> {
342 protected:
343 T computeSteinerTree(const EdgeWeightedGraph<T> &G, const List<node> &terminals,
344 const NodeArray<bool> &isTerminal,
345 EdgeWeightedGraphCopy<T> *&finalSteinerTree) override {
346 throw std::runtime_error("Not implemented.");
347 }
348 };
349
350 MinSteinerTreeDummy dummy;
351 Instance<T> S({},
352 {{1, 2, 26}, {2, 3, 16}, {3, 1, 10},
353 {0, 1, 15}, {0, 2, 14}, {0, 3, 1}});
354 EdgeWeightedGraphCopy<T> *solution;
355
356 before_each([&] {
357 solution = nullptr;
358 });
359
360 after_each([&] {
361 delete solution;
362 });
363
364 it("solves an instance without terminals", [&] {
365 T cost = dummy.call(S.graph, S.terminals, S.isTerminal, solution);
366 AssertThat(cost, Equals(0));
367 AssertThat(solution, !IsNull());
368 AssertThat(solution->empty(), IsTrue());
369 });
370
371 it("solves an instance with exactly one terminal", [&] {
372 S.setTerminals({3});
373 T cost = dummy.call(S.graph, S.terminals, S.isTerminal, solution);
374 AssertThat(cost, Equals(0));
375 AssertThat(solution, !IsNull());
376 AssertThat(solution->numberOfNodes(), Equals(1));
377 AssertThat(solution->numberOfEdges(), Equals(0));
378 AssertThat(solution->original(solution->firstNode()), Equals(S.v[3]));
379 });
380
381 it("solves an instance with exactly two terminals", [&] {
382 S.setTerminals({2, 1});
383 T cost = dummy.call(S.graph, S.terminals, S.isTerminal, solution);
384 AssertThat(cost, Equals(25));
385 AssertThat(solution, !IsNull());
386 AssertThat(solution->numberOfNodes(), Equals(4));
387 AssertThat(solution->numberOfEdges(), Equals(3));
388 AssertThat(MinSteinerTreeModule<T>::isSteinerTree(S.graph, S.terminals, S.isTerminal, *solution), IsTrue());
389 });
390}
391
392template<typename T>
393static void describeMinSteinerTreeModule(const std::string &&type) {
394 describe("MinSteinerTreeModule<" + type + ">", [&] {
395 describe("Modified shortest path algorithms", [] {
396 testShortestPathAlgorithms<T>();
397 });
398 describe("isSteinerTree", [] {
399 testIsSteinerTree<T>();
400 });
401 describe("call on trivial cases", [] {
402 testCallTrivial<T>();
403 });
404 });
405}
406
407template<typename T>
408static void assertTerminals(const Instance<T> &S, std::initializer_list<node> terminals) {
409 for (node t : terminals) {
410 AssertThat(S.isTerminal[t], IsTrue());
411 }
412}
413
414template<typename T>
415static void testFull2ComponentGenerator(const steiner_tree::Full2ComponentGenerator<T> &fcg) {
416 Instance<T> S({0, 1, 2},
417 {{0, 3, 1}, {3, 2, 1}, {2, 4, 2}, {4, 1, 1},
418 {3, 5, 1}, {5, 4, 2}});
419
420 it("generates full components with terminal-avoiding APSP", [&] {
421 Arguments<T> arg;
422 apspDetour(S, arg);
423
424 int number = 0;
425 fcg.call(S.graph, S.terminals, arg.distance, arg.pred,
426 [&](node u, node v, T minCost) {
427 ++number;
428 assertTerminals(S, {u, v});
429 std::set<std::set<node>> allowed = {{S.v[0], S.v[1]}, {S.v[0], S.v[2]}, {S.v[1], S.v[2]}};
430 std::set<node> actual = {u, v};
431 AssertThat(allowed, Contains(actual));
432 if (std::set<node>{u, v} == std::set<node>{S.v[0], S.v[1]}) {
433 AssertThat(et.equal(minCost, T(5)), IsTrue());
434 } else
435 if (std::set<node>{u, v} == std::set<node>{S.v[0], S.v[2]}) {
436 AssertThat(et.equal(minCost, T(2)), IsTrue());
437 } else
438 if (std::set<node>{u, v} == std::set<node>{S.v[1], S.v[2]}) {
439 AssertThat(et.equal(minCost, T(3)), IsTrue());
440 }
441 });
442 AssertThat(number, Equals(3));
443 });
444
445 it("generates full components with terminal-preferring APSP", [&] {
446 Arguments<T> arg;
447 apspStrict(S, arg);
448
449 int number = 0;
450 fcg.call(S.graph, S.terminals, arg.distance, arg.pred,
451 [&](node u, node v, T minCost) {
452 ++number;
453 assertTerminals(S, {u, v});
454 std::set<std::set<node>> allowed = {{S.v[0], S.v[2]}, {S.v[1], S.v[2]}};
455 std::set<node> actual = {u, v};
456 AssertThat(allowed, Contains(actual));
457 if (std::set<node>{u, v} == std::set<node>{S.v[0], S.v[2]}) {
458 AssertThat(et.equal(minCost, T(2)), IsTrue());
459 } else
460 if (std::set<node>{u, v} == std::set<node>{S.v[1], S.v[2]}) {
461 AssertThat(et.equal(minCost, T(3)), IsTrue());
462 }
463 });
464 AssertThat(number, Equals(2));
465 });
466}
467
468template<typename T>
469static void testFull3ComponentGeneratorModule(std::string name, const steiner_tree::Full3ComponentGeneratorModule<T> &fcg) {
470 describe(name, [&] {
471 std::unique_ptr<Instance<T>> S; // a pointer because we may change the instance in the "it"s
472
473 before_each([&] {
474 S.reset(new Instance<T>({0, 1, 2, 3, 4},
475 {{0, 5, 1}, {1, 5, 1}, {3, 5, 1},
476 {5, 6, 1}, {2, 6, 1},
477 {2, 7, 4}, {4, 7, 3},
478 {0, 1, 2}, {2, 1, 3}}));
479 });
480
481 it("generates full components with terminal-avoiding APSP", [&] {
482 Arguments<T> arg;
483 apspDetour(*S, arg);
484
485 int number = 0;
486 fcg.call(S->graph, S->terminals, S->isTerminal, arg.distance, arg.pred,
487 [&](node u, node v, node w, node center, T minCost) {
488 ++number;
489 assertTerminals(*S, {u, v, w});
490 AssertThat(S->isTerminal[center], IsFalse());
491 AssertThat(u, !Equals<node>(S->v[4]));
492 AssertThat(v, !Equals<node>(S->v[4]));
493 AssertThat(w, !Equals<node>(S->v[4]));
494 AssertThat(center, Equals<node>(S->v[5]));
495 });
496 AssertThat(number, IsGreaterThan(2) || IsLessThan(5));
497 });
498
499 it("generates full components with terminal-preferring APSP", [&] {
500 Arguments<T> arg;
501 apspStrict(*S, arg);
502
503 int number = 0;
504 fcg.call(S->graph, S->terminals, S->isTerminal, arg.distance, arg.pred,
505 [&](node u, node v, node w, node center, T minCost) {
506 ++number;
507 assertTerminals(*S, {u, v, w});
508 AssertThat(S->isTerminal[center], IsFalse());
509 AssertThat(u, !Equals<node>(S->v[4]));
510 AssertThat(v, !Equals<node>(S->v[4]));
511 AssertThat(w, !Equals<node>(S->v[4]));
512 AssertThat(center, Equals<node>(S->v[5]));
513 });
514 AssertThat(number, IsGreaterThan(2) || IsLessThan(5));
515 });
516
517 it("omits generating 3-components that are dominated by 2-components", [&] {
518 S->graph.newEdge(S->v[2], S->v[3], 1);
519 S->graph.newEdge(S->v[3], S->v[1], 1);
520 S->graph.newEdge(S->v[1], S->v[2], 1);
521
522 Arguments<T> arg;
523 apspStrict(*S, arg);
524
525 int number = 0;
526 fcg.call(S->graph, S->terminals, S->isTerminal, arg.distance, arg.pred,
527 [&](node u, node v, node w, node center, T minCost) {
528 ++number;
529 });
530 AssertThat(number, Equals(0));
531 });
532 });
533}
534
535template<typename T>
536static void testFullComponentGeneratorDreyfusWagner() {
537 std::unique_ptr<Instance<T>> S;
538 using FCG = steiner_tree::FullComponentGeneratorDreyfusWagner<T>;
539
540 before_each([&] {
541 S.reset(new Instance<T>({0, 1, 2, 3, 4},
542 {{0, 5, 1}, {1, 5, 1}, {3, 5, 1},
543 {5, 6, 1}, {2, 6, 1},
544 {2, 7, 4}, {4, 7, 3},
545 {0, 1, 2}, {2, 1, 3}}));
546 });
547
548 auto testComponents = [&](const Arguments<T>& arg, const FCG& fcg, int k) {
549 int nTotal = 0;
550 int nValid = 0;
551
552 SubsetEnumerator<node> terminalSubset(S->terminals);
553 for (terminalSubset.begin(k); terminalSubset.valid(); terminalSubset.next()) {
554 EdgeWeightedGraphCopy<T> component;
555 List<node> terminals;
556 terminalSubset.list(terminals);
557 fcg.getSteinerTreeFor(terminals, component);
558 if (FCG::isValidComponent(component, arg.pred, S->isTerminal)) {
559 for (node t : terminals) {
560 AssertThat(component.copy(t)->degree(), Equals(1));
561 };
562 ++nValid;
563 };
564 ++nTotal;
565 };
566 AssertThat(nTotal, Equals(Math::binomial(S->terminals.size(), k)));
567 return nValid;
568 };
569
570 it("generates full components with terminal-avoiding APSP", [&] {
571 Arguments<T> arg;
572 apspDetour(*S, arg);
573
574 FCG fcg(S->graph, S->terminals, arg.distance);
575 fcg.call(5);
576
577 AssertThat(testComponents(arg, fcg, 2), Equals(7));
578 AssertThat(testComponents(arg, fcg, 3), Equals(4));
579 AssertThat(testComponents(arg, fcg, 4), Equals(1));
580 AssertThat(testComponents(arg, fcg, 5), Equals(0));
581 });
582
583 it("generates full components with terminal-preferring APSP", [&] {
584 Arguments<T> arg;
585 apspStrict(*S, arg);
586
587 FCG fcg(S->graph, S->terminals, arg.distance);
588 fcg.call(5);
589
590 AssertThat(testComponents(arg, fcg, 2), Equals(7));
591 AssertThat(testComponents(arg, fcg, 3), Equals(4));
592 AssertThat(testComponents(arg, fcg, 4), Equals(1));
593 AssertThat(testComponents(arg, fcg, 5), Equals(0));
594 });
595
596 it("omits generating 3-components that are dominated by 2-components", [&] {
597 S->graph.newEdge(S->v[2], S->v[3], 1);
598 S->graph.newEdge(S->v[3], S->v[1], 1);
599 S->graph.newEdge(S->v[1], S->v[2], 1);
600
601 Arguments<T> arg;
602 apspStrict(*S, arg);
603
604 FCG fcg(S->graph, S->terminals, arg.distance);
605 fcg.call(3);
606
607 AssertThat(testComponents(arg, fcg, 3), Equals(0));
608 });
609}
610
611template<typename T>
612static void describeFullComponentGenerators(const std::string &&type) {
613 describe("Full2ComponentGenerator<" + type + ">", [&] {
614 steiner_tree::Full2ComponentGenerator<T> fcg;
615 testFull2ComponentGenerator(fcg);
616 });
617 describe("Full3ComponentGeneratorModule<" + type + ">", [&] {
618 steiner_tree::Full3ComponentGeneratorVoronoi<T> fcgVoronoi;
619 testFull3ComponentGeneratorModule("Voronoi", fcgVoronoi);
620
621 steiner_tree::Full3ComponentGeneratorEnumeration<T> fcgEnumeration;
622 testFull3ComponentGeneratorModule("Enumeration", fcgEnumeration);
623 });
624 describe("FullComponentGeneratorDreyfusWagner<" + type + ">", [&] {
625 testFullComponentGeneratorDreyfusWagner<T>();
626 });
627}
628
629template<typename T>
630static void describeFullComponentStore(const std::string&& type) {
631 describe("FullComponentStore<" + type + ">", [&] {
632 Instance<T> S({0, 1, 2, 3}, {
633 {0, 4, 1}, {4, 8, 1},
634 {1, 5, 1}, {5, 8, 1},
635 {2, 6, 1}, {6, 8, 1},
636 {3, 7, 1}, {7, 8, 1},
637 });
638
639 std::unique_ptr<steiner_tree::FullComponentStore<T>> fcs;
640 before_each([&] {
641 fcs.reset(new steiner_tree::FullComponentStore<T>(S.graph, S.terminals, S.isTerminal));
642 });
643
644 it("is empty when nothing is inserted", [&] {
645 AssertThat(fcs->isEmpty(), IsTrue());
646 });
647
648 describe("containing component with degree-2 nodes", [&] {
649 EdgeWeightedGraphCopy<T> copy(S.graph);
650
651 before_each([&] {
652 fcs->insert(copy);
653 });
654
655 it("inserts the component", [&] {
656 AssertThat(fcs->isEmpty(), IsFalse());
657 AssertThat(fcs->size(), Equals(1));
658 AssertThat(fcs->terminals(0).size(), Equals(4));
659 AssertThat(fcs->terminals(0)[0]->index(), Equals(0));
660 AssertThat(fcs->terminals(0)[1]->index(), Equals(1));
661 AssertThat(fcs->terminals(0)[2]->index(), Equals(2));
662 AssertThat(fcs->terminals(0)[3]->index(), Equals(3));
663 });
664
665 it("iterates over all nodes without predecessor matrix", [&] {
666 NodeArray<int> marked(S.graph, 0);
667
668 fcs->foreachNode(0, [&](node v) {
669 ++marked[v];
670 });
671
672 for (int count : marked) {
673 AssertThat(count, Equals(1));
674 }
675 });
676
677 it("iterates over all nodes with predecessor matrix", [&] {
678 Arguments<T> arg;
679 MinSteinerTreeModule<T>::allPairShortestPathsStrict(S.graph, S.isTerminal, arg.distance, arg.pred);
680 NodeArray<int> marked(S.graph, 0);
681
682 fcs->foreachNode(0, arg.pred, [&](node v) {
683 ++marked[v];
684 });
685
686 for (int count : marked) {
687 AssertThat(count, Equals(1));
688 }
689 });
690 });
691
692 describe("containing component without degree-2 nodes", [&] {
693 EdgeWeightedGraphCopy<T> component(S.graph);
694 for (int i : {4, 5, 6, 7}) {
695 component.delNode(component.copy(S.v[i]));
696 }
697 for (int i : {0, 1, 2, 3}) {
698 component.newEdge(component.copy(S.v[i]), component.copy(S.v[8]), 2);
699 }
700
701 before_each([&] {
702 fcs->insert(component);
703 });
704
705 it("inserts the component", [&] {
706 AssertThat(fcs->isEmpty(), IsFalse());
707 AssertThat(fcs->size(), Equals(1));
708 AssertThat(fcs->terminals(0).size(), Equals(4));
709 AssertThat(fcs->terminals(0)[0]->index(), Equals(0));
710 AssertThat(fcs->terminals(0)[1]->index(), Equals(1));
711 AssertThat(fcs->terminals(0)[2]->index(), Equals(2));
712 AssertThat(fcs->terminals(0)[3]->index(), Equals(3));
713 });
714
715 it("iterates over all critical nodes only", [&] {
716 NodeArray<int> marked(S.graph, 0);
717
718 fcs->foreachNode(0, [&](node v) {
719 ++marked[v];
720 });
721
722 AssertThat(marked[S.v[0]], Equals(1));
723 AssertThat(marked[S.v[1]], Equals(1));
724 AssertThat(marked[S.v[2]], Equals(1));
725 AssertThat(marked[S.v[3]], Equals(1));
726 AssertThat(marked[S.v[4]], Equals(0));
727 AssertThat(marked[S.v[5]], Equals(0));
728 AssertThat(marked[S.v[6]], Equals(0));
729 AssertThat(marked[S.v[7]], Equals(0));
730 AssertThat(marked[S.v[8]], Equals(1));
731 });
732
733 it("iterates over all nodes using predecessor matrix", [&] {
734 Arguments<T> arg;
735 MinSteinerTreeModule<T>::allPairShortestPathsStrict(S.graph, S.isTerminal, arg.distance, arg.pred);
736 NodeArray<int> marked(S.graph, 0);
737
738 fcs->foreachNode(0, arg.pred, [&](node v) {
739 ++marked[v];
740 });
741
742 for (int count : marked) {
743 AssertThat(count, Equals(1));
744 }
745 });
746 });
747 });
748}
749
750go_bandit([]{
751 describe("Steiner tree approximation helpers", [] {
752 describeMinSteinerTreeModule<int>("int");
753 describeMinSteinerTreeModule<double>("double");
754 describeFullComponentGenerators<int>("int");
755 describeFullComponentGenerators<double>("double");
756 describeFullComponentStore<int>("int");
757 describeFullComponentStore<double>("double");
758 });
759});
760