UnionFindEnum

Declared in lemon/unionfind.h, in the group Auxiliary Data Structures; the same class on the Doxygen site.

template< typename IM >
class UnionFindEnum

A Union-Find data structure implementation which is able to enumerate the components.

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 joins the smaller class to the larger one, while the find operation uses path compression.

Pre:

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

Public Types

typedef IM ItemIntMap

typedef ItemIntMap::Key Item

Public Functions

inline UnionFindEnum( ItemIntMap & _index )
inline int insert( const Item & item )

Inserts the given element into a new component.

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

inline void insert( const Item & item , int cls )

Inserts the given element into the component of the others.

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

inline void clear()

Clears the union-find data structure.

Erase each item from the data structure.

inline int find( const Item & item ) const

Finds the component of the given element.

The method returns the component id of the given element.

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

Joining the component of element a and element b.

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.

inline int size( int cls ) const

Returns the size of the class.

inline void split( int cls )

Splits up the component.

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

inline void erase( const Item & item )

Removes the given element from the structure.

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.

Warning

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

inline Item item( int cls ) const

Gives back a representant item of the component.

inline void eraseClass( int cls )

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.

class ClassIt

LEMON style iterator for the representant items.

ClassIt is a lemon style iterator for the components. It iterates on the ids of the classes.

Public Functions

inline ClassIt( const UnionFindEnum & ufe )

Constructor of the iterator

inline ClassIt(Invalid)

Constructor to get invalid iterator

inline ClassIt & operator++()

Increment operator.

It steps to the next representant item.

inline operator int() const

Conversion operator.

It converts the iterator to the current representant item.

inline bool operator==( const ClassIt & i )

Equality operator

inline bool operator!=( const ClassIt & i )

Inequality operator

class ItemIt

LEMON style iterator for the items of a component.

ClassIt is a lemon style iterator for the components. It iterates on the items of a class. By example if you want to iterate on each items of each classes then you may write the next code.

for( ClassIt cit( ufe ) ; cit != INVALID ; ++cit )
{
 std::cout << "Class: ";
 for( ItemIt iit( ufe , cit ) ; iit != INVALID ; ++iit ) {
  std::cout << toString( iit ) << ' ' << std::endl;
  }
 std::cout << std::endl;
 }

Public Functions

inline ItemIt( const UnionFindEnum & ufe , int cls )

Constructor of the iterator. The iterator iterates on the class of the item.

inline ItemIt(Invalid)

Constructor to get invalid iterator

inline ItemIt & operator++()

Increment operator.

It steps to the next item in the class.

inline operator const Item&() const

Conversion operator.

It converts the iterator to the current item.

inline bool operator==( const ItemIt & i )

Equality operator

inline bool operator!=( const ItemIt & i )

Inequality operator