Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
|
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 | |
Vertex * | make_set (bool data) |
Vertex * | make_set (void) |
Create a new independent set with one default Vertex. More... | |
Vertex * | make_set (Vertex *v) |
Creation of a set with a vertex created outside. More... | |
Vertex * | find_set (Vertex *u) |
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... | |
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 (bool 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 | |
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... | |
Default Union-Find data structure with no data attached to the vertices.
Default Union-Find data structure with no data attached to the vertices.
|
inherited |
Iterator type over the independent set of a Union-Find Vertex.
|
inherited |
Iterator type over all the leaders of the Union-Find data structure.
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().
|
inlineinherited |
Remove all the vertices in the Union-Find data structure.
|
inlineinherited |
Const find the leader of the independent set containing v.
Contrarily to the non const method, there is no path compression.
|
inline |
Find the leader of the independent set containing v.
|
inlineinherited |
Find the leader of the independent set containing v.
|
inlineinherited |
Access to the number of independent sets in the Union-Find data structure.
|
inlineinherited |
Number of vertices in the Union-Find data structure.
|
inlineinherited |
Access to the size of an independent set containing a Union-Find Vertex.
|
inlineinherited |
Starts the independent set of vertices containing v.
|
inlineinherited |
Ends the independent set of vertices containing v.
|
inlineinherited |
Check that there is no Vertex in the Union-Find data structure.
|
inlineinherited |
Check that v is a leader in the Union-Find data structure.
|
inlineinherited |
Check that v is in a singleton.
|
inlineinherited |
Starts the set of leaders of the Union-Find data structure.
|
inlineinherited |
Ends the set of leaders of the Union-Find data structure.
|
inlineinherited |
Create a new independent set with one Vertex initialized with the input data.
|
inlineinherited |
Create a new independent set with the input Vertex.
|
inline |
Creation of a set with a vertex created outside.
|
inline |
Create a new independent set with one default Vertex.
|
inlineinherited |
Access to the ith inserted vertex in the Union-Find data structrure.
|
inlineinherited |
Const access to the ith inserted vertex in the Union-Find data structrure.
|
inlineinherited |
Reset the Union-Find data structure and union all the vertices that are in the same independent set related to a given comparator.
UnionComparator | Binary functor checking that two vertices are in the same independent set |
|
inlineinherited |
Separate all the vertices in the Union-Find data structure.
|
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 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.
|
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.
|
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.
|
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).
InputIterator | Iterator over a set of pairs of vertices. |
|
inlineinherited |
Merge the (possibly different) independent sets containing u and v.
|
inline |
Merge the (possibly different) independent sets containing u and v.