Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinSteinerTreeGoemans139< T > Class Template Reference

This class implements the (1.39+epsilon)-approximation algorithm for the Steiner tree problem by Goemans et. More...

#include <ogdf/graphalg/MinSteinerTreeGoemans139.h>

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

Classes

class  Main
 Class managing LP-based approximation. More...
 

Public Member Functions

 MinSteinerTreeGoemans139 ()
 
virtual ~MinSteinerTreeGoemans139 ()
 
void disablePreprocessing (bool preprocess=true)
 Disable preprocessing of LP solutions. More...
 
void separateCycles (bool separateCycles=true)
 Use stronger LP relaxation (not recommended in general) More...
 
void setMaxComponentSize (int k)
 Sets the maximal number of terminals in a full component. More...
 
void setSeed (int seed)
 Set seed for the random number generation. More...
 
void use2Approximation (bool use2approx=true)
 Use Takahashi-Matsuyama 2-approximation as upper bounds. More...
 
- Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual ~MinSteinerTreeModule ()
 Do nothing on destruction. More...
 
virtual T call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
 Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly. 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 for a given weighted graph with terminals. More...
 

Protected Attributes

bool m_preprocess
 
int m_restricted
 
int m_seed
 
bool m_separateCycles
 
bool m_use2approx
 

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::MinSteinerTreeGoemans139< T >

This class implements the (1.39+epsilon)-approximation algorithm for the Steiner tree problem by Goemans et.

al.

This implementation is based on:

M.X. Goemans, N. Olver, T. RothvoƟ, R. Zenklusen: Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations. STOC 2012, pages 1161-1176, 2012

and

S. Beyer, M. Chimani: Steiner Tree 1.39-Approximation in Practice. MEMICS 2014, LNCS 8934, 60-72, Springer, 2014

Definition at line 64 of file MinSteinerTreeGoemans139.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeGoemans139()

template<typename T >
ogdf::MinSteinerTreeGoemans139< T >::MinSteinerTreeGoemans139 ( )
inline

Definition at line 77 of file MinSteinerTreeGoemans139.h.

◆ ~MinSteinerTreeGoemans139()

template<typename T >
virtual ogdf::MinSteinerTreeGoemans139< T >::~MinSteinerTreeGoemans139 ( )
inlinevirtual

Definition at line 86 of file MinSteinerTreeGoemans139.h.

Member Function Documentation

◆ computeSteinerTree()

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

Builds a minimum Steiner tree for a given weighted graph with terminals.

See also
MinSteinerTreeModule::computeSteinerTree
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 152 of file MinSteinerTreeGoemans139.h.

◆ disablePreprocessing()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::disablePreprocessing ( bool  preprocess = true)
inline

Disable preprocessing of LP solutions.

Note
not recommended to use in general
Parameters
preprocessTrue to disable, false to enable

Definition at line 121 of file MinSteinerTreeGoemans139.h.

◆ separateCycles()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::separateCycles ( bool  separateCycles = true)
inline

Use stronger LP relaxation (not recommended in general)

Parameters
separateCyclesTrue to turn the stronger LP relaxation on

Definition at line 130 of file MinSteinerTreeGoemans139.h.

◆ setMaxComponentSize()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::setMaxComponentSize ( int  k)
inline

Sets the maximal number of terminals in a full component.

Parameters
kthe maximal number of terminals in a full component

Definition at line 92 of file MinSteinerTreeGoemans139.h.

◆ setSeed()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::setSeed ( int  seed)
inline

Set seed for the random number generation.

Parameters
seedThe seed

Definition at line 101 of file MinSteinerTreeGoemans139.h.

◆ use2Approximation()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::use2Approximation ( bool  use2approx = true)
inline

Use Takahashi-Matsuyama 2-approximation as upper bounds.

Note
not recommended to use in general
Parameters
use2approxTrue to apply the bound

Definition at line 111 of file MinSteinerTreeGoemans139.h.

Member Data Documentation

◆ m_preprocess

template<typename T >
bool ogdf::MinSteinerTreeGoemans139< T >::m_preprocess
protected

Definition at line 71 of file MinSteinerTreeGoemans139.h.

◆ m_restricted

template<typename T >
int ogdf::MinSteinerTreeGoemans139< T >::m_restricted
protected

Definition at line 67 of file MinSteinerTreeGoemans139.h.

◆ m_seed

template<typename T >
int ogdf::MinSteinerTreeGoemans139< T >::m_seed
protected

Definition at line 74 of file MinSteinerTreeGoemans139.h.

◆ m_separateCycles

template<typename T >
bool ogdf::MinSteinerTreeGoemans139< T >::m_separateCycles
protected

Definition at line 73 of file MinSteinerTreeGoemans139.h.

◆ m_use2approx

template<typename T >
bool ogdf::MinSteinerTreeGoemans139< T >::m_use2approx
protected

Definition at line 72 of file MinSteinerTreeGoemans139.h.


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