CGAL 6.0.1 - Profiling tools, Hash Map, Union-find, Modifiers
|
#include <CGAL/Union_find.h>
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 | |
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. | |
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)
.
h
is a handle in P
. void CGAL::Union_find< T, A >::insert | ( | Forward_iterator | first, |
Forward_iterator | beyond | ||
) |
inserts the range of values referenced by [first,beyond)
.
Forward_iterator | must be a forward iterator with value type T . |
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
.
h1
and h2
are in P
. void CGAL::Union_find< T, A >::unify_sets | ( | handle | h1, |
handle | h2 | ||
) |
unites the sets of partition P
containing h1
and h2
.
h1
and h2
are in P
.