1/** \file
2 * \brief Declaration of ogdf::MinSteinerTreeModule
3 *
4 * \author Matthias Woste, 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#pragma once
33
34#include <ogdf/basic/GraphAttributes.h>
35#include <ogdf/basic/PriorityQueue.h>
36#include <ogdf/basic/simple_graph_alg.h>
37#include <ogdf/basic/extended_graph_alg.h>
38#include <ogdf/energybased/FMMMLayout.h>
39#include <ogdf/graphalg/steiner_tree/Triple.h>
40#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
41#include <ogdf/fileformats/GraphIO.h>
42#include <ogdf/graphalg/AStarSearch.h>
43#include <sstream>
44
45namespace ogdf {
46
47/**
48 * Serves as an interface for various methods to
49 * compute or approximate minimum Steiner trees
50 * on undirected graphs with edge costs.
51 *
52 * Furthermore it supplies some auxiliary methods.
53 *
54 * @tparam T The type of the edge costs of the Steiner tree instance
55 */
56template<typename T>
57class MinSteinerTreeModule {
58public:
59 //! Do nothing on destruction
60 virtual ~MinSteinerTreeModule() { }
61
62 /**
63 * Calls the Steiner tree algorithm for nontrivial cases
64 * but handles trivial cases directly.
65 *
66 * @param G The weighted input graph
67 * @param terminals The list of terminal nodes
68 * @param isTerminal A bool array of terminals
69 * @param finalSteinerTree The final Steiner tree
70 * @return The total cost of the final Steiner tree
71 */
72 virtual T call(const EdgeWeightedGraph<T> &G,
73 const List<node> &terminals,
74 const NodeArray<bool> &isTerminal,
75 EdgeWeightedGraphCopy<T> *&finalSteinerTree
76 );
77
78 //! @name Auxiliary post-processing functions
79 //! @{
80
81 /**
82 * Prunes nonterminal leaves and their paths to terminal or branching nodes
83 *
84 * @param steinerTree The given Steiner tree
85 * @param isTerminal Incidence vector indicating terminal nodes
86 * @return The total cost of the removed edges (achieved improvement)
87 */
88 static T pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal);
89
90 /**
91 * Prunes the dangling Steiner path beginning at a given nonterminal leaf only
92 *
93 * @param steinerTree The given Steiner tree
94 * @param isTerminal Incidence vector indicating terminals
95 * @param start A nonterminal leaf to start pruning at
96 * @return The total cost of the removed edges (achieved improvement)
97 */
98 static T pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, node start);
99
100 /**
101 * Prunes dangling Steiner paths beginning at given nonterminal leaves only
102 *
103 * @see pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, node start)
104 */
105 static T pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, const List<node> &start);
106
107 /**
108 * Remove remaining cycles from a Steiner "almost" tree
109 *
110 * @return The edge weights of the removed edges (achieved improvement)
111 */
112 static T removeCyclesFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal);
113
114 //! @}
115 //! @name Special SSSP and APSP algorithms used in component-based approximation algorithms
116 //! @{
117
118 /**
119 * Modified single-source-shortest-paths (%Dijkstra)
120 * with heuristic to prefer paths over terminals
121 *
122 * A shortest path over a terminal will mark the nodes that
123 * come after that terminal as unreachable by setting the predecessor
124 * to \c nullptr.
125 * Nevertheless, the distance will be set correctly.
126 *
127 * @param G Input graph
128 * @param source Start terminal
129 * @param isTerminal Incidence vector indicating terminal nodes
130 * @param distance Distance matrix result
131 * @param pred Resulting shortest path such that \p pred[s][t] contains last edge of an s-t-path
132 */
133 static void singleSourceShortestPathsStrict(const EdgeWeightedGraph<T> &G, node source, const NodeArray<bool> &isTerminal, NodeArray<T> &distance, NodeArray<edge> &pred);
134
135 /**
136 * Modified single-source-shortest-paths (%Dijkstra)
137 * with heuristic to avoid paths over terminals
138 *
139 * Avoiding terminals results in paths with detours.
140 * If a node is only reachable over a terminal, there is no path to it in the solution, i.e.,
141 * there is no predecessor and the distance is \c std::numeric_limits<T>::max().
142 */
143 static void singleSourceShortestPathsDetour(const EdgeWeightedGraph<T> &G, node source, const NodeArray<bool> &isTerminal, NodeArray<T> &distance, NodeArray<edge> &pred);
144
145 //! Runs #singleSourceShortestPathsDetour from all terminals
146 static void allTerminalShortestPathsDetour(
147 const EdgeWeightedGraph<T> &G,
148 const List<node> &terminals,
149 const NodeArray<bool> &isTerminal,
150 NodeArray<NodeArray<T>> &distance,
151 NodeArray<NodeArray<edge>> &pred)
152 {
153 allTerminalShortestPaths(G, terminals, isTerminal, distance, pred, singleSourceShortestPathsDetour);
154 }
155
156 //! Runs #singleSourceShortestPathsStrict from all terminals
157 static void allTerminalShortestPathsStrict(
158 const EdgeWeightedGraph<T> &G,
159 const List<node> &terminals,
160 const NodeArray<bool> &isTerminal,
161 NodeArray<NodeArray<T>> &distance,
162 NodeArray<NodeArray<edge>> &pred)
163 {
164 allTerminalShortestPaths(G, terminals, isTerminal, distance, pred, singleSourceShortestPathsStrict);
165 }
166
167 /**
168 * Modified all-pair-shortest-paths algorithm (%Floyd-Warshall) over nonterminals
169 * with heuristic to prefer paths over terminals
170 *
171 * @param G Input graph
172 * @param isTerminal Incidence vector indicating terminal nodes
173 * @param distance Distance matrix result
174 * @param pred Resulting shortest path such that \p pred[s][t] contains last edge of an s-t-path
175 */
176 static void allPairShortestPathsStrict(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal, NodeArray<NodeArray<T>> &distance, NodeArray<NodeArray<edge>> &pred);
177
178 /**
179 * Modified all-pair-shortest-paths algorithm (%Floyd-Warshall) over nonterminals
180 * with heuristic to avoid paths over terminals
181 * and hence accepting detours
182 *
183 * @param G Input graph
184 * @param nonterminals Container of nonterminals
185 * @param distance Distance matrix result
186 * @param pred Resulting shortest path such that \p pred[s][t] contains last edge of an s-t-path
187 * @tparam CONTAINER Container
188 */
189 template<typename CONTAINER>
190 static void allPairShortestPathsDetour(const EdgeWeightedGraph<T> &G, const CONTAINER &nonterminals, NodeArray<NodeArray<T>> &distance, NodeArray<NodeArray<edge>> &pred);
191
192 //! @}
193 //! @name Drawings for debugging
194 //! @{
195
196 /**
197 * Writes an SVG file of a minimum Steiner tree in the original graph
198 *
199 * @param G The original weighted graph
200 * @param isTerminal Incidence vector indicating terminal nodes
201 * @param steinerTree The Steiner tree of the given graph
202 * @param filename The name of the output file
203 */
204 static void drawSVG(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal, const EdgeWeightedGraphCopy<T> &steinerTree, const char *filename);
205
206 /**
207 * Writes an SVG file of the instance graph
208 *
209 * @param G The weighted graph instance
210 * @param isTerminal Incidence vector indicating terminal nodes
211 * @param filename The name of the output file
212 */
213 static void drawSVG(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal, const char *filename) {
214 EdgeWeightedGraphCopy<T> emptySteinerTree;
215 emptySteinerTree.createEmpty(G);
216 drawSVG(G, isTerminal, emptySteinerTree, filename);
217 }
218
219 /**
220 * Writes a SVG that shows only the given Steiner tree
221 *
222 * @param steinerTree The Steiner tree to be drawn
223 * @param isTerminal Incidence vector indicating terminal nodes
224 * @param filename The name of the output file
225 */
226 static void drawSteinerTreeSVG(const EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, const char *filename);
227
228 //! @}
229
230 /**
231 * Checks in O(n) time if a given tree is acually a Steiner Tree
232 *
233 * @param G The original graph
234 * @param terminals The list of terminal nodes
235 * @param isTerminal A bool array of terminals
236 * @param steinerTree The Steiner tree to be checked
237 * @return true iff the given Steiner tree is actually one, false otherwise
238 */
239 static bool isSteinerTree(const EdgeWeightedGraph<T> &G, const List<node> &terminals, const NodeArray<bool> &isTerminal, const EdgeWeightedGraphCopy<T> &steinerTree);
240
241 /**
242 * Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite
243 *
244 * @param G The original graph
245 * @param isTerminal A bool array of terminals
246 * @return true iff the given Steiner tree problem instance is quasi-bipartite
247 */
248 static bool isQuasiBipartite(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal);
249
250 /**
251 * Generates a list (as List<node>) of all terminals
252 *
253 * @param terminals The returned list (terminals are appended)
254 * @param G The weighted input graph
255 * @param isTerminal A bool array of terminals
256 */
257 static inline void getTerminals(List<node> &terminals, const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal)
258 {
259 for (node v : G.nodes) {
260 if (isTerminal[v]) {
261 terminals.pushBack(v);
262 }
263 }
264 }
265
266 //! Sort terminals by index
267 static inline void sortTerminals(List<node> &terminals)
268 {
269 terminals.quicksort(GenericComparer<node, int>([](node v) { return v->index(); }));
270 }
271
272 /**
273 * Generates a list (as ArrayBuffer<node>) of all nonterminals
274 *
275 * @param nonterminals The returned list (nonterminals are appended)
276 * @param G The weighted input graph
277 * @param isTerminal A bool array of terminals
278 */
279 static inline void getNonterminals(ArrayBuffer<node> &nonterminals, const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal)
280 {
281 for (node v : G.nodes) {
282 if (!isTerminal[v]) {
283 nonterminals.push(v);
284 }
285 }
286 }
287
288protected:
289 /**
290 * Computes the actual Steiner tree
291 *
292 * @return The total cost of the final Steiner tree
293 */
294 virtual T computeSteinerTree(const EdgeWeightedGraph<T> &G,
295 const List<node> &terminals,
296 const NodeArray<bool> &isTerminal,
297 EdgeWeightedGraphCopy<T> *&finalSteinerTree
298 ) = 0;
299
300 //! Runs a given single-source-shortest-paths function from all terminals
301 static void allTerminalShortestPaths(
302 const EdgeWeightedGraph<T> &G,
303 const List<node> &terminals,
304 const NodeArray<bool> &isTerminal,
305 NodeArray<NodeArray<T>> &distance,
306 NodeArray<NodeArray<edge>> &pred,
307 std::function<void(const EdgeWeightedGraph<T> &, node, const NodeArray<bool> &, NodeArray<T> &, NodeArray<edge> &)> ssspFunc)
308 {
309 distance.init(G);
310 pred.init(G);
311 for (node u : terminals) {
312 ssspFunc(G, u, isTerminal, distance[u], pred[u]);
313 }
314 }
315
316private:
317 //! Common initialization routine for APSP algorithms
318 static void apspInit(const EdgeWeightedGraph<T> &G, NodeArray<NodeArray<T>> &distance, NodeArray<NodeArray<edge>> &pred);
319 //! Common initialization routine for SSSP algorithms
320 static void ssspInit(const EdgeWeightedGraph<T> &G, node source, PrioritizedMapQueue<node, T> &queue, NodeArray<T> &distance, NodeArray<edge> &pred);
321
322 //! The inner loop for APSP algorithm to avoid code duplication
323 inline static void apspInnerLoop(node v, const EdgeWeightedGraph<T> &G, NodeArray<NodeArray<T>> &distance, std::function<void(node, node, T)> func)
324 {
325 for (node u : G.nodes) {
326 const T duv = distance[u][v];
327 if (duv < std::numeric_limits<T>::max()) {
328 for (node w = u->succ(); w != nullptr; w = w->succ()) {
329 if (distance[v][w] < std::numeric_limits<T>::max()) {
330 func(u, w, duv + distance[v][w]);
331 }
332 }
333 }
334 }
335 }
336};
337
338template<typename T>
339T MinSteinerTreeModule<T>::call(const EdgeWeightedGraph<T> &G,
340 const List<node> &terminals,
341 const NodeArray<bool> &isTerminal,
342 EdgeWeightedGraphCopy<T> *&finalSteinerTree
343 )
344{
345 OGDF_ASSERT(isConnected(G));
346
347 if (terminals.size() > 2) {
348 return this->computeSteinerTree(G, terminals, isTerminal, finalSteinerTree);
349 }
350
351 finalSteinerTree = new EdgeWeightedGraphCopy<T>();
352 finalSteinerTree->createEmpty(G);
353 if (!terminals.empty()) {
354 finalSteinerTree->newNode(terminals.back());
355 }
356 if (terminals.size() <= 1) {
357 return 0;
358 }
359
360 OGDF_ASSERT(terminals.size() == 2);
361 T cost(0);
362 AStarSearch<T> astar;
363 NodeArray<edge> pred;
364 NodeArray<T> dist;
365 astar.call(G, G.edgeWeights(), terminals.front(), terminals.back(), pred);
366 OGDF_ASSERT(pred[terminals.back()] != nullptr); // connected
367 for (node t = terminals.back(); t != terminals.front(); t = pred[t]->opposite(t)) {
368 const edge e = pred[t];
369 finalSteinerTree->newNode(e->opposite(t));
370 finalSteinerTree->newEdge(e, G.weight(e));
371 cost += G.weight(e);
372 }
373 return cost;
374}
375
376template<typename T>
377bool MinSteinerTreeModule<T>::isSteinerTree(
378 const EdgeWeightedGraph<T> &G,
379 const List<node> &terminals,
380 const NodeArray<bool> &isTerminal,
381 const EdgeWeightedGraphCopy<T> &steinerTree)
382{
383 // the Steiner tree is actually a tree
384 if (!isTree(steinerTree)) {
385 return false;
386 }
387
388 // all terminal nodes are in the graph and have degree >= 1
389 for(node v : terminals) {
390 const node u = steinerTree.copy(v);
391 if (!u || (terminals.size() > 1 && u->degree() < 1)) {
392 return false;
393 }
394 }
395
396 // all Steiner nodes are inner nodes
397 for(node u : steinerTree.nodes) {
398 if (!isTerminal[steinerTree.original(u)]
399 && u->degree() <= 1) {
400 return false;
401 }
402 }
403
404 return true;
405}
406
407template<typename T>
408bool MinSteinerTreeModule<T>::isQuasiBipartite(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal)
409{
410 for (node v = G.firstNode(); v; v = v->succ()) {
411 if (!isTerminal[v]) {
412 for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
413 if (!isTerminal[adj->twinNode()]) {
414 return false;
415 }
416 }
417 }
418 }
419 return true;
420}
421
422template<typename T>
423T MinSteinerTreeModule<T>::pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, const node start)
424{
425 OGDF_ASSERT(isConnected(steinerTree));
426 T delWeights(0);
427 node u = start;
428 while (u->degree() == 1
429 && !isTerminal[steinerTree.original(u)]) {
430 const adjEntry adj = u->firstAdj();
431 const node v = adj->twinNode();
432 delWeights += steinerTree.weight(adj->theEdge());
433 steinerTree.delNode(u);
434 u = v;
435 }
436 return delWeights;
437}
438
439template<typename T>
440T MinSteinerTreeModule<T>::pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, const List<node> &start)
441{
442 T delWeights(0);
443 for (node v : start) {
444 delWeights += pruneDanglingSteinerPathFrom(steinerTree, isTerminal, v);
445 }
446 return delWeights;
447}
448
449template<typename T>
450T MinSteinerTreeModule<T>::pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal)
451{
452 List<node> start;
453 for (node u : steinerTree.nodes) {
454 if (u->degree() == 1
455 && !isTerminal[steinerTree.original(u)]) {
456 start.pushBack(u);
457 }
458 }
459
460 return pruneDanglingSteinerPathsFrom(steinerTree, isTerminal, start);
461}
462
463template<typename T>
464T MinSteinerTreeModule<T>::removeCyclesFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal)
465{
466 if (steinerTree.numberOfEdges() > steinerTree.numberOfNodes() - 1) {
467 EdgeArray<bool> isInTree(steinerTree);
468 T oldCost(0);
469 T newCost(computeMinST(steinerTree, steinerTree.edgeWeights(), isInTree));
470
471 List<node> pendant; // collect resulting pendant edges
472 for (edge nextEdge, e = steinerTree.firstEdge(); e; e = nextEdge) {
473 oldCost += steinerTree.weight(e);
474 nextEdge = e->succ();
475 if (!isInTree[e]) {
476 if (e->source()->degree() == 2) {
477 pendant.pushBack(e->source());
478 }
479 if (e->target()->degree() == 2) {
480 pendant.pushBack(e->target());
481 }
482 steinerTree.delEdge(e);
483 }
484 }
485 newCost -= MinSteinerTreeModule<T>::pruneDanglingSteinerPathsFrom(steinerTree, isTerminal, pendant);
486 return oldCost - newCost;
487 }
488 return 0;
489}
490
491template<typename T>
492void MinSteinerTreeModule<T>::ssspInit(const EdgeWeightedGraph<T> &G, node source, PrioritizedMapQueue<node, T> &queue, NodeArray<T> &distance, NodeArray<edge> &pred)
493{
494 distance.init(G, std::numeric_limits<T>::max());
495 distance[source] = 0;
496
497 for (node v : G.nodes) {
498 queue.push(v, distance[v]);
499 }
500
501 pred.init(G, nullptr);
502}
503
504template<typename T>
505void MinSteinerTreeModule<T>::singleSourceShortestPathsStrict(const EdgeWeightedGraph<T> &G, node source, const NodeArray<bool> &isTerminal, NodeArray<T> &distance, NodeArray<edge> &pred)
506{
507 PrioritizedMapQueue<node, T> queue(G);
508 ssspInit(G, source, queue, distance, pred);
509
510 // we must handle the source explicitly because it is a terminal
511 node v = queue.topElement();
512 queue.pop();
513 OGDF_ASSERT(v == source);
514 for (adjEntry adj : v->adjEntries) {
515 edge e = adj->theEdge();
516 node w = adj->twinNode();
517 if (distance[w] > G.weight(e)) { // this check is only necessary for multigraphs, otherwise this is always true
518 queue.decrease(w, (distance[w] = G.weight(e)));
519 pred[w] = e;
520 }
521 }
522
523 auto setPredecessor = [&](node w, edge e) {
524 bool wOnPathWithTerminal = isTerminal[v] || pred[v] == nullptr;
525 pred[w] = wOnPathWithTerminal ? nullptr : e;
526 };
527 while (!queue.empty()) {
528 v = queue.topElement();
529 queue.pop();
530
531 if (distance[v] == std::numeric_limits<T>::max()) { // min is unreachable, finished
532 break;
533 }
534 for (adjEntry adj : v->adjEntries) {
535 edge e = adj->theEdge();
536 node w = adj->twinNode();
537 T dist = distance[v] + G.weight(e);
538 if (distance[w] > dist) {
539 queue.decrease(w, (distance[w] = dist));
540 setPredecessor(w, e);
541 } else
542 if (distance[w] == dist
543 && pred[w] != nullptr) { // tie
544 setPredecessor(w, e);
545 }
546 }
547 }
548}
549
550template<typename T>
551void MinSteinerTreeModule<T>::singleSourceShortestPathsDetour(const EdgeWeightedGraph<T> &G, node source, const NodeArray<bool> &isTerminal, NodeArray<T> &distance, NodeArray<edge> &pred)
552{
553 PrioritizedMapQueue<node, T> queue(G);
554 ssspInit(G, source, queue, distance, pred);
555
556 while (!queue.empty()) {
557 node v = queue.topElement();
558 queue.pop();
559
560 if (isTerminal[v] && v != source) { // v is a terminal, ignore
561 continue;
562 }
563 if (distance[v] == std::numeric_limits<T>::max()) { // min is unreachable, finished
564 break;
565 }
566 for (adjEntry adj : v->adjEntries) {
567 edge e = adj->theEdge();
568 node w = adj->twinNode();
569 if (distance[w] > distance[v] + G.weight(e)) {
570 queue.decrease(w, (distance[w] = distance[v] + G.weight(e)));
571 pred[w] = e;
572 }
573 }
574 }
575}
576
577template<typename T>
578void MinSteinerTreeModule<T>::allPairShortestPathsStrict(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal, NodeArray<NodeArray<T>> &distance, NodeArray<NodeArray<edge>> &pred)
579{
580 apspInit(G, distance, pred);
581
582 for (node v : G.nodes) {
583 if (isTerminal[v]) { // v is a terminal
584 apspInnerLoop(v, G, distance, [&distance, &pred](node u, node w, T duvw) {
585 if (duvw <= distance[u][w]) { // prefer terminals
586 distance[w][u] = distance[u][w] = duvw;
587 pred[w][u] = pred[u][w] = nullptr;
588 }
589 });
590 } else { // v is not a terminal
591 apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
592 if (duvw < distance[u][w]) { // do not prefer nonterminals
593 distance[w][u] = distance[u][w] = duvw;
594 pred[u][w] = (pred[u][v] ? pred[v][w] : nullptr);
595 pred[w][u] = (pred[w][v] ? pred[v][u] : nullptr);
596 }
597 });
598 }
599 }
600 for (node u : G.nodes) {
601 distance[u][u] = 0;
602 }
603}
604
605template<typename T>
606void MinSteinerTreeModule<T>::apspInit(const EdgeWeightedGraph<T> &G, NodeArray<NodeArray<T>> &distance, NodeArray<NodeArray<edge>> &pred)
607{
608 distance.init(G);
609 pred.init(G);
610 for (node u : G.nodes) {
611 distance[u].init(G, std::numeric_limits<T>::max());
612 pred[u].init(G, nullptr);
613 }
614 for (edge e : G.edges) {
615 const node u = e->source(), v = e->target();
616 distance[u][v] = distance[v][u] = G.weight(e);
617 pred[u][v] = pred[v][u] = e;
618 }
619}
620
621template<typename T>
622template<typename CONTAINER>
623void MinSteinerTreeModule<T>::allPairShortestPathsDetour(const EdgeWeightedGraph<T> &G, const CONTAINER &nonterminals, NodeArray<NodeArray<T>> &distance, NodeArray<NodeArray<edge>> &pred)
624{
625 apspInit(G, distance, pred);
626
627 for (node v : nonterminals) {
628 apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
629 if (duvw < distance[u][w]) {
630 distance[w][u] = distance[u][w] = duvw;
631 pred[u][w] = pred[v][w];
632 pred[w][u] = pred[v][u];
633 }
634 });
635 }
636 for (node u : G.nodes) {
637 distance[u][u] = 0;
638 }
639}
640
641template<typename T>
642void MinSteinerTreeModule<T>::drawSteinerTreeSVG(const EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, const char *filename)
643{
644 GraphAttributes GA(steinerTree,
645 GraphAttributes::nodeGraphics |
646 GraphAttributes::nodeStyle |
647 GraphAttributes::nodeLabel |
648 GraphAttributes::edgeGraphics |
649 GraphAttributes::edgeStyle |
650 GraphAttributes::edgeLabel);
651
652 GA.directed() = false;
653
654 string s;
655
656 for (node v : steinerTree.nodes) {
657 std::stringstream out;
658 GA.width(v) = GA.height(v) = 25.0;
659 if (isTerminal[steinerTree.original(v)]) {
660 out << "T";
661 GA.shape(v) = Shape::Rect;
662 GA.fillColor(v) = Color::Name::Red;
663 } else {
664 out << "S";
665 GA.shape(v) = Shape::Ellipse;
666 GA.fillColor(v) = Color::Name::Gray;
667 }
668 out << steinerTree.original(v);
669 GA.label(v) = out.str();
670 }
671
672 FMMMLayout fmmm;
673
674 fmmm.useHighLevelOptions(true);
675 fmmm.unitEdgeLength(44.0);
676 fmmm.newInitialPlacement(true);
677 fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
678
679 fmmm.call(GA);
680 std::ofstream writeStream(filename, std::ofstream::out);
681 GraphIO::drawSVG(GA, writeStream);
682}
683
684template<typename T>
685void MinSteinerTreeModule<T>::drawSVG(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal, const EdgeWeightedGraphCopy<T> &steinerTree, const char *filename)
686{
687 GraphAttributes GA(G,
688 GraphAttributes::nodeGraphics |
689 GraphAttributes::nodeStyle |
690 GraphAttributes::nodeLabel |
691 GraphAttributes::edgeGraphics |
692 GraphAttributes::edgeStyle |
693 GraphAttributes::edgeLabel);
694
695 GA.directed() = false;
696
697 for (edge e : G.edges) {
698 GA.strokeColor(e) = Color::Name::Black;
699 GA.label(e) = to_string(G.weight(e));
700 GA.strokeWidth(e) = 1;
701 }
702 for (edge e : steinerTree.edges) {
703 GA.strokeColor(steinerTree.original(e)) = Color::Name::Red;
704 GA.strokeWidth(steinerTree.original(e)) = 2;
705 }
706
707 for (node v : G.nodes) {
708 std::stringstream out;
709 GA.width(v) = GA.height(v) = 25.0;
710 GA.strokeColor(v) = Color::Name::Black;
711 if (isTerminal[v]) {
712 out << "T" << v;
713 GA.shape(v) = Shape::Rect;
714 GA.fillColor(v) = Color::Name::Red;
715 GA.strokeWidth(v) = 2;
716 } else {
717 out << "S" << v;
718 GA.shape(v) = Shape::Ellipse;
719 if (steinerTree.copy(v)) {
720 GA.fillColor(v) = Color::Name::Gray;
721 GA.strokeWidth(v) = 2;
722 } else {
723 GA.fillColor(v) = Color::Name::White;
724 GA.strokeWidth(v) = 1;
725 }
726 }
727 GA.label(v) = out.str();
728 }
729
730 FMMMLayout fmmm;
731
732 fmmm.useHighLevelOptions(true);
733 fmmm.unitEdgeLength(44.0);
734 fmmm.newInitialPlacement(true);
735 fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
736
737 fmmm.call(GA);
738
739 std::ofstream writeStream(filename, std::ofstream::out);
740 GraphIO::drawSVG(GA, writeStream);
741}
742
743}
744