Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MinSteinerTreePrimalDual< T > Class Template Reference

Primal-Dual approximation algorithm for Steiner tree problems. More...

#include <ogdf/graphalg/MinSteinerTreePrimalDual.h>

+ Inheritance diagram for ogdf::MinSteinerTreePrimalDual< T >:

Public Member Functions

virtual T call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
 Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly. More...
 
double getLastLowerBound () const
 Returns the lower bound calculated while solving the last problem. More...
 
- Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual ~MinSteinerTreeModule ()
 Do nothing on destruction. More...
 

Protected Member Functions

virtual T computeSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
 Builds a minimum Steiner tree given a weighted graph and a list of terminals. More...
 

Private Member Functions

int getComponent (const node v) const
 Finds the biggest set including node v. More...
 
double getNextEdge (edge *nextEdge)
 Idendifies the next edge with a tight-to-be packing constraint. More...
 
void init ()
 Initializes all required datastructes. More...
 
bool isActive (int component) const
 Returns whether the given component is active. More...
 
void makeActive (int component)
 Marks the specified component as active. More...
 
void mergeComponents (const node v, const node w)
 Merges two disjoint components. More...
 
void updatePriorities (double eps)
 Must be called after merging any two components. More...
 

Private Attributes

HashArray< int, ListIterator< int > > m_activeComponentIterators
 
List< int > m_activeComponents
 
NodeArray< int > m_componentMapping
 
double m_lowerBound
 
DisjointSetsm_pComponents
 
const EdgeWeightedGraph< T > * m_pGraph
 
const NodeArray< bool > * m_pIsTerminal
 
NodeArray< double > m_priorities
 
const List< node > * m_pTerminals
 
const T MAX_VALUE = std::numeric_limits<T>::max()
 

Additional Inherited Members

- Static Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
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...
 

Detailed Description

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.

Member Function Documentation

◆ call()

template<typename T >
virtual T ogdf::MinSteinerTreePrimalDual< T >::call ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal,
EdgeWeightedGraphCopy< T > *&  finalSteinerTree 
)
inlineoverridevirtual

Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.

Parameters
GThe weighted input graph
terminalsThe list of terminal nodes
isTerminalA bool array of terminals
finalSteinerTreeThe final Steiner tree
Returns
The total cost of the final Steiner tree

Reimplemented from ogdf::MinSteinerTreeModule< T >.

Definition at line 141 of file MinSteinerTreePrimalDual.h.

◆ computeSteinerTree()

template<typename T >
T ogdf::MinSteinerTreePrimalDual< T >::computeSteinerTree ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal,
EdgeWeightedGraphCopy< T > *&  finalSteinerTree 
)
overrideprotectedvirtual

Builds a minimum Steiner tree given a weighted graph and a list of terminals.

Parameters
GThe weighted input graph
terminalsThe list of terminal nodes
isTerminalA bool array of terminals
finalSteinerTreeThe final Steiner tree
Returns
The objective value (sum of edge costs) of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 239 of file MinSteinerTreePrimalDual.h.

◆ getComponent()

template<typename T >
int ogdf::MinSteinerTreePrimalDual< T >::getComponent ( const node  v) const
private

Finds the biggest set including node v.

Parameters
vthe representative of the set to find

Definition at line 164 of file MinSteinerTreePrimalDual.h.

◆ getLastLowerBound()

template<typename T >
double ogdf::MinSteinerTreePrimalDual< T >::getLastLowerBound

Returns the lower bound calculated while solving the last problem.

Will return 0 if no problem was solved before.

Definition at line 320 of file MinSteinerTreePrimalDual.h.

◆ getNextEdge()

template<typename T >
double ogdf::MinSteinerTreePrimalDual< T >::getNextEdge ( edge nextEdge)
private

Idendifies the next edge with a tight-to-be packing constraint.

Parameters
nextEdgethe found edge
Returns
the adjusted weight (aka epsilon) for the found edge

Definition at line 210 of file MinSteinerTreePrimalDual.h.

◆ init()

template<typename T >
void ogdf::MinSteinerTreePrimalDual< T >::init
private

Initializes all required datastructes.

Definition at line 156 of file MinSteinerTreePrimalDual.h.

◆ isActive()

template<typename T >
bool ogdf::MinSteinerTreePrimalDual< T >::isActive ( int  component) const
private

Returns whether the given component is active.

Returns
true if the component is active, false otherwise

Definition at line 169 of file MinSteinerTreePrimalDual.h.

◆ makeActive()

template<typename T >
void ogdf::MinSteinerTreePrimalDual< T >::makeActive ( int  component)
private

Marks the specified component as active.

Parameters
componentthe component to be activated.

Definition at line 174 of file MinSteinerTreePrimalDual.h.

◆ mergeComponents()

template<typename T >
void ogdf::MinSteinerTreePrimalDual< T >::mergeComponents ( const node  v,
const node  w 
)
private

Merges two disjoint components.

Parameters
vrepresentative of the first component
wrepresentative of the second component

Definition at line 179 of file MinSteinerTreePrimalDual.h.

◆ updatePriorities()

template<typename T >
void ogdf::MinSteinerTreePrimalDual< T >::updatePriorities ( double  eps)
private

Must be called after merging any two components.

Will update all the priorities of all active edges by epsilon.

Parameters
epsthe value of the last tight edge

Definition at line 199 of file MinSteinerTreePrimalDual.h.

Member Data Documentation

◆ m_activeComponentIterators

template<typename T >
HashArray<int, ListIterator<int> > ogdf::MinSteinerTreePrimalDual< T >::m_activeComponentIterators
private

Definition at line 66 of file MinSteinerTreePrimalDual.h.

◆ m_activeComponents

template<typename T >
List<int> ogdf::MinSteinerTreePrimalDual< T >::m_activeComponents
private

Definition at line 67 of file MinSteinerTreePrimalDual.h.

◆ m_componentMapping

template<typename T >
NodeArray<int> ogdf::MinSteinerTreePrimalDual< T >::m_componentMapping
private

Definition at line 64 of file MinSteinerTreePrimalDual.h.

◆ m_lowerBound

template<typename T >
double ogdf::MinSteinerTreePrimalDual< T >::m_lowerBound
private

Definition at line 68 of file MinSteinerTreePrimalDual.h.

◆ m_pComponents

template<typename T >
DisjointSets* ogdf::MinSteinerTreePrimalDual< T >::m_pComponents
private

Definition at line 65 of file MinSteinerTreePrimalDual.h.

◆ m_pGraph

template<typename T >
const EdgeWeightedGraph<T>* ogdf::MinSteinerTreePrimalDual< T >::m_pGraph
private

Definition at line 59 of file MinSteinerTreePrimalDual.h.

◆ m_pIsTerminal

template<typename T >
const NodeArray<bool>* ogdf::MinSteinerTreePrimalDual< T >::m_pIsTerminal
private

Definition at line 61 of file MinSteinerTreePrimalDual.h.

◆ m_priorities

template<typename T >
NodeArray<double> ogdf::MinSteinerTreePrimalDual< T >::m_priorities
private

Definition at line 69 of file MinSteinerTreePrimalDual.h.

◆ m_pTerminals

template<typename T >
const List<node>* ogdf::MinSteinerTreePrimalDual< T >::m_pTerminals
private

Definition at line 60 of file MinSteinerTreePrimalDual.h.

◆ MAX_VALUE

template<typename T >
const T ogdf::MinSteinerTreePrimalDual< T >::MAX_VALUE = std::numeric_limits<T>::max()
private

Definition at line 62 of file MinSteinerTreePrimalDual.h.


The documentation for this class was generated from the following file: