Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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.

Definition at line 228 of file unionfind.h.

Public Member Functions

void insert (const T &a)
 Insert the given element into a new component.
void insert (const T &a, const T &comp)
 Insert the given element into the component of the others.
find (const T &a) const
 Find 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)
 Split up the component of the element.
void makeRep (const T &a)
 Set the given element to the leader element of its component.
bool move (const T &a, const T &comp)
 Move the given element to an other component.
void erase (const T &a)
 Remove 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.

Definition at line 272 of file unionfind.h.

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

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

Definition at line 296 of file unionfind.h.

T find const T &  a  )  const [inline]
 

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

Definition at line 315 of file unionfind.h.

bool join a,
b
[inline]
 

This is the union operation of the Union-Find structure. Joins the component of elemenent a and component of element b. If a and b are in the same component then returns false else returns true.

Definition at line 329 of file unionfind.h.

int size const T &  a  )  const [inline]
 

Returns the size of the component of element a.

Definition at line 371 of file unionfind.h.

void split const T &  a  )  [inline]
 

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

Definition at line 383 of file unionfind.h.

void makeRep const T &  a  )  [inline]
 

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

Definition at line 413 of file unionfind.h.

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.

Definition at line 440 of file unionfind.h.

void erase const T &  a  )  [inline]
 

Remove 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.

Definition at line 493 of file unionfind.h.

Here is the call graph for this function:

void eraseClass const T &  a  )  [inline]
 

Removes the component of the given element from the structure.

Definition at line 525 of file unionfind.h.

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;
  }

Definition at line 589 of file unionfind.h.

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.

Definition at line 603 of file unionfind.h.

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.

Definition at line 616 of file unionfind.h.

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;
   }

Definition at line 679 of file unionfind.h.

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.

Definition at line 696 of file unionfind.h.

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.

Definition at line 712 of file unionfind.h.


The documentation for this class was generated from the following file:
Generated on Mon Feb 21 15:02:36 2005 for LEMON by  doxygen 1.4.1