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

#include <tpl_union.H>

Inheritance diagram for Fixed_Relation:

Collaboration diagram for Fixed_Relation:

Public Member Functions
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.

Protected Member Functions
void	verify_index (const size_t i) const

virtual size_t	root (size_t i)

size_t	depth (size_t i) const

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 static relation of equivalence between a set of n integers from 0 until n - 1.

By static is understood that the number of items cannot change.

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 81 of file tpl_union.H.

Constructor & Destructor Documentation

◆ ~Fixed_Relation()

virtual Fixed_Relation::~Fixed_Relation ( )

virtualdefault

◆ Fixed_Relation()

Fixed_Relation::Fixed_Relation ( const size_t n = 0 )

inline

Initialize an empty binary relation of integers between 0 and n - 1.

Definition at line 127 of file tpl_union.H.

References id, num_blocks, Aleph::DynArray< T >::reserve(), and sz.

Member Function Documentation

◆ are_connected()

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

inline

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

Definition at line 187 of file tpl_union.H.

References root().

Referenced by Relation_T< T, Compare >::are_connected(), demo_basic_operations(), demo_kruskal_simulation(), demo_path_compression(), PercolationSystem::is_full(), PercolationSystem::percolates(), and Relation_T< T, Compare >::test_and_insert_new_item().

◆ depth()

size_t Fixed_Relation::depth ( size_t i ) const

inlineprotected

Definition at line 105 of file tpl_union.H.

References ah_logic_error_if, id, size(), and verify_index().

◆ get_num_blocks()

constexpr size_t Fixed_Relation::get_num_blocks ( ) const

inlineconstexprnoexcept

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

Definition at line 173 of file tpl_union.H.

References num_blocks.

Referenced by demo_basic_operations(), demo_path_compression(), and Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().

◆ join()

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

inline

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

Definition at line 198 of file tpl_union.H.

References id, num_blocks, root(), and sz.

Referenced by demo_basic_operations(), demo_kruskal_simulation(), demo_path_compression(), Relation_T< T, Compare >::join(), PercolationSystem::open(), and Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().

◆ root()

virtual size_t Fixed_Relation::root ( size_t i )

inlineprotectedvirtual

Reimplemented in Relation.

Definition at line 93 of file tpl_union.H.

References id, and verify_index().

Referenced by are_connected(), join(), and Relation::root().

◆ set_n()

void Fixed_Relation::set_n ( size_t n )

inline

Set the number of items of the relation.

The advantage of this method is that it allows constructing a Fixed_Relation without needing to know the number of items. Afterward, when these are known, this number could be set with this method.

Parameters

[in] n the number of items.

Exceptions

bad_alloc if there is not enough memory

Definition at line 151 of file tpl_union.H.

References Aleph::DynArray< T >::empty(), id, num_blocks, Aleph::DynArray< T >::reserve(), and sz.