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

This class behaves basically the same as SaveDynamic except that the update of the weighted graph is not done dynamically here. More...

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

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

Public Member Functions
	SaveStatic (EdgeWeightedGraphCopy< T > &steinerTree)
virtual	~SaveStatic ()
virtual T	gain (node u, node v, node w) const
	Returns the gain (sum of the save edges) of a node triple by an LCA query.
node	lca (node u, node v) const
	Returns the node corresponding to the LCA between two given nodes.
void	rebuild ()
	Rebuild the data structure (necessary if the tree has changed)
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 ()

Private Attributes
NodeArray< node >	m_cTerminals
LCA *	m_lca
	The LCA data structure for m_tree.
node	m_root
	The root of m_tree.
EdgeWeightedGraphCopy< T > *	m_steinerTree
	A pointer to the tree we represent the save for.
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::SaveStatic< T >

This class behaves basically the same as SaveDynamic except that the update of the weighted graph is not done dynamically here.

Definition at line 57 of file SaveStatic.h.

Constructor & Destructor Documentation

SaveStatic()

template<typename T >

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

inlineexplicit

Definition at line 59 of file SaveStatic.h.

~SaveStatic()

template<typename T >

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

inlinevirtual

Definition at line 69 of file SaveStatic.h.

Member Function Documentation

gain()

template<typename T >

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

inlinevirtual

Returns the gain (sum of the save edges) of a node triple by an LCA query.

Parameters

u	First triple node
v	Second triple node
w	Third triple node

Returns

Sum of the save edges between the three nodes

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

Definition at line 100 of file SaveStatic.h.

lca()

template<typename T >

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

inline

Returns the node corresponding to the LCA between two given nodes.

Parameters

u	First node
v	Second node

Returns

The LCA of u and v

Definition at line 144 of file SaveStatic.h.

rebuild()

template<typename T >

void ogdf::steiner_tree::SaveStatic< T >::rebuild ( )

inline

Rebuild the data structure (necessary if the tree has changed)

Definition at line 113 of file SaveStatic.h.

saveEdge()

template<typename T >

virtual edge ogdf::steiner_tree::SaveStatic< 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 85 of file SaveStatic.h.

saveWeight()

template<typename T >

virtual T ogdf::steiner_tree::SaveStatic< 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 77 of file SaveStatic.h.

update()

template<typename T >

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

inlinevirtual

Updates the weighted tree data structure given a contracted triple.

The update first identifies the save edges and removes them. After removing links between the triple terminals and replacing them with 0-cost edges a new weighted tree is created and the LCA data structure is rebuilt as well.

Parameters

t	The contracted triple

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

Definition at line 129 of file SaveStatic.h.

Member Data Documentation

m_cTerminals

template<typename T >

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

private

Definition at line 153 of file SaveStatic.h.

m_lca

template<typename T >

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

private

The LCA data structure for m_tree.

Definition at line 152 of file SaveStatic.h.

m_root

template<typename T >

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

private

The root of m_tree.

Definition at line 151 of file SaveStatic.h.

m_steinerTree

template<typename T >

EdgeWeightedGraphCopy<T>* ogdf::steiner_tree::SaveStatic< T >::m_steinerTree

private

A pointer to the tree we represent the save for.

Definition at line 150 of file SaveStatic.h.

m_tree

template<typename T >

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

private

The weighted binary tree to represent the edge weight hierarchy.

Definition at line 148 of file SaveStatic.h.

m_treeEdge

template<typename T >

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

private

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

Definition at line 149 of file SaveStatic.h.

---

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

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