lal::properties Namespace Reference

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

Classes
class	bipartite_graph_coloring
	A class to represent a coloring of the vertices of a bipartite graph. More...
class	branchless_path
	Branchless paths in trees. More...
class	connected_components
	The connected components of a graph. More...

Functions
bipartite_graph_coloring	bipartite_coloring (const graphs::undirected_graph &g) noexcept
	Calculates the coloring of a bipartite graph.
bipartite_graph_coloring	bipartite_coloring (const graphs::directed_graph &g) noexcept
	Calculates the coloring of a bipartite graph.
bool	is_graph_bipartite (const graphs::undirected_graph &g, const bipartite_graph_coloring &c) noexcept
	Is a graph bipartite?
bool	is_graph_bipartite (const graphs::undirected_graph &g) noexcept
	Is a graph bipartite?
bool	is_graph_bipartite (const graphs::directed_graph &g, const bipartite_graph_coloring &c) noexcept
	Is a graph bipartite?
bool	is_graph_bipartite (const graphs::directed_graph &g) noexcept
	Is a graph bipartite?
std::vector< branchless_path >	branchless_paths_compute (const graphs::free_tree &t) noexcept
	Finds all branchless paths in a tree.
std::vector< branchless_path >	branchless_paths_compute (const graphs::rooted_tree &t) noexcept
	Finds all branchless paths in a tree.
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, const 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, const 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]\).
connected_components< graphs::undirected_graph >	connected_components_compute (const graphs::undirected_graph &g) noexcept
	Compute the connected components of an undirected graph.
connected_components< graphs::directed_graph >	connected_components_compute (const graphs::directed_graph &g) noexcept
	Compute the connected components of a directed graph.
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_bipartite_rational (const graphs::undirected_graph &g) noexcept
	Expected sum of edge lengths of a bipartite graph in bipartite arrangments, \(\mathbb{E}_{\mathrm{bip}}[D]\).
double	exp_sum_edge_lengths_bipartite (const graphs::undirected_graph &g) noexcept
	Expected sum of edge lengths of a bipartite graph in bipartite arrangments, \(\mathbb{E}_{\mathrm{bip}}[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]\).
template<class graph_t , class return_type >
return_type	sum_powers_degrees (const graph_t &g, const uint64_t p, uint64_t(graph_t::*degree_function)(node) const noexcept) noexcept
	Generic template function for the sum of degrees.
numeric::integer	sum_powers_degrees_integer (const graphs::undirected_graph &g, const uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power.
uint64_t	sum_powers_degrees (const graphs::undirected_graph &g, const uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power.
numeric::integer	sum_powers_degrees_integer (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power.
uint64_t	sum_powers_degrees (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the sum of degrees raised to the \(p\)-th power.
numeric::integer	sum_powers_in_degrees_integer (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power.
uint64_t	sum_powers_in_degrees (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power.
numeric::integer	sum_powers_in_degrees_integer (const graphs::rooted_tree &t, const uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power.
uint64_t	sum_powers_in_degrees (const graphs::rooted_tree &t, const uint64_t p) noexcept
	Computes the sum of in-degrees raised to the \(p\)-th power.
numeric::integer	sum_powers_out_degrees_integer (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the sum of out-degrees raised to the \(p\)-th power.
uint64_t	sum_powers_out_degrees (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the sum of out-degrees raised to the \(p\)-th power.
template<class graph_t , class return_type >
return_type	moment_degree (const graph_t &g, const uint64_t p, uint64_t(graph_t::*degree_function)(node) const noexcept) noexcept
	Generic template function for the moment of degree about 0.
numeric::rational	moment_degree_rational (const graphs::undirected_graph &g, const uint64_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, const uint64_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, const uint64_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, const uint64_t p) noexcept
	Computes the \(p\)-th moment of degree about zero of a directed graph as a floating point value.
numeric::rational	moment_in_degree_rational (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a directed graph as an exact rational value.
double	moment_in_degree (const graphs::directed_graph &g, const uint64_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_in_degree_rational (const graphs::rooted_tree &t, const uint64_t p) noexcept
	Computes the \(p\)-th moment of in-degree about zero of a rooted tree as an exact rational value.
double	moment_in_degree (const graphs::rooted_tree &t, const uint64_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_out_degree_rational (const graphs::directed_graph &g, const uint64_t p) noexcept
	Computes the \(p\)-th moment of out-degree about zero of a directed graph as an exact rational value.
double	moment_out_degree (const graphs::directed_graph &g, const uint64_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.
uint64_t	sum_hierarchical_distances (const graphs::rooted_tree &t) noexcept
	Sum of hierarchical distances (SHD).
numeric::rational	mean_hierarchical_distance_rational (const graphs::rooted_tree &t) noexcept
	Mean Hierarchical Distance (MHD).
double	mean_hierarchical_distance (const graphs::rooted_tree &t) noexcept
	Mean Hierarchical Distance (MHD).
uint64_t	tree_caterpillar_distance (const graphs::free_tree &t) noexcept
	Caterpillar distance of a tree.
uint64_t	tree_caterpillar_distance (const graphs::rooted_tree &t) noexcept
	Caterpillar distance of a tree.
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.
uint64_t	tree_diameter (const graphs::free_tree &t) noexcept
	Calculate the diameter of a free tree.
uint64_t	tree_diameter (const graphs::rooted_tree &t) noexcept
	Calculate the diameter of a free tree.
std::vector< std::vector< node > >	vertex_orbits_compute (const graphs::free_tree &t) noexcept
	Construct the set of vertex orbits of a 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. To read more about the concept of linear arrangement see the Linear Arrangement page.

Function Documentation

bipartite_coloring() [1/2]

bipartite_graph_coloring lal::properties::bipartite_coloring ( const graphs::directed_graph & g )

nodiscardnoexcept

Calculates the coloring of a bipartite graph.

This function converts the input directed graph into an undirected graph (see lal::graphs::directed_graph::to_undirected()).

Parameters

g	Input directed graph.

Returns

An object of type lal::properties::bipartite_graph_coloring.

Precondition

The underlying undirected graph must be bipartite.

bipartite_coloring() [2/2]

bipartite_graph_coloring lal::properties::bipartite_coloring ( const graphs::undirected_graph & g )

nodiscardnoexcept

Calculates the coloring of a bipartite graph.

Parameters

g	Input undirected graph.

Returns

An object of type lal::properties::bipartite_graph_coloring.

Precondition

The graph must be bipartite.

branchless_paths_compute() [1/2]

std::vector< branchless_path > lal::properties::branchless_paths_compute ( const graphs::free_tree & t )

nodiscardnoexcept

Finds all branchless paths in a tree.

Parameters

t	Input tree.

Returns

The list of branchless paths.

branchless_paths_compute() [2/2]

std::vector< branchless_path > lal::properties::branchless_paths_compute ( const graphs::rooted_tree & t )

nodiscardnoexcept

Finds all branchless paths in a tree.

Parameters

t	Input tree.

Returns

The list of branchless paths.

connected_components_compute() [1/2]

connected_components< graphs::directed_graph > lal::properties::connected_components_compute ( const graphs::directed_graph & g )

nodiscardnoexcept

Compute the connected components of a directed graph.

Parameters

g	Input directed graph.

Returns

An object containing all connected components.

connected_components_compute() [2/2]

connected_components< graphs::undirected_graph > lal::properties::connected_components_compute ( const graphs::undirected_graph & g )

nodiscardnoexcept

Compute the connected components of an undirected graph.

Parameters

g	Input undirected graph.

Returns

An object containing all connected components.

exp_num_crossings()

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

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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

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

inlinenodiscardnoexcept

Expected sum of edge lengths of a bipartite graph in bipartite arrangments, \(\mathbb{E}_{\mathrm{bip}}[D]\).

See Types of arrangements for the definition of bipartite arrangement.

This function uses the formula in [10].

Parameters

g	The input bipartite graph.

Returns

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

Precondition

Input graph g is a bipartite arrangement.

exp_sum_edge_lengths_bipartite_rational()

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

inlinenodiscardnoexcept

Expected sum of edge lengths of a bipartite graph in bipartite arrangments, \(\mathbb{E}_{\mathrm{bip}}[D]\).

See Types of arrangements for the definition of bipartite arrangement.

This function uses the formula in [10].

Parameters

g	The input bipartite graph.

Returns

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

Precondition

Input graph g is a bipartite arrangement.

exp_sum_edge_lengths_planar() [1/2]

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

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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 )

inlinenodiscardnoexcept

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

This function uses the formulae derived in [23].

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 )

inlinenodiscardnoexcept

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

This function uses the formulae derived in [23].

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 )

inlinenodiscardnoexcept

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

This function uses the formulae derived in [21], [23].

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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

inlinenodiscardnoexcept

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

is_graph_bipartite() [1/4]

bool lal::properties::is_graph_bipartite ( const graphs::directed_graph & g )

nodiscardnoexcept

Is a graph bipartite?

Parameters

g	Input directed graph.

Returns

Whether or not the input graph is bipartite.

is_graph_bipartite() [2/4]

bool lal::properties::is_graph_bipartite ( const graphs::directed_graph & g, const bipartite_graph_coloring & c )

nodiscardnoexcept

Is a graph bipartite?

Parameters

g	Input directed graph.
c	Coloring of the input graph.

Returns

Whether or not the input graph is bipartite.

is_graph_bipartite() [3/4]

bool lal::properties::is_graph_bipartite ( const graphs::undirected_graph & g )

nodiscardnoexcept

Is a graph bipartite?

Parameters

g	Input undirected graph.

Returns

Whether or not the input graph is bipartite.

is_graph_bipartite() [4/4]

bool lal::properties::is_graph_bipartite ( const graphs::undirected_graph & g, const bipartite_graph_coloring & c )

nodiscardnoexcept

Is a graph bipartite?

Parameters

g	Input undirected graph.
c	Coloring of the input graph.

Returns

Whether or not the input graph is bipartite.

mean_hierarchical_distance()

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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

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, const uint64_t p, uint64_t(graph_t::* degree_function )(node) const noexcept )

nodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const 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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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

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, const uint64_t p, uint64_t(graph_t::* degree_function )(node) const noexcept )

nodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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, const uint64_t p )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 lal::graphs::free_tree::is_tree returns true.

tree_centroid() [2/2]

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

nodiscardnoexcept

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 lal::graphs::rooted_tree::is_rooted_tree returns true.

tree_diameter() [1/2]

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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, const bool reuse = true )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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, const bool reuse = true )

nodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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

Parameters

g	Input graph.

Returns

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

vertex_orbits_compute()

std::vector< std::vector< node > > lal::properties::vertex_orbits_compute ( const graphs::free_tree & t )

nodiscardnoexcept

Construct the set of vertex orbits of a tree.

This function implements an algorithm of time complexity \(O(n^2)\), where \(n\) is the number of vertices of the tree. In the future, the linear-time algorithm in [16] may be implemented.

Parameters

t	The input free tree.

Returns

A vector, each with a list of vertices that belong to the same orbit.