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

Constructor & Destructor Documentation

◆ MinSteinerTreeGoemans139()

template<typename T >

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

inline

Definition at line 91 of file MinSteinerTreeGoemans139.h.

◆ ~MinSteinerTreeGoemans139()

template<typename T >

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

inlinevirtual

Definition at line 98 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 146 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 124 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 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

k	the maximal number of terminals in a full component

Definition at line 104 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 110 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

template<typename T >

bool ogdf::MinSteinerTreeGoemans139< T >::m_use2approx

protected

Definition at line 86 of file MinSteinerTreeGoemans139.h.

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

include/ogdf/graphalg/MinSteinerTreeGoemans139.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

template<typename T> class ogdf::MinSteinerTreeGoemans139< T >

Constructor & Destructor Documentation

◆ MinSteinerTreeGoemans139()

◆ ~MinSteinerTreeGoemans139()

Member Function Documentation

◆ computeSteinerTree()

◆ disablePreprocessing()

◆ separateCycles()

◆ setMaxComponentSize()

◆ setSeed()

◆ use2Approximation()

Member Data Documentation

◆ m_preprocess

◆ m_restricted

◆ m_seed

◆ m_separateCycles

◆ m_use2approx

Open
Graph Drawing
Framework

template<typename T>
class ogdf::MinSteinerTreeGoemans139< T >