Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Relation_T< T, Compare > Class Template Reference

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

#include <tpl_union.H>

Inheritance diagram for Relation_T< T, Compare >:
[legend]
Collaboration diagram for Relation_T< T, Compare >:
[legend]

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

Detailed Description

template<typename T, class Compare = Aleph::less<T>>
class Relation_T< T, Compare >

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

See also
Relation Relation_T
Author
Leandro Rabindranath Leon

Definition at line 285 of file tpl_union.H.

Member Function Documentation

◆ are_connected()

template<typename T , class Compare = Aleph::less<T>>
bool Relation_T< T, Compare >::are_connected ( const T p,
const T q 
)
inline

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

template<typename T , class Compare = Aleph::less<T>>
void Relation_T< T, Compare >::join ( const T p,
const T q 
)
inline

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

◆ test_and_insert_new_item()

template<typename T , class Compare = Aleph::less<T>>
size_t Relation_T< T, Compare >::test_and_insert_new_item ( const T item)
inlineprivate

Member Data Documentation

◆ items_tree

template<typename T , class Compare = Aleph::less<T>>
DynSetAvlTree<Pair, Cmp> Relation_T< T, Compare >::items_tree
private

Definition at line 308 of file tpl_union.H.

Referenced by Relation_T< T, Compare >::test_and_insert_new_item().


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