opengm::Partition< T > Class Template Reference

Disjoint set data structure with path compression. More...

#include <partition.hxx>

Collaboration diagram for opengm::Partition< T >:

[legend]

List of all members.

Public Types
typedef T	value_type
Public Member Functions
	Partition ()
	Construct a partition.
	Partition (const value_type &)
	Construct a partition.
value_type	find (const value_type &) const
	Find the representative element of the set that contains the given element.
value_type	find (value_type)
	Find the representative element of the set that contains the given element.
value_type	numberOfElements () const
value_type	numberOfSets () const
template<class Iterator >
void	elementLabeling (Iterator) const
	Output a continuous labeling of all elements.
template<class Iterator >
void	representatives (Iterator) const
	Output all elements which are set representatives.
void	representativeLabeling (std::map< value_type, value_type > &) const
	Output a continuous labeling of the representative elements.
void	reset (const value_type &)
	Reset a partition such that each set contains precisely one element.
void	merge (value_type, value_type)
	Merge two sets.
void	insert (const value_type &)
	Insert new sets.

---

Detailed Description

template<class T = size_t>
class opengm::Partition< T >

Disjoint set data structure with path compression.

Definition at line 13 of file partition.hxx.

---

Member Typedef Documentation

template<class T = size_t>

typedef T opengm::Partition< T >::value_type

Definition at line 15 of file partition.hxx.

---

Constructor & Destructor Documentation

template<class T >

opengm::Partition< T >::Partition

(

)

[inline]

Construct a partition.

Definition at line 43 of file partition.hxx.

template<class T >

opengm::Partition< T >::Partition

(

const value_type &

size

)

[inline]

Construct a partition.

Parameters:

size

Number of distinct sets.

Definition at line 57 of file partition.hxx.

---

Member Function Documentation

template<class T >

template<class Iterator >

void opengm::Partition< T >::elementLabeling

(

Iterator

out

)

const [inline]

Output a continuous labeling of all elements.

Parameters:

out

(Output) Iterator into a container in which the j-th entry is the label of the element j.

Definition at line 237 of file partition.hxx.

template<class T >

Partition< T >::value_type opengm::Partition< T >::find

(

value_type

element

)

[inline]

Find the representative element of the set that contains the given element.

This mutable function compresses the search path.

Parameters:

element

Element.

Definition at line 121 of file partition.hxx.

template<class T >

Partition< T >::value_type opengm::Partition< T >::find

(

const value_type &

element

)

const [inline]

Find the representative element of the set that contains the given element.

This constant function does not compress the search path.

Parameters:

element

Element.

Definition at line 100 of file partition.hxx.

template<class T >

void opengm::Partition< T >::insert

(

const value_type &

number

)

[inline]

Insert new sets.

Parameters:

number

Number of sets to insert.

Definition at line 177 of file partition.hxx.

template<class T >

void opengm::Partition< T >::merge	(	value_type	element1,
		value_type	element2
	)			[inline]

Merge two sets.

Parameters:

	element1	Element in the first set.
	element2	Element in the second set.

Definition at line 147 of file partition.hxx.

Here is the caller graph for this function:

template<class T >

Partition< T >::value_type opengm::Partition< T >::numberOfElements

(

)

const [inline]

Definition at line 251 of file partition.hxx.

template<class T >

Partition< T >::value_type opengm::Partition< T >::numberOfSets

(

)

const [inline]

Definition at line 258 of file partition.hxx.

Here is the caller graph for this function:

template<class T >

void opengm::Partition< T >::representativeLabeling

(

std::map< value_type, value_type > &

out

)

const [inline]

Output a continuous labeling of the representative elements.

Parameters:

out

(Output) A map that assigns each representative element to its label.

Definition at line 217 of file partition.hxx.

template<class T >

template<class Iterator >

void opengm::Partition< T >::representatives

(

Iterator

it

)

const [inline]

Output all elements which are set representatives.

Parameters:

it

(Output) Iterator into a container.

Definition at line 198 of file partition.hxx.

Here is the caller graph for this function:

template<class T >

void opengm::Partition< T >::reset

(

const value_type &

size

)

[inline]

Reset a partition such that each set contains precisely one element.

Parameters:

size

Number of distinct sets.

Definition at line 77 of file partition.hxx.