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.
void	separateCycles (bool separateCycles=true)
	Use stronger LP relaxation (not recommended in general)
void	setMaxComponentSize (int k)
	Sets the maximal number of terminals in a full component.
void	setSeed (int seed)
	Set seed for the random number generation.
void	use2Approximation (bool use2approx=true)
	Use Takahashi-Matsuyama 2-approximation as upper bounds.
Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual	~MinSteinerTreeModule ()
	Do nothing on destruction.
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.

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.

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.
static void	getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
	Generates a list (as List<node>) of all terminals.
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.
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.
static void	sortTerminals (List< node > &terminals)
	Sort terminals by index.
static T	pruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
	Prunes nonterminal leaves and their paths to terminal or branching nodes.
static T	pruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
	Prunes the dangling Steiner path beginning at a given nonterminal leaf only.
static T	pruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
	Prunes dangling Steiner paths beginning at given nonterminal leaves only.
static T	removeCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
	Remove remaining cycles from a Steiner "almost" tree.
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.
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)
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.
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.
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.
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.
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.
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.
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.
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.
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)
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.
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.
static void	drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
	Writes an SVG file of the instance graph.
static void	drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
	Writes a SVG that shows only the given Steiner tree.

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 76 of file MinSteinerTreeGoemans139.h.

~MinSteinerTreeGoemans139()

template<typename T >

virtual ogdf::MinSteinerTreeGoemans139< T >::~MinSteinerTreeGoemans139 ( )

inlinevirtual

Definition at line 83 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

G	The weighted input graph
terminals	The list of terminal nodes
isTerminal	A bool array of terminals
finalSteinerTree	The final Steiner tree

Returns

The objective value (sum of edge costs) of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 131 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

preprocess

True to disable, false to enable

Definition at line 109 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

separateCycles

True to turn the stronger LP relaxation on

Definition at line 115 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

k	the maximal number of terminals in a full component

Definition at line 89 of file MinSteinerTreeGoemans139.h.

setSeed()

template<typename T >

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

inline

Set seed for the random number generation.

Parameters

seed

The seed

Definition at line 95 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

use2approx

True to apply the bound

Definition at line 102 of file MinSteinerTreeGoemans139.h.

Member Data Documentation

m_preprocess

template<typename T >

bool ogdf::MinSteinerTreeGoemans139< T >::m_preprocess

protected

Definition at line 70 of file MinSteinerTreeGoemans139.h.

m_restricted

template<typename T >

int ogdf::MinSteinerTreeGoemans139< T >::m_restricted

protected

Definition at line 69 of file MinSteinerTreeGoemans139.h.

m_seed

template<typename T >

int ogdf::MinSteinerTreeGoemans139< T >::m_seed

protected

Definition at line 73 of file MinSteinerTreeGoemans139.h.

m_separateCycles

template<typename T >

bool ogdf::MinSteinerTreeGoemans139< T >::m_separateCycles

protected

Definition at line 72 of file MinSteinerTreeGoemans139.h.

m_use2approx

template<typename T >

bool ogdf::MinSteinerTreeGoemans139< T >::m_use2approx

protected

Definition at line 71 of file MinSteinerTreeGoemans139.h.

---

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

• include/ogdf/graphalg/MinSteinerTreeGoemans139.h