Relation_T< T, Compare > Class Template Reference

#include <tpl_union.H>

Inheritance diagram for Relation_T< T, Compare >:

Collaboration diagram for Relation_T< T, Compare >:

Public Member Functions
bool	are_connected (const T &p, const T &q)
	Retorna true is i y j están conectados.
void	join (const T &p, const T &q)
	Une p con q.
void	set_n (size_t n)
size_t	size () const noexcept
	Return the number of items of set (not of relation)
size_t	get_num_blocks () const noexcept
bool	are_connected (size_t i, size_t j) noexcept
void	join (size_t i, size_t j) noexcept

Protected Member Functions
size_t	depth (size_t i) noexcept

Protected Attributes
DynArray< size_t >	id
DynArray< size_t >	sz
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 integers.

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 but in the practice trends to be .

This implementation is strongly based on java version of Sedgewick and Wayne

See also

Relation Relation_T

Author

Leandro Rabindranath Leon Grafos

Member Function Documentation

are_connected()

bool Fixed_Relation::are_connected ( size_t  i, size_t  j  )

inlinenoexceptinherited

Return true if item i is related to item j.

Note since the relation is symmetric saying that i is related to j is the same thing than saying that j is related to i.

Basically i is related to j if it is possible to reach 'j` from 'i'.

Parameters

[in]	i	an item index
[in]	j	an item index

Returns

true if i is related to j; false otherwise

Here is the caller graph for this function:

get_num_blocks()

size_t Fixed_Relation::get_num_blocks ( ) const

inlinenoexceptinherited

Return the number ob connected blocks, which is the number of equivalence classes

join()

void Fixed_Relation::join ( size_t  i, size_t  j  )

inlinenoexceptinherited

Insert the pair '(i,j)' in the relation. All the reachability state is updated.

Parameters

[in]	i	an item index
[in]	j	an item index

Here is the caller graph for this function:

set_n()

void Fixed_Relation::set_n ( size_t  n )

inlineinherited

Set the number of items of the relation.

The advantage of this method is that it allows to construc A Fixed_relation without need forknowing the number of items. Afterward, when threse are known this number could be set with this method.

Parameters

[in]

n

the number of items.

Exceptions

bad_alloc

if there is no enough memory

Here is the call graph for this function:

---

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

• tpl_union.H