Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

An implementation of the heavy path decomposition on trees. More...

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

Public Member Functions

 HeavyPathDecomposition (const EdgeWeightedGraphCopy< T > &treeEWGraphCopy)
 
getBottleneckSteinerDistance (node x, node y) const
 computes in the bottleneck distance between terminals x and y More...
 
node lowestCommonAncestor (node x, node y) const
 computes the lowest common ancestor of nodes x and y using the hpd More...
 

Private Member Functions

node binarySearchUpmostTerminal (node v, const std::vector< node > &chainOfTerminals) const
 performs a binary search on chainOfTerminals, searches for the closest node to the root on chainOfTerminals that sits below v More...
 
void buildMaxSegmentTree (std::vector< T > &segmentTree, const int nodeIndex, const int left, const int right, const std::vector< T > &baseArray) const
 builds a max segment tree on the baseArray More...
 
void computeBottleneckOnBranch (node x, node ancestor, T &longestPathDistance, T &fromLowestToAncestor) const
 computes for the path from x to ancestor the maximum distance (sum of edges) between any two consecutive terminals using the hpd updates it in longestPathDistance also puts in fromLowestToAncestor the sum of edges from the last terminal found to the ancestor (the last terminal is special since its Steiner ancestor is ancestor for ancestor as well, so we would consider a wrong part of the path More...
 
void computeLongestDistToSteinerAncestorOnChain ()
 creates for every chain an array with the maximum of every prefix of a fictive array which keeps for every node the sum of the edges on the path from it to its closest terminal ancestor More...
 
void computeLongestDistToSteinerAncestorSegTree ()
 creates for every chain a segment tree built on a fictive array which keeps for every node the sum of the edges on the path from it to its closest terminal ancestor More...
 
void dfsHeavyPathDecomposition (node v, node closestSteinerUpNode)
 performs the heavy path decomposition on the tree belonging to the class updates the fields of the class More...
 
distanceToAncestor (node v, node ancestor) const
 computes the sum of all edges on the path from v to ancestor v must be in ancestor's subtree More...
 
getMaxSegmentTree (const std::vector< T > &segmentTree, const int nodeIndex, const int left, const int right, const int queryLeft, const int queryRight) const
 extracts the maximum on the required interval More...
 

Private Attributes

NodeArray< int > chainOfNode
 the index of a node's chain More...
 
std::vector< std::vector< node > > chains
 list of chains of nodes corresponding to the decomposition More...
 
std::vector< std::vector< node > > chainsOfTerminals
 list of chains only of terminals corresponding to the decomposition More...
 
NodeArray< nodeclosestSteinerAncestor
 the highest-level Steiner ancestor of the current node More...
 
NodeArray< T > distanceToRoot
 the length of the edge to his father More...
 
std::vector< nodefatherOfChain
 the first node from bottom up that does not belong to the chain More...
 
const NodeArray< bool > isTerminal
 isTerminal of the desc tree More...
 
std::vector< std::vector< T > > longestDistToSteinerAncestorOnChain
 the max of the interval 0..i for every i on chains More...
 
std::vector< std::vector< T > > longestDistToSteinerAncestorSegTree
 segment tree for segment maxs on every chain More...
 
NodeArray< int > nodeLevel
 the level of a node in the tree More...
 
NodeArray< int > positionOnChain
 position of a node on his chain More...
 
List< nodeterminals
 list of terminals of the desc tree More...
 
const EdgeWeightedGraphCopy< T > & tree
 constant ref to the tree to be decomposed More...
 
NodeArray< int > weightOfSubtree
 weight of the subtree rooted in one node More...
 

Detailed Description

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

An implementation of the heavy path decomposition on trees.

It contains very specific queries used by reductions.

Definition at line 46 of file HeavyPathDecomposition.h.

Constructor & Destructor Documentation

◆ HeavyPathDecomposition()

template<typename T >
ogdf::steiner_tree::HeavyPathDecomposition< T >::HeavyPathDecomposition ( const EdgeWeightedGraphCopy< T > &  treeEWGraphCopy)
inline

Definition at line 286 of file HeavyPathDecomposition.h.

Member Function Documentation

◆ binarySearchUpmostTerminal()

template<typename T >
node ogdf::steiner_tree::HeavyPathDecomposition< T >::binarySearchUpmostTerminal ( node  v,
const std::vector< node > &  chainOfTerminals 
) const
inlineprivate

performs a binary search on chainOfTerminals, searches for the closest node to the root on chainOfTerminals that sits below v

  • Time: O(log n)

Definition at line 223 of file HeavyPathDecomposition.h.

◆ buildMaxSegmentTree()

template<typename T >
void ogdf::steiner_tree::HeavyPathDecomposition< T >::buildMaxSegmentTree ( std::vector< T > &  segmentTree,
const int  nodeIndex,
const int  left,
const int  right,
const std::vector< T > &  baseArray 
) const
inlineprivate

builds a max segment tree on the baseArray

  • Time: O(n)

Definition at line 69 of file HeavyPathDecomposition.h.

◆ computeBottleneckOnBranch()

template<typename T >
void ogdf::steiner_tree::HeavyPathDecomposition< T >::computeBottleneckOnBranch ( node  x,
node  ancestor,
T &  longestPathDistance,
T &  fromLowestToAncestor 
) const
inlineprivate

computes for the path from x to ancestor the maximum distance (sum of edges) between any two consecutive terminals using the hpd updates it in longestPathDistance also puts in fromLowestToAncestor the sum of edges from the last terminal found to the ancestor (the last terminal is special since its Steiner ancestor is ancestor for ancestor as well, so we would consider a wrong part of the path

  • Time: O(log n)

Definition at line 251 of file HeavyPathDecomposition.h.

◆ computeLongestDistToSteinerAncestorOnChain()

template<typename T >
void ogdf::steiner_tree::HeavyPathDecomposition< T >::computeLongestDistToSteinerAncestorOnChain ( )
inlineprivate

creates for every chain an array with the maximum of every prefix of a fictive array which keeps for every node the sum of the edges on the path from it to its closest terminal ancestor

Definition at line 134 of file HeavyPathDecomposition.h.

◆ computeLongestDistToSteinerAncestorSegTree()

template<typename T >
void ogdf::steiner_tree::HeavyPathDecomposition< T >::computeLongestDistToSteinerAncestorSegTree ( )
inlineprivate

creates for every chain a segment tree built on a fictive array which keeps for every node the sum of the edges on the path from it to its closest terminal ancestor

Definition at line 153 of file HeavyPathDecomposition.h.

◆ dfsHeavyPathDecomposition()

template<typename T >
void ogdf::steiner_tree::HeavyPathDecomposition< T >::dfsHeavyPathDecomposition ( node  v,
node  closestSteinerUpNode 
)
inlineprivate

performs the heavy path decomposition on the tree belonging to the class updates the fields of the class

Definition at line 173 of file HeavyPathDecomposition.h.

◆ distanceToAncestor()

template<typename T >
T ogdf::steiner_tree::HeavyPathDecomposition< T >::distanceToAncestor ( node  v,
node  ancestor 
) const
inlineprivate

computes the sum of all edges on the path from v to ancestor v must be in ancestor's subtree

Definition at line 121 of file HeavyPathDecomposition.h.

◆ getBottleneckSteinerDistance()

template<typename T >
T ogdf::steiner_tree::HeavyPathDecomposition< T >::getBottleneckSteinerDistance ( node  x,
node  y 
) const
inline

computes in the bottleneck distance between terminals x and y

  • Time: O(log n)

Definition at line 341 of file HeavyPathDecomposition.h.

◆ getMaxSegmentTree()

template<typename T >
T ogdf::steiner_tree::HeavyPathDecomposition< T >::getMaxSegmentTree ( const std::vector< T > &  segmentTree,
const int  nodeIndex,
const int  left,
const int  right,
const int  queryLeft,
const int  queryRight 
) const
inlineprivate

extracts the maximum on the required interval

  • Time: O(log n)

Definition at line 89 of file HeavyPathDecomposition.h.

◆ lowestCommonAncestor()

template<typename T >
node ogdf::steiner_tree::HeavyPathDecomposition< T >::lowestCommonAncestor ( node  x,
node  y 
) const
inline

computes the lowest common ancestor of nodes x and y using the hpd

  • Time: O(log n)

Definition at line 318 of file HeavyPathDecomposition.h.

Member Data Documentation

◆ chainOfNode

template<typename T >
NodeArray<int> ogdf::steiner_tree::HeavyPathDecomposition< T >::chainOfNode
private

the index of a node's chain

Definition at line 54 of file HeavyPathDecomposition.h.

◆ chains

template<typename T >
std::vector<std::vector<node> > ogdf::steiner_tree::HeavyPathDecomposition< T >::chains
private

list of chains of nodes corresponding to the decomposition

Definition at line 52 of file HeavyPathDecomposition.h.

◆ chainsOfTerminals

template<typename T >
std::vector<std::vector<node> > ogdf::steiner_tree::HeavyPathDecomposition< T >::chainsOfTerminals
private

list of chains only of terminals corresponding to the decomposition

Definition at line 53 of file HeavyPathDecomposition.h.

◆ closestSteinerAncestor

template<typename T >
NodeArray<node> ogdf::steiner_tree::HeavyPathDecomposition< T >::closestSteinerAncestor
private

the highest-level Steiner ancestor of the current node

Definition at line 59 of file HeavyPathDecomposition.h.

◆ distanceToRoot

template<typename T >
NodeArray<T> ogdf::steiner_tree::HeavyPathDecomposition< T >::distanceToRoot
private

the length of the edge to his father

Definition at line 58 of file HeavyPathDecomposition.h.

◆ fatherOfChain

template<typename T >
std::vector<node> ogdf::steiner_tree::HeavyPathDecomposition< T >::fatherOfChain
private

the first node from bottom up that does not belong to the chain

Definition at line 60 of file HeavyPathDecomposition.h.

◆ isTerminal

template<typename T >
const NodeArray<bool> ogdf::steiner_tree::HeavyPathDecomposition< T >::isTerminal
private

isTerminal of the desc tree

Definition at line 50 of file HeavyPathDecomposition.h.

◆ longestDistToSteinerAncestorOnChain

template<typename T >
std::vector<std::vector<T> > ogdf::steiner_tree::HeavyPathDecomposition< T >::longestDistToSteinerAncestorOnChain
private

the max of the interval 0..i for every i on chains

Definition at line 62 of file HeavyPathDecomposition.h.

◆ longestDistToSteinerAncestorSegTree

template<typename T >
std::vector<std::vector<T> > ogdf::steiner_tree::HeavyPathDecomposition< T >::longestDistToSteinerAncestorSegTree
private

segment tree for segment maxs on every chain

Definition at line 63 of file HeavyPathDecomposition.h.

◆ nodeLevel

template<typename T >
NodeArray<int> ogdf::steiner_tree::HeavyPathDecomposition< T >::nodeLevel
private

the level of a node in the tree

Definition at line 57 of file HeavyPathDecomposition.h.

◆ positionOnChain

template<typename T >
NodeArray<int> ogdf::steiner_tree::HeavyPathDecomposition< T >::positionOnChain
private

position of a node on his chain

Definition at line 55 of file HeavyPathDecomposition.h.

◆ terminals

template<typename T >
List<node> ogdf::steiner_tree::HeavyPathDecomposition< T >::terminals
private

list of terminals of the desc tree

Definition at line 49 of file HeavyPathDecomposition.h.

◆ tree

template<typename T >
const EdgeWeightedGraphCopy<T>& ogdf::steiner_tree::HeavyPathDecomposition< T >::tree
private

constant ref to the tree to be decomposed

Definition at line 48 of file HeavyPathDecomposition.h.

◆ weightOfSubtree

template<typename T >
NodeArray<int> ogdf::steiner_tree::HeavyPathDecomposition< T >::weightOfSubtree
private

weight of the subtree rooted in one node

Definition at line 56 of file HeavyPathDecomposition.h.


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