Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Relation Class Reference

Binary relation between a set of integers. More...

#include <tpl_union.H>

Inheritance diagram for Relation:
[legend]
Collaboration diagram for Relation:
[legend]

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_tid
 
DynArray< size_tsz
 
size_t num_blocks
 

Detailed Description

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

See also
Relation Relation_T
Author
Leandro Rabindranath Leon

Definition at line 238 of file tpl_union.H.

Constructor & Destructor Documentation

◆ Relation()

Relation::Relation ( const size_t  n = 0)
inline

Initialize an empty relation of n elements between [0..n)

Definition at line 264 of file tpl_union.H.

Member Function Documentation

◆ root()

size_t Relation::root ( size_t  i)
inlineoverrideprivatevirtual

Reimplemented from Fixed_Relation.

Definition at line 256 of file tpl_union.H.

References Fixed_Relation::root(), and verify_if_add_new_points().

◆ verify_if_add_new_points()

void Relation::verify_if_add_new_points ( const size_t  n)
inlineprivate

The documentation for this class was generated from the following file: