Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Union_find_base< T, VertexDS, InternalVertexTag > Class Template Reference

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 T_Union_find_base< T, VertexDS, InternalVertexTag > Self
 
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...
 
Vertexoperator[] (std::size_t i)
 Access to the ith inserted vertex in the Union-Find data structrure. More...
 
const Vertexoperator[] (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

Vertexfind_vertex (Vertex *v) const
 
Vertexmake_set (void)
 Create a new independent set with one default Vertex. More...
 
Vertexmake_set (T data)
 Create a new independent set with one Vertex initialized with the input data. More...
 
Vertexmake_set (Vertex *v)
 Create a new independent set with the input Vertex. More...
 
Vertexconst_find_set (Vertex *v) const
 Const find the leader of the independent set containing v. More...
 
Vertexfind_set (Vertex *v)
 Find the leader of the independent set containing v. More...
 
Vertexunion_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
TType of data. It has to be default constructible.
VertexDSData structure of vertex in the Union-Find data structure.
InternalVertexTagBoolean 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.

◆ Self

typedef T_Union_find_base<T, VertexDS, InternalVertexTag> Self

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

◆ find_vertex()

T_Union_find_base< T, VertexDS, InternalVertexTag >::Vertex * find_vertex ( Vertex v) const
inline

◆ 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 ( 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
UnionComparatorBinary 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
InputIteratorIterator 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.