QVDisjointSet Class Reference
[Math functionality]

Implementation of a disjoint set data type, based on the union-find algorithm. More...

#include <QVDisjointSet>

Public Member Functions
	QVDisjointSet (uInt numElements)
	Constructs a disjoint set.
	QVDisjointSet (uInt cols, uInt rows)
	Constructs a QVDisjointSet object, that will maintain a partition of the set of pixels in an image.
	QVDisjointSet (const QVGenericImage &image)
	Constructs a QVDisjointSet object, that will maintain a partition of the set of pixels in a given image.
	QVDisjointSet (const QVDisjointSet &other)
	Copy constructor.
uInt	find (QPoint p)
	Overloaded version of find, for partitions over the set of points contained in an image.
uInt	find (uInt col, uInt row)
	Overloaded version of find, for partitions over the set of points contained in an image.
uInt	find (uInt index)
	Retrieves a common integer identifier, for any element in the same subset of the partition.
uInt	unify (QPoint p1, QPoint p2)
	Joins two subsets of points.
uInt	unify (uInt c1, uInt r1, uInt c2, uInt r2)
	Overloaded version of unify, for partitions over the set of points contained in an image.
uInt	unify (uInt index1, uInt index2)
	Joins two subsets.
uInt	getSetCardinality (const QPoint &p1)
	Gets the number of elements contained in the set that includes the given element.
uInt	getSetCardinality (uInt col, uInt row)
	Gets the number of elements contained in the set that uncles the given element.
uInt	getSetCardinality (uInt index)
	Gets the number of elements contained in the set that includes the given element.
uInt	numberOfSets () const
	Gets the number of different subgroups contained in the disjoint set.
uInt	index (QPoint p) const
	Gets the number corresponding to the given point, in the integer set.
uInt	index (uInt col, uInt row) const
	Gets the number corresponding to the given point, in the integer set.
bool	isRootElement (uInt col, uInt row) const
	Checks if a given element is the root of its set.
bool	isRootElement (uInt index) const
	Checks if a given element is the root of its set.

Detailed Description

Implementation of a disjoint set data type, based on the union-find algorithm.

This implementation makes use of union-find algorithms to maintain partitions efficiently. It is essentially built for maintaining disjoint sets of unsigned integer elements, in the rank from 0 to a given maximum element.

QVDisjointSet objects created with the constructor QVDisjointSet(uInt) partition the set $S_{maxElement} \in \aleph, S_{maxElement} = \{0 .. maxElement\}$ in maxElement different sets, each one containing one of the elements of the set $S_{maxElement}$ . Given 'maxElement' will be pass to the constructor to allocate data for the disjoint set.

Later, unify(uInt,uInt) and find(uInt) functions can be used respectively to join subsets of the partition, and to find which elements of the set $S_{maxElement}$ are in the same subset.

Internally, all elements contained in the same subset in a partition are linked with one of those elements. That element will be the canonical element of the subset, and find(uInt) function retrieves that integer value.

Join two subsets is as simple as using unify(uInt,uInt) passing as parameters an element from each subset. After joining, using find(uInt) with any of those elements, or any contained in the original two sets joined, will return the same canonical element.

The class QVDisjointSet can be used to maintain partitions of general sets, as long as there is a bijection mapping between the set to be partitioned, and a set $S_{maxElement}$ . An example of use of the class QVDisjointSet, for a general set $ G $ given G_MAX_ELEMENT being the element to which corresponds the maximal integer value, could be this:

// Create disjoint set, with at least as many elements as the set G.
QVDisjointSet disjointSet(G_MAX_ELEMENT.toInt());

[...]

// Let element1, element2, ... be elements contained in the set G.
// Configure structure of the disjoint set using unify function:
disjointSet.unify(element1.toInt(), element2.toInt());
disjointSet.unify(element3.toInt(), element4.toInt());
[...]

// Let elementA and elementB be elements contained in the set G.
// Test whether elementA and elementB are contained in the same subset of the partition:
if (disjointSet.find(elementA.toInt()) == disjointSet.find(elementB.toInt()))
    // case elements belong to the same subset in the disjoint set.
else
    // elementA and elementB are not in the same subset of the disjoint set.

[...]

This class however is specially design for dealing with sets of points in an image. Constructors QVDisjointSet(uInt,uInt) and QVDisjointSet(const QVGenericImage&) can be used to create disjoint sets prepared to represent a partition of the set of pixels contained in an image, without the need of converting points in the image, to integer values.

For that matter, functions union and find were overloaded to receive points in QPoint format (see find(QPoint) and unify(QPoint,QPoint) functions), and in coordinate pair format (see find(uInt,uInt) and unify(uInt,uInt,uInt,uInt) functions). The previous example, using QVDisjointSet to partitionate the points in a QVImage, could be rewritten like this:

// The QVImage to partition:
QVImage<uChar> image(cols, rows);

// Create disjoint set, from
QVDisjointSet disjointSet(image);

[...]

// Configure structure of the disjoint set using unify function:
disjointSet.unify(QPoint(1,2), QPoint(2,1));
disjointSet.unify(QPoint(4,5), QPoint(3,4));
[...]

// Test whether points (10,9) and (8,8) are contained in the same subset of the partition:
if (disjointSet.find(QPoint(10,9)) == disjointSet.find(QPoint(8,8)))
    // case points belong to the same subset in the disjoint set.
else
    // given points are not in the same subset of the disjoint set.

[...]

It can also be rewritten using find(uInt,uInt), unify(uInt,uInt,uInt,uInt), and QVDisjointSet(uInt,uInt), coordinate pair format overloaded versions of those functions:

// The QVImage to partition:
QVImage<uChar> image(cols, rows);

// Create disjoint set, from
QVDisjointSet disjointSet(cols, rows);

[...]

// Configure structure of the disjoint set using unify function:
disjointSet.unify(1, 2, 2, 1));
disjointSet.unify(4, 5, 3, 4));
[...]

// Test whether points (10,9) and (8,8) are contained in the same subset of the partition:
if (disjointSet.find(10,9) == disjointSet.find(8,8))
    // case points belong to the same subset in the disjoint set.
else
    // given points are not in the same subset of the disjoint set.

[...]

Definition at line 128 of file qvdisjointset.h.

Constructor & Destructor Documentation

QVDisjointSet::QVDisjointSet ( uInt numElements )

Constructs a disjoint set.

This constructor creates a QVDisjointSet object that will maintain a partition over the set of integers in the range 0..numElements.

Parameters:

numElements

maximal element contained in the disjoint set.

Definition at line 28 of file qvdisjointset.cpp.

QVDisjointSet::QVDisjointSet	(	uInt	cols,
		uInt	rows
	)

Constructs a QVDisjointSet object, that will maintain a partition of the set of pixels in an image.

You can only use functions find(QPoint p), find(uInt col, uInt row), unify(QPoint p1, QPoint p2), and unify(uInt c1, uInt r1, uInt c2, uInt r2) if the QVDisjointSet were created with this constructor, or the constructor QVDisjointSet(const QVGenericImage&).

Parameters:

	cols	number of cols of the image to be partitionated.
	rows	number of rows of the image to be partitionated.

See also:: QVDisjointSet(QVGenericImage &image); find(QPoint p); find(uInt col, uInt row); unify(QPoint p1, QPoint p2); unify(uInt c1, uInt r1, uInt c2, uInt r2)

Definition at line 48 of file qvdisjointset.cpp.

QVDisjointSet::QVDisjointSet ( const QVGenericImage & image )

Constructs a QVDisjointSet object, that will maintain a partition of the set of pixels in a given image.

You can only use functions find(QPoint p), find(uInt col, uInt row), unify(QPoint p1, QPoint p2), and unify(uInt c1, uInt r1, uInt c2, uInt r2) if the QVDisjointSet were created with this constructor, or the constructor QVDisjointSet(uInt cols, uInt rows).

Parameters:

image

image containing the pixels to partition.

See also:: QVDisjointSet(uInt cols, uInt rows); find(QPoint p); find(uInt col, uInt row); unify(QPoint p1, QPoint p2); unify(uInt c1, uInt r1, uInt c2, uInt r2)

Definition at line 56 of file qvdisjointset.cpp.

QVDisjointSet::QVDisjointSet ( const QVDisjointSet & other )

Copy constructor.

Definition at line 35 of file qvdisjointset.cpp.

Member Function Documentation

uInt QVDisjointSet::find ( QPoint p ) [inline]

Overloaded version of find, for partitions over the set of points contained in an image.

The function takes a point (QPoint p) as parameter, and converts it into an integer automatically. Then calls find(uInt) to obtain the canonical element (uInt) of the group that holds the integer corresponding to the point p.

This method can only be used if the disjoint set was constructed with the constructors QVDisjointSet(uInt,uInt) or QVDisjointSet(const QVGenericImage&). Otherwise the class can not convert the image point into an integer number.

See also:: QVDisjointSet(uInt cols, uInt rows); QVDisjointSet(const QVGenericImage&); find(uInt)

Parameters:

p

point contained in the image.

Returns:: canonical element of the subset from the partition, that contains point p

ASSERT: point belongs to rectangle (0,0), (cols, rows)

Definition at line 192 of file qvdisjointset.h.

Referenced by find(), getSetCardinality(), and unify().

uInt QVDisjointSet::find	(	uInt	col,
		uInt	row
	)			`[inline]`

Overloaded version of find, for partitions over the set of points contained in an image.

The function takes the coordinates of a point (col, row) as parameter, and converts it into an integer automatically. Then calls find(uInt) to obtain the canonical element (uInt) of the group that holds the integer corresponding to the point p.

This method can only be used if the disjoint set was constructed with the constructors QVDisjointSet(uInt,uInt) or QVDisjointSet(const QVGenericImage&). Otherwise the class can not convert the image point into an integer number.

See also:: QVDisjointSet(uInt cols, uInt rows); QVDisjointSet(const QVGenericImage&); find(uInt)

Parameters:

	col	first coordinate of the point.
	row	second coordinate of the point.

Returns:: canonical element of the subset from the partition that contains point of coordinates (col, row).

Definition at line 220 of file qvdisjointset.h.

uInt QVDisjointSet::find ( uInt index ) [inline]

Retrieves a common integer identifier, for any element in the same subset of the partition.

Parameters:

index

number identifying the element.

See also:: find(QPoint p); find(uInt col, uInt row)

Definition at line 234 of file qvdisjointset.h.

uInt QVDisjointSet::unify	(	QPoint	p1,
		QPoint	p2
	)			`[inline]`

Joins two subsets of points.

This is an overloaded version of unify, for partitions over the set of points contained in an image. The function converts automatically both elements of the points of an image, represented with QPoints p1 and p2, into integers, to apply later the function unify(uInt,uInt) to join both subsets containing the corresponding integer elements for p1 and p2.

This method can only be used if the disjoint set was constructed with the constructors QVDisjointSet(uInt,uInt) or QVDisjointSet(const QVGenericImage&). Otherwise the class can not convert the image point into an integer number.

See also:: QVDisjointSet(uInt cols, uInt rows); QVDisjointSet(const QVGenericImage&); unify(uInt,uInt)

Parameters:

	p1	element contained in the first set to be join.
	p2	element contained in the second set to be join.

Returns:: canonical element of the subset resulting from the union of both subsets.

Definition at line 265 of file qvdisjointset.h.

Referenced by unify().

uInt QVDisjointSet::unify	(	uInt	c1,
		uInt	r1,
		uInt	c2,
		uInt	r2
	)			`[inline]`

Overloaded version of unify, for partitions over the set of points contained in an image.

The function converts automatically both elements of the points of an image, represented with QPoints p1 and p2, into integers, to apply later the function unify(uInt,uInt) to join both subsets containing elements p1 and p2.

This method can only be used if the disjoint set was constructed with the constructors QVDisjointSet(uInt,uInt) or QVDisjointSet(const QVGenericImage&). Otherwise the class can not convert the image point into an integer number.

See also:: QVDisjointSet(uInt cols, uInt rows); QVDisjointSet(const QVGenericImage&); unify(uInt,uInt)

Parameters:

	c1	first coordinate of a point from the first set.
	r1	second coordinate of a point front the first set.
	c2	first coordinate of a point frond the second set.
	r2	second coordinate of a point frown the second set.

Returns:: canonical element of the subset resulting from the union of both subsets.

Definition at line 294 of file qvdisjointset.h.

uInt QVDisjointSet::unify	(	uInt	index1,
		uInt	index2
	)

Joins two subsets.

Given two elements of the partitionated set (or their set indexes), joins the two subsets that contain those elements in a new subset.

Parameters:

	index1	number identifying first element.
	index2	number identifying second element.

See also:: unify(QPoint p1, QPoint p2); unify(uInt c1, uInt r1, uInt c2, uInt r2)

Returns:: the canonical element for the new set.

Definition at line 72 of file qvdisjointset.cpp.

uInt QVDisjointSet::getSetCardinality ( const QPoint & p1 ) [inline]

Gets the number of elements contained in the set that includes the given element.

Parameters:

p1

point contained in the set.

Returns:: number of elements contained in the set.

Definition at line 321 of file qvdisjointset.h.

Referenced by getSetCardinality().

uInt QVDisjointSet::getSetCardinality	(	uInt	col,
		uInt	row
	)			`[inline]`

Gets the number of elements contained in the set that uncles the given element.

Parameters:

	col	first coordinate of the point.
	row	second coordinate of the point.

Returns:: number of elements contained in the set.

Definition at line 328 of file qvdisjointset.h.

Referenced by getSetCardinality().

uInt QVDisjointSet::getSetCardinality ( uInt index ) [inline]

Gets the number of elements contained in the set that includes the given element.

Parameters:

index

identifying integer of the element contained in the set.

Returns:: number of elements contained in the set.

Definition at line 334 of file qvdisjointset.h.

uInt QVDisjointSet::numberOfSets ( ) const [inline]

Gets the number of different subgroups contained in the disjoint set.

Returns:: number of different subgroups held in the disjoint set.

Definition at line 343 of file qvdisjointset.h.

uInt QVDisjointSet::index ( QPoint p ) const [inline]

Gets the number corresponding to the given point, in the integer set.

Parameters:

p

point contained in the image.

Returns:: number corresponding to the given point in the disjoint set.

Definition at line 349 of file qvdisjointset.h.

uInt QVDisjointSet::index	(	uInt	col,
		uInt	row
	)			const `[inline]`

Gets the number corresponding to the given point, in the integer set.

Parameters:

	col	first coordinate of the point.
	col	second coordinate of the point.

Returns:: number corresponding to the given point in the disjoint set.

Definition at line 356 of file qvdisjointset.h.

bool QVDisjointSet::isRootElement	(	uInt	col,
		uInt	row
	)			const `[inline]`

Checks if a given element is the root of its set.

Parameters:

	col	first coordinate of the point.
	col	second coordinate of the point.

Returns:: true if the element is the canonical element of its group, false otherwise.

See also:: isRootElement(uInt index)

Definition at line 364 of file qvdisjointset.h.

Referenced by isRootElement().

bool QVDisjointSet::isRootElement ( uInt index ) const [inline]

Checks if a given element is the root of its set.

This function is a replacement for the expression:

 (find(index) == index)

Faster than that expression, if find is not needed to be called.

Parameters:

	col	first coordinate of the point.
	col	second coordinate of the point.

Returns:: true if the element is the canonical element of its group, false otherwise.

Definition at line 376 of file qvdisjointset.h.

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

src/qvmath/qvdisjointset.h
src/qvmath/qvdisjointset.cpp

QVDisjointSet Class Reference [Math functionality]

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

QVDisjointSet Class Reference
[Math functionality]