Relation Class Reference

#include <tpl_union.H>

Inheritance diagram for Relation:

Collaboration diagram for Relation:

Public Member Functions
	Relation (size_t n=0)
	Intialize an empty relation of n elementos between [0..n)
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

Binary relation between a set of integers.

This class implements a dynamic relation of equivalence between a set of n integer from 0 until n - 1.

By static is understood that the number of items can grow.

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