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

Dynamically updatable weighted Tree for determining save edges via LCA computation. More...

#include <ogdf/graphalg/steiner_tree/SaveDynamic.h>

Inheritance diagram for ogdf::steiner_tree::SaveDynamic< T >:

Public Member Functions
	SaveDynamic (EdgeWeightedGraphCopy< T > &steinerTree)
	Builds a weighted binary tree based on the given terminal spanning tree.
virtual	~SaveDynamic ()
virtual T	gain (node u, node v, node w) const
	Returns the gain (sum of save edge costs) of the given triple, calculated by an LCA query.
virtual edge	saveEdge (node u, node v) const
	Determines the save edge between two nodes by a LCA query.
virtual T	saveWeight (node u, node v) const
	Determines the weight of the save edge between two nodes by a LCA query.
virtual void	update (const Triple< T > &t)
	Updates the weighted tree data structure given a contracted triple.
Public Member Functions inherited from ogdf::steiner_tree::Save< T >
	Save ()
virtual	~Save ()

Protected Member Functions
node	lca (node u, node v) const
	Returns the node in m_tree that is the LCA of two nodes.
T	weight (edge e) const
	Returns the weight of an edge in the terminal tree or 0.
T	weight (node v) const
	Returns the associated weight of a node v in m_tree, or 0 if it is not associated.

Private Attributes
NodeArray< node >	m_cTerminals
	Connects terminal nodes in the terminal spanning tree to their leafs in the weighted tree.
LCA *	m_lca
	Data structure for calculating the LCAs.
node	m_root
	The root node of the weighted binary tree.
const EdgeWeightedGraphCopy< T > *	m_steinerTree
	The underlying terminal spanning tree this weighted tree instance represents.
Graph	m_tree
	The weighted binary tree to represent the edge weight hierarchy.
NodeArray< edge >	m_treeEdge
	Maps each inner node of m_tree to an edge in m_steinerTree.

Detailed Description

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

Dynamically updatable weighted Tree for determining save edges via LCA computation.

Note that in this dynamic approach, only the auxiliary tree is updated and not the actual terminal spanning tree (if OGDF_SAVEDYNAMIC_CHANGE_TST is not set).

Definition at line 50 of file SaveDynamic.h.

Constructor & Destructor Documentation

SaveDynamic()

template<typename T >

ogdf::steiner_tree::SaveDynamic< T >::SaveDynamic ( EdgeWeightedGraphCopy< T > &  steinerTree )

inlineexplicit

Builds a weighted binary tree based on the given terminal spanning tree.

Additionally the LCA data structure is initialized.

Parameters

steinerTree

the given terminal spanning tree

Definition at line 58 of file SaveDynamic.h.

~SaveDynamic()

template<typename T >

virtual ogdf::steiner_tree::SaveDynamic< T >::~SaveDynamic ( )

inlinevirtual

Definition at line 68 of file SaveDynamic.h.

Member Function Documentation

gain()

template<typename T >

virtual T ogdf::steiner_tree::SaveDynamic< T >::gain ( node  u, node  v, node  w  ) const

inlinevirtual

Returns the gain (sum of save edge costs) of the given triple, calculated by an LCA query.

Parameters

u	First terminal
v	Second terminal
w	Third terminal

Returns

The gain (sum of save edge costs) of the given triple

Implements ogdf::steiner_tree::Save< T >.

Definition at line 78 of file SaveDynamic.h.

lca()

template<typename T >

node ogdf::steiner_tree::SaveDynamic< T >::lca ( node  u, node  v  ) const

inlineprotected

Returns the node in m_tree that is the LCA of two nodes.

Parameters

u	first node
v	second node

Returns

the LCA of u and v

Definition at line 239 of file SaveDynamic.h.

saveEdge()

template<typename T >

virtual edge ogdf::steiner_tree::SaveDynamic< T >::saveEdge ( node  u, node  v  ) const

inlinevirtual

Determines the save edge between two nodes by a LCA query.

Parameters

u	First node
v	First node

Returns

The save edge between two given nodes

Implements ogdf::steiner_tree::Save< T >.

Definition at line 103 of file SaveDynamic.h.

saveWeight()

template<typename T >

virtual T ogdf::steiner_tree::SaveDynamic< T >::saveWeight ( node  u, node  v  ) const

inlinevirtual

Determines the weight of the save edge between two nodes by a LCA query.

Parameters

u	First node
v	First node

Returns

Weight of the save edge between two given nodes

Implements ogdf::steiner_tree::Save< T >.

Definition at line 94 of file SaveDynamic.h.

update()

template<typename T >

virtual void ogdf::steiner_tree::SaveDynamic< T >::update ( const Triple< T > &  t )

inlinevirtual

Updates the weighted tree data structure given a contracted triple.

The update of the weighted tree is performed dynamically. To achieve this, the weighted tree is traversed bottom-up, starting at the three leaves corresponding to the terminals in the triple. It takes time O(height of m_tree).

Parameters

t	The contracted triple

Implements ogdf::steiner_tree::Save< T >.

Definition at line 119 of file SaveDynamic.h.

weight() [1/2]

template<typename T >

T ogdf::steiner_tree::SaveDynamic< T >::weight ( edge  e ) const

inlineprotected

Returns the weight of an edge in the terminal tree or 0.

Definition at line 246 of file SaveDynamic.h.

weight() [2/2]

template<typename T >

T ogdf::steiner_tree::SaveDynamic< T >::weight ( node  v ) const

inlineprotected

Returns the associated weight of a node v in m_tree, or 0 if it is not associated.

Definition at line 249 of file SaveDynamic.h.

Member Data Documentation

m_cTerminals

template<typename T >

NodeArray<node> ogdf::steiner_tree::SaveDynamic< T >::m_cTerminals

private

Connects terminal nodes in the terminal spanning tree to their leafs in the weighted tree.

Definition at line 259 of file SaveDynamic.h.

m_lca

template<typename T >

LCA* ogdf::steiner_tree::SaveDynamic< T >::m_lca

private

Data structure for calculating the LCAs.

Definition at line 260 of file SaveDynamic.h.

m_root

template<typename T >

node ogdf::steiner_tree::SaveDynamic< T >::m_root

private

The root node of the weighted binary tree.

Definition at line 254 of file SaveDynamic.h.

m_steinerTree

template<typename T >

const EdgeWeightedGraphCopy<T>* ogdf::steiner_tree::SaveDynamic< T >::m_steinerTree

private

The underlying terminal spanning tree this weighted tree instance represents.

Definition at line 258 of file SaveDynamic.h.

m_tree

template<typename T >

Graph ogdf::steiner_tree::SaveDynamic< T >::m_tree

private

The weighted binary tree to represent the edge weight hierarchy.

Definition at line 252 of file SaveDynamic.h.

m_treeEdge

template<typename T >

NodeArray<edge> ogdf::steiner_tree::SaveDynamic< T >::m_treeEdge

private

Maps each inner node of m_tree to an edge in m_steinerTree.

Definition at line 253 of file SaveDynamic.h.

---

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

• include/ogdf/graphalg/steiner_tree/SaveDynamic.h