Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSteinerTreeModule.h
Go to the documentation of this file.
1
32#pragma once
33
44
45#include <sstream>
46
47namespace ogdf {
48
58template<typename T>
60public:
63
74 virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
76
79
88 const NodeArray<bool>& isTerminal);
89
99 const NodeArray<bool>& isTerminal, node start);
100
107 const NodeArray<bool>& isTerminal, const List<node>& start);
108
115 const NodeArray<bool>& isTerminal);
116
120
137 node source, const NodeArray<bool>& isTerminal, NodeArray<T>& distance,
138 NodeArray<edge>& pred);
139
142 const NodeArray<bool>&, NodeArray<T>& distance, NodeArray<edge>& pred) {
143 Dijkstra<T> sssp;
144 sssp.call(G, G.edgeWeights(), source, pred, distance);
145 }
146
149 static inline void singleSourceShortestPaths(const EdgeWeightedGraph<T>& G, node source,
150 const NodeArray<bool>& isTerminal, NodeArray<T>& distance, NodeArray<edge>& pred) {
151#ifdef OGDF_MINSTEINERTREEMODULE_SHORTEST_PATHS_STANDARD
152 singleSourceShortestPathsStandard(G, source, isTerminal, distance, pred);
153#else
154 singleSourceShortestPathsPreferringTerminals(G, source, isTerminal, distance, pred);
155#endif
156 }
157
160 const List<node>& terminals, const NodeArray<bool>& isTerminal,
161 NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
162 allTerminalShortestPaths(G, terminals, isTerminal, distance, pred,
164 }
165
168 const List<node>& terminals, const NodeArray<bool>& isTerminal,
169 NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
170 allTerminalShortestPaths(G, terminals, isTerminal, distance, pred,
172 }
173
175 static void allTerminalShortestPaths(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
176 const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
178 std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
181 allNodesByListShortestPaths(G, terminals, isTerminal, terminals, distance, pred, ssspFunc);
182 }
183
186 const List<node>& terminals, const NodeArray<bool>& isTerminal,
187 NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
188 allNodeShortestPaths(G, terminals, isTerminal, distance, pred,
190 }
191
194 const List<node>& terminals, const NodeArray<bool>& isTerminal,
195 NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
196 allNodeShortestPaths(G, terminals, isTerminal, distance, pred,
198 }
199
201 static void allNodeShortestPaths(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
202 const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
204 std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
207 allNodesByListShortestPaths(G, terminals, isTerminal, G.nodes, distance, pred, ssspFunc);
208 }
209
220 const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
222
226
229 static void allPairShortestPaths(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
230 NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
231#ifdef OGDF_MINSTEINERTREEMODULE_SHORTEST_PATHS_STANDARD
232 allPairShortestPathsStandard(G, isTerminal, distance, pred);
233#else
234 allPairShortestPathsPreferringTerminals(G, isTerminal, distance, pred);
235#endif
236 }
237
241
250 static void drawSVG(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
251 const EdgeWeightedGraphCopy<T>& steinerTree, const char* filename);
252
260 static void drawSVG(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
261 const char* filename) {
264 drawSVG(G, isTerminal, emptySteinerTree, filename);
265 }
266
275 const NodeArray<bool>& isTerminal, const char* filename);
276
278
288 static bool isSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
289 const NodeArray<bool>& isTerminal, const EdgeWeightedGraphCopy<T>& steinerTree);
290
298 static bool isQuasiBipartite(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal);
299
307 static inline void getTerminals(List<node>& terminals, const EdgeWeightedGraph<T>& G,
308 const NodeArray<bool>& isTerminal) {
309 for (node v : G.nodes) {
310 if (isTerminal[v]) {
311 terminals.pushBack(v);
312 }
313 }
314 }
315
317 static inline void sortTerminals(List<node>& terminals) {
318 terminals.quicksort(GenericComparer<node, int>([](node v) { return v->index(); }));
319 }
320
329 const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal) {
330 for (node v : G.nodes) {
331 if (!isTerminal[v]) {
332 nonterminals.push(v);
333 }
334 }
335 }
336
337protected:
343 virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
345
346private:
348 static void apspInit(const EdgeWeightedGraph<T>& G, NodeArray<NodeArray<T>>& distance,
351 static void ssspInit(const EdgeWeightedGraph<T>& G, node source,
353
355 inline static void apspInnerLoop(node v, const EdgeWeightedGraph<T>& G,
356 NodeArray<NodeArray<T>>& distance, std::function<void(node, node, T)> func) {
357 for (node u : G.nodes) {
358 const T duv = distance[u][v];
359 if (duv < std::numeric_limits<T>::max()) {
360 for (node w = u->succ(); w != nullptr; w = w->succ()) {
361 if (distance[v][w] < std::numeric_limits<T>::max()) {
362 func(u, w, duv + distance[v][w]);
363 }
364 }
365 }
366 }
367 }
368
370 template<typename NODELIST>
372 const List<node>& terminals, const NodeArray<bool>& isTerminal, const NODELIST& nodes,
374 std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
376 ssspFunc) {
377 distance.init(G);
378 pred.init(G);
379 for (node u : nodes) {
380 ssspFunc(G, u, isTerminal, distance[u], pred[u]);
381 }
382 }
383};
384
385template<typename T>
389
390 if (terminals.size() > 2) {
391 return this->computeSteinerTree(G, terminals, isTerminal, finalSteinerTree);
392 }
393
395 finalSteinerTree->createEmpty(G);
396 if (!terminals.empty()) {
397 finalSteinerTree->newNode(terminals.back());
398 }
399 if (terminals.size() <= 1) {
400 return 0;
401 }
402
403 OGDF_ASSERT(terminals.size() == 2);
404 T cost(0);
406 NodeArray<edge> pred;
408 astar.call(G, G.edgeWeights(), terminals.front(), terminals.back(), pred);
409 OGDF_ASSERT(pred[terminals.back()] != nullptr); // connected
410 for (node t = terminals.back(); t != terminals.front(); t = pred[t]->opposite(t)) {
411 const edge e = pred[t];
412 finalSteinerTree->newNode(e->opposite(t));
413 finalSteinerTree->newEdge(e, G.weight(e));
414 cost += G.weight(e);
415 }
416 return cost;
417}
418
419template<typename T>
421 const List<node>& terminals, const NodeArray<bool>& isTerminal,
423 // the Steiner tree is actually a tree
424 if (!isTree(steinerTree)) {
425 return false;
426 }
427
428 // all terminal nodes are in the graph and have degree >= 1
429 for (node v : terminals) {
430 const node u = steinerTree.copy(v);
431 if (!u || (terminals.size() > 1 && u->degree() < 1)) {
432 return false;
433 }
434 }
435
436 // all Steiner nodes are inner nodes
437 for (node u : steinerTree.nodes) {
438 if (!isTerminal[steinerTree.original(u)] && u->degree() <= 1) {
439 return false;
440 }
441 }
442
443 return true;
444}
445
446template<typename T>
448 const NodeArray<bool>& isTerminal) {
449 for (node v = G.firstNode(); v; v = v->succ()) {
450 if (!isTerminal[v]) {
451 for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
452 if (!isTerminal[adj->twinNode()]) {
453 return false;
454 }
455 }
456 }
457 }
458 return true;
459}
460
461template<typename T>
463 const NodeArray<bool>& isTerminal, const node start) {
465 T delWeights(0);
466 node u = start;
467 while (u->degree() == 1 && !isTerminal[steinerTree.original(u)]) {
468 const adjEntry adj = u->firstAdj();
469 const node v = adj->twinNode();
470 delWeights += steinerTree.weight(adj->theEdge());
471 steinerTree.delNode(u);
472 u = v;
473 }
474 return delWeights;
475}
476
477template<typename T>
479 const NodeArray<bool>& isTerminal, const List<node>& start) {
480 T delWeights(0);
481 for (node v : start) {
482 delWeights += pruneDanglingSteinerPathFrom(steinerTree, isTerminal, v);
483 }
484 return delWeights;
485}
486
487template<typename T>
489 const NodeArray<bool>& isTerminal) {
490 List<node> start;
491 for (node u : steinerTree.nodes) {
492 if (u->degree() == 1 && !isTerminal[steinerTree.original(u)]) {
493 start.pushBack(u);
494 }
495 }
496
497 return pruneDanglingSteinerPathsFrom(steinerTree, isTerminal, start);
498}
499
500template<typename T>
502 const NodeArray<bool>& isTerminal) {
503 if (steinerTree.numberOfEdges() > steinerTree.numberOfNodes() - 1) {
505 T oldCost(0);
506 T newCost(computeMinST(steinerTree, steinerTree.edgeWeights(), isInTree));
507
508 List<node> pendant; // collect resulting pendant edges
509 for (edge nextEdge, e = steinerTree.firstEdge(); e; e = nextEdge) {
510 oldCost += steinerTree.weight(e);
511 nextEdge = e->succ();
512 if (!isInTree[e]) {
513 if (e->source()->degree() == 2) {
514 pendant.pushBack(e->source());
515 }
516 if (e->target()->degree() == 2) {
517 pendant.pushBack(e->target());
518 }
519 steinerTree.delEdge(e);
520 }
521 }
523 pendant);
524 return oldCost - newCost;
525 }
526 return 0;
527}
528
529template<typename T>
532 distance.init(G, std::numeric_limits<T>::max());
533 distance[source] = 0;
534
535 for (node v : G.nodes) {
536 queue.push(v, distance[v]);
537 }
538
539 pred.init(G, nullptr);
540}
541
542template<typename T>
544 const EdgeWeightedGraph<T>& G, node source, const NodeArray<bool>& isTerminal,
545 NodeArray<T>& distance, NodeArray<edge>& pred) {
547 ssspInit(G, source, queue, distance, pred);
548
549 // we must handle the source explicitly because it is a terminal
550 node v = queue.topElement();
551 queue.pop();
552 OGDF_ASSERT(v == source);
553 for (adjEntry adj : v->adjEntries) {
554 edge e = adj->theEdge();
555 node w = adj->twinNode();
556 if (distance[w] > G.weight(
557 e)) { // this check is only necessary for multigraphs, otherwise this is always true
558 queue.decrease(w, (distance[w] = G.weight(e)));
559 pred[w] = e;
560 }
561 }
562
563 auto setPredecessor = [&](node w, edge e) {
564 bool wOnPathWithTerminal = isTerminal[v] || pred[v] == nullptr;
565 pred[w] = wOnPathWithTerminal ? nullptr : e;
566 };
567 while (!queue.empty()) {
568 v = queue.topElement();
569 queue.pop();
570
571 if (distance[v] == std::numeric_limits<T>::max()) { // min is unreachable, finished
572 break;
573 }
574 for (adjEntry adj : v->adjEntries) {
575 edge e = adj->theEdge();
576 node w = adj->twinNode();
577 T dist = distance[v] + G.weight(e);
578 if (distance[w] > dist) {
579 queue.decrease(w, (distance[w] = dist));
580 setPredecessor(w, e);
581 } else if (distance[w] == dist && pred[w] != nullptr) { // tie
582 setPredecessor(w, e);
583 }
584 }
585 }
586}
587
588template<typename T>
590 const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
591 NodeArray<NodeArray<edge>>& pred) {
592 apspInit(G, distance, pred);
593
594 for (node v : G.nodes) {
595 if (isTerminal[v]) { // v is a terminal
596 apspInnerLoop(v, G, distance, [&distance, &pred](node u, node w, T duvw) {
597 if (duvw <= distance[u][w]) { // prefer terminals
598 distance[w][u] = distance[u][w] = duvw;
599 pred[w][u] = pred[u][w] = nullptr;
600 }
601 });
602 } else { // v is not a terminal
603 apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
604 if (duvw < distance[u][w]) { // do not prefer nonterminals
605 distance[w][u] = distance[u][w] = duvw;
606 pred[u][w] = (pred[u][v] ? pred[v][w] : nullptr);
607 pred[w][u] = (pred[w][v] ? pred[v][u] : nullptr);
608 }
609 });
610 }
611 }
612 for (node u : G.nodes) {
613 distance[u][u] = 0;
614 }
615}
616
617template<typename T>
619 NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
620 distance.init(G);
621 pred.init(G);
622 for (node u : G.nodes) {
623 distance[u].init(G, std::numeric_limits<T>::max());
624 pred[u].init(G, nullptr);
625 }
626 for (edge e : G.edges) {
627 const node u = e->source(), v = e->target();
628 distance[u][v] = distance[v][u] = G.weight(e);
629 pred[u][v] = pred[v][u] = e;
630 }
631}
632
633template<typename T>
636 apspInit(G, distance, pred);
637
638 for (node v : G.nodes) {
639 apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
640 if (duvw < distance[u][w]) {
641 distance[w][u] = distance[u][w] = duvw;
642 pred[u][w] = pred[v][w];
643 pred[w][u] = pred[v][u];
644 }
645 });
646 }
647 for (node u : G.nodes) {
648 distance[u][u] = 0;
649 }
650}
651
652template<typename T>
654 const NodeArray<bool>& isTerminal, const char* filename) {
659
660 GA.directed() = false;
661
662 string s;
663
664 for (node v : steinerTree.nodes) {
665 std::stringstream out;
666 GA.width(v) = GA.height(v) = 25.0;
667 if (isTerminal[steinerTree.original(v)]) {
668 out << "T";
669 GA.shape(v) = Shape::Rect;
670 GA.fillColor(v) = Color::Name::Red;
671 } else {
672 out << "S";
673 GA.shape(v) = Shape::Ellipse;
674 GA.fillColor(v) = Color::Name::Gray;
675 }
676 out << steinerTree.original(v);
677 GA.label(v) = out.str();
678 }
679
680 FMMMLayout fmmm;
681
682 fmmm.useHighLevelOptions(true);
683 fmmm.unitEdgeLength(44.0);
684 fmmm.newInitialPlacement(true);
686
687 fmmm.call(GA);
688 std::ofstream writeStream(filename, std::ofstream::out);
690}
691
692template<typename T>
694 const NodeArray<bool>& isTerminal, const EdgeWeightedGraphCopy<T>& steinerTree,
695 const char* filename) {
700
701 GA.directed() = false;
702
703 for (edge e : G.edges) {
704 GA.strokeColor(e) = Color::Name::Black;
705 GA.label(e) = to_string(G.weight(e));
706 GA.strokeWidth(e) = 1;
707 }
708 for (edge e : steinerTree.edges) {
709 GA.strokeColor(steinerTree.original(e)) = Color::Name::Red;
710 GA.strokeWidth(steinerTree.original(e)) = 2;
711 }
712
713 for (node v : G.nodes) {
714 std::stringstream out;
715 GA.width(v) = GA.height(v) = 25.0;
716 GA.strokeColor(v) = Color::Name::Black;
717 if (isTerminal[v]) {
718 out << "T" << v;
719 GA.shape(v) = Shape::Rect;
720 GA.fillColor(v) = Color::Name::Red;
721 GA.strokeWidth(v) = 2;
722 } else {
723 out << "S" << v;
724 GA.shape(v) = Shape::Ellipse;
725 if (steinerTree.copy(v)) {
726 GA.fillColor(v) = Color::Name::Gray;
727 GA.strokeWidth(v) = 2;
728 } else {
729 GA.fillColor(v) = Color::Name::White;
730 GA.strokeWidth(v) = 1;
731 }
732 }
733 GA.label(v) = out.str();
734 }
735
736 FMMMLayout fmmm;
737
738 fmmm.useHighLevelOptions(true);
739 fmmm.unitEdgeLength(44.0);
740 fmmm.newInitialPlacement(true);
742
743 fmmm.call(GA);
744
745 std::ofstream writeStream(filename, std::ofstream::out);
747}
748
749}
Implementation of the A* informed search algorithm.
Extends the GraphCopy concept to weighted graphs.
Declaration of Fast Multipole Multilevel Method (FM^3).
Declaration of class GraphAttributes which extends a Graph by additional attributes.
Declares class GraphIO which provides access to all graph read and write functionality.
Priority queue interface wrapping various heaps.
Definition of a Triple used in contraction-based approximation algorithm for the minimum Steiner tree...
A-Star informed search algorithm.
Definition AStarSearch.h:54
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry succ() const
Returns the successor in the adjacency list.
Definition Graph_d.h:155
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition Graph_d.h:112
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
Dijkstra's single source shortest path algorithm.
Definition Dijkstra.h:53
void call(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition Dijkstra.h:246
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
node opposite(node v) const
Returns the adjacent node different from v.
Definition Graph_d.h:350
The fast multipole multilevel layout algorithm.
Definition FMMMLayout.h:232
FMMMOptions::QualityVsSpeed qualityVersusSpeed() const
Returns the current setting of option qualityVersusSpeed.
Definition FMMMLayout.h:361
double unitEdgeLength() const
Returns the current setting of option unitEdgeLength.
Definition FMMMLayout.h:337
bool useHighLevelOptions() const
Returns the current setting of option useHighLevelOptions.
Definition FMMMLayout.h:319
virtual void call(GraphAttributes &GA) override
Calls the algorithm for graph GA and returns the layout information in GA.
bool newInitialPlacement() const
Returns the current setting of option newInitialPlacement.
Definition FMMMLayout.h:351
Stores additional attributes of a graph (like layout information).
static const long edgeLabel
Corresponds to edge attribute label(edge).
static const long edgeStyle
Corresponds to edge attributes strokeColor(edge), strokeType(edge), and strokeWidth(edge).
static const long nodeLabel
Corresponds to node attribute label(node).
static const long nodeStyle
Corresponds to node attributes strokeColor(node), strokeType(node), strokeWidth(node),...
static const long edgeGraphics
Corresponds to edge attribute bends(edge).
static const long nodeGraphics
Corresponds to node attributes x(node), y(node), width(node), height(node), and shape(node).
static bool drawSVG(const GraphAttributes &A, std::ostream &os, const SVGSettings &settings)
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
int size() const
Returns the number of elements in the list.
Definition List.h:1472
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
const_reference front() const
Returns a const reference to the first element.
Definition List.h:289
const_reference back() const
Returns a const reference to the last element.
Definition List.h:307
bool empty() const
Returns true iff the list is empty.
Definition List.h:270
void quicksort()
Sorts the list using Quicksort.
Definition List.h:1315
Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirec...
static void allNodeShortestPathsStandard(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsStandard from all nodes.
static void allNodesByListShortestPaths(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NODELIST &nodes, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc)
Runs a given (or the default) single-source-shortest-paths function from all nodes.
static bool isQuasiBipartite(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite.
static void allTerminalShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsPreferringTerminals from all terminals.
virtual T call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.
static T pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Prunes nonterminal leaves and their paths to terminal or branching nodes.
static void getTerminals(List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as List<node>) of all terminals.
static T pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
Prunes the dangling Steiner path beginning at a given nonterminal leaf only.
static void allPairShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Modified all-pair-shortest-paths algorithm (Floyd-Warshall) with heuristic to prefer paths over termi...
static void allTerminalShortestPaths(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all terminals.
static void apspInit(const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Common initialization routine for APSP algorithms.
static void allPairShortestPaths(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
The default all-pair-shortest-paths algorithm.
static void singleSourceShortestPaths(const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
The default single-source-shortest-paths algorithm.
virtual T computeSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)=0
Computes the actual Steiner tree.
static void ssspInit(const EdgeWeightedGraph< T > &G, node source, PrioritizedMapQueue< node, T > &queue, NodeArray< T > &distance, NodeArray< edge > &pred)
Common initialization routine for SSSP algorithms.
static T removeCyclesFrom(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Remove remaining cycles from a Steiner "almost" tree.
static void singleSourceShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
Modified single-source-shortest-paths (Dijkstra) with heuristic to prefer paths over terminals.
static void drawSVG(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree, const char *filename)
Writes an SVG file of a minimum Steiner tree in the original graph.
static void sortTerminals(List< node > &terminals)
Sort terminals by index.
static void allPairShortestPathsStandard(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Standard all-pair-shortest-paths algorithm (Floyd-Warshall)
static void allNodeShortestPaths(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all nodes.
static void singleSourceShortestPathsStandard(const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &, NodeArray< T > &distance, NodeArray< edge > &pred)
Standard single-source-shortest-paths algoritm (Dijkstra)
static void allNodeShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsPreferringTerminals from all nodes.
static void apspInnerLoop(node v, const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T > > &distance, std::function< void(node, node, T)> func)
The inner loop for APSP algorithm to avoid code duplication.
static bool isSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree)
Checks in O(n) time if a given tree is acually a Steiner Tree.
static void drawSVG(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
Writes an SVG file of the instance graph.
static void drawSteinerTreeSVG(const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
Writes a SVG that shows only the given Steiner tree.
static void allTerminalShortestPathsStandard(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsStandard from all terminals.
static T pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
Prunes dangling Steiner paths beginning at given nonterminal leaves only.
static void getNonterminals(ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as ArrayBuffer<node>) of all nonterminals.
virtual ~MinSteinerTreeModule()
Do nothing on destruction.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
void init()
Reinitializes the array. Associates the array with no graph.
Definition NodeArray.h:266
Class for the representation of nodes.
Definition Graph_d.h:177
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition Graph_d.h:220
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
node succ() const
Returns the successor in the list of all nodes.
Definition Graph_d.h:229
int index() const
Returns the (unique) node index.
Definition Graph_d.h:211
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition Graph_d.h:223
Prioritized queue interface wrapper for heaps.
Declaration of extended graph algorithms.
Implementation of Dijkstra's single source shortest path algorithm.
bool isConnected(const Graph &G)
Returns true iff G is connected.
T computeMinST(const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm.
bool isTree(const Graph &G)
Returns true iff G is a tree, i.e. contains no undirected cycle and is connected.
@ Ellipse
ellipse
@ Rect
rectangle
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Declaration of simple graph algorithms.
Compare elements based on a single comparable attribute.
Definition comparer.h:398