UnionFindEnum Class Template Reference
[Auxiliary Data Structures]

#include <lemon/unionfind.h>

List of all members.


Detailed Description

template<typename _Item, typename _ItemIntMap>
class lemon::UnionFindEnum< _Item, _ItemIntMap >

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.


Public Member Functions

void insert (const Item &item)
 Inserts the given element into a new component.
void insert (const Item &item, const Item &comp)
 Inserts the given element into the component of the others.
const Item & find (const Item &item) const
 Finds the leader of the component of the given element.
bool join (const Item &a, const Item &b)
 Joining the component of element a and element b.
int size (const Item &item) const
 Returns the size of the component of element a.
void split (const Item &item)
 Splits up the component of the element.
void makeRep (const Item &item)
 Sets the given element to the leader element of its component.
void erase (const Item &item)
 Removes the given element from the structure.
bool move (const Item &item, const Item &comp)
 Moves the given element to another component.
void eraseClass (const Item &item)
 Removes the component of the given element from the structure.

Classes

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


Member Function Documentation

void insert ( const Item &  item  )  [inline]

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

void insert ( const Item &  item,
const Item &  comp 
) [inline]

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

const Item& find ( const Item &  item  )  const [inline]

The method returns the leader of the component of the given element.

bool 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 false else returns true.

int size ( const Item &  item  )  const [inline]

Returns the size of the component of element a.

void split ( const Item &  item  )  [inline]

Splitting the component of the element into sigleton components (component of size one).

void makeRep ( const Item &  item  )  [inline]

Sets the given element to the leader element of its component.

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.

bool move ( const Item &  item,
const Item &  comp 
) [inline]

This method moves the element a from its component to the component of comp. If a and comp are in the same component then it returns false otherwise it returns true.

void eraseClass ( const Item &  item  )  [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.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:51:23 2006 for LEMON by  doxygen 1.5.1