|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Binary relation between a set of items. More...
#include <tpl_union.H>
Classes | |
| struct | Cmp |
| struct | Pair |
Public Member Functions | |
| bool | are_connected (const T &p, const T &q) |
| Return true if p and q are connected; inserts missing items into the relation. | |
| void | join (const T &p, const T &q) |
| Join p with q; inserts missing items into the relation. | |
Public Member Functions inherited from Relation | |
| Relation (const size_t n=0) | |
| Initialize an empty relation of n elements between [0..n) | |
Public Member Functions inherited from Fixed_Relation | |
| virtual | ~Fixed_Relation ()=default |
| Fixed_Relation (const size_t n=0) | |
| Initialize an empty binary relation of integers between 0 and n - 1. | |
| void | set_n (size_t n) |
| Set the number of items of the relation. | |
| size_t | size () const noexcept |
| Return the number of items of the set (not of relation) | |
| constexpr size_t | get_num_blocks () const noexcept |
| Return the number of connected blocks, which is the number of equivalence classes. | |
| bool | are_connected (size_t i, size_t j) |
Return true if item i is related to item j. | |
| void | join (size_t i, size_t j) |
| Insert the pair '(i,j)' in the relation. | |
Private Member Functions | |
| size_t | test_and_insert_new_item (const T &item) |
Private Attributes | |
| DynSetAvlTree< Pair, Cmp > | items_tree |
Additional Inherited Members | |
Protected Member Functions inherited from Fixed_Relation | |
| void | verify_index (const size_t i) const |
| size_t | depth (size_t i) const |
Protected Attributes inherited from Fixed_Relation | |
| DynArray< size_t > | id |
| DynArray< size_t > | sz |
| size_t | num_blocks |
Binary relation between a set of items.
This class implements a dynamic relation of equivalence between a set of n different items of type T
The used algorithm is the quick weighted fast union which is very fast, bounded by \(O(\lg n)\) but in the practice trends to be \(O(1)\).
This implementation is strongly based on java version of Sedgewick and Wayne
Definition at line 285 of file tpl_union.H.
Return true if p and q are connected; inserts missing items into the relation.
Definition at line 326 of file tpl_union.H.
References Fixed_Relation::are_connected(), and Relation_T< T, Compare >::test_and_insert_new_item().
Join p with q; inserts missing items into the relation.
Definition at line 335 of file tpl_union.H.
References Fixed_Relation::join(), and Relation_T< T, Compare >::test_and_insert_new_item().
|
inlineprivate |
Definition at line 311 of file tpl_union.H.
References Fixed_Relation::are_connected(), Relation_T< T, Compare >::Pair::i, Relation_T< T, Compare >::items_tree, Aleph::maps(), and Fixed_Relation::size().
Referenced by Relation_T< T, Compare >::are_connected(), and Relation_T< T, Compare >::join().
|
private |
Definition at line 308 of file tpl_union.H.
Referenced by Relation_T< T, Compare >::test_and_insert_new_item().