UnionFindEnum< IM > Class Template Reference

Detailed Description

template<typename IM>
class lemon::UnionFindEnum< IM >

The class implements a Union-Find data structure which is able to enumerate the components and the items in a component. If you don't need this feature then perhaps it's better to use the UnionFind class which is more efficient.

The union operation uses rank heuristic, while the find operation uses path compression.

Precondition

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

#include <lemon/unionfind.h>

Classes
class	ClassIt
	LEMON style iterator for the representant items. More...
class	ItemIt
	LEMON style iterator for the items of a component. More...

Public Types
typedef IM	ItemIntMap
typedef ItemIntMap::Key	Item

Public Member Functions
int	insert (const Item &item)
	Inserts the given element into a new component.
void	insert (const Item &item, int cls)
	Inserts the given element into the component of the others.
void	clear ()
	Clears the union-find data structure.
int	find (const Item &item) const
	Finds the component of the given element.
int	join (const Item &a, const Item &b)
	Joining the component of element a and element b.
int	size (int cls) const
	Returns the size of the class.
void	split (int cls)
	Splits up the component.
void	erase (const Item &item)
	Removes the given element from the structure.
Item	item (int cls) const
	Gives back a representant item of the component.
void	eraseClass (int cls)
	Removes the component of the given element from the structure.

Member Function Documentation

insert() [1/2]

template<typename IM >

int insert ( const Item &  item )

inline

This method creates a new component consisting only of the given element.

insert() [2/2]

template<typename IM >

void insert ( const Item &  item, int  cls  )

inline

This methods inserts the element a into the component of the element comp.

clear()

template<typename IM >

void clear ( )

inline

Erase each item from the data structure.

find()

template<typename IM >

int find ( const Item &  item ) const

inline

The method returns the component id of the given element.

join()

template<typename IM >

int join ( const Item &  a, const Item &  b  )

inline

This is the union operation of the Union-Find structure. Joins the component of element a and component of element b. If a and b are in the same component then returns -1 else returns the remaining class.

size()

template<typename IM >

int size ( int  cls ) const

inline

Returns the size of the class.

split()

template<typename IM >

void split ( int  cls )

inline

Splitting the component into singleton components (component of size one).

erase()

template<typename IM >

void erase ( const Item &  item )

inline

Removes the element from its component and if the component becomes empty then removes that component from the component list.

Warning

It is an error to remove an element which is not in the structure.

This running time of this operation is proportional to the number of the items in this class.

item()

template<typename IM >

Item item ( int  cls ) const

inline

Gives back a representant item of the component.

eraseClass()

template<typename IM >

void eraseClass ( int  cls )

inline

Removes the component of the given element from the structure.

Warning

It is an error to give an element which is not in the structure.