Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. More...
 
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. More...
 
void setRepetitions (int num)
 Sets the number of repeated calls to the lower bound algorithm (runs with different roots) More...
 

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 254 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 339 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 355 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 257 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 263 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 334 of file SteinerTreeLowerBoundDualAscent.h.

Member Data Documentation

◆ m_repetitions

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

Definition at line 255 of file SteinerTreeLowerBoundDualAscent.h.


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