# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::SteinerTreeLowerBoundDualAscent< T > Class Template Reference

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

#include <ogdf/graphalg/SteinerTreeLowerBoundDualAscent.h>

## Public Member Functions

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

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.

## ◆ 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 )
inlineprivate

Definition at line 261 of file SteinerTreeLowerBoundDualAscent.h.

## ◆ setRepetitions()

template<typename T >
 void ogdf::SteinerTreeLowerBoundDualAscent< T >::setRepetitions ( int num )
inline

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

Definition at line 333 of file SteinerTreeLowerBoundDualAscent.h.

## ◆ m_repetitions

template<typename T >
 int ogdf::SteinerTreeLowerBoundDualAscent< T >::m_repetitions = 1
private

Definition at line 253 of file SteinerTreeLowerBoundDualAscent.h.

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