T_Union_find_contains_with_map< 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 Base::Independent_set_iterator	Independent_set_iterator
	Iterator type over the independent set of a Union-Find Vertex.
typedef Base::Leaders_iterator	Leaders_iterator
	Iterator type over all the leaders of the Union-Find data structure.

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.
Vertex *	find_vertex (T data) const
	Return the vertex associated to the given data, or return 0 if not found.
bool	is_leader (const Vertex *v) const
	Check that v is a leader in the Union-Find data structure.
bool	is_leader (T data) 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.
bool	is_singleton (T data) const
	Check that v is in a singleton.
Vertex *	find_vertex (Vertex *v) const
	Return the vertex itself.

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 (T data)
	Create a new independent set with one Vertex initialized with the input data.
Vertex *	find_set (Vertex *u)
	Find the leader of the independent set containing v.
Vertex *	find_set (T data)
	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.
Vertex *	union_sets (T data_1, T data_2)
	Merge the (possibly different) independent sets containing u and v.

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.
std::size_t	get_size_of_independent_set (T data) 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 *u) const
	Starts the independent set of vertices containing v.
Independent_set_iterator	independent_set_begin (T data) const
	Starts the independent set of vertices containing v.
Independent_set_iterator	independent_set_end (Vertex *u) const
	Ends the independent set of vertices containing v.
Independent_set_iterator	independent_set_end (T data) 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_before_make_set (T data)
	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.
void	rewind_before_union_sets (T data_1, T data_2)
	Rewind the Union-Find data structure before u and v were in the same independent set.

Accessors
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.

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_size_of_independent_set (const Vertex *v) const
	Access to the size of an independent set containing a Union-Find Vertex.

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_before_make_set (Vertex *v)
	Rewind the Union-Find data structure before v was inserted.
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_with_map< T >

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

The data has to be comparable with the less operator

Member Typedef Documentation

Independent_set_iterator

template<class T>

typedef Base::Independent_set_iterator Independent_set_iterator

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

Leaders_iterator

template<class T>

typedef Base::Leaders_iterator Leaders_iterator

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.

Member Function Documentation

clear()

template<class T>

void clear ( void )

inline

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/3]

Vertex * find_set ( Vertex * v )

inlineinherited

Find the leader of the independent set containing v.

find_set() [2/3]

template<class T>

T_Union_find_contains_with_map< T >::Vertex * find_set ( T data )

inline

Find the leader of the independent set containing v.

find_set() [3/3]

template<class T>

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

inline

Find the leader of the independent set containing v.

find_vertex() [1/2]

template<class T>

T_Union_find_contains_with_map< T >::Vertex * find_vertex ( T data ) const

inline

Return the vertex associated to the given data, or return 0 if not found.

find_vertex() [2/2]

template<class T>

Vertex * find_vertex ( Vertex * v ) const

inline

Return the vertex itself.

get_number_of_independent_sets()

template<class T>

std::size_t get_number_of_independent_sets ( void ) const

inline

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

get_number_of_vertices()

template<class T>

std::size_t get_number_of_vertices ( void ) const

inline

Number of vertices in the Union-Find data structure.

get_size_of_independent_set() [1/3]

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.

get_size_of_independent_set() [2/3]

template<class T>

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

inline

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

get_size_of_independent_set() [3/3]

template<class T>

std::size_t get_size_of_independent_set ( T data ) const

inline

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

independent_set_begin() [1/3]

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_begin() [2/3]

template<class T>

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_begin ( T data ) const

inline

Starts the independent set of vertices containing v.

Precondition

v is a leader.

independent_set_begin() [3/3]

template<class T>

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_begin ( Vertex * u ) const

inline

Starts the independent set of vertices containing v.

Precondition

v is a leader.

independent_set_end() [1/3]

Independent_set_iterator independent_set_end ( Vertex * v ) const

inlineinherited

Ends the independent set of vertices containing v.

Precondition

v is a leader.

independent_set_end() [2/3]

template<class T>

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_end ( T data ) const

inline

Ends the independent set of vertices containing v.

Precondition

v is a leader.

independent_set_end() [3/3]

template<class T>

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_end ( Vertex * u ) const

inline

Ends the independent set of vertices containing v.

Precondition

v is a leader.

is_empty()

template<class T>

bool is_empty ( void ) const

inline

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

is_leader() [1/3]

bool is_leader ( const Vertex * v ) const

inlineinherited

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

is_leader() [2/3]

template<class T>

bool is_leader ( const Vertex * v ) const

inline

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

is_leader() [3/3]

template<class T>

bool is_leader ( T data ) const

inline

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

is_singleton() [1/3]

bool is_singleton ( const Vertex * v ) const

inlineinherited

Check that v is in a singleton.

is_singleton() [2/3]

template<class T>

bool is_singleton ( const Vertex * v ) const

inline

Check that v is in a singleton.

is_singleton() [3/3]

template<class T>

bool is_singleton ( T data ) const

inline

Check that v is in a singleton.

leaders_begin()

template<class T>

T_Union_find_contains_with_map< T >::Leaders_iterator leaders_begin ( void )

inline

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

leaders_end()

template<class T>

T_Union_find_contains_with_map< T >::Leaders_iterator leaders_end ( void )

inline

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_with_map< 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. Note that if the data already exists, no new vertex is created, and the existing vertex is returned instead.

operator[]() [1/2]

template<class T>

T_Union_find_contains_with_map< T >::Vertex * operator[] ( std::size_t i )

inline

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

Precondition

i < get_number_of_vertices().

operator[]() [2/2]

template<class T>

const T_Union_find_contains_with_map< T >::Vertex * operator[] ( std::size_t i ) const

inline

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()

template<class T>

void reset ( void )

inline

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

rewind_before_make_set() [1/3]

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_make_set() [2/3]

template<class T>

void rewind_before_make_set ( T data )

inline

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_make_set() [3/3]

template<class T>

void rewind_before_make_set ( Vertex * v )

inline

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() [1/3]

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_before_union_sets() [2/3]

template<class T>

void rewind_before_union_sets ( T data_1, T data_2 )

inline

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_before_union_sets() [3/3]

template<class T>

void rewind_before_union_sets ( Vertex * u, Vertex * v )

inline

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()

template<class T>

void rewind_to_last_make_set ( void )

inline

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()

template<class T>

void rewind_to_last_union_sets ( void )

inline

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/3]

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/3]

template<class T>

T_Union_find_contains_with_map< T >::Vertex * union_sets ( T data_1, T data_2 )

inline

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

Returns

The leader of the independent set containing u and v.

union_sets() [3/3]

template<class T>

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

inline

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

Returns

The leader of the independent set containing u and v.