Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
Union_find_default Class Reference

Default Union-Find data structure with no data attached to the vertices.
More...

#include <Union_find.hpp>

Public Types

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

Union-Find Operations

Vertexmake_set (bool data)
 
Vertexmake_set (void)
 Create a new independent set with one default Vertex. More...
 
Vertexmake_set (Vertex *v)
 Creation of a set with a vertex created outside. More...
 
Vertexfind_set (Vertex *u)
 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...
 

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

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

Default Union-Find data structure with no data attached to the vertices.

Default Union-Find data structure with no data attached to the vertices.

Member Typedef Documentation

◆ Independent_set_iterator

typedef T_Independent_set_iterator<void> Independent_set_iterator
inherited

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

◆ Leaders_iterator

typedef Vertex_list_iterator Leaders_iterator
inherited

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

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

Member Function Documentation

◆ clear()

void clear ( void  )
inlineinherited

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

◆ const_find_set()

T_Union_find_base< bool , Union_find_vertex_data_structure_base , 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/2]

Union_find_default::Vertex * find_set ( Vertex u)
inline

Find the leader of the independent set containing v.

◆ find_set() [2/2]

T_Union_find_base< bool , Union_find_vertex_data_structure_base , InternalVertexTag >::Vertex * find_set ( Vertex v)
inlineinherited

Find the leader of the independent set containing v.

◆ get_number_of_independent_sets()

std::size_t get_number_of_independent_sets ( void  ) const
inlineinherited

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
inlineinherited

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
inlineinherited

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

◆ independent_set_begin()

T_Union_find_base< bool , Union_find_vertex_data_structure_base , 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()

T_Union_find_base< bool , Union_find_vertex_data_structure_base , 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
inlineinherited

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

◆ is_leader()

bool is_leader ( const Vertex v) const
inlineinherited

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

◆ is_singleton()

bool is_singleton ( const Vertex v) const
inlineinherited

Check that v is in a singleton.

◆ leaders_begin()

T_Union_find_base< bool , Union_find_vertex_data_structure_base , InternalVertexTag >::Leaders_iterator leaders_begin ( void  )
inlineinherited

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

◆ leaders_end()

T_Union_find_base< bool , Union_find_vertex_data_structure_base , InternalVertexTag >::Leaders_iterator leaders_end ( void  )
inlineinherited

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

◆ make_set() [1/4]

T_Union_find_base< bool , Union_find_vertex_data_structure_base , InternalVertexTag >::Vertex * make_set ( bool  data)
inlineinherited

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

T_Union_find_base< bool , Union_find_vertex_data_structure_base , InternalVertexTag >::Vertex * make_set ( Vertex v)
inlineinherited

Create a new independent set with the input Vertex.

Returns
The new Vertex.

◆ make_set() [3/4]

Union_find_default::Vertex * make_set ( Vertex v)
inline

Creation of a set with a vertex created outside.

◆ make_set() [4/4]

Union_find_default::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< bool , Union_find_vertex_data_structure_base , InternalVertexTag >::Vertex * operator[] ( std::size_t  i)
inlineinherited

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< bool , Union_find_vertex_data_structure_base , InternalVertexTag >::Vertex * operator[] ( std::size_t  i) const
inlineinherited

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
UnionComparatorBinary functor checking that two vertices are in the same independent set

◆ reset()

void reset ( void  )
inlineinherited

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

◆ rewind_before_make_set()

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

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

void rewind_to_last_make_set ( void  )
inlineinherited

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

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
InputIteratorIterator over a set of pairs of vertices.

◆ union_sets() [1/2]

T_Union_find_base< bool , Union_find_vertex_data_structure_base , 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() [2/2]

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