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)

	LowerBoundDualAscent (const EdgeWeightedGraph< T > &graph, const List< node > &terminals, node root, double eps=1e-6)
	Initializes the algorithm.

void	compute ()
	Computes the lower bound.

T	get () const
	Returns the lower bound.

T	reducedCost (adjEntry adj) const
	Returns the reduced cost of the arc given by `adj`.

Private Member Functions
bool	addNode (ListIterator< TerminalData > &it, node t)
	Adds a node to the cut and add neighbors recursively.

bool	addNodeChecked (ListIterator< TerminalData > &it, node w)

ListIterator< TerminalData >	chooseTerminal ()
	Finds the terminal with the smallest cut arc set (of the last iteration)

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`).

T	findCheapestCutArcCost (const TerminalData &td) const
	Finds the cheapest arc in `cut` and returns its cost.

void	removeTerminalData (ListIterator< TerminalData > it)

void	update (TerminalData &td, T delta)
	Updates reduced costs and cut data.

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.

T	m_lower

AdjEntryArray< T >	m_reducedCost

node	m_root

List< TerminalData >	m_terminals

Detailed Description

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

Computes lower bounds for minimum Steiner tree instances.

Definition at line 53 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 202 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 228 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 95 of file SteinerTreeLowerBoundDualAscent.h.

◆ addNodeChecked()

template<typename T >

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

inlineprivate

Definition at line 131 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 81 of file SteinerTreeLowerBoundDualAscent.h.

◆ compute()

template<typename T >

void ogdf::steiner_tree::LowerBoundDualAscent< T >::compute ( )

inline

Computes the lower bound.

Definition at line 233 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 154 of file SteinerTreeLowerBoundDualAscent.h.