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

Classes
class	dependency_flux
	Dependency flux. More...

Enumerations
enum class	algorithms_C { brute_force , dynamic_programming , ladder , stack_based }
	The different algorithms for computing the number of crossings. More...

enum class	algorithms_Dmin { Shiloach , Chung_2 }
	The different algorithms for computing the minimum sum of the length of the edges \(D\). More...

enum class	algorithms_Dmin_planar { AlemanyEstebanFerrer , HochbergStallmann }
	The different algorithms for computing the minimum sum of the length of the edges \(D\) in planar arrangements of free trees. More...

enum class	algorithms_Dmin_projective { AlemanyEstebanFerrer , HochbergStallmann }
	The different algorithms for computing the minimum sum of the length of the edges \(D\) in projective arrangements of rooted trees. More...

enum class	syntactic_dependency_structure { EC1 , planar , projective , WG1 , unknown }
	The different types of syntactic dependency tree structures. More...

Functions
template<class graph_t >
numeric::rational	mean_dependency_distance_1level_rational (const std::vector< graph_t > &L, const std::vector< linear_arrangement > &P={}) noexcept
	1-level Mean Dependency Distance \(MDD\) over an ensemble of graphs. More...

template<class graph_t >
double	mean_dependency_distance_1level (const std::vector< graph_t > &L, const std::vector< linear_arrangement > &P={}) noexcept
	1-level Mean Dependency Distance \(MDD\) over an ensemble of graphs. More...

template<class graph_t >
numeric::rational	mean_dependency_distance_2level_rational (const std::vector< graph_t > &L, const std::vector< linear_arrangement > &P={}) noexcept
	2-level Mean Dependency Distance \(MDD\) over an ensemble of graphs. More...

template<class graph_t >
double	mean_dependency_distance_2level (const std::vector< graph_t > &L, const std::vector< linear_arrangement > &P={}) noexcept
	2-level Mean Dependency Distance \(MDD\) over an ensemble of graphs. More...

uint64_t	num_crossings (const graphs::directed_graph &G, const algorithms_C &A=algorithms_C::ladder) noexcept
	Computes the number of edge crossings in a linear arrangement. More...

uint64_t	num_crossings (const graphs::undirected_graph &G, const algorithms_C &A=algorithms_C::ladder) noexcept
	Computes the number of edge crossings in a linear arrangement. More...

uint64_t	num_crossings (const graphs::directed_graph &G, const linear_arrangement &arr, const algorithms_C &A=algorithms_C::ladder) noexcept
	Computes the number of edge crossings in a linear arrangement. More...

uint64_t	num_crossings (const graphs::undirected_graph &G, const linear_arrangement &arr, const algorithms_C &A=algorithms_C::ladder) noexcept
	Computes the number of edge crossings in a linear arrangement. More...

std::vector< uint64_t >	num_crossings_list (const graphs::directed_graph &G, const std::vector< linear_arrangement > &arrs, const algorithms_C &A=algorithms_C::ladder) noexcept
	Computes the number of edge crossings in a linear arrangement. More...

std::vector< uint64_t >	num_crossings_list (const graphs::undirected_graph &G, const std::vector< linear_arrangement > &arrs, const algorithms_C &A=algorithms_C::ladder) noexcept
	Computes the number of edge crossings in a linear arrangement. More...

uint64_t	is_num_crossings_lesseq_than (const graphs::directed_graph &G, uint64_t upper_bound, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

uint64_t	is_num_crossings_lesseq_than (const graphs::undirected_graph &G, uint64_t upper_bound, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

uint64_t	is_num_crossings_lesseq_than (const graphs::directed_graph &G, const linear_arrangement &arr, uint64_t upper_bound, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

uint64_t	is_num_crossings_lesseq_than (const graphs::undirected_graph &G, const linear_arrangement &arr, uint64_t upper_bound, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

std::vector< uint64_t >	is_num_crossings_lesseq_than_list (const graphs::directed_graph &G, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

std::vector< uint64_t >	is_num_crossings_lesseq_than_list (const graphs::undirected_graph &G, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

std::vector< uint64_t >	is_num_crossings_lesseq_than_list (const graphs::directed_graph &G, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

std::vector< uint64_t >	is_num_crossings_lesseq_than_list (const graphs::undirected_graph &G, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds, const algorithms_C &A=algorithms_C::ladder) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...

numeric::rational	predicted_num_crossings_rational (const graphs::undirected_graph &g, const linear_arrangement &arr={}) noexcept
	Predicts the number of crossings. More...

numeric::rational	predicted_num_crossings_rational (const graphs::directed_graph &g, const linear_arrangement &arr={}) noexcept
	Predicts the number of crossings. More...

double	predicted_num_crossings (const graphs::undirected_graph &g, const linear_arrangement &arr={}) noexcept
	Approximates the number of crossings. More...

double	predicted_num_crossings (const graphs::directed_graph &g, const linear_arrangement &arr={}) noexcept
	Approximates the number of crossings. More...

std::array< bool, __syntactic_dependency_structure_size >	syntactic_dependency_structure_class (const graphs::rooted_tree &t, uint64_t C, const linear_arrangement &pi={}) noexcept
	Computes the type of syntactic dependency tree. More...

std::array< bool, __syntactic_dependency_structure_size >	syntactic_dependency_structure_class (const graphs::rooted_tree &t, const linear_arrangement &pi={}) noexcept
	Computes the type of syntactic dependency tree. More...

uint64_t	sum_edge_lengths (const graphs::directed_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the sum of the length of the edges in a linear arrangement. More...

uint64_t	sum_edge_lengths (const graphs::undirected_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the sum of the length of the edges in a linear arrangement. More...

numeric::rational	mean_dependency_distance_rational (const graphs::directed_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the mean dependency distance \(MDD\) as an exact rational value. More...

numeric::rational	mean_dependency_distance_rational (const graphs::undirected_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the mean dependency distance \(MDD\) as an exact rational value. More...

double	mean_dependency_distance (const graphs::directed_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the mean dependency distance \(MDD\) as a floating point value. More...

double	mean_dependency_distance (const graphs::undirected_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the mean dependency distance \(MDD\) as a floating point value. More...

std::vector< dependency_flux >	compute_flux (const graphs::free_tree &t, const linear_arrangement &pi={}) noexcept
	Computes the flux of a dependency tree. More...

std::vector< dependency_flux >	compute_flux (const graphs::rooted_tree &t, const linear_arrangement &pi={}) noexcept
	Computes the flux of a dependency tree. More...

std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_planar (const graphs::free_tree &t) noexcept
	Computes the maximum value of \(D\) in trees under the planarity constraint. More...

std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_planar (const graphs::rooted_tree &t) noexcept
	Computes the maximum value of \(D\) in trees under the planarity constraint. More...

std::pair< std::vector< uint64_t >, node >	max_sum_edge_lengths_projective_roots (const graphs::free_tree &t) noexcept
	Computes the maximum value of \(D\) in trees under the projectivity constraint at every vertex of the tree. More...

std::pair< std::vector< uint64_t >, node >	max_sum_edge_lengths_projective_roots (const graphs::rooted_tree &t) noexcept
	Computes the maximum value of \(D\) in trees under the projectivity constraint at every vertex of the tree. More...

std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_projective (const graphs::rooted_tree &t) noexcept
	Computes the maximum value of \(D\) in rooted trees under the projectivity constraint. More...

std::pair< uint64_t, linear_arrangement >	min_sum_edge_lengths (const graphs::free_tree &t, const algorithms_Dmin &a=algorithms_Dmin::Shiloach) noexcept
	Computes the minimum value of \(D\) in free trees. More...

std::pair< uint64_t, linear_arrangement >	min_sum_edge_lengths (const graphs::rooted_tree &t, const algorithms_Dmin &a=algorithms_Dmin::Shiloach) noexcept
	Computes the minimum value of \(D\) in trees. More...

std::pair< uint64_t, linear_arrangement >	min_sum_edge_lengths_planar (const graphs::free_tree &t, const algorithms_Dmin_planar &a=algorithms_Dmin_planar::AlemanyEstebanFerrer) noexcept
	Computes the minimum value of \(D\) in trees under the planarity constraint. More...

std::pair< uint64_t, linear_arrangement >	min_sum_edge_lengths_planar (const graphs::rooted_tree &t, const algorithms_Dmin_planar &a=algorithms_Dmin_planar::AlemanyEstebanFerrer) noexcept
	Computes the minimum value of \(D\) in trees under the planarity constraint. More...

std::pair< uint64_t, linear_arrangement >	min_sum_edge_lengths_projective (const graphs::rooted_tree &t, const algorithms_Dmin_projective &a=algorithms_Dmin_projective::AlemanyEstebanFerrer) noexcept
	Computes the minimum value of \(D\) in rooted trees under the projectivity constraint. More...

bool	is_permutation (const linear_arrangement &arr={}) noexcept
	Is a given input arrangement a permutation? More...

template<class graph_t >
bool	is_arrangement (const graph_t &g, const linear_arrangement &arr) noexcept
	Is a given arrangement valid? More...

template<class graph_t >
bool	is_planar (const graph_t &g, const linear_arrangement &arr={}) noexcept
	Is a given arrangement planar? More...

bool	is_root_covered (const graphs::rooted_tree &rt, const linear_arrangement &arr) noexcept
	Is the root of a rooted tree covered in a given arrangement? More...

bool	is_projective (const graphs::rooted_tree &rt, const linear_arrangement &arr) noexcept
	Is a given arrangement projective? More...

numeric::rational	head_initial_rational (const graphs::directed_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the headedness of a directed graph as an exact rational number. More...

double	head_initial (const graphs::directed_graph &g, const linear_arrangement &pi={}) noexcept
	Computes the headedness of a linearly arranged directed graph. More...

Variables
constexpr std::size_t	__syntactic_dependency_structure_size
	Number of elements within enumeration syntactic_dependency_structure.

Detailed Description

Namespace for all linear-arrangement-dependent algorithms.

This namespace contains functions to calculate properties of graphs that depend on a linear arrangement. Said arrangement van be given explicitly, i.e., by constructing a lal::linear_arrangement object, or by omitting it in the functions to let these use the labelling of the graph (to read more about the concept of linear arrangement see the Linear Arrangement page). For example, given a graph

lal::graphs::undirected_graph g;

lal::graphs::undirected_graph

Undirected graph class.

Definition: undirected_graph.hpp:67

we can calculate the sum of length of the edges using function lal::linarr::sum_edge_lengths in two different ways. The first is by omitting the arrangement:

lal::linarr::sum_edge_lengths(g);

lal::linarr::sum_edge_lengths

uint64_t sum_edge_lengths(const graphs::directed_graph &g, const linear_arrangement &pi={}) noexcept

Computes the sum of the length of the edges in a linear arrangement.

or by giving one explicitly

lal::linarr::sum_edge_lengths(g, {...});

Enumeration Type Documentation

◆ algorithms_C

enum class lal::linarr::algorithms_C

strong

The different algorithms for computing the number of crossings.

Two edges \(\{s,t\},\{u,v\}\) of a graph \(G\) cross in a linear arrangement \(\pi\) of its nodes if, and only if, their positions interleave in the linear arrangement. More formally, given an arrangement \(\pi\) of a graph \(G\), the edges \(\{s,t\},\{u,v\}\) cros iff \(\pi(s) < \pi(u) < \pi(t) < \pi(v)\) .

Enumerator
brute_force	Brute force computation of the number of crossings. Complexity: time \(O(m^2)\), space \(O(1)\).
dynamic_programming	Dynamic programming algorithm [8]. Complexity: time \(O(n^2)\), space \(O(n^2)\).
ladder	Dynamic programming algorithm [8]. Complexity: time \(O(n^2)\), space \(O(n)\).
stack_based	Algorithm based on sorting [8]. Complexity: time \(O(m\log n)\), space \(O(m)\).

◆ algorithms_Dmin

enum class lal::linarr::algorithms_Dmin

strong

The different algorithms for computing the minimum sum of the length of the edges \(D\).

This enumeration's values are used to choose the algorithm which the functions lal::linarr::min_sum_edge_lengths use to compute the minimum value of the sum of the length of the edges \(D\).

Enumerator

Shiloach

Yossi Shiloach's algorithm.

Shiloach's quadratic algorithm \(O(n^{2.2})\). Said algorithm was published in [34], but the implementation applies the correction published in [13].

Chung_2

Fan Chung's quadratic algorithm.

Fan Chung's quadratic algorithm \(O(n^2)\). Said algorithm was published in [11]. In particular, this implements Fan Chung's quadratic algorithm (Section 3).

◆ algorithms_Dmin_planar

enum class lal::linarr::algorithms_Dmin_planar

strong

The different algorithms for computing the minimum sum of the length of the edges \(D\) in planar arrangements of free trees.

Recall that a planar arrangement is one in which there are no edge crossings.

This enumeration's values are used to choose the algorithm which the functions lal::linarr::min_sum_edge_lengths_planar use to compute the minimum value of the sum of the length of the edges \(D\).

Enumerator

AlemanyEstebanFerrer

Alemany-Esteban-Ferrer's algorithm.

Interval-based approach to the calculation of minimum planar arrangements. Algorithm published in [7].

This algorithm's complexity is \(O(n)\).

HochbergStallmann

Hochberg-Stallmann's algorithm.

Displacement-based approach to the calculation of minimum planar arrangements. The algorithm was originally published in [24], however, the implementation uses the correction in [7].

This algorithm's complexity is \(O(n)\).

◆ algorithms_Dmin_projective

enum class lal::linarr::algorithms_Dmin_projective

strong

The different algorithms for computing the minimum sum of the length of the edges \(D\) in projective arrangements of rooted trees.

Recall that a projective arrangement is one in which there are no edge crossings and the root is not covered by any edge.

This enumeration's values are used to choose the algorithm which the functions lal::linarr::min_sum_edge_lengths_projective use to compute the minimum value of the sum of the length of the edges \(D\).

Enumerator

AlemanyEstebanFerrer

Alemany-Esteban-Ferrer's algorithm.

Interval-based approach to the calculation of minimum projective arrangements. Algorithm published in [7].

This algorithm's complexity is \(O(n)\).

HochbergStallmann

Hochberg-Stallmann's algorithm.

Displacement-based approach to the calculation of minimum projective arrangements. The algorithm was originally published in [24], however, the implementation uses the correction in [7].

This algorithm's complexity is \(O(n)\).

◆ syntactic_dependency_structure

enum class lal::linarr::syntactic_dependency_structure

strong

The different types of syntactic dependency tree structures.

Any tree with its nodes linearly arranged can be classified into several different classes.

We can currently identify the following structures:

Projective structures (see syntactic_dependency_structure::projective),
Planar structures (see syntactic_dependency_structure::planar),
Well nested trees with maximum degree gap 1 (see syntactic_dependency_structure::WG1),
1-Endpoint Crossing (see syntactic_dependency_structure::EC1),

Enumerator
EC1	1-Endpoint Crossing. A structure is 1-endpoint crossing if, given any dependency, all other dependencies crossing it are incident to a common node. See [33] for further details.
planar	Planar structures. A structure is planar if none of its dependencies cross. Two dependencies \((s,t), (u,v)\) cross if, and only if, their positions in the arrangement are interleaved, i.e., if \(\pi(s) < \pi(u) < \pi(t) < \pi(v)\), assuming that \(s\) precedes \(t\) and \(u\) precedes \(v\) in the arrangement.
projective	Projective structures. A structure is projective if it is syntactic_dependency_structure::planar and the root is not covered by any dependency.
WG1	Well nested trees with maximum gap-degree 1. For further details and a thorough discussion, see [21].
unknown	The structure could not be classified.

Function Documentation

◆ compute_flux() [1/2]

std::vector< dependency_flux > lal::linarr::compute_flux	(	const graphs::free_tree &	t,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the flux of a dependency tree.

This function is implemented based on the explanations given in [26].

Parameters

t	Input free tree (or dependency tree).
pi	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: The set of dependency fluxes in the arrangement.

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

◆ compute_flux() [2/2]

std::vector< dependency_flux > lal::linarr::compute_flux	(	const graphs::rooted_tree &	t,
		const linear_arrangement &	pi = `{}`
	)

inlinenoexcept

Computes the flux of a dependency tree.

This function is implemented based on the explanations given in [26].

Parameters

t	Input rooted tree (or dependency tree).
pi	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: The set of dependency fluxes in the arrangement.

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

◆ head_initial()

double lal::linarr::head_initial	(	const graphs::directed_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the headedness of a linearly arranged directed graph.

See lal::linarr::head_initial_rational for details.

Parameters

g	Input graph.
pi	Permutation of the nodes. When omitted, \(\pi_I\) is used.

Returns: The return value is a floating point value.

Precondition: \(m > 0\).

◆ head_initial_rational()

numeric::rational lal::linarr::head_initial_rational	(	const graphs::directed_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the headedness of a directed graph as an exact rational number.

Given a graph and a permutation of its nodes, the headedness \(h\) is the ratio of right-branching edges over the total amount of edges. More precisely, it is

\(h = \frac{r}{m}\)

where \(r\) is the number of right-branching edges and \(m\) is the number of edges of the graph.

A value of 0 indicates perfect left branching, and a value of 1 indicates perfect right-branching. See [27] for further detals.

Parameters

g	Input graph.
pi	Permutation of the nodes. When omitted, \(\pi_I\) is used.

Returns: The headedness ratio as an exact rational number.

Precondition: \(m > 0\).

◆ is_arrangement()

template<class graph_t >

bool lal::linarr::is_arrangement	(	const graph_t &	g,
		const linear_arrangement &	arr
	)

noexcept

Is a given arrangement valid?

Checks that an input arrangement is valid for the corresponding input graph. An arrangement is valid if it is a valid permutation of the vertices of the graph.

Parameters

g	Input graph.
arr	Input arrangement.

Returns: Whether or not the input arrangement is a valid permutation.

◆ is_num_crossings_lesseq_than() [1/4]

uint64_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::directed_graph &	G,
		const linear_arrangement &	arr,
		uint64_t	upper_bound,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\) and a linear arrangements \(\pi\) of its nodes, returns the number of edge crossings \(C_{\pi}(G)\) if it is less than or equal to the given upper bound constant \(u\). In case the number of crossings is greater, returns a value strictly larger than the upper bound. This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Upper bound on the number of crossings.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than the upper bound if otherwise.

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_num_crossings_lesseq_than() [2/4]

uint64_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::directed_graph &	G,
		uint64_t	upper_bound,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\) computes the number of edge crossings using the identity arrangement \(\pi_I\), \(C_{\pi_I}(G)\), if it is less than or equal to the given upper bound constant \(u\). In case the number of crossings is greater, returns a value strictly larger than the upper bound. This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
upper_bound	Upper bound on the number of crossings.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than the upper bound if otherwise.

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_num_crossings_lesseq_than() [3/4]

uint64_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::undirected_graph &	G,
		const linear_arrangement &	arr,
		uint64_t	upper_bound,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\) and a linear arrangements \(\pi\) of its nodes, returns the number of edge crossings \(C_{\pi}(G)\) if is less than or equal to the given upper bound constant \(u\). In case the number of crossings is greater, returns a value strictly larger than the upper bound. This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Upper bound on the number of crossings.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than than the upper bound if otherwise.

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_num_crossings_lesseq_than() [4/4]

uint64_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::undirected_graph &	G,
		uint64_t	upper_bound,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\) computes the number of edge crossings using the identity arrangement \(\pi_I\), \(C_{\pi_I}(G)\), if it is less than or equal to the given upper bound constant \(u\). In case the number of crossings is greater, returns a value strictly larger than the upper bound. This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
upper_bound	Upper bound on the number of crossings.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than the upper bound if otherwise.

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_num_crossings_lesseq_than_list() [1/4]

std::vector< uint64_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::directed_graph &	G,
		const std::vector< linear_arrangement > &	arrs,
		const std::vector< uint64_t > &	upper_bounds,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\), a list of linear arrangements \(L=\{\pi_i\}_{i=1}^k\) of its nodes and a list of upper bounds \(\{u_i\}_{i=1}^k\), computes the number of edge crossings for each of the linear arrangements \(\pi_i\) if that amount is less than or equal to the given upper bound \(u_i\), i.e., computes \(\{ f_i \}_{i=1}^k\), where \(f_i=C_{\pi_i}(G)\) if \(C_{\pi_i}(G)\le u_i\), or a value larger than \(u_i\) if \(C_{\pi_i}(G)>u_i\). This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
arrs	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bounds	A list of upper bounds on the number of crossings for each linear arrangement.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than the upper bound if otherwise.

Precondition: There must be as many linear arrangements as upper bounds.; The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_num_crossings_lesseq_than_list() [2/4]

std::vector< uint64_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::directed_graph &	G,
		const std::vector< linear_arrangement > &	arrs,
		uint64_t	upper_bound,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\) and a list of linear arrangements \(L=\{\pi_i\}_{i=1}^k\) of its nodes, computes the number of edge crossings for each of the linear arrangements \(\pi_i\) if that amount is less than or equal to the given upper bound \(u\), i.e., computes \(\{f_i\}_{i=1}^k\), where \(f_i=C_{\pi_i}(G)\) if \(C_{\pi_i}(G)\le u\), or a value strictly larger than the upper bound \(u\) if \(C_{\pi_i}(G)>u\). This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
arrs	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Upper bound on the number of crossings.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than the upper bound if otherwise.

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_num_crossings_lesseq_than_list() [3/4]

std::vector< uint64_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::undirected_graph &	G,
		const std::vector< linear_arrangement > &	arrs,
		const std::vector< uint64_t > &	upper_bounds,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\), a list of linear arrangements \(L=\{\pi_i\}_{i=1}^k\) of its nodes and a list of upper bounds \(\{u_i\}_{i=1}^k\), computes the number of edge crossings for each of the linear arrangements \(\pi_i\) if that amount is less than or equal to the given upper bound \(u_i\), i.e., computes \(\{ f_i \}_{i=1}^k\), where \(f_i=C_{\pi_i}(G)\) if \(C_{\pi_i}(G)\le u_i\), or \(f_i>m^2\) if \(C_{\pi_i}(G)>u_i\). This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
arrs	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bounds	A list of upper bounds on the number of crossings for each linear arrangement.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than the upper bound if otherwise.

Precondition: There must be as many linear arrangements as upper bounds.; The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_num_crossings_lesseq_than_list() [4/4]

std::vector< uint64_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::undirected_graph &	G,
		const std::vector< linear_arrangement > &	arrs,
		uint64_t	upper_bound,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Is the number of crossings in the linear arrangement less than a constant?

Given a graph \(G\) and a list of linear arrangements \(L=\{\pi_i\}_{i=1}^k\) of its nodes, computes the number of edge crossings for each of the linear arrangements \(\pi_i\) if that amount is less than or equal to the given upper bound \(u\), i.e., computes \(\{f_i\}_{i=1}^k\), where \(f_i=C_{\pi_i}(G)\) if \(C_{\pi_i}(G)\le u\), or \(f_i>m^2\) if \(C_{\pi_i}(G)>u\). This function uses a modified version of the algorithm specified by the parameter A. The modification involves early termination in case the actual number of crossings is strictly larger than the upper bound.

Parameters

G	Input graph.
arrs	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Upper bound on the number of crossings.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\) if said number is less than or equal to the upper bound. The function returns a value strictly larger than the upper bound if otherwise.

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ is_permutation()

bool lal::linarr::is_permutation ( const linear_arrangement & arr = {} )

inlinenoexcept

Is a given input arrangement a permutation?

A linear arrangement is a permutation if all the positions are numbers in \([0,n-1]\), where \(n\) denotes the size of the arrangement and if no two numbers appear twice in the arrangement.

Parameters

arr	Input linear arrangement

Returns: Whether or not the input arrangement is a valid permutation.

◆ is_planar()

template<class graph_t >

bool lal::linarr::is_planar	(	const graph_t &	g,
		const linear_arrangement &	arr = `{}`
	)

noexcept

Is a given arrangement planar?

A planar arrangement of a graph is an arrangement in which there are no edge crossings. If the input arrangement is empty then the identity arrangement \(\pi_I\) is used.

Parameters

g	Input graph.
arr	Input linear arrangement.

Returns: Whether or not the input graph arranged with the input arrangement is planar.

◆ is_projective()

bool lal::linarr::is_projective	(	const graphs::rooted_tree &	rt,
		const linear_arrangement &	arr
	)

inlinenoexcept

Is a given arrangement projective?

A projective arrangement of a rooted tree is an arrangement that is planar and the root is not covered by any edge. The root is covered if, for a given input arrangement \(\pi\), there exists an edge of the tree \(\{s,t\}\) such that \(\pi(s) < \pi(r) < \pi(t)\) or \(\pi(t) < \pi(r) < \pi(s)\).

If the input arrangement is empty then the identity arrangement \(\pi_I\) is used.

See method is_planar for further details on the characterisation of planar arrangements.

Parameters

rt	Input rooted tree
arr	Input linear arrangement.

Returns: Whether or not the input rooted tree arranged with the input arrangement is projective.

Precondition: The input rooted tree must be a valid rooted tree (see lal::graphs::rooted_tree::is_rooted_tree).

◆ is_root_covered()

bool lal::linarr::is_root_covered	(	const graphs::rooted_tree &	rt,
		const linear_arrangement &	arr
	)

noexcept

Is the root of a rooted tree covered in a given arrangement?

The root is covered if, for a given input arrangement \(\pi\), there exists an edge of the tree \(\{s,t\}\) such that \(\pi(s) < \pi(r) < \pi(t)\) or \(\pi(t) < \pi(r) < \pi(s)\).

If the input arrangement is empty then the identity arrangement \(\pi_I\) is used.

Parameters

rt	Input rooted tree
arr	Input linear arrangement.

Returns: Whether or not the root is covered in the given arrangement.

Precondition: The input rooted tree must be a valid rooted tree (see lal::graphs::rooted_tree::is_rooted_tree).

◆ max_sum_edge_lengths_planar() [1/2]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_planar ( const graphs::free_tree & t )

noexcept

Computes the maximum value of \(D\) in trees under the planarity constraint.

Calculates the maximum value of \(D\) over all planar arrangements of the input tree. This function also returns the linear arrangement that yields the maximum value. The caller can choose the algorithm to calculate such maximum value.

See Types of arrangements for the definition of planar arrangement.

This function implements the algorithm described in [6].

Parameters

t	Input free tree.

Returns: The maximum value of \(D\) and a maximum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ max_sum_edge_lengths_planar() [2/2]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_planar ( const graphs::rooted_tree & t )

inlinenoexcept

Computes the maximum value of \(D\) in trees under the planarity constraint.

Calculates the maximum value of \(D\) over all planar arrangements of the input tree. This function also returns the linear arrangement that yields the maximum value. The caller can choose the algorithm to calculate such maximum value.

See Types of arrangements for the definition of planar arrangement.

This function implements the algorithm described in [6].

This function converts the input rooted into a free tree (see lal::graphs::rooted_tree::to_free_tree())

Parameters

t	Input rooted tree.

Returns: The maximum value of \(D\) and a maximum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ max_sum_edge_lengths_projective()

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_projective ( const graphs::rooted_tree & t )

noexcept

Computes the maximum value of \(D\) in rooted trees under the projectivity constraint.

Calculates the maximum value of \(D\) over all projective arrangements of the input tree. This function also returns the linear arrangement that yields the maximum value. The caller can choose the algorithm to calculate such maximum value.

See Types of arrangements for the definition of projective arrangement.

This function implements the algorithm described in [6].

Parameters

t	Input rooted tree.

Returns: The maximum value of \(D\) and a maximum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ max_sum_edge_lengths_projective_roots() [1/2]

std::pair< std::vector< uint64_t >, node > lal::linarr::max_sum_edge_lengths_projective_roots ( const graphs::free_tree & t )

noexcept

Computes the maximum value of \(D\) in trees under the projectivity constraint at every vertex of the tree.

Calculates the maximum sum of edge lengths under the projectivity constraint at every vertex of the tree, that is, the result returned is a list of values \(\{M_1,M_2,\dots,M_n\}\) where \(M_i\) is the maximum sum of edge lengths under projectivity for the tree rooted at the \(i\)-th vertex.

See Types of arrangements for the definition of projective arrangement.

This function implements the algorithm described in [6].

Parameters

t	Input free tree.

Returns: The maximum value of \(D\) and a maximum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ max_sum_edge_lengths_projective_roots() [2/2]

std::pair< std::vector< uint64_t >, node > lal::linarr::max_sum_edge_lengths_projective_roots ( const graphs::rooted_tree & t )

inlinenoexcept

Computes the maximum value of \(D\) in trees under the projectivity constraint at every vertex of the tree.

Calculates the maximum sum of edge lengths under the projectivity constraint at every vertex of the tree, that is, the result returned is a list of values \(\{M_1,M_2,\dots,M_n\}\) where \(M_i\) is the maximum sum of edge lengths under projectivity for the tree rooted at the \(i\)-th vertex.

See Types of arrangements for the definition of projective arrangement.

This function implements the algorithm described in [6].

This function converts the input rooted into a free tree (see lal::graphs::rooted_tree::to_free_tree()). Therefore, the root is ignored.

Parameters

t	Input free tree.

Returns: The maximum value of \(D\) and a maximum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ mean_dependency_distance() [1/2]

double lal::linarr::mean_dependency_distance	(	const graphs::directed_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the mean dependency distance \(MDD\) as a floating point value.

See lal::linarr::mean_dependency_distance_rational for details.

Parameters

g	Input graph.
pi	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: The return value is a floating point value.

Precondition: \(m > 0\).

◆ mean_dependency_distance() [2/2]

double lal::linarr::mean_dependency_distance	(	const graphs::undirected_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the mean dependency distance \(MDD\) as a floating point value.

See lal::linarr::mean_dependency_distance_rational for details.

Parameters

g	Input graph.
pi	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: The return value is a floating point value.

Precondition: \(m > 0\).

◆ mean_dependency_distance_1level()

template<class graph_t >

double lal::linarr::mean_dependency_distance_1level	(	const std::vector< graph_t > &	L,
		const std::vector< linear_arrangement > &	P = `{}`
	)

noexcept

1-level Mean Dependency Distance \(MDD\) over an ensemble of graphs.

See lal::linarr::mean_dependency_distance_1level_rational for further details.

Parameters

L	List of input graphs.
P	List of linear arrangements of the nodes \(Pi = \{\pi_i\}_{i=1}^k\). When omitted, \(\pi_I\) is used for every graph.

Template Parameters

graph_t A graph type. A class that derives from lal::graphs::graph.

Returns: Jing's and Liu's 1-level \(MDD\) for an ensemble of graphs as a floating point value.

◆ mean_dependency_distance_1level_rational()

template<class graph_t >

numeric::rational lal::linarr::mean_dependency_distance_1level_rational	(	const std::vector< graph_t > &	L,
		const std::vector< linear_arrangement > &	P = `{}`
	)

noexcept

1-level Mean Dependency Distance \(MDD\) over an ensemble of graphs.

Given a list of graphs \(L\) and a list of linear arrangements for each of them, \(P\), computes the 1-level Mean Dependency Distance as the quotient of \(D\), the sum of all the edge lengths of each graph, and of \(M\) the sum of the number of edges of all the graphs.

Formally, given a list of graphs \(L = \{L_i\}_{i=1}^k\) and a list of linear arrangements \(\Pi = \{\pi_i\}_{i=1}^k\), computes \(D/M\), where

\(D = \sum_{i=1}^k D(L_i, \pi_i)\) is the sum of edge lengths of all graphs.
\(M = \sum_{i=1}^k |E(L_i)|\) is the sum of the number of edges of all graphs.

Parameters

L	List of input graphs.
P	List of linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When omitted, \(\pi_I\) is used for every graph.

Template Parameters

graph_t A graph type. A class that derives from lal::graphs::graph.

Returns: Jing's and Liu's 1-level \(MDD\) for an ensemble of graphs as an exact rational value.

◆ mean_dependency_distance_2level()

template<class graph_t >

double lal::linarr::mean_dependency_distance_2level	(	const std::vector< graph_t > &	L,
		const std::vector< linear_arrangement > &	P = `{}`
	)

noexcept

2-level Mean Dependency Distance \(MDD\) over an ensemble of graphs.

See lal::linarr::mean_dependency_distance_2level_rational for details.

Parameters

L	List of input graphs.
P	List of linear arrangements of the nodes \(L = \{\pi_i\}_{i=1}^k\). When omitted, \(\pi_I\) is used for every graph.

Template Parameters

graph_t A graph type. A class that derives from lal::graphs::graph.

Returns: Jing's and Liu's 2-level \(MDD\) for an ensemble of graphs as a floating point value.

◆ mean_dependency_distance_2level_rational()

template<class graph_t >

numeric::rational lal::linarr::mean_dependency_distance_2level_rational	(	const std::vector< graph_t > &	L,
		const std::vector< linear_arrangement > &	P = `{}`
	)

noexcept

2-level Mean Dependency Distance \(MDD\) over an ensemble of graphs.

Given a list of graphs \(L\) and a list of linear arrangements of the nodes for each of them, \(P\), computes the 2-level Mean Dependency Distance, i.e., it computes the average Mean Dependency Distance of the graphs in the list.

Formally, given a list of graphs \(L = \{L_i\}_{i=1}^k\) and a list of linear arrangements \(P = \{\pi_i\}_{i=1}^k\), computes \((1/k)S_{<d>}\), where \(S_{<d>} = \sum_{i=1}^k MDD(L_i, \pi_i)\) is the sum of the mean dependency distances of every graph (see lal::linarr::mean_dependency_distance_rational for details on the definition of the Mean Dependency Distance).

Parameters

L	List of input graphs.
P	List of linear arrangements of the nodes \(P = \{\pi_i\}_{i=1}^k\). When omitted, \(\pi_I\) is used for every graph.

Template Parameters

graph_t A graph type. A class that derives from lal::graphs::graph.

Returns: Jing's and Liu's 2-level \(MDD\) for an ensemble of graphs as an exact rational value.

◆ mean_dependency_distance_rational() [1/2]

numeric::rational lal::linarr::mean_dependency_distance_rational	(	const graphs::directed_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the mean dependency distance \(MDD\) as an exact rational value.

Given a graph \(G\) and a linear arrangement of its nodes \(\pi\), computes the average edge length, or the mean dependency distance (see [25]). Formally, it computes \(\frac{D_{\pi}(G)}{|E(G)|}\). See function sum_edge_lengths for further details on \(D_{\pi}(G)\).

Parameters

g	Input graph.
pi	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: Jing's and Liu's \(MDD\).

Precondition: \(m > 0\).

◆ mean_dependency_distance_rational() [2/2]

numeric::rational lal::linarr::mean_dependency_distance_rational	(	const graphs::undirected_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the mean dependency distance \(MDD\) as an exact rational value.

Given a graph \(G\) and a linear arrangement of its nodes \(\pi\), computes the average edge length, or the mean dependency distance (see [25]). Formally, it computes \(\frac{D_{\pi}(G)}{|E(G)|}\). See function sum_edge_lengths for further details on \(D_{\pi}(G)\).

Parameters

g	Input graph.
pi	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: Jing's and Liu's \(MDD\).

Precondition: \(m > 0\).

◆ min_sum_edge_lengths() [1/2]

std::pair< uint64_t, linear_arrangement > lal::linarr::min_sum_edge_lengths	(	const graphs::free_tree &	t,
		const algorithms_Dmin &	a = `algorithms_Dmin::Shiloach`
	)

noexcept

Computes the minimum value of \(D\) in free trees.

Calculates the minimum value of \(D\) over all possible arrangements of the input tree. This function also returns the linear arrangement that yields the minimum value. The caller can choose the algorithm to calculate such minimum value.

See the description of the values in lal::linarr::algorithms_Dmin for details on the algorithm implemented and to see references to the papers.

Parameters

t	Input free tree.
a	The algorithm to use.

Returns: The minimum value of \(D\) and a minimum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).; This function has as extra preconditions those specified in the enumeration passed as parameter.

◆ min_sum_edge_lengths() [2/2]

std::pair< uint64_t, linear_arrangement > lal::linarr::min_sum_edge_lengths	(	const graphs::rooted_tree &	t,
		const algorithms_Dmin &	a = `algorithms_Dmin::Shiloach`
	)

inlinenoexcept

Computes the minimum value of \(D\) in trees.

Calculates the minimum value of \(D\) over all possible arrangements of the input tree. This function also returns the linear arrangement that yields the minimum value. The caller can choose the algorithm to calculate such minimum value.

See the description of the values in lal::linarr::algorithms_Dmin for details on the algorithm to be used and to see references to the papers.

This function converts the input rooted into a free tree (see lal::graphs::rooted_tree::to_free_tree())

Parameters

t	Input rooted tree.
a	The algorithm to use.

Returns: The minimum value of \(D\) and a minimum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).; This function has as extra preconditions those specified in the enumeration passed as parameter.

◆ min_sum_edge_lengths_planar() [1/2]

std::pair< uint64_t, linear_arrangement > lal::linarr::min_sum_edge_lengths_planar	(	const graphs::free_tree &	t,
		const algorithms_Dmin_planar &	a = `algorithms_Dmin_planar::AlemanyEstebanFerrer`
	)

noexcept

Computes the minimum value of \(D\) in trees under the planarity constraint.

Calculates the minimum value of \(D\) over all planar arrangements of the input tree. This function also returns the linear arrangement that yields the minimum value. The caller can choose the algorithm to calculate such minimum value.

See Types of arrangements for the definition of planar arrangement.

See the description of the values in lal::linarr::algorithms_Dmin_planar for details on the algorithm to be used and to see references to the papers.

Parameters

t	Input free tree.
a	The algorithm to use.

Returns: The minimum value of \(D\) and a minimum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ min_sum_edge_lengths_planar() [2/2]

std::pair< uint64_t, linear_arrangement > lal::linarr::min_sum_edge_lengths_planar	(	const graphs::rooted_tree &	t,
		const algorithms_Dmin_planar &	a = `algorithms_Dmin_planar::AlemanyEstebanFerrer`
	)

inlinenoexcept

Computes the minimum value of \(D\) in trees under the planarity constraint.

Calculates the minimum value of \(D\) over all planar arrangements of the input tree. This function also returns the linear arrangement that yields the minimum value. The caller can choose the algorithm to calculate such minimum value.

See Types of arrangements for the definition of planar arrangement.

See the description of the values in lal::linarr::algorithms_Dmin_planar for details on the algorithm to be used and to see references to the papers.

This function converts the input rooted into a free tree (see lal::graphs::rooted_tree::to_free_tree())

Parameters

t	Input rooted tree.
a	The algorithm to use.

Returns: The minimum value of \(D\) and a minimum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ min_sum_edge_lengths_projective()

std::pair< uint64_t, linear_arrangement > lal::linarr::min_sum_edge_lengths_projective	(	const graphs::rooted_tree &	t,
		const algorithms_Dmin_projective &	a = `algorithms_Dmin_projective::AlemanyEstebanFerrer`
	)

noexcept

Computes the minimum value of \(D\) in rooted trees under the projectivity constraint.

Calculates the minimum value of \(D\) over all projective arrangements of the input tree. This function also returns the linear arrangement that yields the minimum value. The caller can choose the algorithm to calculate such minimum value.

See Types of arrangements for the definition of projective arrangement.

See the description of the values in lal::linarr::algorithms_Dmin_projective for details on the algorithm to be used and to see references to the papers.

Parameters

t	Input rooted tree.
a	The algorithm to use.

Returns: The minimum value of \(D\) and a minimum arrangement.

Precondition: Input tree t must be a valid tree (see lal::graphs::tree::is_tree()).

◆ num_crossings() [1/4]

uint64_t lal::linarr::num_crossings	(	const graphs::directed_graph &	G,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Computes the number of edge crossings in a linear arrangement.

Given a graph \(G\), computes the number of edge crossings using the identity arrangement \(\pi_I\), i.e., computes \(C_{\pi_I}(G)\) using the algorithm specified by the parameter A.

Parameters

G	Input graph.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\).

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ num_crossings() [2/4]

uint64_t lal::linarr::num_crossings	(	const graphs::directed_graph &	G,
		const linear_arrangement &	arr,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Computes the number of edge crossings in a linear arrangement.

Given a graph \(G\) and a linear arrangements \(\pi\) of its nodes, computes the number of edge crossings \(C_{\pi}(G)\) using the algorithm specified by the parameter A.

Parameters

G	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\).

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ num_crossings() [3/4]

uint64_t lal::linarr::num_crossings	(	const graphs::undirected_graph &	G,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Computes the number of edge crossings in a linear arrangement.

Given a graph \(G\), computes the number of edge crossings using the identity arrangement \(\pi_I\), i.e., computes \(C_{\pi_I}(G)\) using the algorithm specified by the parameter A.

Parameters

G	Input graph.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\).

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ num_crossings() [4/4]

uint64_t lal::linarr::num_crossings	(	const graphs::undirected_graph &	G,
		const linear_arrangement &	arr,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Computes the number of edge crossings in a linear arrangement.

Given a graph \(G\) and a linear arrangements \(\pi\) of its nodes, computes the number of edge crossings \(C_{\pi}(G)\) using the algorithm specified by the parameter A.

Parameters

G	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
A	Algorithm to use to compute the number of crossings.

Returns: The number of crossings \(C\).

Precondition: The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ num_crossings_list() [1/2]

std::vector< uint64_t > lal::linarr::num_crossings_list	(	const graphs::directed_graph &	G,
		const std::vector< linear_arrangement > &	arrs,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Computes the number of edge crossings in a linear arrangement.

Given a graph \(G\) and a list of linear arrangements \(L=\{\pi_i\}_{i=1}^k\) of its nodes, computes the number of edge crossings for each of the linear arrangements \(\pi_i\), i.e., computes \(\{C_{\pi_i}(G)\}_{i=1}^k\), using the algorithm specified by the parameter A.

Parameters

G	Input graph.
arrs	A list of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\).
A	Algorithm to use to compute the number of crossings.

Returns: A list \(L\) where \(L_i = C_{\pi_i}(G)\).

Precondition: None of the arrangements in pis can be empty.; The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ num_crossings_list() [2/2]

std::vector< uint64_t > lal::linarr::num_crossings_list	(	const graphs::undirected_graph &	G,
		const std::vector< linear_arrangement > &	arrs,
		const algorithms_C &	A = `algorithms_C::ladder`
	)

noexcept

Computes the number of edge crossings in a linear arrangement.

Given a graph \(G\) and a list of linear arrangements \(L=\{\pi_i\}_{i=1}^k\) of its nodes, computes the number of edge crossings for each of the linear arrangements \(\pi_i\), i.e., computes \(\{C_{\pi_i}(G)\}_{i=1}^k\), using the algorithm specified by the parameter A.

Parameters

G	Input graph.
arrs	A list of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\).
A	Algorithm to use to compute the number of crossings.

Returns: A list \(L\) where \(L_i = C_{\pi_i}(G)\).

Precondition: None of the arrangements in pis can be empty.; The preconditions of this function depend on the choice of algorithm. See the preconditions of each algorithm in lal::linarr::algorithms_C.

◆ predicted_num_crossings() [1/2]

double lal::linarr::predicted_num_crossings	(	const graphs::directed_graph &	g,
		const linear_arrangement &	arr = `{}`
	)

noexcept

Approximates the number of crossings.

See lal::linarr::predicted_num_crossings_rational for details.

Parameters

g	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: Approximation of the number of crossings \(E_2[C_G\;|\;\delta]\).

◆ predicted_num_crossings() [2/2]

double lal::linarr::predicted_num_crossings	(	const graphs::undirected_graph &	g,
		const linear_arrangement &	arr = `{}`
	)

noexcept

Approximates the number of crossings.

See lal::linarr::predicted_num_crossings_rational for details.

Parameters

g	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: Approximation of the number of crossings \(E_2[C_G\;|\;\delta]\).

◆ predicted_num_crossings_rational() [1/2]

numeric::rational lal::linarr::predicted_num_crossings_rational	(	const graphs::directed_graph &	g,
		const linear_arrangement &	arr = `{}`
	)

noexcept

Predicts the number of crossings.

Given a linear arrangement, which determines the length of the edges, predict the number of crossings conditioned by the length of the edges in the linear arrangement. Implementation of [16]. If the arrangement is not specified, the identity arrangement is used.

Parameters

g	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: Approximation of the number of crossings \(E_2[C_G\;|\;\delta]\).

◆ predicted_num_crossings_rational() [2/2]

numeric::rational lal::linarr::predicted_num_crossings_rational	(	const graphs::undirected_graph &	g,
		const linear_arrangement &	arr = `{}`
	)

noexcept

Predicts the number of crossings.

Given a linear arrangement, which determines the length of the edges, predict the number of crossings conditioned by the length of the edges in the linear arrangement. Implementation of [16]. If the arrangement is not specified, the identity arrangement is used.

Parameters

g	Input graph.
arr	A linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: Approximation of the number of crossings \(E_2[C_G\;|\;\delta]\).

◆ sum_edge_lengths() [1/2]

uint64_t lal::linarr::sum_edge_lengths	(	const graphs::directed_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the sum of the length of the edges in a linear arrangement.

Given a graph \(G\) and a linear arrangement of its nodes \(\pi\), computes the sum of the length of the graph's edges in the arrangement. Formally, this function computes the value \(D_{\pi}(G)=\sum_{uv\in E(G)} |\pi(u) - \pi(v)|\).

If the arrangement is not specified, the identity arrangement is used.

Parameters

g	Input graph.
pi	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: The sum of edge lengths \(D\).

◆ sum_edge_lengths() [2/2]

uint64_t lal::linarr::sum_edge_lengths	(	const graphs::undirected_graph &	g,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the sum of the length of the edges in a linear arrangement.

Given a graph \(G\) and a linear arrangement of its nodes \(\pi\), computes the sum of the length of the graph's edges in the arrangement. Formally, this function computes the value \(D_{\pi}(G)=\sum_{uv\in E(G)} |\pi(u) - \pi(v)|\).

If the arrangement is not specified, the identity arrangement is used.

Parameters

g	Input graph.
pi	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.

Returns: The sum of edge lengths \(D\).

◆ syntactic_dependency_structure_class() [1/2]

std::array< bool, __syntactic_dependency_structure_size > lal::linarr::syntactic_dependency_structure_class	(	const graphs::rooted_tree &	t,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the type of syntactic dependency tree.

Given an undirected rooted tree and a linear arrangement of its nodes, computes the class of projective structure the tree belongs to.

Parameters

t	Input tree.
pi	Linear arrangement of the nodes. If \(\pi[u]=p\) then node u is placed in position p of the arrangement.

Returns: The class of projective structure. If the class could not be determined the method returns lal::linarr::syntactic_dependency_structure::unknown.

◆ syntactic_dependency_structure_class() [2/2]

std::array< bool, __syntactic_dependency_structure_size > lal::linarr::syntactic_dependency_structure_class	(	const graphs::rooted_tree &	t,
		uint64_t	C,
		const linear_arrangement &	pi = `{}`
	)

noexcept

Computes the type of syntactic dependency tree.

Given an undirected rooted tree and a linear arrangement of its nodes, computes the class of projective structure the tree belongs to.

This function admits the precomputed number of edge crossings in the same linear arrangement passed as parameter to this function.

Parameters

t	Input tree.
C	Number of crossings (see lal::linarr::num_crossings).
pi	Linear arrangement of the nodes. If \(\pi[u]=p\) then node u is placed in position p of the arrangement.

Returns: The class of projective structure. If the class could not be determined the method returns lal::linarr::syntactic_dependency_structure::unknown.

Classes

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ algorithms_C

◆ algorithms_Dmin

◆ algorithms_Dmin_planar

◆ algorithms_Dmin_projective

◆ syntactic_dependency_structure

Function Documentation

◆ compute_flux() [1/2]

◆ compute_flux() [2/2]

◆ head_initial()

◆ head_initial_rational()

◆ is_arrangement()

◆ is_num_crossings_lesseq_than() [1/4]

◆ is_num_crossings_lesseq_than() [2/4]

◆ is_num_crossings_lesseq_than() [3/4]

◆ is_num_crossings_lesseq_than() [4/4]

◆ is_num_crossings_lesseq_than_list() [1/4]

◆ is_num_crossings_lesseq_than_list() [2/4]

◆ is_num_crossings_lesseq_than_list() [3/4]

◆ is_num_crossings_lesseq_than_list() [4/4]

◆ is_permutation()

◆ is_planar()

◆ is_projective()

◆ is_root_covered()

◆ max_sum_edge_lengths_planar() [1/2]

◆ max_sum_edge_lengths_planar() [2/2]

◆ max_sum_edge_lengths_projective()

◆ max_sum_edge_lengths_projective_roots() [1/2]

◆ max_sum_edge_lengths_projective_roots() [2/2]

◆ mean_dependency_distance() [1/2]

◆ mean_dependency_distance() [2/2]

◆ mean_dependency_distance_1level()

◆ mean_dependency_distance_1level_rational()

◆ mean_dependency_distance_2level()

◆ mean_dependency_distance_2level_rational()

◆ mean_dependency_distance_rational() [1/2]

◆ mean_dependency_distance_rational() [2/2]

◆ min_sum_edge_lengths() [1/2]

◆ min_sum_edge_lengths() [2/2]

◆ min_sum_edge_lengths_planar() [1/2]

◆ min_sum_edge_lengths_planar() [2/2]

◆ min_sum_edge_lengths_projective()

◆ num_crossings() [1/4]

◆ num_crossings() [2/4]

◆ num_crossings() [3/4]

◆ num_crossings() [4/4]

◆ num_crossings_list() [1/2]

◆ num_crossings_list() [2/2]

◆ predicted_num_crossings() [1/2]

◆ predicted_num_crossings() [2/2]

◆ predicted_num_crossings_rational() [1/2]

◆ predicted_num_crossings_rational() [2/2]

◆ sum_edge_lengths() [1/2]

◆ sum_edge_lengths() [2/2]

◆ syntactic_dependency_structure_class() [1/2]

◆ syntactic_dependency_structure_class() [2/2]