Implementation of a dual-ascent-based lower bound heuristic for Steiner tree problems. More...

#include <ogdf/graphalg/SteinerTreeLowerBoundDualAscent.h>

Public Member Functions
T	call (const EdgeWeightedGraph< T > &graph, const List< node > &terminals)
	Calls the algorithm and returns the lower bound.

void	call (const EdgeWeightedGraph< T > &graph, const List< node > &terminals, NodeArray< T > &lbNodes, EdgeArray< T > &lbEdges)
	Compute the lower bounds under the assumption nodes or edges are included in the solution.

void	setRepetitions (int num)
	Sets the number of repeated calls to the lower bound algorithm (runs with different roots)

Private Member Functions
T	compute (const EdgeWeightedGraph< T > &graph, const List< node > &terminals, node root)

void	compute (const EdgeWeightedGraph< T > &graph, const List< node > &terminals, node root, NodeArray< T > &lbNodes, EdgeArray< T > &lbEdges)

Private Attributes
int	m_repetitions = 1

Detailed Description

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

Implementation of a dual-ascent-based lower bound heuristic for Steiner tree problems.

This implementation is based on the paper Tobias Polzin, Siavash Vahdati Daneshmand: Improved algorithms for the Steiner problem in networks. Discrete Applied Mathematics 112(1-3): 263-300 (2001)

Definition at line 252 of file SteinerTreeLowerBoundDualAscent.h.

Member Function Documentation

◆ call() [1/2]

template<typename T >

T ogdf::SteinerTreeLowerBoundDualAscent< T >::call	(	const EdgeWeightedGraph< T > &	graph,
		const List< node > &	terminals
	)

inline

Calls the algorithm and returns the lower bound.

Definition at line 336 of file SteinerTreeLowerBoundDualAscent.h.

◆ call() [2/2]

template<typename T >

void ogdf::SteinerTreeLowerBoundDualAscent< T >::call	(	const EdgeWeightedGraph< T > &	graph,
		const List< node > &	terminals,
		NodeArray< T > &	lbNodes,
		EdgeArray< T > &	lbEdges
	)

inline

Compute the lower bounds under the assumption nodes or edges are included in the solution.

The parameter lbNodes and lbEdges are filled with the lower bound for each node and edge, respectively.

Definition at line 352 of file SteinerTreeLowerBoundDualAscent.h.

◆ compute() [1/2]

template<typename T >

T ogdf::SteinerTreeLowerBoundDualAscent< T >::compute	(	const EdgeWeightedGraph< T > &	graph,
		const List< node > &	terminals,
		node	root
	)

inlineprivate

Definition at line 255 of file SteinerTreeLowerBoundDualAscent.h.

◆ compute() [2/2]

template<typename T >

void ogdf::SteinerTreeLowerBoundDualAscent< T >::compute	(	const EdgeWeightedGraph< T > &	graph,
		const List< node > &	terminals,
		node	root,
		NodeArray< T > &	lbNodes,
		EdgeArray< T > &	lbEdges
	)