DisjointSet Class Reference

Represents a disjoint set of integers. More...

#include <DisjointSet.hpp>

List of all members.

Public Member Functions
	DisjointSet (unsigned int numItems)
	Constructor. Creates a disjoint set with numItems sets labelled 0 to numItems - 1. Initially, each set is disjoint.
	DisjointSet (const DisjointSet &that)
	Copy constructor. Copies contents of that DisjointSet object into this object.
	~DisjointSet ()
	Destructor. Frees the memory used by this object. Called automatically when the object goes out of scope.
void	setUnion (unsigned int x, unsigned int y)
	Unions the set which contains x with that which contains y.
unsigned int	find (unsigned int x) const
	Gets the representative (or label) of the set that contains item x.
void	split (unsigned int x, unsigned int y)
	Splits the set which contains x and y into the disjoint sets which originally contained x and y. Essentially undoes the setUnion() operation.
void	getSetSizes (std::vector< unsigned int > &sizes) const
	Makes a list of the cardinalites of each set. This is sorted greatest to least and is identical to the sizes of the connected components of the tree (the way this object is used, in the main program, at least). The sizes of the connected components are needed when computing the CSF. See Theorem 2.5 in "A Symmetric Function Generalization of the Chromatic Polynomial of a Graph" by Richard Stanley.
void	print () const
	Prints information useful for debugging. For each item, it prints the items parent, representative, and the size of the component if it was disconnected from its parent.
DisjointSet &	operator= (const DisjointSet &that)
	Overloaded assignment operator. Enables deep copy of this object using assignment operator "=".

---

Detailed Description

Represents a disjoint set of integers.

Underneath the hood, it represents the disjoint set as a directed tree. This is to support computing the sizes of the connected components of a forest. We know that each edge of the tree is a cut edge, so adding an edge always unions two disjoint components, and removing an edge always splits one a component into two disjoint ones.

Definition at line 20 of file DisjointSet.hpp.

---

Constructor & Destructor Documentation

DisjointSet::DisjointSet

(

unsigned int

numItems

)

Constructor. Creates a disjoint set with numItems sets labelled 0 to numItems - 1. Initially, each set is disjoint.

Parameters:

numItems

Number of disjoint sets to start with.

Precondition:

numItems should be greater than 0 to avoid weird memory errors.

Definition at line 14 of file DisjointSet.cpp.

DisjointSet::DisjointSet

(

const DisjointSet &

that

)

Copy constructor. Copies contents of that DisjointSet object into this object.

Parameters:

that

DisjointSet object to copy.

Precondition:

that should be a valid DisjointSet object.

Postcondition:

This object will be an exact copy of that DisjointSet, and that DisjointSet will not be modified at all.

Definition at line 29 of file DisjointSet.cpp.

---

Member Function Documentation

unsigned int DisjointSet::find

(

unsigned int

x

)

const

Gets the representative (or label) of the set that contains item x.

Parameters:

x

Item in a set.

Precondition:

Need 0 <= x < mNumItems.

Postcondition:

Returns the representative of the set which contains x. Does not modify this object at all.

Definition at line 80 of file DisjointSet.cpp.

void DisjointSet::getSetSizes

(

std::vector< unsigned int > &

sizes

)

const

Makes a list of the cardinalites of each set. This is sorted greatest to least and is identical to the sizes of the connected components of the tree (the way this object is used, in the main program, at least). The sizes of the connected components are needed when computing the CSF. See Theorem 2.5 in "A Symmetric Function Generalization of the Chromatic Polynomial of a Graph" by Richard Stanley.

Parameters:

sizes

Vector in which to store the set sizes.

Postcondition:

Doesn't modify this object, but sizes will contain the cardinalities of each set, sorted largest to smallest.

Definition at line 122 of file DisjointSet.cpp.

DisjointSet & DisjointSet::operator=

(

const DisjointSet &

that

)

Overloaded assignment operator. Enables deep copy of this object using assignment operator "=".

Parameters:

that

The DisjointSet object to copy into this object.

Precondition:

that should be a valid DisjointSet object.

Postcondition:

This object will be an exact copy of that.

Definition at line 150 of file DisjointSet.cpp.

void DisjointSet::print

(

)

const

Prints information useful for debugging. For each item, it prints the items parent, representative, and the size of the component if it was disconnected from its parent.

Postcondition:

Doesn't modify this object at all.

Definition at line 138 of file DisjointSet.cpp.

void DisjointSet::setUnion	(	unsigned int	x,
		unsigned int	y
	)

Unions the set which contains x with that which contains y.

Parameters:

	x	Item in a set. Doesn't need to be a representative.
	y	Item in a set. Doesn't need to be a representative.

Precondition:

x and y should not be equal to each other, and they should both satisfy 0 <= x,y < mNumItems. Also, x and y should not be in the same set.

Postcondition:

The two disjoint sets, one with x, and one with y, will become a single set whose representative is x if the original disjoint set containing x was larger, or y if the original disjoint set containing y was larger.

Definition at line 47 of file DisjointSet.cpp.

void DisjointSet::split	(	unsigned int	x,
		unsigned int	y
	)

Splits the set which contains x and y into the disjoint sets which originally contained x and y. Essentially undoes the setUnion() operation.

Parameters:

	x	Item in a set. Doesn't need to be a representative.
	y	Item in a set. Doesn't need to be a representative.

Precondition:

x and y should not be equal to each other, and they should both satisfy 0 <= x,y < mNumItems. Also, x and y should be in the same set.

Postcondition:

The set which contains x and y will be split into the two disjoint sets which originally contained x and y, respectively.

Definition at line 95 of file DisjointSet.cpp.

---

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

• DisjointSet.hpp
• DisjointSet.cpp