# OpenGraph DrawingFramework

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.

## ◆ HeavyPathDecomposition()

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

Definition at line 286 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 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.

## ◆ chainOfNode

template<typename T >
 NodeArray 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 > 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 > 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 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 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 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 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 > 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 > 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 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 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 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& 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 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: