Dynamically updatable weighted Tree for determining save edges via LCA computation. More...
#include <ogdf/graphalg/steiner_tree/SaveDynamic.h>
Public Member Functions | |
SaveDynamic (EdgeWeightedGraphCopy< T > &steinerTree) | |
Builds a weighted binary tree based on the given terminal spanning tree. More... | |
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. 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 () |
Protected Member Functions | |
node | lca (node u, node v) const |
Returns the node in m_tree that is the LCA of two nodes. More... | |
T | weight (edge e) const |
Returns the weight of an edge in the terminal tree or 0. More... | |
T | weight (node v) const |
Returns the associated weight of a node v in m_tree, or 0 if it is not associated. More... | |
Private Attributes | |
NodeArray< node > | m_cTerminals |
Connects terminal nodes in the terminal spanning tree to their leafs in the weighted tree. More... | |
LCA * | m_lca |
Data structure for calculating the LCAs. More... | |
node | m_root |
The root node of the weighted binary tree. More... | |
const EdgeWeightedGraphCopy< T > * | m_steinerTree |
The underlying terminal spanning tree this weighted tree instance represents. More... | |
Graph | m_tree |
The weighted binary tree to represent the edge weight hierarchy. More... | |
NodeArray< edge > | m_treeEdge |
Maps each inner node of m_tree to an edge in m_steinerTree. More... | |
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.
|
inlineexplicit |
Builds a weighted binary tree based on the given terminal spanning tree.
Additionally the LCA data structure is initialized.
steinerTree | the given terminal spanning tree |
Definition at line 58 of file SaveDynamic.h.
|
inlinevirtual |
Definition at line 68 of file SaveDynamic.h.
|
inlinevirtual |
Returns the gain (sum of save edge costs) of the given triple, calculated by an LCA query.
u | First terminal |
v | Second terminal |
w | Third terminal |
Implements ogdf::steiner_tree::Save< T >.
Definition at line 78 of file SaveDynamic.h.
|
inlineprotected |
Returns the node in m_tree that is the LCA of two nodes.
u | first node |
v | second node |
Definition at line 239 of file SaveDynamic.h.
|
inlinevirtual |
Determines the save edge between two nodes by a LCA query.
u | First node |
v | First node |
Implements ogdf::steiner_tree::Save< T >.
Definition at line 103 of file SaveDynamic.h.
|
inlinevirtual |
Determines the weight of the save edge between two nodes by a LCA query.
u | First node |
v | First node |
Implements ogdf::steiner_tree::Save< T >.
Definition at line 94 of file SaveDynamic.h.
|
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).
t | The contracted triple |
Implements ogdf::steiner_tree::Save< T >.
Definition at line 119 of file SaveDynamic.h.
|
inlineprotected |
Returns the weight of an edge in the terminal tree or 0.
Definition at line 246 of file SaveDynamic.h.
|
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.
|
private |
Connects terminal nodes in the terminal spanning tree to their leafs in the weighted tree.
Definition at line 259 of file SaveDynamic.h.
|
private |
Data structure for calculating the LCAs.
Definition at line 260 of file SaveDynamic.h.
|
private |
The root node of the weighted binary tree.
Definition at line 254 of file SaveDynamic.h.
|
private |
The underlying terminal spanning tree this weighted tree instance represents.
Definition at line 258 of file SaveDynamic.h.
|
private |
The weighted binary tree to represent the edge weight hierarchy.
Definition at line 252 of file SaveDynamic.h.
|
private |
Maps each inner node of m_tree to an edge in m_steinerTree.
Definition at line 253 of file SaveDynamic.h.