This class implements the loss-contracting (1.55+epsilon)-approximation algorithm for the Steiner tree problem by Robins and Zelikovsky. More...

#include <ogdf/graphalg/MinSteinerTreeRZLoss.h>

Inheritance diagram for ogdf::MinSteinerTreeRZLoss< T >:

Classes
class	Main

Public Member Functions
	MinSteinerTreeRZLoss ()

	MinSteinerTreeRZLoss (int v)

virtual	~MinSteinerTreeRZLoss ()

long	numberOfComponentLookUps ()
	Returns the number of components lookups during execution time.

long	numberOfContractedComponents ()
	Returns the number of contracted components.

long	numberOfGeneratedComponents ()
	Returns the number of generated components.

void	setMaxComponentSize (int k)
	Sets the maximal number of terminals in a full component.

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 given a weighted graph and a list of terminals.

Private Attributes
std::unique_ptr< Main >	m_alg

int	m_restricted

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

This class implements the loss-contracting (1.55+epsilon)-approximation algorithm for the Steiner tree problem by Robins and Zelikovsky.

This implementation is based on:

(G. Robins, A. Zelikovsky, Improved Steiner Tree Approximation in Graphs, SODA 2000, pages 770-779, SIAM, 2000)

Definition at line 62 of file MinSteinerTreeRZLoss.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeRZLoss() [1/2]

template<typename T >

ogdf::MinSteinerTreeRZLoss< T >::MinSteinerTreeRZLoss ( )

inline

Definition at line 69 of file MinSteinerTreeRZLoss.h.

◆ MinSteinerTreeRZLoss() [2/2]

template<typename T >

ogdf::MinSteinerTreeRZLoss< T >::MinSteinerTreeRZLoss ( int v )

inline

Definition at line 71 of file MinSteinerTreeRZLoss.h.

◆ ~MinSteinerTreeRZLoss()

template<typename T >

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

inlinevirtual

Definition at line 73 of file MinSteinerTreeRZLoss.h.

Member Function Documentation

◆ computeSteinerTree()

template<typename T >

virtual T ogdf::MinSteinerTreeRZLoss< T >::computeSteinerTree	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal,
		EdgeWeightedGraphCopy< T > *&	finalSteinerTree
	)

inlineoverrideprotectedvirtual

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

See also: MinSteinerTreeModule::call

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 114 of file MinSteinerTreeRZLoss.h.

◆ numberOfComponentLookUps()

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::numberOfComponentLookUps ( )

inline

Returns the number of components lookups during execution time.

Definition at line 98 of file MinSteinerTreeRZLoss.h.

◆ numberOfContractedComponents()

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::numberOfContractedComponents ( )

inline

Returns the number of contracted components.

Definition at line 90 of file MinSteinerTreeRZLoss.h.

◆ numberOfGeneratedComponents()

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::numberOfGeneratedComponents ( )

inline

Returns the number of generated components.

Definition at line 82 of file MinSteinerTreeRZLoss.h.

◆ setMaxComponentSize()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< 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 79 of file MinSteinerTreeRZLoss.h.

Member Data Documentation

◆ m_alg

template<typename T >

std::unique_ptr<Main> ogdf::MinSteinerTreeRZLoss< T >::m_alg

private

Definition at line 66 of file MinSteinerTreeRZLoss.h.

◆ m_restricted

template<typename T >

int ogdf::MinSteinerTreeRZLoss< T >::m_restricted

private

Definition at line 63 of file MinSteinerTreeRZLoss.h.

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

include/ogdf/graphalg/MinSteinerTreeRZLoss.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MinSteinerTreeRZLoss() [1/2]

◆ MinSteinerTreeRZLoss() [2/2]

◆ ~MinSteinerTreeRZLoss()

Member Function Documentation

◆ computeSteinerTree()

◆ numberOfComponentLookUps()

◆ numberOfContractedComponents()

◆ numberOfGeneratedComponents()

◆ setMaxComponentSize()

Member Data Documentation

◆ m_alg

◆ m_restricted

Open
Graph Drawing
Framework