|
|||
|
|
|
|||
|
|
Namespaces | |
| namespace | 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... | |
| 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 53 of file common_algorithms.h.
| T ogdf::steiner_tree::constructTerminalSpanningTreeUsingVoronoiRegions | ( | EdgeWeightedGraphCopy< T > & | terminalSpanningTree, |
| const EdgeWeightedGraph< T > & | graph, | ||
| const List< node > & | terminals | ||
| ) |
Definition at line 295 of file MinSteinerTreeMehlhorn.h.
|
inline |
Definition at line 157 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 143 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 164 of file common_algorithms.h.
