|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Binary relation between a set of integers. More...
#include <tpl_union.H>
Public Member Functions | |
| 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 | |
| void | verify_if_add_new_points (const size_t n) |
| size_t | root (size_t i) override |
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 integers.
This class implements a dynamic relation of equivalence between a set of n integers from 0 until n - 1.
By dynamic is understood that the number of items can grow.
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 238 of file tpl_union.H.
Initialize an empty relation of n elements between [0..n)
Definition at line 264 of file tpl_union.H.
Reimplemented from Fixed_Relation.
Definition at line 256 of file tpl_union.H.
References Fixed_Relation::root(), and verify_if_add_new_points().
Definition at line 240 of file tpl_union.H.
References Fixed_Relation::id, l, Fixed_Relation::num_blocks, Aleph::DynArray< T >::reserve(), Fixed_Relation::size(), and Fixed_Relation::sz.
Referenced by root().