# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

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. More...

node lca (node u, node v) const
Returns the node corresponding to the LCA between two given nodes. More...

void rebuild ()
Rebuild the data structure (necessary if the tree has changed) More...

virtual edge saveEdge (node u, node v) const
Determines the save edge between two nodes by a LCA query. More...

virtual T saveWeight (node u, node v) const
Determines the weight of the save edge between two nodes by a LCA query. More...

virtual void update (const Triple< T > &t)
Updates the weighted tree data structure given a contracted triple. More...

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. More...

node m_root
The root of m_tree. More...

EdgeWeightedGraphCopy< T > * m_steinerTree
A pointer to the tree we represent the save for. More...

Graph m_tree
The weighted binary tree to represent the edge weight hierarchy. More...

NodeArray< edgem_treeEdge
Maps each inner node of m_tree to an edge in m_steinerTree. More...

## 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.

## ◆ 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 61 of file SaveStatic.h.

## ◆ 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 99 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 146 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 83 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 72 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 130 of file SaveStatic.h.

## ◆ m_cTerminals

template<typename T >
 NodeArray ogdf::steiner_tree::SaveStatic< T >::m_cTerminals
private

Definition at line 159 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 158 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 157 of file SaveStatic.h.

## ◆ m_steinerTree

template<typename T >
 EdgeWeightedGraphCopy* ogdf::steiner_tree::SaveStatic< T >::m_steinerTree
private

A pointer to the tree we represent the save for.

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

## ◆ m_treeEdge

template<typename T >
 NodeArray ogdf::steiner_tree::SaveStatic< T >::m_treeEdge
private

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

Definition at line 155 of file SaveStatic.h.

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