lal::properties Namespace Reference

Namespace for all linear-arrangement-independent algorithms. More...

Functions
numeric::rational	exp_num_crossings_rational (const graphs::undirected_graph &g) noexcept
	Computes the the expected number of crossings in unconstrained arrangements, \(\mathbb{E}[C]\). More...
double	exp_num_crossings (const graphs::undirected_graph &g) noexcept
	Computes the the expected number of crossings in unconstrained arrangements, \(\mathbb{E}[C]\). More...
numeric::rational	var_num_crossings_rational (const graphs::undirected_graph &g, bool reuse=true) noexcept
	Computes the variance of the number of crossings of a graph in unconstrained arrangements, \(\mathbb{V}[C]\). More...
double	var_num_crossings (const graphs::undirected_graph &g, bool reuse=true) noexcept
	Computes the variance of the number of crossings of a graph in unconstrained arrangements, \(\mathbb{V}[C]\). More...
numeric::rational	var_num_crossings_forest_rational (const graphs::undirected_graph &g) noexcept
	Computes the variance of the number of crossings of a forest in unconstrained arrangements, \(\mathbb{V}[C]\). More...
double	var_num_crossings_forest (const graphs::undirected_graph &g) noexcept
	Computes the variance of the number of crossings of a forest in unconstrained arrangements, \(\mathbb{V}[C]\). More...
numeric::rational	var_num_crossings_tree_rational (const graphs::free_tree &t) noexcept
	Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\). More...
double	var_num_crossings_tree (const graphs::free_tree &t) noexcept
	Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\). More...
numeric::rational	var_num_crossings_tree_rational (const graphs::rooted_tree &t) noexcept
	Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\). More...
double	var_num_crossings_tree (const graphs::rooted_tree &t) noexcept
	Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\). More...
numeric::rational	exp_sum_edge_lengths_rational (const graphs::undirected_graph &g) noexcept
	Expected sum of edge lengths of an undirected graph in unconstrained arrangments, \(\mathbb{E}[D]\). More...
double	exp_sum_edge_lengths (const graphs::undirected_graph &g) noexcept
	Expected sum of edge lengths of an undirected graph in unconstrained arrangments, \(\mathbb{E}[D]\). More...
numeric::rational	exp_sum_edge_lengths_rational (const graphs::free_tree &t) noexcept
	Expected sum of edge lengths of a free tree in unconstrained arrangments, \(\mathbb{E}[D]\). More...
double	exp_sum_edge_lengths (const graphs::free_tree &t) noexcept
	Expected sum of edge lengths of a free tree in unconstrained arrangments, \(\mathbb{E}[D]\). More...
numeric::rational	exp_sum_edge_lengths_rational (const graphs::rooted_tree &t) noexcept
	Expected sum of edge lengths of a rooted tree in unconstrained arrangments, \(\mathbb{E}[D]\). More...
double	exp_sum_edge_lengths (const graphs::rooted_tree &t) noexcept
	Expected sum of edge lengths of a rooted tree in unconstrained arrangments, \(\mathbb{E}[D]\). More...
numeric::rational	exp_sum_edge_lengths_projective_rational (const graphs::rooted_tree &rt) noexcept
	Expected sum of edge lengths of a tree constrained to projective arrangments, \(\mathbb{E}_{\mathrm{pr}}[D]\). More...
double	exp_sum_edge_lengths_projective (const graphs::rooted_tree &rt) noexcept
	Expected sum of edge lengths of a tree constrained to projective arrangments, \(\mathbb{E}_{\mathrm{pr}}[D]\). More...
numeric::rational	exp_sum_edge_lengths_planar_rational (const graphs::free_tree &t) noexcept
	Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\). More...
numeric::rational	exp_sum_edge_lengths_planar_rational (const graphs::rooted_tree &rt) noexcept
	Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\). More...
double	exp_sum_edge_lengths_planar (const graphs::free_tree &t) noexcept
	Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\). More...
double	exp_sum_edge_lengths_planar (const graphs::rooted_tree &rt) noexcept
	Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\). More...
numeric::rational	var_sum_edge_lengths_rational (const graphs::undirected_graph &g) noexcept
	Computes the variance of the sum of the length of edges of a graph, \(\mathbb{V}[D]\). More...
double	var_sum_edge_lengths (const graphs::undirected_graph &g) noexcept
	Computes the variance of the sum of the length of edges of a graph, \(\mathbb{V}[D]\). More...
template<class graph_t , class return_type >
return_type	sum_powers_degrees (const graph_t &g, uint64_t p, uint64_t(graph_t::*degree_function)(node) const noexcept) noexcept
	Generic template function for the sum of degrees. More...
numeric::integer	sum_powers_degrees_integer (const graphs::undirected_graph &g, uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power. More...
uint64_t	sum_powers_degrees (const graphs::undirected_graph &g, uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power. More...
numeric::integer	sum_powers_degrees_integer (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power. More...
uint64_t	sum_powers_degrees (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power. More...
numeric::integer	sum_powers_in_degrees_integer (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power. More...
uint64_t	sum_powers_in_degrees (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power. More...
numeric::integer	sum_powers_in_degrees_integer (const graphs::rooted_tree &t, uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power. More...
uint64_t	sum_powers_in_degrees (const graphs::rooted_tree &t, uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power. More...
numeric::integer	sum_powers_out_degrees_integer (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the sum of out-degrees raised to the \(p\)-th power. More...
uint64_t	sum_powers_out_degrees (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the sum of out-degrees raised to the \(p\)-th power. More...
template<class graph_t , class return_type >
return_type	moment_degree (const graph_t &g, uint64_t p, uint64_t(graph_t::*degree_function)(node) const noexcept) noexcept
	Generic template function for the moment of degree about 0. More...
numeric::rational	moment_degree_rational (const graphs::undirected_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a graph as an exact rational value. More...
double	moment_degree (const graphs::undirected_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a directed graph as a floating point value. More...
numeric::rational	moment_degree_rational (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a directed graph as an exact rational value. More...
double	moment_degree (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a directed graph as a floating point value. More...
numeric::rational	moment_in_degree_rational (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a directed graph as an exact rational value. More...
double	moment_in_degree (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a directed graph as a floating point value. More...
numeric::rational	moment_in_degree_rational (const graphs::rooted_tree &t, uint64_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a rooted tree as an exact rational value. More...
double	moment_in_degree (const graphs::rooted_tree &t, uint64_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a directed graph as a floating point value. More...
numeric::rational	moment_out_degree_rational (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of out-degree about zero of a directed graph as an exact rational value. More...
double	moment_out_degree (const graphs::directed_graph &g, uint64_t p) noexcept
	Computes the \(p\)-th moment of out-degree about zero of a directed graph as a floating point value. More...
numeric::rational	hubiness_rational (const graphs::free_tree &t) noexcept
	Computes the hubiness coefficient as an exact rational number. More...
numeric::rational	hubiness_rational (const graphs::rooted_tree &t) noexcept
	Computes the hubiness coefficient as an exact rational number. More...
double	hubiness (const graphs::free_tree &t) noexcept
	Computes the hubiness coefficient as a floating point value. More...
double	hubiness (const graphs::rooted_tree &t) noexcept
	Computes the hubiness coefficient as a floating point value. More...
uint64_t	sum_hierarchical_distances (const graphs::rooted_tree &t) noexcept
	Sum of hierarchical distances (SHD). More...
numeric::rational	mean_hierarchical_distance_rational (const graphs::rooted_tree &t) noexcept
	Mean Hierarchical Distance (MHD). More...
double	mean_hierarchical_distance (const graphs::rooted_tree &t) noexcept
	Mean Hierarchical Distance (MHD). More...
uint64_t	tree_caterpillar_distance (const graphs::free_tree &t) noexcept
	Caterpillar distance of a tree. More...
uint64_t	tree_caterpillar_distance (const graphs::rooted_tree &t) noexcept
	Caterpillar distance of a tree. More...
numeric::integer	num_pairs_independent_edges_integer (const graphs::undirected_graph &g) noexcept
	Compute the size of \(Q(G)\). More...
uint64_t	num_pairs_independent_edges (const graphs::undirected_graph &g) noexcept
	Compute the size of \(Q(G)\). More...
numeric::integer	num_pairs_independent_edges_integer (const graphs::directed_graph &g) noexcept
	Compute the size of \(Q(G)\). More...
uint64_t	num_pairs_independent_edges (const graphs::directed_graph &g) noexcept
	Compute the size of \(Q(G)\). More...
std::pair< node, node >	tree_centre (const graphs::rooted_tree &t) noexcept
	Calculate the centre of a rooted tree. More...
std::pair< node, node >	tree_centre (const graphs::free_tree &t) noexcept
	Calculate the centre of a free tree. More...
std::pair< node, node >	tree_centroid (const graphs::rooted_tree &t) noexcept
	Calculate the centroid of a rooted tree. More...
std::pair< node, node >	tree_centroid (const graphs::free_tree &t) noexcept
	Calculate the centroid of a free tree. More...
uint64_t	tree_diameter (const graphs::free_tree &t) noexcept
	Calculate the diameter of a free tree. More...
uint64_t	tree_diameter (const graphs::rooted_tree &t) noexcept
	Calculate the diameter of a free tree. More...

Detailed Description

Namespace for all linear-arrangement-independent algorithms.

This namespace contains functions to calculate properties of graphs that do not depend, whether implicitly or explicitly, on a linear arrangement. To read more about the concept of linear arrangement see the Linear Arrangement page.

Function Documentation

exp_num_crossings()

double lal::properties::exp_num_crossings ( const graphs::undirected_graph &  g )

inlinenoexcept

Computes the the expected number of crossings in unconstrained arrangements, \(\mathbb{E}[C]\).

See lal::properties::exp_num_crossings_rational for details.

Parameters

g	The input graph.

Returns

The expected value of the number of crossings as a floating point value.

exp_num_crossings_rational()

numeric::rational lal::properties::exp_num_crossings_rational ( const graphs::undirected_graph &  g )

noexcept

Computes the the expected number of crossings in unconstrained arrangements, \(\mathbb{E}[C]\).

Returns \(\mathbb{E}[C]\) as a rational value.

Parameters

g	The input graph.

Returns

The expected value of the number of crossings as a rational value.

exp_sum_edge_lengths() [1/3]

double lal::properties::exp_sum_edge_lengths ( const graphs::free_tree &  t )

inlinenoexcept

Expected sum of edge lengths of a free tree in unconstrained arrangments, \(\mathbb{E}[D]\).

See lal::properties::exp_sum_edge_lengths_rational for details.

Parameters

t	The input free tree.

Returns

The expected value of the sum of edge lengths as a floating point value.

exp_sum_edge_lengths() [2/3]

double lal::properties::exp_sum_edge_lengths ( const graphs::rooted_tree &  t )

inlinenoexcept

Expected sum of edge lengths of a rooted tree in unconstrained arrangments, \(\mathbb{E}[D]\).

See lal::properties::exp_sum_edge_lengths_rational for details.

Parameters

t	The input rooted tree.

Returns

The expected value of the sum of edge lengths as a floating point value.

exp_sum_edge_lengths() [3/3]

double lal::properties::exp_sum_edge_lengths ( const graphs::undirected_graph &  g )

inlinenoexcept

Expected sum of edge lengths of an undirected graph in unconstrained arrangments, \(\mathbb{E}[D]\).

See lal::properties::exp_sum_edge_lengths_rational for details.

Parameters

g	The input graph.

Returns

The expected value of the sum of edge lengths as a floating point value.

exp_sum_edge_lengths_planar() [1/2]

double lal::properties::exp_sum_edge_lengths_planar ( const graphs::free_tree &  t )

inlinenoexcept

Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\).

See lal::properties::exp_sum_edge_lengths_planar_rational for details.

Parameters

t	The input free tree.

Returns

The expected value of the sum of edge lengths constrained to planar arrangements as a floating point value.

Precondition

rt must be a valid free tree (see lal::graphs::free_tree::is_tree).

exp_sum_edge_lengths_planar() [2/2]

double lal::properties::exp_sum_edge_lengths_planar ( const graphs::rooted_tree &  rt )

inlinenoexcept

Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\).

See lal::properties::exp_sum_edge_lengths_planar_rational for details.

Parameters

rt	The input rooted tree.

Returns

The expected value of the sum of edge lengths constrained to planar arrangements as a floating point value.

Precondition

rt must be a valid rooted tree (see lal::graphs::rooted_tree::is_rooted_tree).

exp_sum_edge_lengths_planar_rational() [1/2]

numeric::rational lal::properties::exp_sum_edge_lengths_planar_rational ( const graphs::free_tree &  t )

noexcept

Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\).

This function uses the formulae derived in [4].

Returns the value \(E_{\mathrm{pl}}[D]\) as a rational value.

Parameters

t	The input free tree.

Returns

The expected value of the sum of edge lengths constrained to planar arrangements as an exact rational value.

Precondition

rt must be a valid free tree (see lal::graphs::free_tree::is_tree).

exp_sum_edge_lengths_planar_rational() [2/2]

numeric::rational lal::properties::exp_sum_edge_lengths_planar_rational ( const graphs::rooted_tree &  rt )

inlinenoexcept

Expected sum of edge lengths of a tree constrained to planar arrangments, \(\mathbb{E}_{\mathrm{pl}}[D]\).

Returns the value \(E_{\mathrm{pl}}[D]\) as a rational value.

This function uses the formulae derived in [4].

This function transforms the input rooted tree into a free tree.

Parameters

rt	The input rooted tree.

Returns

The expected value of the sum of edge lengths constrained to planar arrangements as an exact rational value.

Precondition

rt must be a valid rooted tree (see lal::graphs::rooted_tree::is_rooted_tree).

exp_sum_edge_lengths_projective()

double lal::properties::exp_sum_edge_lengths_projective ( const graphs::rooted_tree &  rt )

inlinenoexcept

Expected sum of edge lengths of a tree constrained to projective arrangments, \(\mathbb{E}_{\mathrm{pr}}[D]\).

See lal::properties::exp_sum_edge_lengths_projective_rational for details.

Parameters

rt	The input rooted tree.

Returns

The expected value of the sum of edge lengths constrained to projective arrangements as a floating point value.

Precondition

rt must be a valid rooted tree (see lal::graphs::rooted_tree::is_rooted_tree).

exp_sum_edge_lengths_projective_rational()

numeric::rational lal::properties::exp_sum_edge_lengths_projective_rational ( const graphs::rooted_tree &  rt )

noexcept

Expected sum of edge lengths of a tree constrained to projective arrangments, \(\mathbb{E}_{\mathrm{pr}}[D]\).

This function uses the formulae derived in [5].

Returns the value \(E_{\mathrm{pr}}[D]\) as a rational value.

Parameters

rt	The input rooted tree.

Returns

The expected value of the sum of edge lengths constrained to projective arrangements as an exact rational value.

Precondition

rt must be a valid rooted tree (see lal::graphs::rooted_tree::is_rooted_tree).

exp_sum_edge_lengths_rational() [1/3]

numeric::rational lal::properties::exp_sum_edge_lengths_rational ( const graphs::free_tree &  t )

inlinenoexcept

Expected sum of edge lengths of a free tree in unconstrained arrangments, \(\mathbb{E}[D]\).

This function uses the formulae derived in [17].

Returns the value \(E[D]\) as a rational value.

Parameters

t	The input rooted tree.

Returns

The expected value of the sum of edge lengths as a rational value.

exp_sum_edge_lengths_rational() [2/3]

numeric::rational lal::properties::exp_sum_edge_lengths_rational ( const graphs::rooted_tree &  t )

inlinenoexcept

Expected sum of edge lengths of a rooted tree in unconstrained arrangments, \(\mathbb{E}[D]\).

This function uses the formulae derived in [17].

Returns the value \(E[D]\) as a rational value.

Parameters

t	The input rooted tree.

Returns

The expected value of the sum of edge lengths as a rational value.

exp_sum_edge_lengths_rational() [3/3]

numeric::rational lal::properties::exp_sum_edge_lengths_rational ( const graphs::undirected_graph &  g )

inlinenoexcept

Expected sum of edge lengths of an undirected graph in unconstrained arrangments, \(\mathbb{E}[D]\).

This function uses the formulae derived in [15], [17].

Returns the value \(E[D]\) as a rational value.

Parameters

g	The input graph.

Returns

The expected value of the sum of edge lengths as a rational value.

hubiness() [1/2]

double lal::properties::hubiness ( const graphs::free_tree &  t )

inlinenoexcept

Computes the hubiness coefficient as a floating point value.

See lal::properties::hubiness_rational for details.

Parameters

t	Input free tree.

Returns

The hubiness coefficient as a floating point value.

Precondition

The tree t is a valid tree. Method graphs::free_tree::is_tree returns true.

\(n > 3\).

hubiness() [2/2]

double lal::properties::hubiness ( const graphs::rooted_tree &  t )

inlinenoexcept

Computes the hubiness coefficient as a floating point value.

See lal::properties::hubiness_rational for details.

Parameters

t	Input rooted tree.

Returns

The hubiness coefficient as a floating point value.

Precondition

The tree t is a valid rooted tree. Method graphs::rooted_tree::is_rooted_tree returns true.

\(n > 3\).

hubiness_rational() [1/2]

numeric::rational lal::properties::hubiness_rational ( const graphs::free_tree &  t )

inlinenoexcept

Computes the hubiness coefficient as an exact rational number.

The hubiness coefficient is defined as.

\(h = \frac{ \langle k^2 \rangle - \langle k^2 \rangle_{linear} } { \langle k^2 \rangle_{star} - \langle k^2 \rangle_{linear} }\),

where \(\langle k^2 \rangle_{star}\) and \(\langle k^2 \rangle_{linear}\) are the second moment of degree about 0 (see lal::properties::moment_degree_rational) of a star and linear tree respectively.

See [14] for further details.

Parameters

t	Input free tree.

Returns

The hubiness coefficient as a rational value.

Precondition

The tree t is a valid tree. Method graphs::free_tree::is_tree returns true.

\(n > 3\).

hubiness_rational() [2/2]

numeric::rational lal::properties::hubiness_rational ( const graphs::rooted_tree &  t )

inlinenoexcept

Computes the hubiness coefficient as an exact rational number.

The hubiness coefficient is defined as.

\(h = \frac{ \langle k^2 \rangle - \langle k^2 \rangle_{linear} } { \langle k^2 \rangle_{star} - \langle k^2 \rangle_{linear} }\),

where \(\langle k^2 \rangle_{star}\) and \(\langle k^2 \rangle_{linear}\) are the second moment of degree about 0 (see lal::properties::moment_degree_rational) of a star and linear tree respectively.

See [14] for further details.

Parameters

t	Input rooted tree.

Returns

The hubiness coefficient as a rational value.

Precondition

The tree t is a valid rooted tree. Method graphs::rooted_tree::is_rooted_tree returns true.

\(n > 3\).

mean_hierarchical_distance()

double lal::properties::mean_hierarchical_distance ( const graphs::rooted_tree &  t )

noexcept

Mean Hierarchical Distance (MHD).

See lal::properties::mean_hierarchical_distance_rational for details.

Parameters

t	Input rooted tree.

Returns

The Mean Hierarchical Distance of a rooted tree as a floating point value.

Precondition

The tree t is a valid rooted tree. Method graphs::rooted_tree::is_rooted_tree returns true.

\(n > 1\) (which is the same as \(m > 0\).

mean_hierarchical_distance_rational()

numeric::rational lal::properties::mean_hierarchical_distance_rational ( const graphs::rooted_tree &  t )

noexcept

Mean Hierarchical Distance (MHD).

The hierarchical distance \(HD_u\) of a vertex \(u\) to the root of the tree is calculated as the number of edges between these two vertices. Therefore, the hierarchical distance from a root's child and the root is exactly 1.

The result of this function is the average of such distances: \(MHD = \frac{1}{n-1} \sum_{u\in V} HD_u\).

For furhter details see [25].

Parameters

t	Input rooted tree.

Returns

The Mean Hierarchical Distance of a rooted tree as a rational value.

Precondition

The tree t is a valid rooted tree. Method graphs::rooted_tree::is_rooted_tree returns true.

\(n > 1\) (which is the same as \(m > 0\).

moment_degree() [1/3]

template<class graph_t , class return_type >

return_type lal::properties::moment_degree ( const graph_t &  g, uint64_t  p, uint64_t(graph_t::*)(node) const noexcept  degree_function  )

inlinenoexcept

Generic template function for the moment of degree about 0.

Calculates the \(p\)-th moment of degree about 0, where the degree is given by some function.

Template Parameters

graph_t	Type of graph
return_type	Type of function's result (double, lal::numeric::rational)

Parameters

g	Input graph
p	Power to which degrees must be raised
degree_function	The function that returns the specific degree (full, out, in, or other).

Returns

The \(p\)-th moment of degree about 0.

moment_degree() [2/3]

double lal::properties::moment_degree ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of degree about zero of a directed graph as a floating point value.

See lal::properties::moment_degree_rational for details.

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the degree about 0 as a floating point value.

moment_degree() [3/3]

double lal::properties::moment_degree ( const graphs::undirected_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of degree about zero of a directed graph as a floating point value.

See lal::properties::moment_degree_rational for details.

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the degree about 0 as a floating point value.

moment_degree_rational() [1/2]

numeric::rational lal::properties::moment_degree_rational ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of degree about zero of a directed graph as an exact rational value.

Computes the \(p\)-th moment of degree about zero, \(\langle k^p \rangle\), of a graph using:

\(\langle k^p \rangle = \frac{1}{n} \sum_{i=1}^n k_i^p \).

where \(n\) denotes the number of nodes of the graph and \(k_i\) is the in-degree plus the out-degree of vertex \(i\).

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the in-degree about 0 as a rational value.

moment_degree_rational() [2/2]

numeric::rational lal::properties::moment_degree_rational ( const graphs::undirected_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of degree about zero of a graph as an exact rational value.

Computes the \(p\)-th moment of degree about zero, \(\langle k^p \rangle\), of a graph using:

\(\langle k^p \rangle = \frac{1}{n} \sum_{i=1}^n k_i^p \).

where \(n\) denotes the number of nodes of the graph and \(k_i\) is the degree of vertex \(i\).

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the in-degree about 0 as a rational value.

moment_in_degree() [1/2]

double lal::properties::moment_in_degree ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of in-degree about zero of a directed graph as a floating point value.

See lal::properties::moment_in_degree_rational for details.

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the in-degree about 0 as a floating point value.

moment_in_degree() [2/2]

double lal::properties::moment_in_degree ( const graphs::rooted_tree &  t, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of in-degree about zero of a directed graph as a floating point value.

See lal::properties::moment_in_degree_rational for details.

Parameters

t	Input rooted tree.
p	Moment of degree.

Returns

The \(p\)-th moment of the in-degree about 0 as a floating point value.

Precondition

Tree t is a valid rooted tree.

moment_in_degree_rational() [1/2]

numeric::rational lal::properties::moment_in_degree_rational ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of in-degree about zero of a directed graph as an exact rational value.

Computes the \(p\)-th moment of in-degree about zero, \(\langle k_{in}^p \rangle\), of a directed graph using:

\(\langle k_{in}^p \rangle = \frac{1}{n} \sum_{i=1}^n k_{in, i}^p \).

where \(n\) denotes the number of nodes of the graph and \(k_{in, i}\) is the in-degree of vertex \(i\).

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the in-degree about 0 as a rational value.

moment_in_degree_rational() [2/2]

numeric::rational lal::properties::moment_in_degree_rational ( const graphs::rooted_tree &  t, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of in-degree about zero of a rooted tree as an exact rational value.

Computes the \(p\)-th moment of in-degree about zero, \(\langle k_{in}^p \rangle\), of a rooted tree using:

\(\langle k_{in}^p \rangle = \frac{1}{n} \sum_{i=1}^n k_{in, i}^p \).

where \(n\) denotes the number of nodes of the tree. In this case, this value is trivially independent of the moment \(p\),

\(\langle k_{in}^p \rangle = \frac{n - 1}{n}\).

Parameters

t	Input rooted tree.
p	Moment of degree.

Returns

The \(p\)-th moment of the in-degree about 0 as a rational value.

Precondition

Tree t is a valid rooted tree.

moment_out_degree()

double lal::properties::moment_out_degree ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of out-degree about zero of a directed graph as a floating point value.

See lal::properties::moment_out_degree_rational for details.

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the out-degree about 0 as a floating point value.

moment_out_degree_rational()

numeric::rational lal::properties::moment_out_degree_rational ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the \(p\)-th moment of out-degree about zero of a directed graph as an exact rational value.

Computes the \(p\)-th moment of out-degree about zero, \(\langle k_{out}^p \rangle\), of a directed graph using:

\(\langle k_{out}^p \rangle = \frac{1}{n} \sum_{i=1}^n k_{out, i}^p \).

where \(n\) denotes the number of nodes of the graph and \(k_{out, i}\) is the out-degree of vertex \(i\).

Parameters

g	Input graph.
p	Moment of degree.

Returns

The \(p\)-th moment of the out-degree about 0 as a rational value.

num_pairs_independent_edges() [1/2]

uint64_t lal::properties::num_pairs_independent_edges ( const graphs::directed_graph &  g )

inlinenoexcept

Compute the size of \(Q(G)\).

See lal::properties::num_pairs_independent_edges_integer for details.

Parameters

g	Input graph.

Returns

The size of \(Q(G)\) as a 64-bit integer.

num_pairs_independent_edges() [2/2]

uint64_t lal::properties::num_pairs_independent_edges ( const graphs::undirected_graph &  g )

inlinenoexcept

Compute the size of \(Q(G)\).

See lal::properties::num_pairs_independent_edges_integer for details.

Parameters

g	Input graph.

Returns

The size of \(Q(G)\) as a 64-bit integer.

num_pairs_independent_edges_integer() [1/2]

numeric::integer lal::properties::num_pairs_independent_edges_integer ( const graphs::directed_graph &  g )

noexcept

Compute the size of \(Q(G)\).

The set \(Q(G)\) of a graph \(G\) is the set of pairs of independent edges. Two edges are said to be independent if they do not share vertices. Therefore, this function returns the amount of independent edges of this directed graph.

Parameters

g	Input graph.

Returns

The size of \(Q(G)\) as an integer of arbitrary precision.

num_pairs_independent_edges_integer() [2/2]

numeric::integer lal::properties::num_pairs_independent_edges_integer ( const graphs::undirected_graph &  g )

noexcept

Compute the size of \(Q(G)\).

The set \(Q(G)\) of a graph \(G\) is the set of pairs of independent edges. Two edges are said to be independent if they do not share vertices. Therefore, this function returns the amount of independent edges of this undirected graph.

Parameters

g	Input graph.

Returns

The size of \(Q(G)\) as an integer of arbitrary precision.

sum_hierarchical_distances()

uint64_t lal::properties::sum_hierarchical_distances ( const graphs::rooted_tree &  t )

noexcept

Sum of hierarchical distances (SHD).

The hierarchical distance \(HD_u\) of a vertex \(u\) to the root of the tree is calculated as the number of edges between these two vertices. Therefore, the hierarchical distance from a root's child and the root is exactly 1.

The result of this function is the sum of such distances: \(SHD = \sum_{u\in V} HD_u\).

For furhter details see [25].

Parameters

t	Input rooted tree.

Returns

The sum of hierarchical distances of a rooted tree.

Precondition

The tree t is a valid rooted tree. Method graphs::rooted_tree::is_rooted_tree returns true.

sum_powers_degrees() [1/3]

template<class graph_t , class return_type >

return_type lal::properties::sum_powers_degrees ( const graph_t &  g, uint64_t  p, uint64_t(graph_t::*)(node) const noexcept  degree_function  )

inlinenoexcept

Generic template function for the sum of degrees.

Each degree is raised to a certain power according to the parameter.

Template Parameters

graph_t	Type of graph.
return_type	Type of function's result (uint64_t, lal::numeric::integer)

Parameters

g	Input graph
p	Power to which degrees must be raised
degree_function	The function that returns the specific degree (in+out, out, in, or other).

Returns

The sum of degrees raised to the input power p.

sum_powers_degrees() [2/3]

uint64_t lal::properties::sum_powers_degrees ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of degrees raised to the \(p\)-th power.

Computes the sum of degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_i^p\).

where \(n\) denotes the number of nodes of the graph and \(k_i\) is the degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of in-degrees raised to the \(p\)-th power.

sum_powers_degrees() [3/3]

uint64_t lal::properties::sum_powers_degrees ( const graphs::undirected_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of degrees raised to the \(p\)-th power.

Computes the sum of degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_i^p\).

where \(n\) denotes the number of nodes of the graph and \(k_i\) is the degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of degrees raised to the \(p\)-th power.

sum_powers_degrees_integer() [1/2]

numeric::integer lal::properties::sum_powers_degrees_integer ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of degrees raised to the \(p\)-th power.

Computes the sum of degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_i^p\).

where \(n\) denotes the number of nodes of the graph and \(k_i\) is the degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of degrees raised to the \(p\)-th power.

sum_powers_degrees_integer() [2/2]

numeric::integer lal::properties::sum_powers_degrees_integer ( const graphs::undirected_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of degrees raised to the \(p\)-th power.

Computes the sum of degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_i^p\).

where \(n\) denotes the number of nodes of the graph and \(k_i\) is the degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of degrees raised to the \(p\)-th power.

sum_powers_in_degrees() [1/2]

uint64_t lal::properties::sum_powers_in_degrees ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of in-degrees raised to the \(p\)-th power.

Computes the sum of in-degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_{in, i}^p\).

where \(n\) denotes the number of nodes of the graph and \(k_{in, i}\) is the in-degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of in-degrees raised to the \(p\)-th power.

sum_powers_in_degrees() [2/2]

uint64_t lal::properties::sum_powers_in_degrees ( const graphs::rooted_tree &  t, uint64_t  p  )

inlinenoexcept

Computes the sum of in-degrees raised to the \(p\)-th power.

Computes the sum of in-degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_{in, i}^p\).

where \(n\) denotes the number of nodes of the graph and \(k_{in, i}\) is the in-degree of vertex \(i\).

Parameters

t	Input tree.
p	Power of degree.

Returns

The sum of in-degrees raised to the \(p\)-th power.

Precondition

Tree t is a valid rooted tree.

sum_powers_in_degrees_integer() [1/2]

numeric::integer lal::properties::sum_powers_in_degrees_integer ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of in-degrees raised to the \(p\)-th power.

Computes the sum of in-degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_{in, i}^p\).

where \(n\) denotes the number of nodes of the graph and \(k_{in, i}\) is the in-degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of in-degrees raised to the \(p\)-th power.

sum_powers_in_degrees_integer() [2/2]

numeric::integer lal::properties::sum_powers_in_degrees_integer ( const graphs::rooted_tree &  t, uint64_t  p  )

inlinenoexcept

Computes the sum of in-degrees raised to the \(p\)-th power.

Computes the sum of in-degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_{in, i}^p\).

where \(n\) denotes the number of nodes of the graph and \(k_{in, i}\) is the in-degree of vertex \(i\).

Parameters

t	Input tree.
p	Power of degree.

Returns

The sum of in-degrees raised to the \(p\)-th power.

Precondition

Tree t is a valid rooted tree.

sum_powers_out_degrees()

uint64_t lal::properties::sum_powers_out_degrees ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of out-degrees raised to the \(p\)-th power.

Computes the sum of out-degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_{out, i}^p\).

where \(n\) denotes the number of nodes of the graph and \(k_{out, i}\) is the out-degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of in-degrees raised to the \(p\)-th power.

sum_powers_out_degrees_integer()

numeric::integer lal::properties::sum_powers_out_degrees_integer ( const graphs::directed_graph &  g, uint64_t  p  )

inlinenoexcept

Computes the sum of out-degrees raised to the \(p\)-th power.

Computes the sum of out-degrees raised to the \(p\)-th power using

\(K^p = \sum_{i=1}^n k_{out, i}^p\).

where \(n\) denotes the number of nodes of the graph and \(k_{out, i}\) is the out-degree of vertex \(i\).

Parameters

g	Input graph.
p	Power of degree.

Returns

The sum of out-degrees raised to the \(p\)-th power.

tree_caterpillar_distance() [1/2]

uint64_t lal::properties::tree_caterpillar_distance ( const graphs::free_tree &  t )

noexcept

Caterpillar distance of a tree.

The caterpillar distance of a given tree is defined as the minimum amount of vertices to be removed from the tree so that the result is a caterpillar tree. See page The different types of trees for a definition of caterpillar tree.

Parameters

t	Input free tree.

Returns

A positive integer value, the caterpillar distance of the input tree.

tree_caterpillar_distance() [2/2]

uint64_t lal::properties::tree_caterpillar_distance ( const graphs::rooted_tree &  t )

noexcept

Caterpillar distance of a tree.

The caterpillar distance of a given tree is defined as the minimum amount of vertices to be removed from the tree so that the result is a caterpillar tree. See page The different types of trees for a definition of caterpillar tree.

Parameters

t	Input free tree.

Returns

A positive integer value, the caterpillar distance of the input tree.

tree_centre() [1/2]

std::pair< node, node > lal::properties::tree_centre ( const graphs::free_tree &  t )

noexcept

Calculate the centre of a free tree.

See Centre and centroid of a tree for details on the centre and centroid of a tree.

Parameters

t	Input tree.

Returns

A tuple of the two nodes in the centre. If the tree has a single central node, only the first node is valid and the second is assigned an invalid vertex index. It is guaranteed that the first vertex has smaller index value than the second.

Precondition

The tree t is a valid rooted tree. Method graphs::free_tree::is_tree returns true.

tree_centre() [2/2]

std::pair< node, node > lal::properties::tree_centre ( const graphs::rooted_tree &  t )

noexcept

Calculate the centre of a rooted tree.

See Centre and centroid of a tree for details on the centre and centroid of a tree.

Parameters

t	Input tree.

Returns

A tuple of the two nodes in the centre. If the tree has a single central node, only the first node is valid and the second is assigned an invalid vertex index. It is guaranteed that the first vertex has smaller index value than the second.

Precondition

The tree t is a valid rooted tree. Method graphs::rooted_tree::is_rooted_tree returns true.

tree_centroid() [1/2]

std::pair< node, node > lal::properties::tree_centroid ( const graphs::free_tree &  t )

noexcept

Calculate the centroid of a free tree.

See Centre and centroid of a tree for details on what the centroid of a tree is.

Parameters

t	Input tree.

Returns

A tuple of two values: the nodes in the centre. If the tree has a single central node, only the first node is valid and the second is assigned an invalid vertex index. It is guaranteed that the first vertex has smaller index value than the second.

Precondition

The tree t is a valid free tree. Method graphs::free_tree::is_tree returns true.

tree_centroid() [2/2]

std::pair< node, node > lal::properties::tree_centroid ( const graphs::rooted_tree &  t )

noexcept

Calculate the centroid of a rooted tree.

See Centre and centroid of a tree for details on what the centroid of a tree is.

Parameters

t	Input tree.

Returns

A tuple of two values: the nodes in the centre. If the tree has a single central node, only the first node is valid and the second is assigned an invalid vertex index. It is guaranteed that the first vertex has smaller index value than the second.

Precondition

The tree t is a valid rooted tree. Method graphs::rooted_tree::is_rooted_tree returns true.

tree_diameter() [1/2]

uint64_t lal::properties::tree_diameter ( const graphs::free_tree &  t )

noexcept

Calculate the diameter of a free tree.

See Diameter of a tree for details on the definition of the diameter of a tree.

Parameters

t	Input tree.

Returns

The diameter of the input tree.

tree_diameter() [2/2]

uint64_t lal::properties::tree_diameter ( const graphs::rooted_tree &  t )

noexcept

Calculate the diameter of a free tree.

See Diameter of a tree for details on the definition of the diameter of a tree.

Parameters

t	Input tree.

Returns

The diameter of the input tree.

var_num_crossings()

double lal::properties::var_num_crossings ( const graphs::undirected_graph &  g, bool  reuse = true  )

inlinenoexcept

Computes the variance of the number of crossings of a graph in unconstrained arrangements, \(\mathbb{V}[C]\).

See lal::properties::var_num_crossings_rational for details.

Parameters

g	Input graph.
reuse	The algorithm will reuse computations in order to compute the variance faster. Note: this might be too memory-consuming.

Returns

The exact value of \(V_{rla}[C]\) as a rationafloating point value.

var_num_crossings_forest()

double lal::properties::var_num_crossings_forest ( const graphs::undirected_graph &  g )

inlinenoexcept

Computes the variance of the number of crossings of a forest in unconstrained arrangements, \(\mathbb{V}[C]\).

See lal::properties::var_num_crossings_forest_rational for details.

Parameters

g	Input forest.

Returns

The exact value of \(V_{rla}[C]\) as a floating point value.

var_num_crossings_forest_rational()

numeric::rational lal::properties::var_num_crossings_forest_rational ( const graphs::undirected_graph &  g )

noexcept

Computes the variance of the number of crossings of a forest in unconstrained arrangements, \(\mathbb{V}[C]\).

Computes \(\mathbb{V}[C]\) on the given forest. This function implements the algorithm in [3] for forests, which stems from the study in [2].

Complexity: time \(O(n)\), space \(O(n)\).

Parameters

g	Input forest.

Returns

The exact value of \(V_{rla}[C]\) as a rational value.

Precondition

The input graph g is a forest.

var_num_crossings_rational()

numeric::rational lal::properties::var_num_crossings_rational ( const graphs::undirected_graph &  g, bool  reuse = true  )

noexcept

Computes the variance of the number of crossings of a graph in unconstrained arrangements, \(\mathbb{V}[C]\).

Computes \(\mathbb{V}[C]\) on the given graph. This function implements the algorithm in [3] for general graphs, which stems from the study in [2].

Since there are many computations that can be resued, setting reuse to 'true' can help speed up the algorithm. Warning: reusing memory might be too memory-consuming for large graphs (handle with care).

Parameters

g	Input graph.
reuse	The algorithm will reuse computations in order to compute the variance faster. Note: this might be too memory-consuming.

Returns

The exact value of \(V_{rla}[C]\) as a rational value.

var_num_crossings_tree() [1/2]

double lal::properties::var_num_crossings_tree ( const graphs::free_tree &  t )

inlinenoexcept

Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\).

See lal::properties::var_num_crossings_tree_rational for details.

Parameters

t	Input free tree.

Returns

The return value is a floating point value.

var_num_crossings_tree() [2/2]

double lal::properties::var_num_crossings_tree ( const graphs::rooted_tree &  t )

inlinenoexcept

Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\).

This function converts the input rooted tree into a free tree.

See lal::properties::var_num_crossings_tree_rational for details.

Parameters

t	Input rooted tree.

Returns

The return value is a floating point value.

var_num_crossings_tree_rational() [1/2]

numeric::rational lal::properties::var_num_crossings_tree_rational ( const graphs::free_tree &  t )

inlinenoexcept

Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\).

Computes \(\mathbb{V}[C]\) on the given tree. This function computes the simplified formula of \(V_{rla}[C]\) on general graphs for the case of trees. Complexity: time \(O(n)\), space \(O(n)\).

Parameters

t	Input free tree.

Returns

The exact value of \(V_{rla}[C]\) as a rational value.

var_num_crossings_tree_rational() [2/2]

numeric::rational lal::properties::var_num_crossings_tree_rational ( const graphs::rooted_tree &  t )

inlinenoexcept

Computes the variance of the number of crossings of a tree in unconstrained arrangements, \(\mathbb{V}[C]\).

This function converts the input rooted tree into a free tree.

Computes \(\mathbb{V}[C]\) on the given tree. This function computes the simplified formula of \(V_{rla}[C]\) on general graphs for the case of trees. Complexity: time \(O(n)\), space \(O(n)\).

Parameters

t	Input rooted tree.

Returns

The exact value of \(V_{rla}[C]\) as a rational value.

var_sum_edge_lengths()

double lal::properties::var_sum_edge_lengths ( const graphs::undirected_graph &  g )

inlinenoexcept

Computes the variance of the sum of the length of edges of a graph, \(\mathbb{V}[D]\).

See lal::properties::var_sum_edge_lengths_rational for details.

Parameters

g	The input graph.

Returns

The exact value of \(V[D]\) as a floating point value.

var_sum_edge_lengths_rational()

numeric::rational lal::properties::var_sum_edge_lengths_rational ( const graphs::undirected_graph &  g )

noexcept

Computes the variance of the sum of the length of edges of a graph, \(\mathbb{V}[D]\).

Computes the variance of the sum of edge lengths over all \(n!\) arrangements.

This function uses the formula derived in [17].

Parameters

g	Input graph.

Returns

The exact value of \(V[D]\) as a rational value.