Set of utilities. More...

Functions
template<typename result_t , bool second_set_empty, typename iterator_first_t , typename iterator_second_t , class metric , class accumulate_Q , class accumulate_R , class make_average_Q , class make_average_R , class make_average >
result_t	one_level_aggregation (iterator_first_t bfirst, const iterator_first_t efirst, iterator_second_t bsecond, const iterator_second_t esecond, metric values, accumulate_Q accQ, accumulate_R accR, make_average_Q avgQ, make_average_R avgR, make_average avg) noexcept
	Computation of 1-level aggregation of \(Q\) and \(R\). More...

template<typename result_t , bool second_set_empty, typename iterator_first_t , typename iterator_second_t , class metric , class combine , class accumulate , class make_average >
result_t	two_level_aggregation (iterator_first_t bfirst, const iterator_first_t efirst, iterator_second_t bsecond, const iterator_second_t esecond, metric values, combine comb_values, accumulate acc_values, make_average avg) noexcept
	Computation of 2-level aggregation of \(Q\) and \(R\). More...

bool	are_trees_isomorphic (const graphs::rooted_tree &t1, const graphs::rooted_tree &t2) noexcept
	Isomorphism test for unlabelled rooted trees. More...

bool	are_trees_isomorphic (const graphs::free_tree &t1, const graphs::free_tree &t2) noexcept
	Isomorphism test for unlabelled free trees. More...

Detailed Description

Set of utilities.

This namespace contains several utilities for the library, useful for experimentation. This includes the following functions:

Isomorphism tests. For free trees (see lal::utilities::are_trees_isomorphic(const lal::graphs::free_tree&,const lal::graphs::free_tree&)) and for rooted trees (see lal::utilities::are_trees_isomorphic(const lal::graphs::rooted_tree&,const graphs::rooted_tree&)).

Function Documentation

◆ are_trees_isomorphic() [1/2]

bool lal::utilities::are_trees_isomorphic	(	const graphs::free_tree &	t1,
		const graphs::free_tree &	t2
	)

noexcept

Isomorphism test for unlabelled free trees.

See Isomorphism of trees for a short definition of what tree isomorphism is.

The algorithm implemented in this function can be found in [1].

Parameters

t1	Input free tree.
t2	Input free tree.

Returns: Whether or not the input trees are isomorphic.

Precondition: Both input trees are valid free trees (see lal::graphs::free_tree::is_tree).

◆ are_trees_isomorphic() [2/2]

bool lal::utilities::are_trees_isomorphic	(	const graphs::rooted_tree &	t1,
		const graphs::rooted_tree &	t2
	)

noexcept

Isomorphism test for unlabelled rooted trees.

See Isomorphism of trees for a short definition of what tree isomorphism is.

The algorithm implemented in this function can be found in [1].

Parameters

t1	Input rooted tree.
t2	Input rooted tree.

Returns: Whether or not the input trees are isomorphic or not.

Precondition: Both input trees are valid rooted trees (see lal::graphs::rooted_tree::is_rooted_tree).

◆ one_level_aggregation()

template<typename result_t , bool second_set_empty, typename iterator_first_t , typename iterator_second_t , class metric , class accumulate_Q , class accumulate_R , class make_average_Q , class make_average_R , class make_average >

result_t lal::utilities::one_level_aggregation	(	iterator_first_t	bfirst,
		const iterator_first_t	efirst,
		iterator_second_t	bsecond,
		const iterator_second_t	esecond,
		metric	values,
		accumulate_Q	accQ,
		accumulate_R	accR,
		make_average_Q	avgQ,
		make_average_R	avgR,
		make_average	avg
	)

noexcept

Computation of 1-level aggregation of \(Q\) and \(R\).

Given

a list of \(n\) values \(Q_i\) and \(n\) values \(R_i\) (produced by the function values),
an 'accumulator' operator \(\oplus\) for \(Q_i\) (parameter accQ),
an 'accumulator' operator \(\otimes\) for \(R_i\) (parameter accR),
a \(Q\)-average function \(F_Q\) (parameter avgQ),
a \(R\)-average function \(F_R\) (parameter avgR),
and a combination operator \(\odot\) (parameter avg),

this function computes the following average

\(A_1(Q,R) = \left( F_Q\left( \bigoplus_{i=1}^n Q_i \right) \right) \odot \left( F_R\left( \bigotimes_{i=1}^n R_i \right) \right)\)

The values \(Q_i\) and \(R_i\) are obtained from applying function QR passed as parameter. This function iterates over two sets of elements, where the second is optional and may be empty; this must be known at compile time through the template parameter second_set_empty. These sets are passed with iterators (parameters bfirst, efirst, bsecond, esecond).

If the second set is empty then function QR only has one parameter of the same type as the values in the first set. If the second set is not empty then QR has two parameters: the first parameter is of the same type as the elements in the first set, and the second parameter is of the same type as the elements in the second set. In the latter case, QR is called with the i-th element in the first set and the i-th element in the second set.

The function that average the values \(Q_i\), function avgQ, (resp. \(R_i\), function avgR) has two parameters: the summation of the values \(Q_i\) (resp. \(R_i\)) and the total amount of values.

See the implementation of function lal::linarr::mean_dependency_distance_1level_rational and its documentation for an example of usage of this function.

Template Parameters

result_t	The type of the result of this function.
second_set_empty	Is the second set of elements empty?
iterator_first_t	Iterator type.
iterator_second_t	Iterator type.
metric	Function type.
accumulate_Q	Function type.
accumulate_R	Function type.
make_average_Q	Function type.
make_average_R	Function type.
make_average	Function type.

Parameters

bfirst	Iterator at the beginning of the first set.
efirst	Iterator at the end of the first set.
bsecond	Iterator at the beginning of the second set.
esecond	Iterator at the end of the second set.
values	Function to calculate the values \(Q_i,R_i\) called with the \(i\)-th element in the first set only (if second_set_empty is true) or called with the \(i\)-th elements in the first and second sets (if second_set_empty is false). Implements \(\odot\).
accQ	Operator \(\oplus\). A function that accumulates the values \(Q_i\). It has two parameters: the total accumulated value (passed by reference), and the value to be accumulated.
accR	Operator \(\otimes\). A function that accumulates the values \(R_i\). It has two parameters: the total accumulated value (passed by reference), and the value to be accumulated.
avgQ	Function \(F_Q\) that averages the values \(Q_i\). It has two parameters: the accumulation of the values \(Q_i\) and the total amount of values.
avgR	Function \(F_R\) that averages the values \(R_i\). It has two parameters: the accumulation of the values \(R_i\) and the total amount of values.
avg	Operator \(\odot\). A function that is passed the result of \(F_Q\) and \(F_R\).

Precondition: If the second set of elements is empty then second_set_empty must be true. It must be false otherwise.

Returns: \(A_1(Q,R)\).

◆ two_level_aggregation()

template<typename result_t , bool second_set_empty, typename iterator_first_t , typename iterator_second_t , class metric , class combine , class accumulate , class make_average >

result_t lal::utilities::two_level_aggregation	(	iterator_first_t	bfirst,
		const iterator_first_t	efirst,
		iterator_second_t	bsecond,
		const iterator_second_t	esecond,
		metric	values,
		combine	comb_values,
		accumulate	acc_values,
		make_average	avg
	)

noexcept

Computation of 2-level aggregation of \(Q\) and \(R\).

Given

a list of \(n\) values \(Q_i\) and \(n\) values \(R_i\) (produced by the function values),
and a combination operator \(\oplus\) to operator two values \(Q_i\) and \(R_i\) (parameter comb_values),
an 'accumulator' operator \(\otimes\) for \(Q_i\oplus R_i\) (parameter acc_values),
a function \(F\) to average the result of \(\otimes\) (parameter avg),

this function computes the following average

\(A_2(Q,R) = F\left( \bigotimes_{i=1}^n (Q_i\oplus R_i) \right)\)

The values \(Q_i\) and \(R_i\) are obtained from applying function values passed as parameter. This function iterates over two sets of elements, where the second is optional and may be empty; this must be known at compile time through the template parameter second_set_empty. These sets are passed with iterators (parameters bfirst, efirst, bsecond, esecond).

If the second set is empty then function values only has one parameter of the same type as the values in the first set. If the second set is not empty then values has two parameters: the first parameter is of the same type as the elements in the first set, and the second parameter is of the same type as the elements in the second set. In the latter case, values is called with the i-th element in the first set and the i-th element in the second set.

See the implementation of function lal::linarr::mean_dependency_distance_2level_rational and its documentation for an example of usage of this function.

Note: this function can be extended to more values than just \(Q\) and \(R\) by implementing the functions accordingly: QR can return a structure with several values, function comb_values should accept said structure and combine the values accordingly, ...

Template Parameters

result_t	The type of the result of this function.
second_set_empty	Is the second set of elements empty?
iterator_first_t	Iterator type.
iterator_second_t	Iterator type.
metric	Function type.
combine	Function type.
accumulate	Function type.
make_average	Function type.

Parameters

bfirst	Iterator at the beginning of the first set.
efirst	Iterator at the end of the first set.
bsecond	Iterator at the beginning of the second set.
esecond	Iterator at the end of the second set.
values	Function to calculate the values \(Q_i,R_i\) called with the \(i\)-th element in the first set only (if second_set_empty is true) or called with the \(i\)-th elements in the first and second sets (if second_set_empty is false).
comb_values	Operator \(\oplus\). Function that combines two values \(Q_i\) and \(R_i\).
acc_values	Operator \(\otimes\). Function that accumulates the combination of two values \(Q_i\) and \(R_i\).
avg	Function \(F\) that averages the result of \(\otimes\). It is passed the result of \(\otimes\) and the total amount of elements.

Precondition: If the second set of elements is empty then second_set_empty must be true. It must be false otherwise.

Returns: \(A_2(Q,R)\).

Functions

Detailed Description

Function Documentation

◆ are_trees_isomorphic() [1/2]

◆ are_trees_isomorphic() [2/2]

◆ one_level_aggregation()

◆ two_level_aggregation()