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)

T	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

T	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

T	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< int >	chainOfNode
	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< node >	closestSteinerAncestor
	the highest-level Steiner ancestor of the current node

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

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

const NodeArray< bool >	isTerminal
	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< int >	nodeLevel
	the level of a node in the tree

NodeArray< int >	positionOnChain
	position of a node on his chain

List< node >	terminals
	list of terminals of the desc tree

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

NodeArray< int >	weightOfSubtree
	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.

Constructor & Destructor Documentation

◆ HeavyPathDecomposition()

template<typename T >

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

inline

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

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 55 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 53 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 54 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 60 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 59 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 61 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 51 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 63 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 64 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 58 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 56 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 50 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 49 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 57 of file HeavyPathDecomposition.h.

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

include/ogdf/graphalg/steiner_tree/HeavyPathDecomposition.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ HeavyPathDecomposition()

Member Function Documentation

◆ binarySearchUpmostTerminal()

◆ buildMaxSegmentTree()

◆ computeBottleneckOnBranch()

◆ computeLongestDistToSteinerAncestorOnChain()

◆ computeLongestDistToSteinerAncestorSegTree()

◆ dfsHeavyPathDecomposition()

◆ distanceToAncestor()

◆ getBottleneckSteinerDistance()

◆ getMaxSegmentTree()

◆ lowestCommonAncestor()

Member Data Documentation

◆ chainOfNode

◆ chains

◆ chainsOfTerminals

◆ closestSteinerAncestor

◆ distanceToRoot

◆ fatherOfChain

◆ isTerminal

◆ longestDistToSteinerAncestorOnChain

◆ longestDistToSteinerAncestorSegTree

◆ nodeLevel

◆ positionOnChain

◆ terminals

◆ tree

◆ weightOfSubtree

Open
Graph Drawing
Framework