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

Constructors
	T_Union_find_base (void)
	Constructs an empty Union-Find data structure.
	~T_Union_find_base (void)
	If vertices are created internally, destroy them.

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 (void)
	Create a new independent set with one default Vertex.
Vertex *	make_set (T data)
	Create a new independent set with one Vertex initialized with the input data.
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
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.
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).

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

template<class T, class VertexDS, bool InternalVertexTag>

typedef T_Independent_set_iterator<void> Independent_set_iterator

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

◆ Leaders_iterator

template<class T, class VertexDS, bool InternalVertexTag>

typedef Vertex_list_iterator Leaders_iterator

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

◆ Vertex

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

T_Union_find_base ( void )

inline

Constructs an empty Union-Find data structure.

◆ ~T_Union_find_base()

template<class T, class VertexDS, bool InternalVertexTag>

~T_Union_find_base ( void )

inline

If vertices are created internally, destroy them.

Member Function Documentation

◆ clear()

template<class T, class VertexDS, bool InternalVertexTag>

void clear ( void )

inline

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

◆ const_find_set()

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

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, class VertexDS, bool InternalVertexTag>

std::size_t get_number_of_vertices ( void ) const

inline

Number of vertices in the Union-Find data structure.

◆ get_size_of_independent_set()

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

bool is_empty ( void ) const

inline

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

◆ is_leader()

template<class T, class VertexDS, bool InternalVertexTag>

bool is_leader ( const Vertex * v ) const

inline

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

◆ is_singleton()

template<class T, class VertexDS, bool InternalVertexTag>

bool is_singleton ( const Vertex * v ) const

inline

Check that v is in a singleton.

◆ leaders_begin()

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

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]

template<class T, class VertexDS, bool InternalVertexTag>

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]

template<class T, class VertexDS, bool InternalVertexTag>

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]

template<class T, class VertexDS, bool InternalVertexTag>

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]

template<class T, class VertexDS, bool InternalVertexTag>

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]

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

template<class UnionComparator>

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

template<class T, class VertexDS, bool InternalVertexTag>

void reset ( void )

inline

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

◆ rewind_before_make_set()

template<class T, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

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, class VertexDS, bool InternalVertexTag>

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, class VertexDS, bool InternalVertexTag>

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

template<class T, class VertexDS, bool InternalVertexTag>

template<class InputIterator>

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

template<class T, class VertexDS, bool InternalVertexTag>

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

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