|
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::MinSteinerTreePrimalDual< T >
Primal-Dual approximation algorithm for Steiner tree problems.
Yields a guaranteed approximation factor of two.
This algorithm was first described by Michel X. Goemans and David P. Williamson in "A General Approximation Technique for Constrained Forest Problems", SIAM Journal on Computing, 24:296-317, 1995.
Definition at line 57 of file MinSteinerTreePrimalDual.h.