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.

double	getLastLowerBound () const
	Returns the lower bound calculated while solving the last problem.

Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual	~MinSteinerTreeModule ()
	Do nothing on destruction.

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 Member Functions
int	getComponent (const node v) const
	Finds the biggest set including node v.

double	getNextEdge (edge *nextEdge)
	Idendifies the next edge with a tight-to-be packing constraint.

void	init ()
	Initializes all required datastructes.

bool	isActive (int component) const
	Returns whether the given component is active.

void	makeActive (int component)
	Marks the specified component as active.

void	mergeComponents (const node v, const node w)
	Merges two disjoint components.

void	updatePriorities (double eps)
	Must be called after merging any two components.

Private Attributes
HashArray< int, ListIterator< int > >	m_activeComponentIterators

List< int >	m_activeComponents

NodeArray< int >	m_componentMapping

double	m_lowerBound

DisjointSets *	m_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.

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

G	The weighted input graph
terminals	The list of terminal nodes
isTerminal	A bool array of terminals
finalSteinerTree	The 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

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 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

v	the representative of the set to find

Definition at line 164 of file MinSteinerTreePrimalDual.h.

◆ getLastLowerBound()

template<typename T >

double ogdf::MinSteinerTreePrimalDual< T >::getLastLowerBound ( ) const

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

nextEdge the 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

component the 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

v	representative of the first component
w	representative 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

eps	the value of the last tight edge

private

Definition at line 62 of file MinSteinerTreePrimalDual.h.

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

include/ogdf/graphalg/MinSteinerTreePrimalDual.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ call()

◆ computeSteinerTree()

◆ getComponent()

◆ getLastLowerBound()

◆ getNextEdge()

◆ init()

◆ isActive()

◆ makeActive()

◆ mergeComponents()

◆ updatePriorities()

Member Data Documentation

◆ m_activeComponentIterators

◆ m_activeComponents

◆ m_componentMapping

◆ m_lowerBound

◆ m_pComponents

◆ m_pGraph

◆ m_pIsTerminal

◆ m_priorities

◆ m_pTerminals

◆ MAX_VALUE

Open
Graph Drawing
Framework