Classes | Public Types | Public Member Functions

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>

List of all members.

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
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
void eraseClass (int cls)
 Removes the component of the given element from the structure.

Member Function Documentation

int insert ( const Item item) [inline]

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

void insert ( const Item item,
int  cls 
) [inline]

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

void clear ( ) [inline]

Erase each item from the data structure.

int find ( const Item item) const [inline]

The method returns the component id of the given element.

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.

int size ( int  cls) const [inline]

Returns the size of the class.

void split ( int  cls) [inline]

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

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 item ( int  cls) const [inline]

Gives back a representant item of the component.

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.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines