1/** \file
2 * \brief Basic bandit test suite used for Steiner Tree problem reductions.
3 *
4 * \author Mihai Popa, 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 <string>
33#include <sstream>
34
35#include <ogdf/graphalg/SteinerTreePreprocessing.h>
36#include <ogdf/basic/graph_generators.h>
37#include <ogdf/graphalg/MinSteinerTreeDirectedCut.h>
38
39#include <testing.h>
40
41using namespace std;
42
43template<typename T>
44static void
45putRandomTerminals(const EdgeWeightedGraph<T> &wg, List<node> &terminals, NodeArray<bool> &isTerminal, int numberOfTerminals)
46{
47 isTerminal.init(wg, false);
48
49 Array<node> nodes(wg.numberOfNodes());
50 wg.allNodes(nodes);
51 nodes.permute();
52
53 Math::updateMin(numberOfTerminals, wg.numberOfNodes() - 1);
54 for (int i = 0; i < numberOfTerminals; ++i) {
55 const node v = nodes[i];
56 terminals.pushBack(v);
57 isTerminal[v] = true;
58 }
59}
60
61template<typename T>
62static void
63putRandomCosts(EdgeWeightedGraph<T> &wg, T x, T y, typename std::enable_if<std::is_integral<T>::value >::type* = 0)
64{
65 for (edge e : wg.edges) {
66 wg.setWeight(e, randomNumber(x, y));
67 }
68}
69
70template<typename T>
71static void
72putRandomCosts(EdgeWeightedGraph<T> &wg, T x, T y, typename std::enable_if<std::is_floating_point<T>::value >::type* = 0)
73{
74 for (edge e : wg.edges) {
75 wg.setWeight(e, randomDouble(x, y));
76 }
77}
78
79template<typename T>
80static void
81randomEdgeWeightedGraph(int numberOfnodes, int numberOfedges, int numberOfTerminals, T maxEdgeCost, EdgeWeightedGraph<T> &wg, List<node> &terminals, NodeArray<bool> &isTerminal)
82{
83 randomGraph(wg, numberOfnodes, numberOfedges);
84 makeConnected(wg);
85 putRandomTerminals<T>(wg, terminals, isTerminal, numberOfTerminals);
86 putRandomCosts<T>(wg, 1, maxEdgeCost);
87}
88
89template<typename T>
90static T
91getCostOfSolution(const EdgeWeightedGraphCopy<T> &wg)
92{
93 T cost = 0;
94 for (edge e : wg.edges) {
95 cost += wg.weight(e);
96 }
97
98 return cost;
99}
100
101template<typename T, typename Fun>
102static void
103testReduction(Fun reductionFun)
104{
105 int numberOfNodes = randomNumber(50, 120);
106 int numberOfEdges = randomNumber(numberOfNodes-1, 3*numberOfNodes);
107 int numberOfTerminals = randomNumber(1, numberOfNodes);
108 T maxEdgeCost = randomNumber(3, 1000000);
109 MinSteinerTreeDirectedCut<T> mst;
110
111 EdgeWeightedGraph<T> wg;
112 List<node> terminals;
113 NodeArray<bool> isTerminal;
114 randomEdgeWeightedGraph<T>(numberOfNodes, numberOfEdges, numberOfTerminals, maxEdgeCost, wg, terminals, isTerminal);
115
116 EdgeWeightedGraphCopy<T> *treeBefore = nullptr;
117 T costBefore = mst.call(wg, terminals, isTerminal, treeBefore);
118
119 SteinerTreePreprocessing<T> stprep(wg, terminals, isTerminal);
120 reductionFun(stprep);
121
122 EdgeWeightedGraphCopy<T> *treeAfter = nullptr;
123 T costAfter = stprep.solve(mst, treeAfter);
124
125 EpsilonTest et(1e-6);
126 AssertThat(et.equal(costAfter, costBefore), IsTrue());
127
128 AssertThat(MinSteinerTreeModule<T>::isSteinerTree(wg, terminals, isTerminal, *treeAfter), IsTrue());
129 AssertThat(et.equal(getCostOfSolution<T>(*treeAfter), costBefore), IsTrue());
130
131 delete treeBefore;
132 delete treeAfter;
133}
134
135template<typename T>
136static void
137testBasicReductions(int numberOfTests)
138{
139 for (int i = 1; i <= numberOfTests; ++i) {
140 it("does not change solution cost and finds a solution in the original graph", [&]() {
141 testReduction<T>([](SteinerTreePreprocessing<T> &stp) {
142 stp.deleteLeaves();
143 stp.degree2Test();
144 stp.makeSimple();
145 stp.leastCostTest();
146 });
147 });
148 }
149}
150
151template<typename T>
152static void
153testPrecomposedReductions(int numberOfTests)
154{
155 std::pair<const string, std::function<void(SteinerTreePreprocessing<T> &)>> reductions[] = {
156 { "trivial reductions", [](SteinerTreePreprocessing<T> &stprep) {
157 stprep.reduceTrivial();
158 }},
159 { "fast reductions", [](SteinerTreePreprocessing<T> &stprep) {
160 stprep.reduceFast();
161 }},
162 };
163 for (const auto &reduction : reductions) {
164 describe(reduction.first, [numberOfTests, &reduction]() {
165 for (int i = 1; i <= numberOfTests; ++i) {
166 it("does not change solution cost and finds a solution in the original graph", [&]() {
167 testReduction<T>(reduction.second);
168 });
169 }
170 });
171 }
172}
173
174template<typename T>
175static void
176testWildMixesOfReductions(string typeName, int numberOfTests)
177{
178 std::pair<string, std::function<void(SteinerTreePreprocessing<T> &)>> reductions[] = {
179 { "nearest-vertex", [](SteinerTreePreprocessing<T> &stprep) {
180 stprep.makeSimple();
181 stprep.deleteComponentsWithoutTerminals();
182 stprep.nearestVertexTest();
183 }},
184 { "shortest-link", [](SteinerTreePreprocessing<T> &stprep) {
185 stprep.deleteComponentsWithoutTerminals();
186 stprep.shortLinksTest();
187 }},
188 { "PTm", [](SteinerTreePreprocessing<T> &stprep) {
189 stprep.deleteComponentsWithoutTerminals();
190 stprep.PTmTest();
191 }},
192 { "terminal-distance", [](SteinerTreePreprocessing<T> &stprep) {
193 stprep.deleteComponentsWithoutTerminals();
194 stprep.terminalDistanceTest();
195 }},
196 { "long-edge", [](SteinerTreePreprocessing<T> &stprep) {
197 stprep.longEdgesTest();
198 }},
199 { "NTDk", [](SteinerTreePreprocessing<T> &stprep) {
200 stprep.makeSimple();
201 stprep.deleteComponentsWithoutTerminals();
202 stprep.NTDkTest();
203 }},
204 { "lower-bound-node", [](SteinerTreePreprocessing<T> &stprep) {
205 stprep.deleteComponentsWithoutTerminals();
206 stprep.lowerBoundBasedNodeTest();
207 }},
208 { "lower-bound-edge", [](SteinerTreePreprocessing<T> &stprep) {
209 stprep.deleteComponentsWithoutTerminals();
210 stprep.lowerBoundBasedEdgeTest();
211 }},
212 { "reachability", [](SteinerTreePreprocessing<T> &stprep) {
213 stprep.makeSimple();
214 stprep.deleteComponentsWithoutTerminals();
215 stprep.reachabilityTest();
216 }},
217 { "cut-reachability", [](SteinerTreePreprocessing<T> &stprep) {
218 stprep.deleteLeaves();
219 stprep.deleteComponentsWithoutTerminals();
220 stprep.cutReachabilityTest();
221 }},
222 };
223 auto size = sizeof reductions / sizeof reductions[0];
224 for (auto reductionBitmask = 1; reductionBitmask < (1 << size); ++reductionBitmask) {
225 string desc = "appliance of reductions";
226 ArrayBuffer<int> usedReductions;
227 for (auto cur = reductionBitmask, i = 0; cur; ++i, cur >>= 1) {
228 if (cur & 1) {
229 usedReductions.push(i);
230 }
231 }
232
233 for (auto i : usedReductions) {
234 desc += " " + reductions[i].first;
235 }
236 desc += " (" + typeName + ")";
237
238 describe(desc, [numberOfTests, &usedReductions, &reductions]() {
239 Array<int> order(usedReductions.size());
240 for (int j = 0; j < order.size(); ++j) {
241 order[j] = j;
242 }
243 for (int i = 1; i <= numberOfTests; ++i) {
244 std::stringstream ss;
245 ss << "does not change solution cost and finds a solution in the original graph (order "
246 << order << ")";
247 it(ss.str(), [&]() {
248 testReduction<T>([&usedReductions, &reductions](SteinerTreePreprocessing<T> &stp) {
249 for (auto redIndex : usedReductions) {
250 reductions[redIndex].second(stp);
251 }
252 });
253 });
254 order.permute();
255 }
256 });
257 }
258}
259
260template<typename T>
261static void
262registerSuite(const string &typeName)
263{
264 describe("basic reductions (" + typeName + ")", []() {
265 testBasicReductions<T>(15);
266 });
267 describe_skip("mix of all subsets of reductions (" + typeName + ")", [&typeName]() {
268 testWildMixesOfReductions<T>(typeName, 3);
269 });
270 describe("precomposed reductions (" + typeName + ")", []() {
271 testPrecomposedReductions<T>(15);
272 });
273}
274
275go_bandit([]() {
276 describe("SteinerTreePreprocessing", []() {
277 registerSuite<int>("int");
278 registerSuite<double>("double");
279 });
280});
281