HeapUnionFind< V, IM, Comp > Class Template Reference

---

Detailed Description

template<typename V, typename IM, typename Comp = std::less<V>>
class lemon::HeapUnionFind< V, IM, Comp >

A Union-Find data structure implementation which is able to store a priority for each item and retrieve the minimum of each class. In addition, it supports the joining and splitting the components. If you don't need this feature then you makes better to use the UnionFind class which is more efficient.

The union-find data strcuture based on a (2, 16)-tree with a tournament minimum selection on the internal nodes. The insert operation takes O(1), the find, set, decrease and increase takes O(log(n)), where n is the number of nodes in the current component. The complexity of join and split is O(log(n)*k), where n is the sum of the number of the nodes and k is the number of joined components or the number of the components after the split.

Precondition:

You need to add all the elements by the insert() method.

#include <lemon/unionfind.h>

List of all members.

Classes
class	ClassIt
	Class iterator. More...
class	ItemIt
	LEMON style iterator for the items of a class. More...
Public Types
typedef V	Value
typedef IM::Key	Item
typedef IM	ItemIntMap
typedef Comp	Compare
Public Member Functions
bool	alive (int cls) const
	Returns true when the given class is alive.
bool	trivial (int cls) const
	Returns true when the given class is trivial.
	HeapUnionFind (ItemIntMap &_index)
	Constructs the union-find.
void	clear ()
	Clears the union-find data structure.
int	insert (const Item &item, const Value &prio)
	Insert a new node into a new component.
int	find (const Item &item) const
	The class of the item.
template<typename Iterator >
int	join (Iterator begin, Iterator end)
	Joins the classes.
template<typename Iterator >
void	split (int cls, Iterator out)
	Split the class to subclasses.
const Value &	operator[] (const Item &item) const
void	set (const Item &item, const Value &prio)
void	increase (const Item &item, const Value &prio)
void	decrease (const Item &item, const Value &prio)
const Value &	classPrio (int cls) const
const Item &	classTop (int cls) const
	Gives back the minimum priority item of the class.
const Item &	classRep (int id) const
	Gives back a representant item of the class.

---

Constructor & Destructor Documentation

HeapUnionFind

(

ItemIntMap &

_index

)

[inline]

Constructs the union-find. _index The index map of the union-find. The data structure uses internally for store references.

---

Member Function Documentation

bool alive

(

int

cls

)

const [inline]

Returns true when the given class is alive, ie. the class is not nested into other class.

bool trivial

(

int

cls

)

const [inline]

Returns true when the given class is trivial, ie. the class contains just one item directly.

void clear

(

)

[inline]

Erase each item from the data structure.

int insert	(	const Item &	item,
		const Value &	prio
	)		[inline]

Insert a new node into a new component.

Parameters:

item	The item of the new node.
prio	The priority of the new node.

Returns:

The class id of the one-item-heap.

int find

(

const Item &

item

)

const [inline]

Returns:

The alive class id of the item, which is not nested into other classes.

The time complexity is O(log(n)).

int join	(	Iterator	begin,
		Iterator	end
	)		[inline]

The current function joins the given classes. The parameter is an STL range which should be contains valid class ids. The time complexity is O(log(n)*k) where n is the overall number of the joined nodes and k is the number of classes.

Returns:

The class of the joined classes.

Precondition:

The range should contain at least two class ids.

void split	(	int	cls,
		Iterator	out
	)		[inline]

The current function splits the given class. The join, which made the current class, stored a reference to the subclasses. The splitClass() member restores the classes and creates the heaps. The parameter is an STL output iterator which will be filled with the subclass ids. The time complexity is O(log(n)*k) where n is the overall number of nodes in the splitted classes and k is the number of the classes.

const Value& operator[]

(

const Item &

item

)

const [inline]

Gives back the priority of the current item.

void set	(	const Item &	item,
		const Value &	prio
	)		[inline]

Sets the priority of the current item.

void increase	(	const Item &	item,
		const Value &	prio
	)		[inline]

Increase the priority of the current item.

void decrease	(	const Item &	item,
		const Value &	prio
	)		[inline]

Increase the priority of the current item.

const Value& classPrio

(

int

cls

)

const [inline]

Gives back the minimum priority of the class.

const Item& classTop

(

int

cls

)

const [inline]

Returns:

Gives back the minimum priority item of the class.

const Item& classRep

(

int

id

)

const [inline]

Gives back a representant item of the class. The representant is indpendent from the priorities of the items.