lal::utilities Namespace Reference

Set of utilities. More...

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

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.

Decides whether the input trees are isomorphic or not. Two trees \(t_1\) and \(t_2\) (or graphs in general) are isomorphic if there exists a mapping \(\phi \;:\; V(t_1) \longrightarrow V(t_2)\) such that

\(\forall u,v\in V(t_1) \; uv\in E(t_1) \longleftrightarrow \phi(u)\phi(v)\in E(t_2)\)

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

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.

Decides whether the input trees are isomorphic or not. Two trees \(t_1\) and \(t_2\) (or graphs in general) are isomorphic if there exists a mapping \(\phi \;:\; V(t_1) \longrightarrow V(t_2)\) such that

\(\forall u,v\in V(t_1) \; (u,v)\in E(t_1) \longleftrightarrow (\phi(u),\phi(v))\in E(t_2)\)

and \(\phi(r_1)=r_2\) where \(r_1\) and \(r_2\) are, respectively, the roots of \(t_1\) and \(t_2\). Note that \((u,v)\) denotes a directed edge.

The algorithm implemented 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).