CGAL::Union_find< T, A > Class Template Reference

#include <CGAL/Union_find.h>

Definition

template<typename T, typename A>
class CGAL::Union_find< T, A >

An instance P of the data type Union_find<T,A> is a partition of values of type T into disjoint sets.

The template parameter A has to be a model of the allocator concept as defined in the C++ standard. It has a default argument CGAL_ALLOCATOR(T).

Implementation

Union_find<T,A> is implemented with union by rank and path compression. The running time for \( m\) set operations on \( n\) elements is \(O(n \alpha(m,n))\) where \( \alpha(m,n)\) is the extremely slow growing inverse of Ackermann's function.

Types
There are also constant versions const_handle and const_iterator.
typedef unspecified_type	value_type
	values stored in items (equal to T).
typedef unspecified_type	handle
	handle to values.
typedef unspecified_type	iterator
	iterator over values.
typedef unspecified_type	allocator
	allocator.

Creation
	Union_find ()
	creates an instance P of type Union_find<T,A> and initializes it to the empty partition.

Operations
allocator	get_allocator () const
	the allocator of the partition.
std::size_t	number_of_sets () const
	returns the number of disjoint sets of the partition.
std::size_t	size () const
	returns the number of values of the partition.
std::size_t	bytes () const
	returns the memory consumed by the partition.
std::size_t	size (const_handle h) const
	returns the size of the set containing h.
void	clear ()
	reinitializes to an empty partition.
handle	make_set (const T &x)
	creates a new singleton set containing x and returns a handle to it.
handle	push_back (const T &x)
	same as make_set().
template<class Forward_iterator >
void	insert (Forward_iterator first, Forward_iterator beyond)
	inserts the range of values referenced by [first,beyond).
handle	find (handle h) const
const_handle	find (const_handle p) const
	returns a canonical handle of the set that contains h, i.e., P.same_set(h,h2) iff P.find(h) == P.find(h2).
void	unify_sets (handle h1, handle h2)
	unites the sets of partition P containing h1 and h2.
bool	same_set (const_handle h1, const_handle h2) const
	returns true iff h1 and h2 belong to the same set of P.
iterator	begin () const
	returns an iterator pointing to the first value of the partition.
iterator	end () const
	returns an iterator pointing beyond the last value of the partition.

Member Function Documentation

find()

template<typename T , typename A >

const_handle CGAL::Union_find< T, A >::find

(

const_handle

p

)

const

returns a canonical handle of the set that contains h, i.e., P.same_set(h,h2) iff P.find(h) == P.find(h2).

Precondition

h is a handle in P.

insert()

template<typename T , typename A >

template<class Forward_iterator >

void CGAL::Union_find< T, A >::insert	(	Forward_iterator	first,
		Forward_iterator	beyond
	)

inserts the range of values referenced by [first,beyond).

Template Parameters

Forward_iterator

must be a forward iterator with value type T.

same_set()

template<typename T , typename A >

bool CGAL::Union_find< T, A >::same_set	(	const_handle	h1,
		const_handle	h2
	)		const

returns true iff h1 and h2 belong to the same set of P.

Precondition

h1 and h2 are in P.

unify_sets()

template<typename T , typename A >

void CGAL::Union_find< T, A >::unify_sets	(	handle	h1,
		handle	h2
	)

unites the sets of partition P containing h1 and h2.

Precondition

h1 and h2 are in P.