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

typedef Base::Independent_set_iterator	Independent_set_iterator
	Iterator type over the independent set of a Union-Find Vertex. More...

typedef Base::Leaders_iterator	Leaders_iterator
	Iterator type over all the leaders of the Union-Find data structure. More...

Accessors
std::size_t	get_number_of_vertices (void) const
	Number of vertices in the Union-Find data structure. More...

Vertex *	operator[] (std::size_t i)
	Access to the ith inserted vertex in the Union-Find data structrure. More...

const Vertex *	operator[] (std::size_t i) const
	Const access to the ith inserted vertex in the Union-Find data structrure. More...

bool	is_empty (void) const
	Check that there is no Vertex in the Union-Find data structure. More...

Vertex *	find_vertex (T data) const
	Return the vertex associated to the given data, or return 0 if not found. More...

bool	is_leader (const Vertex *v) const
	Check that v is a leader in the Union-Find data structure. More...

bool	is_leader (T data) const
	Check that v is a leader in the Union-Find data structure. More...

bool	is_singleton (const Vertex *v) const
	Check that v is in a singleton. More...

bool	is_singleton (T data) const
	Check that v is in a singleton. More...

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

void	clear (void)
	Remove all the vertices in the Union-Find data structure. More...

Union-Find Operations
Vertex *	make_set (T data)
	Create a new independent set with one Vertex initialized with the input data. More...

Vertex *	find_set (Vertex *u)
	Find the leader of the independent set containing v. More...

Vertex *	find_set (T data)
	Find the leader of the independent set containing v. More...

Vertex *	union_sets (Vertex u, Vertex v)
	Merge the (possibly different) independent sets containing u and v. More...

Vertex *	union_sets (T data_1, T data_2)
	Merge the (possibly different) independent sets containing u and v. More...

Leaders
std::size_t	get_number_of_independent_sets (void) const
	Access to the number of independent sets in the Union-Find data structure. More...

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

std::size_t	get_size_of_independent_set (T data) const
	Access to the size of an independent set containing a Union-Find Vertex. More...

Leaders_iterator	leaders_begin (void)
	Starts the set of leaders of the Union-Find data structure. More...

Leaders_iterator	leaders_end (void)
	Ends the set of leaders of the Union-Find data structure. More...

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

Independent_set_iterator	independent_set_begin (T data) const
	Starts the independent set of vertices containing v. More...

Independent_set_iterator	independent_set_end (Vertex *u) const
	Ends the independent set of vertices containing v. More...

Independent_set_iterator	independent_set_end (T data) const
	Ends the independent set of vertices containing v. More...

Rewind
void	rewind_to_last_make_set (void)
	Rewind the Union-Find data structure before the last inserted Vertex. More...

void	rewind_before_make_set (Vertex *v)
	Rewind the Union-Find data structure before v was inserted. More...

void	rewind_before_make_set (T data)
	Rewind the Union-Find data structure before v was inserted. More...

void	rewind_to_last_union_sets (void)
	Rewind the Union-Find data structure before the last union of distinct independent sets. More...

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

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

Accessors
bool	is_leader (const Vertex *v) const
	Check that v is a leader in the Union-Find data structure. More...

bool	is_singleton (const Vertex *v) const
	Check that v is in a singleton. More...

Union-Find Operations
Vertex *	find_vertex (Vertex *v) const

Vertex *	make_set (Vertex *v)
	Create a new independent set with the input Vertex. More...

Vertex *	const_find_set (Vertex *v) const
	Const find the leader of the independent set containing v. More...

Vertex *	find_set (Vertex *v)
	Find the leader of the independent set containing v. More...

Vertex *	union_sets (Vertex u, Vertex v)
	Merge the (possibly different) independent sets containing u and v. More...

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

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). More...

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

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

Independent_set_iterator	independent_set_end (Vertex *v) const
	Ends the independent set of vertices containing v. More...

Rewind
void	rewind_before_make_set (Vertex *v)
	Rewind the Union-Find data structure before v was inserted. More...

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

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

typedef Base::Independent_set_iterator Independent_set_iterator

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

◆ Leaders_iterator

typedef Base::Leaders_iterator Leaders_iterator

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

◆ Vertex

typedef T_Union_find_vertex_data_structure_contains<T> Vertex

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

Member Function Documentation

◆ clear()

void clear ( void )

inline

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

◆ const_find_set()

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::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]

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

inline

Find the leader of the independent set containing v.

◆ find_set() [2/3]

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

inline

Find the leader of the independent set containing v.

◆ find_set() [3/3]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Vertex * find_set ( Vertex * v )

inlineinherited

Find the leader of the independent set containing v.

◆ find_vertex()

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.

◆ get_number_of_independent_sets()

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

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]

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]

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]

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

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

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::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() [1/3]

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

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.

◆ independent_set_end() [3/3]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::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

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]

bool is_leader ( const Vertex * v ) const

inline

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

◆ is_leader() [3/3]

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]

bool is_singleton ( const Vertex * v ) const

inline

Check that v is in a singleton.

◆ is_singleton() [3/3]

bool is_singleton ( T data ) const

inline

Check that v is in a singleton.

◆ leaders_begin()

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

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]

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.

◆ make_set() [2/2]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Vertex * make_set ( Vertex * v )

inlineinherited

Create a new independent set with the input Vertex.

Returns: The new Vertex.

◆ operator[]() [1/2]

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]

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

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

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

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

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

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]

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

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::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() [3/3]

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.

Public Types

Accessors

Modifiers

Union-Find Operations

Leaders

Independent Set Iterators

Rewind

Accessors

Union-Find Operations

Algorithms

Leaders

Independent Set Iterators

Rewind

Detailed Description

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

Member Typedef Documentation

◆ Independent_set_iterator

◆ Leaders_iterator

◆ Vertex

Member Function Documentation

◆ clear()

◆ const_find_set()

◆ find_set() [1/3]

◆ find_set() [2/3]

◆ find_set() [3/3]

◆ find_vertex()

◆ get_number_of_independent_sets()

◆ get_number_of_vertices()

◆ get_size_of_independent_set() [1/3]

◆ get_size_of_independent_set() [2/3]

◆ get_size_of_independent_set() [3/3]

◆ independent_set_begin() [1/3]

◆ independent_set_begin() [2/3]

◆ independent_set_begin() [3/3]

◆ independent_set_end() [1/3]

◆ independent_set_end() [2/3]

◆ independent_set_end() [3/3]

◆ is_empty()

◆ is_leader() [1/3]

◆ is_leader() [2/3]

◆ is_leader() [3/3]

◆ is_singleton() [1/3]

◆ is_singleton() [2/3]

◆ is_singleton() [3/3]

◆ leaders_begin()

◆ leaders_end()

◆ make_set() [1/2]

◆ make_set() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ quadratic_union()

◆ reset()

◆ rewind_before_make_set() [1/3]

◆ rewind_before_make_set() [2/3]

◆ rewind_before_make_set() [3/3]

◆ rewind_before_union_sets() [1/3]

◆ rewind_before_union_sets() [2/3]

◆ rewind_before_union_sets() [3/3]

◆ rewind_to_last_make_set()

◆ rewind_to_last_union_sets()

◆ union_from_edges()

◆ union_sets() [1/3]

◆ union_sets() [2/3]

◆ union_sets() [3/3]

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