|
|||
|
|
|
|||
|
|
Namespaces | |
| goemans | |
Classes | |
| class | Full2ComponentGenerator |
| Trivial full 2-component generation by lookups of shortest paths between terminal pairs. More... | |
| class | Full3ComponentGeneratorEnumeration |
| Full 3-component generation using enumeration. More... | |
| class | Full3ComponentGeneratorModule |
| Interface for full 3-component generation including auxiliary functions. More... | |
| class | Full3ComponentGeneratorVoronoi |
| Full 3-component generation using Voronoi regions. More... | |
| struct | FullComponentDecisions |
| Contains rules of thumb to decide which (sub-)algorithms to use for the generation of full components. More... | |
| class | FullComponentGeneratorCaller |
| class | FullComponentGeneratorDreyfusWagner |
| A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm. More... | |
| class | FullComponentGeneratorDreyfusWagnerWithoutMatrix |
| A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm that does not need a precomputed all-pair-shortest-paths matrix because single-source-shortest-path are used within. More... | |
| class | FullComponentStore |
| A data structure to store full components. More... | |
| class | FullComponentWithExtraStore |
| A data structure to store full components with extra data for each component. More... | |
| class | FullComponentWithLossStore |
| A data structure to store full components with additional "loss" functionality. More... | |
| class | HeavyPathDecomposition |
| An implementation of the heavy path decomposition on trees. More... | |
| struct | LossMetadata |
| class | LowerBoundDualAscent |
| Computes lower bounds for minimum Steiner tree instances. More... | |
| class | LPRelaxationSER |
| Class managing the component-based subtour elimination LP relaxation for the Steiner tree problem and its solving. More... | |
| class | Save |
| This class serves as an interface for different approaches concerning the calculation of save edges. More... | |
| class | SaveDynamic |
| Dynamically updatable weighted Tree for determining save edges via LCA computation. More... | |
| class | SaveEnum |
| This class computes save edges recursively and stores for every node pair their save edge in a HashArray. More... | |
| class | SaveStatic |
| This class behaves basically the same as SaveDynamic except that the update of the weighted graph is not done dynamically here. More... | |
| class | Triple |
| This class represents a triple used by various contraction-based minimum Steiner tree approximations. More... | |
| class | UnorderedNodePairEquality |
| A class used by the unordered_maps inside the reductions. More... | |
| class | UnorderedNodePairHasher |
| A class used by the unordered_maps inside the reductions. More... | |
Functions | |
| template<typename T > | |
| node | buildHeaviestEdgeInComponentTree (const EdgeWeightedGraphCopy< T > &inputTree, NodeArray< node > &externalNodes, NodeArray< edge > &treeEdge, Graph &outputTree) |
| Given an edge-weighted tree, builds an auxiliary arborescence where each arc of the input tree is a node in the arborescence. More... | |
| template<typename T > | |
| T | constructTerminalSpanningTreeUsingVoronoiRegions (EdgeWeightedGraphCopy< T > &terminalSpanningTree, const EdgeWeightedGraph< T > &graph, const List< node > &terminals) |
| template<typename T > | |
| void | contractTripleInSteinerTree (const Triple< T > &t, EdgeWeightedGraphCopy< T > &st, edge e0, edge e1, edge e2) |
| template<typename T > | |
| void | contractTripleInSteinerTree (const Triple< T > &t, EdgeWeightedGraphCopy< T > &st, edge save0, edge save1, edge save2, edge &ne0, edge &ne1) |
| Updates the Steiner tree by deleting save edges, removing all direct connections between the terminals of the contracted triple and connecting them through 0-cost edges. More... | |
| template<typename T > | |
| T | obtainFinalSteinerTree (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const NodeArray< bool > &isOriginalTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) |
| node ogdf::steiner_tree::buildHeaviestEdgeInComponentTree | ( | const EdgeWeightedGraphCopy< T > & | inputTree, |
| NodeArray< node > & | externalNodes, | ||
| NodeArray< edge > & | treeEdge, | ||
| Graph & | outputTree | ||
| ) |
Given an edge-weighted tree, builds an auxiliary arborescence where each arc of the input tree is a node in the arborescence.
The weight of each node is at least the weight of its children. The construction algorithm takes time O(n log n).
| inputTree | the input tree |
| externalNodes | the resulting mapping from input nodes to arborescence leaves (must be nullptr'ed in input!) |
| treeEdge | the resulting mapping from each (inner) node of the arborescence to an edge in the input tree |
| outputTree | the output arborescence |
Definition at line 69 of file common_algorithms.h.
| T ogdf::steiner_tree::constructTerminalSpanningTreeUsingVoronoiRegions | ( | EdgeWeightedGraphCopy< T > & | terminalSpanningTree, |
| const EdgeWeightedGraph< T > & | graph, | ||
| const List< node > & | terminals | ||
| ) |
Definition at line 300 of file MinSteinerTreeMehlhorn.h.
|
inline |
Definition at line 173 of file common_algorithms.h.
| void ogdf::steiner_tree::contractTripleInSteinerTree | ( | const Triple< T > & | t, |
| EdgeWeightedGraphCopy< T > & | st, | ||
| edge | save0, | ||
| edge | save1, | ||
| edge | save2, | ||
| edge & | ne0, | ||
| edge & | ne1 | ||
| ) |
Updates the Steiner tree by deleting save edges, removing all direct connections between the terminals of the contracted triple and connecting them through 0-cost edges.
| t | The contracted triple |
| st | The Steiner Tree |
| save0 | One of the three save edges of the triple |
| save1 | One of the three save edges of the triple |
| save2 | One of the three save edges of the triple |
| ne0 | One of the new zero-weight edges |
| ne1 | One of the new zero-weight edges |
Definition at line 159 of file common_algorithms.h.
| T ogdf::steiner_tree::obtainFinalSteinerTree | ( | const EdgeWeightedGraph< T > & | G, |
| const NodeArray< bool > & | isTerminal, | ||
| const NodeArray< bool > & | isOriginalTerminal, | ||
| EdgeWeightedGraphCopy< T > *& | finalSteinerTree | ||
| ) |
Definition at line 180 of file common_algorithms.h.
