Base class implementing the Union-Find data structure. More...

#include <Union_find.hpp>

Classes
class	Descendants_iterator
	Iterator over the descendants of a given vertex. More...

Public Types
typedef VertexDS	Vertex
	Representation of a Vertex in the Union-Find data structure. More...

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

typedef T_Independent_set_iterator< void >	Independent_set_iterator
	Iterator type over the independent set of a Union-Find Vertex. More...

Constructors
	T_Union_find_base (void)
	Constructs an empty Union-Find data structure. More...

	~T_Union_find_base (void)
	If vertices are created internally, destroy them. 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...

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

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 *	find_vertex (Vertex *v) const

Vertex *	make_set (void)
	Create a new independent set with one default Vertex. More...

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

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
template<class UnionComparator >
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...

template<class InputIterator >
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_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...

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 *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_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_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...

Detailed Description

template<class T, class VertexDS, bool InternalVertexTag>
class SBL::CADS::T_Union_find_base< T, VertexDS, InternalVertexTag >

Base class implementing the Union-Find data structure.

The implemented functionnalities are:

Accessors: accessing the vertices of the Union-Find structure and some statistics on the structure.

Modifiers: adding a vertex to the Union-Find structure or clearing the structure related to the container of vertices.

Union-Find Operations: the union and find operations.

Algorithms: methods linking the vertices following different conditions.

Leaders: methods related to the list of leaders of the Union-Find structure.

Independent Set Iterators: iterators over the different independent sets in the Union-Find structure.

Rewind: the possibility to rewind the Union-Find structure to a previous given state.

Template Parameters

T	Type of data. It has to be default constructible.
VertexDS	Data structure of vertex in the Union-Find data structure.
InternalVertexTag	Boolean indicating if vertices are created internally or not.

Member Typedef Documentation

◆ Independent_set_iterator

typedef T_Independent_set_iterator<void> Independent_set_iterator

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

◆ Leaders_iterator

typedef Vertex_list_iterator Leaders_iterator

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

◆ Vertex

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

Constructor & Destructor Documentation

◆ T_Union_find_base()

T_Union_find_base ( void )

inline

Constructs an empty Union-Find data structure.

◆ ~T_Union_find_base()

~T_Union_find_base ( void )

inline

If vertices are created internally, destroy them.

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, VertexDS, InternalVertexTag >::Vertex * const_find_set ( Vertex * v ) const

inline

Const find the leader of the independent set containing v.

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

◆ find_set()

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

inline

Find the leader of the independent set containing v.

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

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.

◆ independent_set_begin()

T_Union_find_base< T, VertexDS, InternalVertexTag >::Independent_set_iterator independent_set_begin ( Vertex * v ) const

inline

Starts the independent set of vertices containing v.

Precondition: v is a leader.

◆ independent_set_end()

T_Union_find_base< T, VertexDS, InternalVertexTag >::Independent_set_iterator independent_set_end ( Vertex * v ) const

inline

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

bool is_leader ( const Vertex * v ) const

inline

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

◆ is_singleton()

bool is_singleton ( const Vertex * v ) const

inline

Check that v is in a singleton.

◆ leaders_begin()

T_Union_find_base< T, VertexDS, InternalVertexTag >::Leaders_iterator leaders_begin ( void )

inline

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

◆ leaders_end()

T_Union_find_base< T, VertexDS, InternalVertexTag >::Leaders_iterator leaders_end ( void )

inline

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

◆ make_set() [1/3]

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

◆ make_set() [2/3]

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

inline

Create a new independent set with the input Vertex.

Returns: The new Vertex.

◆ make_set() [3/3]

T_Union_find_base< T, VertexDS, InternalVertexTag >::Vertex * make_set ( void )

inline

Create a new independent set with one default Vertex.

Precondition: The InternalVertexTag tag is set to true.

Returns: The new Vertex.

◆ operator[]() [1/2]

T_Union_find_base< T, VertexDS, InternalVertexTag >::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_base< T, VertexDS, InternalVertexTag >::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() )

inline

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

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

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
	)

inline

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

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

Classes

Public Types

Constructors

Accessors

Modifiers

Union-Find Operations

Algorithms

Leaders

Independent Set Iterators

Rewind

Detailed Description

template<class T, class VertexDS, bool InternalVertexTag> class SBL::CADS::T_Union_find_base< T, VertexDS, InternalVertexTag >

Member Typedef Documentation

◆ Independent_set_iterator

◆ Leaders_iterator

◆ Vertex

Constructor & Destructor Documentation

◆ T_Union_find_base()

◆ ~T_Union_find_base()

Member Function Documentation

◆ clear()

◆ const_find_set()

◆ find_set()

◆ get_number_of_independent_sets()

◆ get_number_of_vertices()

◆ get_size_of_independent_set()

◆ independent_set_begin()

◆ independent_set_end()

◆ is_empty()

◆ is_leader()

◆ is_singleton()

◆ leaders_begin()

◆ leaders_end()

◆ make_set() [1/3]

◆ make_set() [2/3]

◆ make_set() [3/3]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ quadratic_union()

◆ reset()

◆ rewind_before_make_set()

◆ rewind_before_union_sets()

◆ rewind_to_last_make_set()

◆ rewind_to_last_union_sets()

◆ union_from_edges()

◆ union_sets()

template<class T, class VertexDS, bool InternalVertexTag>
class SBL::CADS::T_Union_find_base< T, VertexDS, InternalVertexTag >