|
virtual | ~MinSteinerTreeModule () |
| Do nothing on destruction. More...
|
|
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. More...
|
|
static void | getNonterminals (ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal) |
| Generates a list (as ArrayBuffer<node>) of all nonterminals. More...
|
|
static void | getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal) |
| Generates a list (as List<node>) of all terminals. More...
|
|
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. More...
|
|
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. More...
|
|
static void | sortTerminals (List< node > &terminals) |
| Sort terminals by index. More...
|
|
static T | pruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal) |
| Prunes nonterminal leaves and their paths to terminal or branching nodes. More...
|
|
static T | pruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start) |
| Prunes the dangling Steiner path beginning at a given nonterminal leaf only. More...
|
|
static T | pruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start) |
| Prunes dangling Steiner paths beginning at given nonterminal leaves only. More...
|
|
static T | removeCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal) |
| Remove remaining cycles from a Steiner "almost" tree. More...
|
|
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. More...
|
|
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) More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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 terminals. More...
|
|
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) More...
|
|
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. More...
|
|
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. More...
|
|
static void | drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename) |
| Writes an SVG file of the instance graph. More...
|
|
static void | drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename) |
| Writes a SVG that shows only the given Steiner tree. More...
|
|
template<typename T>
class ogdf::MinSteinerTreeDualAscent< T >
Dual ascent heuristic for the minimum Steiner tree problem.
The algorithm is implemented following the paper by Richard T. Wong, "A Dual Ascent Approach for Steiner Tree Problems on a Directed Graph", Mathematical Programming 28, pages 271-287, 1984.
Definition at line 65 of file MinSteinerTreeDualAscent.h.