DynamicTree< _Value, _ItemIntMap, _Tolerance, _enableSize > Class Template Reference

---

Detailed Description

template<typename _Value, typename _ItemIntMap, typename _Tolerance, bool _enableSize>
class lemon::DynamicTree< _Value, _ItemIntMap, _Tolerance, _enableSize >

This class provides an implementation of the dynamic tree data structure for maintaining a set of node-disjoint rooted trees. Each item has an associated value, and the item with minimum value can be find in on the path from a node to the its root, and the items on such path can be increased or decreased globally with a certain value in the same running time. We regard a tree edge as directed toward the root, that is from child to parent. Its structure can be modified by two basic operations: link(v,w) adds an edge between a root v and a node w in a different component; cut(v) removes the edge between v and its parent.

Parameters:

	_Value	The value type of the items.
	_ItemIntMap	Converts item type of node to integer.
	_Tolerance	The tolerance class to handle computation problems.
	_enableSize	If true then the data structre manatain the size of each tree. The feature is used in GoldbergTarjan algorithm. The default value is true.

Author:

Hamori Tamas

#include <lemon/dynamic_tree.h>

List of all members.

Public Types
typedef _ItemIntMap	ItemIntMap
	The integer map on the items.
typedef ItemIntMap::Key	Item
	The item type of nodes.
typedef _Value	Value
	The value type of the algorithms.
typedef _Tolerance	Tolerance
	The tolerance used by the algorithm.
Public Member Functions
	DynamicTree (ItemIntMap &iim, const Tolerance &tolerance=Tolerance())
	The constructor of the class.
void	clear ()
	Clears the data structure.
void	tolerance (const Tolerance &tolerance) const
const Tolerance &	tolerance () const
void	makeTree (const Item &item)
	Create a new tree containing a single node with cost zero.
Item	findRoot (const Item &item)
	Return the root of the tree containing node with itemtype item.
int	findSize (const Item &item)
	Return the the value of nodes in the tree containing node with itemtype item.
Item	findCost (const Item &item, Value &d)
	Return the minimum cost containing node.
void	addCost (const Item &item, Value x)
	Add x value to the cost of every node on the path from item to findRoot(item).
void	link (const Item &item1, const Item &item2)
	Combine the trees containing nodes item1 and item2 by adding an edge from item1 item2.
void	cut (const Item &item)
	Divide the tree containing node item into two trees by deleting the edge out of item.
Value	maxValue () const
	Return the upper bound of the costs.

---

Constructor & Destructor Documentation

DynamicTree	(	ItemIntMap &	iim,
		const Tolerance &	tolerance = Tolerance()
	)			[inline]

Parameters:

	iim	The integer map on the items.
	tolerance	Tolerance class.

---

Member Function Documentation

void clear

(

)

[inline]

Clears the data structure

void tolerance

(

const Tolerance &

tolerance

)

const [inline]

Sets the tolerance used by algorithm.

const Tolerance& tolerance

(

)

const [inline]

Returns the tolerance used by algorithm.

Item findCost	(	const Item &	item,
		Value &	d
	)			[inline]

Return into d the minimum cost on the tree path from item to findRoot(item). Return the last item (closest to its root) on this path of the minimum cost.

void link	(	const Item &	item1,
		const Item &	item2
	)			[inline]

This operation assumes that item1 is root and item2 is in a different tree.

void cut

(

const Item &

item

)

[inline]

This operation assumes that item is not a tree root.