T_Union_find_contains< T > Class Template Reference

Union-Find data structure where the vertices contains a data. More...

#include <Union_find.hpp>

Public Types
typedef T_Union_find_vertex_data_structure_contains< T >	Vertex
	Representation of a Vertex in the Union-Find data structure.
typedef Vertex_list_iterator	Leaders_iterator
	Iterator type over all the leaders of the Union-Find data structure.
typedef T_Independent_set_iterator< void >	Independent_set_iterator
	Iterator type over the independent set of a Union-Find Vertex.

Union-Find Operations
Vertex *	make_set (T data)
	Create a new independent set with one Vertex initialized with the input data.
Vertex *	find_set (Vertex *u)
Vertex *	union_sets (Vertex *u, Vertex *v)
Vertex *	find_vertex (Vertex *v) const
	Return the vertex itself.

Accessors
std::size_t	get_number_of_vertices (void) const
	Number of vertices in the Union-Find data structure.
Vertex *	operator[] (std::size_t i)
	Access to the ith inserted vertex in the Union-Find data structrure.
const Vertex *	operator[] (std::size_t i) const
	Const access to the ith inserted vertex in the Union-Find data structrure.
bool	is_empty (void) const
	Check that there is no Vertex in the Union-Find data structure.
bool	is_leader (const Vertex *v) const
	Check that v is a leader in the Union-Find data structure.
bool	is_singleton (const Vertex *v) const
	Check that v is in a singleton.

Modifiers
void	reset (void)
	Separate all the vertices in the Union-Find data structure.
void	clear (void)
	Remove all the vertices in the Union-Find data structure.

Union-Find Operations
Vertex *	make_set (Vertex *v)
	Create a new independent set with the input Vertex.
Vertex *	const_find_set (Vertex *v) const
	Const find the leader of the independent set containing v.
Vertex *	find_set (Vertex *v)
	Find the leader of the independent set containing v.
Vertex *	union_sets (Vertex *u, Vertex *v)
	Merge the (possibly different) independent sets containing u and v.

Algorithms
void	quadratic_union (const UnionComparator &comp=UnionComparator())
	Reset the Union-Find data structure and union all the vertices that are in the same independent set related to a given comparator.
void	union_from_edges (InputIterator begin, InputIterator end)
	Reset the union-Find data structure and union all the vertices that are in the same independent set related to the pairs of vertices in between [begin, end).

Leaders
std::size_t	get_number_of_independent_sets (void) const
	Access to the number of independent sets in the Union-Find data structure.
std::size_t	get_size_of_independent_set (const Vertex *v) const
	Access to the size of an independent set containing a Union-Find Vertex.
Leaders_iterator	leaders_begin (void)
	Starts the set of leaders of the Union-Find data structure.
Leaders_iterator	leaders_end (void)
	Ends the set of leaders of the Union-Find data structure.

Independent Set Iterators
Independent_set_iterator	independent_set_begin (Vertex *v) const
	Starts the independent set of vertices containing v.
Independent_set_iterator	independent_set_end (Vertex *v) const
	Ends the independent set of vertices containing v.

Rewind
void	rewind_to_last_make_set (void)
	Rewind the Union-Find data structure before the last inserted Vertex.
void	rewind_before_make_set (Vertex *v)
	Rewind the Union-Find data structure before v was inserted.
void	rewind_to_last_union_sets (void)
	Rewind the Union-Find data structure before the last union of distinct independent sets.
void	rewind_before_union_sets (Vertex *u, Vertex *v)
	Rewind the Union-Find data structure before u and v were in the same independent set.

Detailed Description

template<class T>
class SBL::CADS::T_Union_find_contains< T >

Union-Find data structure where the vertices contains a data.

Union-Find data structure where the vertices contains a data.

Member Typedef Documentation

Independent_set_iterator

typedef T_Independent_set_iterator<void> Independent_set_iterator

inherited

Iterator type over the independent set of a Union-Find Vertex.

Leaders_iterator

typedef Vertex_list_iterator Leaders_iterator

inherited

Iterator type over all the leaders of the Union-Find data structure.

Vertex

template<class T>

typedef T_Union_find_vertex_data_structure_contains<T> Vertex

Representation of a Vertex in the Union-Find data structure.

When a vertex v contains a data, it is accessible from the method v.data().

Member Function Documentation

clear()

void clear ( void )

inlineinherited

Remove all the vertices in the Union-Find data structure.

const_find_set()

Vertex * const_find_set ( Vertex * v ) const

inlineinherited

Const find the leader of the independent set containing v.

Contrarily to the non const method, there is no path compression.

find_set() [1/2]

Vertex * find_set ( Vertex * v )

inlineinherited

Find the leader of the independent set containing v.

find_set() [2/2]

template<class T>

T_Union_find_contains< T >::Vertex * find_set ( Vertex * u )

inline

find_vertex()

template<class T>

Vertex * find_vertex ( Vertex * v ) const

inline

Return the vertex itself.

get_number_of_independent_sets()

std::size_t get_number_of_independent_sets ( void ) const

inlineinherited

Access to the number of independent sets in the Union-Find data structure.

get_number_of_vertices()

std::size_t get_number_of_vertices ( void ) const

inlineinherited

Number of vertices in the Union-Find data structure.

get_size_of_independent_set()

std::size_t get_size_of_independent_set ( const Vertex * v ) const

inlineinherited

Access to the size of an independent set containing a Union-Find Vertex.

independent_set_begin()

Independent_set_iterator independent_set_begin ( Vertex * v ) const

inlineinherited

Starts the independent set of vertices containing v.

Precondition

v is a leader.

independent_set_end()

Independent_set_iterator independent_set_end ( Vertex * v ) const

inlineinherited

Ends the independent set of vertices containing v.

Precondition

v is a leader.

is_empty()

bool is_empty ( void ) const

inlineinherited

Check that there is no Vertex in the Union-Find data structure.

is_leader()

bool is_leader ( const Vertex * v ) const

inlineinherited

Check that v is a leader in the Union-Find data structure.

is_singleton()

bool is_singleton ( const Vertex * v ) const

inlineinherited

Check that v is in a singleton.

leaders_begin()

Leaders_iterator leaders_begin ( void )

inlineinherited

Starts the set of leaders of the Union-Find data structure.

leaders_end()

Leaders_iterator leaders_end ( void )

inlineinherited

Ends the set of leaders of the Union-Find data structure.

make_set() [1/2]

Vertex * make_set ( Vertex * v )

inlineinherited

Create a new independent set with the input Vertex.

Returns

The new Vertex.

make_set() [2/2]

template<class T>

T_Union_find_contains< T >::Vertex * make_set ( T data )

inline

Create a new independent set with one Vertex initialized with the input data.

Precondition

The InternalVertexTag Tag is set to true.

Returns

The new Vertex.

operator[]() [1/2]

Vertex * operator[] ( std::size_t i )

inlineinherited

Access to the ith inserted vertex in the Union-Find data structrure.

Precondition

i < get_number_of_vertices().

operator[]() [2/2]

const Vertex * operator[] ( std::size_t i ) const

inlineinherited

Const access to the ith inserted vertex in the Union-Find data structrure.

Precondition

i < get_number_of_vertices().

quadratic_union()

void quadratic_union ( const UnionComparator & comp = UnionComparator() )

inlineinherited

Reset the Union-Find data structure and union all the vertices that are in the same independent set related to a given comparator.

Template Parameters

UnionComparator

Binary functor checking that two vertices are in the same independent set

reset()

void reset ( void )

inlineinherited

Separate all the vertices in the Union-Find data structure.

rewind_before_make_set()

void rewind_before_make_set ( Vertex * v )

inlineinherited

Rewind the Union-Find data structure before v was inserted.

It does a rewind_to_last_make_set() until v is removed from the union-Find structure. Note that v is not valid anymore after this operation.

rewind_before_union_sets()

void rewind_before_union_sets ( Vertex * u, Vertex * v )

inlineinherited

Rewind the Union-Find data structure before u and v were in the same independent set.

It does a rewind_to_last_union_sets() until u and v are not in the same independent set.

rewind_to_last_make_set()

void rewind_to_last_make_set ( void )

inlineinherited

Rewind the Union-Find data structure before the last inserted Vertex.

It pops the stack until an insertion is found, and undo all operations encountered.

rewind_to_last_union_sets()

void rewind_to_last_union_sets ( void )

inlineinherited

Rewind the Union-Find data structure before the last union of distinct independent sets.

It pops the stack until an union is found, and undo all operations encountered.

union_from_edges()

void union_from_edges ( InputIterator begin, InputIterator end )

inlineinherited

Reset the union-Find data structure and union all the vertices that are in the same independent set related to the pairs of vertices in between [begin, end).

Template Parameters

InputIterator

Iterator over a set of pairs of vertices.

union_sets() [1/2]

Vertex * union_sets ( Vertex * u, Vertex * v )

inlineinherited

Merge the (possibly different) independent sets containing u and v.

Returns

The leader of the independent set containing u and v.

union_sets() [2/2]

template<class T>

T_Union_find_contains< T >::Vertex * union_sets ( Vertex * u, Vertex * v )

inline