\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5.1 - Profiling tools, Hash Map, Union-find, Modifiers
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Union_find< T, A > Class Template Reference
Profiling Tools, Hash Map, Union-find, Modifiers Reference

#include <CGAL/Union_find.h>

Definition

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). More...
 
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). More...
 
void unify_sets (handle h1, handle h2)
 unites the sets of partition P containing h1 and h2. More...
 
bool same_set (const_handle h1, const_handle h2) const
 returns true iff h1 and h2 belong to the same set of P. More...
 
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

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.
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_iteratormust be a forward iterator with value type T.
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.
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.