Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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 ()
 
virtualgain (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.
 
virtualsaveWeight (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< nodem_cTerminals
 
LCAm_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< edgem_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 48 of file SaveStatic.h.

Constructor & Destructor Documentation

◆ SaveStatic()

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

Definition at line 50 of file SaveStatic.h.

◆ ~SaveStatic()

template<typename T >
virtual ogdf::steiner_tree::SaveStatic< T >::~SaveStatic ( )
inlinevirtual

Definition at line 60 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
uFirst triple node
vSecond triple node
wThird triple node
Returns
Sum of the save edges between the three nodes

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

Definition at line 91 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
uFirst node
vSecond node
Returns
The LCA of u and v

Definition at line 135 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 104 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
uFirst node
vFirst node
Returns
The save edge between two given nodes

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

Definition at line 76 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
uFirst node
vFirst node
Returns
Weight of the save edge between two given nodes

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

Definition at line 68 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
tThe contracted triple

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

Definition at line 120 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 144 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 143 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 142 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 141 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 139 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 140 of file SaveStatic.h.


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