Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::steiner_tree::LowerBoundDualAscent< T > Class Template Reference

Computes lower bounds for minimum Steiner tree instances. More...

#include <ogdf/graphalg/SteinerTreeLowerBoundDualAscent.h>

Classes

struct  TerminalData
 
struct  TerminalDataReference
 

Public Member Functions

 LowerBoundDualAscent (const EdgeWeightedGraph< T > &graph, const List< node > &terminals, double eps=1e-6)
 Initializes the algorithm (and takes the first terminal as root) More...
 
 LowerBoundDualAscent (const EdgeWeightedGraph< T > &graph, const List< node > &terminals, node root, double eps=1e-6)
 Initializes the algorithm. More...
 
void compute ()
 Computes the lower bound. More...
 
get () const
 Returns the lower bound. More...
 
reducedCost (adjEntry adj) const
 Returns the reduced cost of the arc given by adj. More...
 

Private Member Functions

bool addNode (ListIterator< TerminalData > &it, node t)
 Adds a node to the cut and add neighbors recursively. More...
 
bool addNodeChecked (ListIterator< TerminalData > &it, node w)
 
ListIterator< TerminalDatachooseTerminal ()
 Finds the terminal with the smallest cut arc set (of the last iteration) More...
 
void extendCut (adjEntry adj)
 Assumes that the reduced cost of arc adj is zeroed and hence updates (in relevant cuts) the set of arcs coming into W (where W is the smallest node set containing a given terminal but not m_root such that all these arcs have reduced cost greater than zero; this is done for all terminals affected by adj). More...
 
findCheapestCutArcCost (const TerminalData &td) const
 Finds the cheapest arc in cut and returns its cost. More...
 
void removeTerminalData (ListIterator< TerminalData > it)
 
void update (TerminalData &td, T delta)
 Updates reduced costs and cut data. More...
 

Private Attributes

EpsilonTest m_eps
 
const EdgeWeightedGraph< T > & m_graph
 
NodeArray< List< ListIterator< TerminalData > > > m_inTerminalCut
 Mapping of nodes to the cuts they are in. More...
 
m_lower
 
AdjEntryArray< T > m_reducedCost
 
node m_root
 
List< TerminalDatam_terminals
 

Detailed Description

template<typename T>
class ogdf::steiner_tree::LowerBoundDualAscent< T >

Computes lower bounds for minimum Steiner tree instances.

Definition at line 44 of file SteinerTreeLowerBoundDualAscent.h.

Constructor & Destructor Documentation

◆ LowerBoundDualAscent() [1/2]

template<typename T >
ogdf::steiner_tree::LowerBoundDualAscent< T >::LowerBoundDualAscent ( const EdgeWeightedGraph< T > &  graph,
const List< node > &  terminals,
node  root,
double  eps = 1e-6 
)
inline

Initializes the algorithm.

Definition at line 192 of file SteinerTreeLowerBoundDualAscent.h.

◆ LowerBoundDualAscent() [2/2]

template<typename T >
ogdf::steiner_tree::LowerBoundDualAscent< T >::LowerBoundDualAscent ( const EdgeWeightedGraph< T > &  graph,
const List< node > &  terminals,
double  eps = 1e-6 
)
inline

Initializes the algorithm (and takes the first terminal as root)

Definition at line 218 of file SteinerTreeLowerBoundDualAscent.h.

Member Function Documentation

◆ addNode()

template<typename T >
bool ogdf::steiner_tree::LowerBoundDualAscent< T >::addNode ( ListIterator< TerminalData > &  it,
node  t 
)
inlineprivate

Adds a node to the cut and add neighbors recursively.

Returns
False if m_root is reached

Definition at line 85 of file SteinerTreeLowerBoundDualAscent.h.

◆ addNodeChecked()

template<typename T >
bool ogdf::steiner_tree::LowerBoundDualAscent< T >::addNodeChecked ( ListIterator< TerminalData > &  it,
node  w 
)
inlineprivate

Definition at line 121 of file SteinerTreeLowerBoundDualAscent.h.

◆ chooseTerminal()

template<typename T >
ListIterator<TerminalData> ogdf::steiner_tree::LowerBoundDualAscent< T >::chooseTerminal ( )
inlineprivate

Finds the terminal with the smallest cut arc set (of the last iteration)

Definition at line 71 of file SteinerTreeLowerBoundDualAscent.h.

◆ compute()

template<typename T >
void ogdf::steiner_tree::LowerBoundDualAscent< T >::compute ( )
inline

Computes the lower bound.

Definition at line 222 of file SteinerTreeLowerBoundDualAscent.h.

◆ extendCut()

template<typename T >
void ogdf::steiner_tree::LowerBoundDualAscent< T >::extendCut ( adjEntry  adj)
inlineprivate

Assumes that the reduced cost of arc adj is zeroed and hence updates (in relevant cuts) the set of arcs coming into W (where W is the smallest node set containing a given terminal but not m_root such that all these arcs have reduced cost greater than zero; this is done for all terminals affected by adj).

Definition at line 144 of file SteinerTreeLowerBoundDualAscent.h.

◆ findCheapestCutArcCost()

template<typename T >
T ogdf::steiner_tree::LowerBoundDualAscent< T >::findCheapestCutArcCost ( const TerminalData td) const
inlineprivate

Finds the cheapest arc in cut and returns its cost.

Definition at line 161 of file SteinerTreeLowerBoundDualAscent.h.

◆ get()

template<typename T >
T ogdf::steiner_tree::LowerBoundDualAscent< T >::get ( ) const
inline

Returns the lower bound.

Definition at line 237 of file SteinerTreeLowerBoundDualAscent.h.

◆ reducedCost()

template<typename T >
T ogdf::steiner_tree::LowerBoundDualAscent< T >::reducedCost ( adjEntry  adj) const
inline

Returns the reduced cost of the arc given by adj.

Parameters
adjis the adjacency entry of an edge at a node, represents the arc coming into that node

Definition at line 232 of file SteinerTreeLowerBoundDualAscent.h.

◆ removeTerminalData()

template<typename T >
void ogdf::steiner_tree::LowerBoundDualAscent< T >::removeTerminalData ( ListIterator< TerminalData it)
inlineprivate

Definition at line 130 of file SteinerTreeLowerBoundDualAscent.h.

◆ update()

template<typename T >
void ogdf::steiner_tree::LowerBoundDualAscent< T >::update ( TerminalData td,
delta 
)
inlineprivate

Updates reduced costs and cut data.

Definition at line 172 of file SteinerTreeLowerBoundDualAscent.h.

Member Data Documentation

◆ m_eps

template<typename T >
EpsilonTest ogdf::steiner_tree::LowerBoundDualAscent< T >::m_eps
private

Definition at line 62 of file SteinerTreeLowerBoundDualAscent.h.

◆ m_graph

template<typename T >
const EdgeWeightedGraph<T>& ogdf::steiner_tree::LowerBoundDualAscent< T >::m_graph
private

Definition at line 64 of file SteinerTreeLowerBoundDualAscent.h.

◆ m_inTerminalCut

template<typename T >
NodeArray<List<ListIterator<TerminalData> > > ogdf::steiner_tree::LowerBoundDualAscent< T >::m_inTerminalCut
private

Mapping of nodes to the cuts they are in.

Definition at line 68 of file SteinerTreeLowerBoundDualAscent.h.

◆ m_lower

template<typename T >
T ogdf::steiner_tree::LowerBoundDualAscent< T >::m_lower
private

Definition at line 63 of file SteinerTreeLowerBoundDualAscent.h.

◆ m_reducedCost

template<typename T >
AdjEntryArray<T> ogdf::steiner_tree::LowerBoundDualAscent< T >::m_reducedCost
private

Definition at line 67 of file SteinerTreeLowerBoundDualAscent.h.

◆ m_root

template<typename T >
node ogdf::steiner_tree::LowerBoundDualAscent< T >::m_root
private

Definition at line 66 of file SteinerTreeLowerBoundDualAscent.h.

◆ m_terminals

template<typename T >
List<TerminalData> ogdf::steiner_tree::LowerBoundDualAscent< T >::m_terminals
private

Definition at line 65 of file SteinerTreeLowerBoundDualAscent.h.


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