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]\).
double	exp_num_crossings (const graphs::undirected_graph &g) noexcept
	Computes the the expected number of crossings in unconstrained arrangements, \(\mathbb{E}[C]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
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]\).
numeric::rational	moment_degree_rational (const graphs::undirected_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a graph as an exact rational value.
double	moment_degree (const graphs::undirected_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a directed graph as a floating point value.
numeric::rational	moment_degree_rational (const graphs::directed_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a directed graph as an exact rational value.
double	moment_degree (const graphs::directed_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a directed graph as a floating point value.
numeric::rational	moment_degree_in_rational (const graphs::directed_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a directed graph as an exact rational value.
double	moment_degree_in (const graphs::directed_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a directed graph as a floating point value.
numeric::rational	moment_degree_out_rational (const graphs::directed_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of out-degree about zero of a directed graph as an exact rational value.
double	moment_degree_out (const graphs::directed_graph &g, uint32_t p) noexcept
	Computes the \(p\)-th moment of out-degree about zero of a directed graph as a floating point value.
numeric::rational	hubiness_rational (const graphs::free_tree &t) noexcept
	Computes the hubiness coefficient as an exact rational number.
numeric::rational	hubiness_rational (const graphs::rooted_tree &t) noexcept
	Computes the hubiness coefficient as an exact rational number.
double	hubiness (const graphs::free_tree &t) noexcept
	Computes the hubiness coefficient as a floating point value.
double	hubiness (const graphs::rooted_tree &t) noexcept
	Computes the hubiness coefficient as a floating point value.
numeric::rational	mean_hierarchical_distance_rational (const graphs::rooted_tree &t) noexcept
	Mean Hierarchical Distance.
double	mean_hierarchical_distance (const graphs::rooted_tree &t) noexcept
	Mean Hierarchical Distance.
numeric::integer	num_pairs_independent_edges_integer (const graphs::undirected_graph &g) noexcept
	Compute the size of \(Q(G)\).
uint64_t	num_pairs_independent_edges (const graphs::undirected_graph &g) noexcept
	Compute the size of \(Q(G)\).
numeric::integer	num_pairs_independent_edges_integer (const graphs::directed_graph &g) noexcept
	Compute the size of \(Q(G)\).
uint64_t	num_pairs_independent_edges (const graphs::directed_graph &g) noexcept
	Compute the size of \(Q(G)\).
std::pair< node, node >	tree_centre (const graphs::rooted_tree &t) noexcept
	Calculate the centre of a rooted tree.
std::pair< node, node >	tree_centre (const graphs::free_tree &t) noexcept
	Calculate the centre of a free tree.
std::pair< node, node >	tree_centroid (const graphs::rooted_tree &t) noexcept
	Calculate the centroid of a rooted tree.
std::pair< node, node >	tree_centroid (const graphs::free_tree &t) noexcept
	Calculate the centroid of a free tree.
uint32_t	tree_diameter (const graphs::free_tree &t) noexcept
	Calculate the diameter of a free tree.
uint32_t	tree_diameter (const graphs::rooted_tree &t) noexcept
	Calculate the diameter of a free tree.

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.

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]\).

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 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]\).

This function uses the formulae derived in [4].

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

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]\).

This function uses the formulae derived in [4].

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

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 [21].

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 [21].

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 [21].

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 )

noexcept

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 )

noexcept

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 )

noexcept

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 [12] 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 )

noexcept

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 [12] 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.

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.

The mean hierarchical distance is calculated as a mean of the different hierarchical distances between each vertex and the root of the tree. The hierarchical distance \(HD_u\) of vertex \(u\) is calculated as the number of edges between the tree's root and \(u\). The result of this function is the mean of these distances: \(MHD = \frac{1}{n-1} \sum_{u\in V} HD_u\).

For furhter details see [23].

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/2]

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

noexcept

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() [2/2]

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

noexcept

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_in()

double lal::properties::moment_degree_in ( const graphs::directed_graph & g, uint32_t p )

noexcept

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

See lal::properties::moment_degree_in_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_degree_in_rational()

numeric::rational lal::properties::moment_degree_in_rational ( const graphs::directed_graph & g, uint32_t p )

noexcept

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.

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_out()

double lal::properties::moment_degree_out ( const graphs::directed_graph & g, uint32_t p )

noexcept

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

See lal::properties::moment_degree_out_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_degree_out_rational()

numeric::rational lal::properties::moment_degree_out_rational ( const graphs::directed_graph & g, uint32_t p )

noexcept

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.

Parameters

g	Input graph.
p	Moment of degree.

Returns

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

moment_degree_rational() [1/2]

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

noexcept

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, uint32_t p )

noexcept

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.

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.

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.

Here, "centre" should not be confused with "centroid". The center is the set of (at most) two vertices that have minimum eccentricity. The centroid is the set of (at most) two vertices that have minimum weight, where the weight is the maximum size of the subtrees rooted at that vertex. See [19] (pages 35-36) for further details.

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::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.

Here, "centre" should not be confused with "centroid". The center is the set of (at most) two vertices that have minimum eccentricity. The centroid is the set of (at most) two vertices that have minimum weight, where the weight is the maximum size of the subtrees rooted at that vertex. See [19] (pages 35-36) for further details.

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_centroid() [1/2]

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

noexcept

Calculate the centroid of a free tree.

Here, "centre" should not be confused with "centroid". The center is the set of (at most) two vertices that have minimum eccentricity. The centroid is the set of (at most) two vertices that have minimum weight, where the weight is the maximum size of the subtrees rooted at that vertex. See [19] (pages 35-36) for further details.

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.

Here, "centroid" should not be confused with "centre". The centre is the set of (at most) two vertices that have minimum eccentricity. The centroid is the set of (at most) two vertices that have minimum weight, where the weight is the maximum size of the subtrees rooted at that vertex. In both case, if the set has two vertices then they are adjacent in the tree. See [19] (pages 35-36) for further details.

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]

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

noexcept

Calculate the diameter of a free tree.

The diameter is defined as the longest shortest distance between every pair of vertices. The distance is calculated in number of edges; two adjacent vertices are at a distance 1 from each other. See [19] (pages 24, 35) for further details.

Parameters

t	Input tree.

Returns

The diameter of the input tree.

tree_diameter() [2/2]

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

noexcept

Calculate the diameter of a free tree.

The diameter is defined as the longest shortest distance between every pair of vertices. The distance is calculated in number of edges; two adjacent vertices are at a distance 1 from each other. See [19] (pages 24, 35) for further details.

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 [21].

Parameters

g	Input graph.

Returns

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