# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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

node lowestCommonAncestor (node x, node y) const
computes the lowest common ancestor of nodes x and y using the hpd

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

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

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

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

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

void dfsHeavyPathDecomposition (node v, node closestSteinerUpNode)
performs the heavy path decomposition on the tree belonging to the class updates the fields of the class

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

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

## Private Attributes

NodeArray< intchainOfNode
the index of a node's chain

std::vector< std::vector< node > > chains
list of chains of nodes corresponding to the decomposition

std::vector< std::vector< node > > chainsOfTerminals
list of chains only of terminals corresponding to the decomposition

NodeArray< nodeclosestSteinerAncestor
the highest-level Steiner ancestor of the current node

NodeArray< T > distanceToRoot
the length of the edge to his father

std::vector< nodefatherOfChain
the first node from bottom up that does not belong to the chain

const NodeArray< boolisTerminal
isTerminal of the desc tree

std::vector< std::vector< T > > longestDistToSteinerAncestorOnChain
the max of the interval 0..i for every i on chains

std::vector< std::vector< T > > longestDistToSteinerAncestorSegTree
segment tree for segment maxs on every chain

NodeArray< intnodeLevel
the level of a node in the tree

NodeArray< intpositionOnChain
position of a node on his chain

List< nodeterminals
list of terminals of the desc tree

const EdgeWeightedGraphCopy< T > & tree
constant ref to the tree to be decomposed

NodeArray< intweightOfSubtree
weight of the subtree rooted in one node

## 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 47 of file HeavyPathDecomposition.h.

## ◆ HeavyPathDecomposition()

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

Definition at line 289 of file HeavyPathDecomposition.h.

## ◆ 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 225 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 70 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 252 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 136 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 156 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 177 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 124 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 347 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 91 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 321 of file HeavyPathDecomposition.h.

## ◆ chainOfNode

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

the index of a node's chain

Definition at line 55 of file HeavyPathDecomposition.h.

## ◆ chains

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

list of chains of nodes corresponding to the decomposition

Definition at line 53 of file HeavyPathDecomposition.h.

## ◆ chainsOfTerminals

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

list of chains only of terminals corresponding to the decomposition

Definition at line 54 of file HeavyPathDecomposition.h.

## ◆ closestSteinerAncestor

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

the highest-level Steiner ancestor of the current node

Definition at line 60 of file HeavyPathDecomposition.h.

## ◆ distanceToRoot

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

the length of the edge to his father

Definition at line 59 of file HeavyPathDecomposition.h.

## ◆ fatherOfChain

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

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

Definition at line 61 of file HeavyPathDecomposition.h.

## ◆ isTerminal

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

isTerminal of the desc tree

Definition at line 51 of file HeavyPathDecomposition.h.

## ◆ longestDistToSteinerAncestorOnChain

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

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

Definition at line 63 of file HeavyPathDecomposition.h.

## ◆ longestDistToSteinerAncestorSegTree

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

segment tree for segment maxs on every chain

Definition at line 64 of file HeavyPathDecomposition.h.

## ◆ nodeLevel

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

the level of a node in the tree

Definition at line 58 of file HeavyPathDecomposition.h.

## ◆ positionOnChain

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

position of a node on his chain

Definition at line 56 of file HeavyPathDecomposition.h.

## ◆ terminals

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

list of terminals of the desc tree

Definition at line 50 of file HeavyPathDecomposition.h.

## ◆ tree

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

constant ref to the tree to be decomposed

Definition at line 49 of file HeavyPathDecomposition.h.

## ◆ weightOfSubtree

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

weight of the subtree rooted in one node

Definition at line 57 of file HeavyPathDecomposition.h.

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