UnionFindEnum Class Template Reference
[Auxiliary Data Structures]

#include <lemon/unionfind.h>

List of all members.


Detailed Description

template<typename T, template< typename Item > class Map>
class lemon::UnionFindEnum< T, Map >

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 T &a)
 Inserts the given element into a new component.
void insert (const T &a, const T &comp)
 Inserts the given element into the component of the others.
find (const T &a) const
 Finds the leader of the component of the given element.
bool join (T a, T b)
 Joining the component of element a and element b.
int size (const T &a) const
 Returns the size of the component of element a.
void split (const T &a)
 Splits up the component of the element.
void makeRep (const T &a)
 Sets the given element to the leader element of its component.
bool move (const T &a, const T &comp)
 Moves the given element to an other component.
void erase (const T &a)
 Removes the given element from the structure.
void eraseClass (const T &a)
 Removes the component of the given element from the structure.
ClassIt & first (ClassIt &it) const
 Sets the iterator to point to the first component.
bool valid (ClassIt const &it) const
 Returns whether the iterator is valid.
ClassIt & next (ClassIt &it) const
 Steps the iterator to the next component.
ItemIt & first (ItemIt &it, const T &a) const
 Sets the iterator to point to the first element of the component.
bool valid (ItemIt const &it) const
 Returns whether the iterator is valid.
ItemIt & next (ItemIt &it) const
 Steps the iterator to the next component.


Member Function Documentation

void insert const T &  a  )  [inline]
 

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

void insert const T &  a,
const T &  comp
[inline]
 

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

T find const T &  a  )  const [inline]
 

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

bool join a,
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 T &  a  )  const [inline]
 

Returns the size of the component of element a.

void split const T &  a  )  [inline]
 

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

void makeRep const T &  a  )  [inline]
 

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

bool move const T &  a,
const T &  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 erase const T &  a  )  [inline]
 

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.

void eraseClass const T &  a  )  [inline]
 

Removes the component of the given element from the structure.

ClassIt& first ClassIt &  it  )  const [inline]
 

Sets the iterator to point to the first component.

With the first, valid and next methods you can iterate through the components. For example:

 UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
 UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
 UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
  for (U.first(iter); U.valid(iter); U.next(iter)) {
    // iter is convertible to Graph::Node
    cout << iter << endl;
  }

bool valid ClassIt const &  it  )  const [inline]
 

Returns whether the iterator is valid.

With the first, valid and next methods you can iterate through the components. See the example here: first.

ClassIt& next ClassIt &  it  )  const [inline]
 

Steps the iterator to the next component.

With the first, valid and next methods you can iterate through the components. See the example here: first.

ItemIt& first ItemIt &  it,
const T &  a
const [inline]
 

Sets the iterator to point to the first element of the component.

With the first, valid and next methods you can iterate through the elements of a component. For example (iterating through the component of the node node):

 Graph::Node node = ...;
 UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
 UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
 UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
     // iiter is convertible to Graph::Node
     cout << iiter << endl;
   }

bool valid ItemIt const &  it  )  const [inline]
 

Returns whether the iterator is valid.

With the first, valid and next methods you can iterate through the elements of a component. See the example here: first.

ItemIt& next ItemIt &  it  )  const [inline]
 

Steps the iterator to the next component.

With the first, valid and next methods you can iterate through the elements of a component. See the example here: first.


The documentation for this class was generated from the following file:
Generated on Fri Feb 3 18:42:43 2006 for LEMON by  doxygen 1.4.6