Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::steiner_tree Namespace Reference

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 >
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 >
obtainFinalSteinerTree (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const NodeArray< bool > &isOriginalTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
 

Function Documentation

◆ buildHeaviestEdgeInComponentTree()

template<typename T >
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).

Returns
root node of the arborescence
Parameters
inputTreethe input tree
externalNodesthe resulting mapping from input nodes to arborescence leaves (must be nullptr'ed in input!)
treeEdgethe resulting mapping from each (inner) node of the arborescence to an edge in the input tree
outputTreethe output arborescence

Definition at line 53 of file common_algorithms.h.

◆ constructTerminalSpanningTreeUsingVoronoiRegions()

template<typename T >
T ogdf::steiner_tree::constructTerminalSpanningTreeUsingVoronoiRegions ( EdgeWeightedGraphCopy< T > &  terminalSpanningTree,
const EdgeWeightedGraph< T > &  graph,
const List< node > &  terminals 
)

Definition at line 300 of file MinSteinerTreeMehlhorn.h.

◆ contractTripleInSteinerTree() [1/2]

template<typename T >
void ogdf::steiner_tree::contractTripleInSteinerTree ( const Triple< T > &  t,
EdgeWeightedGraphCopy< T > &  st,
edge  e0,
edge  e1,
edge  e2 
)
inline

Definition at line 159 of file common_algorithms.h.

◆ contractTripleInSteinerTree() [2/2]

template<typename T >
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.

Parameters
tThe contracted triple
stThe Steiner Tree
save0One of the three save edges of the triple
save1One of the three save edges of the triple
save2One of the three save edges of the triple
ne0One of the new zero-weight edges
ne1One of the new zero-weight edges

Definition at line 145 of file common_algorithms.h.

◆ obtainFinalSteinerTree()

template<typename T >
T ogdf::steiner_tree::obtainFinalSteinerTree ( const EdgeWeightedGraph< T > &  G,
const NodeArray< bool > &  isTerminal,
const NodeArray< bool > &  isOriginalTerminal,
EdgeWeightedGraphCopy< T > *&  finalSteinerTree 
)

Definition at line 167 of file common_algorithms.h.