Darwin  1.10(beta)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Classes | Public Member Functions | Protected Types | Protected Attributes | List of all members
drwnDisjointSets Class Reference

Implements a forest of disjoint sets abstract data type. More...


struct  _node_t

Public Member Functions

 drwnDisjointSets (unsigned int count=0)
 construct a disjoint dataset with count nodes
 drwnDisjointSets (const drwnDisjointSets &dset)
 copy constructor
 ~drwnDisjointSets ()
int size () const
 return the total number of nodes in the disjoint set
int size (int setId) const
 return the number of nodes in set setId
int sets () const
 return the number of disjoint sets
std::set< int > getMembers (int setId)
 get the ids of nodes in set with id setId
void add (int count)
 add count (disconnected) nodes
int find (int elementId)
 find which set a particular node belongs to
int join (int setId1, int setId2)
 join two sets and return the joined set id (either setId1 or setId2)
std::vector< int > getSetIds () const
 return a list of valid set ids
drwnDisjointSetsoperator= (const drwnDisjointSets &dset)
 assignment operator

Protected Types

typedef struct

Protected Attributes

int _nElements
 number of elements in the forest
int _nSets
 number of sets in the forest
std::vector< node_t_nodes
 list of nodes

Detailed Description

Implements a forest of disjoint sets abstract data type.

The elements are numbered from 0 to (size() - 1). Each element belongs to exactly one set. The sets have ID sparesly numbered in the range 0 to (size() - 1). To get the number of elements of each set, call size(id) with a valid set ID.

See Also
Disjoint Sets

The documentation for this class was generated from the following files: