UnionFind

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

template< typename IM >
class UnionFind

A Union-Find data structure implementation.

The class implements the Union-Find data structure. The union operation joins the smaller class to the larger one, while the find operation uses path compression. This is a very simple but efficient implementation, providing only four methods: join (union), find, insert and size. For more features, see the UnionFindEnum class.

It is primarily used in Kruskal algorithm for finding minimal cost spanning tree in a graph.

See also

kruskal()

Pre:

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

Public Types

typedef IM ItemIntMap

typedef ItemIntMap::Key Item

Public Functions

inline UnionFind( ItemIntMap & m )

Constructor.

Constructor of the UnionFind class. You should give an item to integer map which will be used from the data structure. If you modify directly this map that may cause segmentation fault, invalid data structure, or infinite loop when you use again the union-find.

inline int find( const Item & a )

Returns the index of the element’s component.

The method returns the index of the element’s component. This is an integer between zero and the number of inserted elements.

inline void clear()

Clears the union-find data structure.

Erase each item from the data structure.

inline int insert( const Item & a )

Inserts a new element into the structure.

This method inserts a new element into the data structure.

The method returns the index of the new component.

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

Joining the components 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 it returns false otherwise it returns true.

inline int size( const Item & a )

Returns the size of the component of element a.