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 { Unconstrained_YS , Unconstrained_FC }
	The different algorithms for computing the minimum sum of the length of the edges \(D\). More...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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.

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.

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.

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.

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

uint32_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, {...});

A linear arrangement object is a vector whose size is equal to the number of nodes of its corresponding graph. Note, however, that a linear arrangement has no associated graph; it is just a vector. Throughout this namespace we use the symbol for the number pi, \(\pi\) to denote a linear arrangement, as is usually done in the scientific literature.

The contents of a lal::linear_arrangement object are as follows: if \(\pi\) is a linear arrangement then the u-th position of \(\pi\) contains the position of that node in the arrangement. Formally, \(\pi[u] = p\) if, and only if, node u is at position p in the linear arrangement.

The identity arrangement \(\pi_I\) is a special case of linear arrangement used in many functions. Such an arrangement is one that maps each node into the position corresponding to their label, i.e., \( \pi_I(u) = u\). When omitting the arrangement in the functions of this namespace, the user should consider that the arrangement used is the identity arrangement.

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. Complexity: time \(O(n^2)\), space \(O(n^2)\).
ladder	Dynamic programming algorithm. Complexity: time \(O(n^2)\), space \(O(n)\).
stack_based	Algorithm based on sorting. 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

Unconstrained_YS

Yossi Shiloach's algorithm to calculate unconstrained optimal linearization of free trees.

This value makes the lal::linarr::min_sum_edge_lengths function choose the implementation of Yossi Shiloach's algorithm. This algorithm was published in [31]. The implementation of this algorithm applies the corrections published in [11].

Unconstrained_FC

Fan Chung's algorithm to calculate unconstrained optimal linearization of free trees.

This value makes the lal::linarr::min_sum_edge_lengths function choose the implementation of Fan Chung's algorithm. This algorithm was published in [10]. In particular, this implements Fan Chung's quadratic algorithm (Section 3).

◆ 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 [30] 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 [17].
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 [24].

Parameters

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

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 = {} )

noexcept

Computes the flux of a dependency tree.

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

Parameters

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

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 [25] 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 G >

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

inlinenoexcept

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]

uint32_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::directed_graph &	G,
		const linear_arrangement &	pi,
		uint32_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 \(m^2\), where \(m\) is the number of edges of the graph. This function uses a modified version of the algorithm specified by the parameter A.

Parameters

G	Input graph.
pi	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 \(m^2\) 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]

uint32_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::directed_graph &	G,
		uint32_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 \(m^2\), where \(m\) is the number of edges of the graph. This function uses a modified version of the algorithm specified by the parameter A.

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 \(m^2\) 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]

uint32_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::undirected_graph &	G,
		const linear_arrangement &	pi,
		uint32_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 \(m^2\), where \(m\) is the number of edges of the graph. This function uses a modified version of the algorithm specified by the parameter A.

Parameters

G	Input graph.
pi	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 \(m^2\) 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]

uint32_t lal::linarr::is_num_crossings_lesseq_than	(	const graphs::undirected_graph &	G,
		uint32_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 \(m^2\), where \(m\) is the number of edges of the graph. This function uses a modified version of the algorithm specified by the parameter A.

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 \(m^2\) 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< uint32_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::directed_graph &	G,
		const std::vector< linear_arrangement > &	pis,
		const std::vector< uint32_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.

Parameters

G	Input graph.
pis	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 \(m^2\) 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< uint32_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::directed_graph &	G,
		const std::vector< linear_arrangement > &	pis,
		uint32_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.

Parameters

G	Input graph.
pis	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 \(m^2\) 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< uint32_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::undirected_graph &	G,
		const std::vector< linear_arrangement > &	pis,
		const std::vector< uint32_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.

Parameters

G	Input graph.
pis	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 \(m^2\) 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< uint32_t > lal::linarr::is_num_crossings_lesseq_than_list	(	const graphs::undirected_graph &	G,
		const std::vector< linear_arrangement > &	pis,
		uint32_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.

Parameters

G	Input graph.
pis	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 \(m^2\) 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 G >

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

inlinenoexcept

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

◆ 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 G >

double lal::linarr::mean_dependency_distance_1level	(	const std::vector< G > &	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

G	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 G >

numeric::rational lal::linarr::mean_dependency_distance_1level_rational	(	const std::vector< G > &	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

G	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 G >

double lal::linarr::mean_dependency_distance_2level	(	const std::vector< G > &	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

G	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 G >

numeric::rational lal::linarr::mean_dependency_distance_2level_rational	(	const std::vector< G > &	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

G	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 [23]). 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 [23]). 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< uint32_t, linear_arrangement > lal::linarr::min_sum_edge_lengths	(	const graphs::free_tree &	t,
		const algorithms_Dmin &	a = algorithms_Dmin::Unconstrained_YS )

noexcept

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

Calculates the minimum value of \(D\) and returns a linear arrangement yielding this value. Such optimal value of \(D\) depends on the choice of algorithm for its calculation.

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 be chosen.

Returns: The minimum value of \(D\) and an optimum 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< uint32_t, linear_arrangement > lal::linarr::min_sum_edge_lengths	(	const graphs::rooted_tree &	t,
		const algorithms_Dmin &	a = algorithms_Dmin::Unconstrained_YS )

inlinenoexcept

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

Calculates the minimum value of \(D\) and returns a linear arrangement yielding this value. Such optimal value of \(D\) depends on the choice of algorithm for its calculation.

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

Parameters

t	Input rooted tree.
a	The algorithm to be chosen.

Returns: The minimum value of \(D\) and an optimum 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< uint32_t, linear_arrangement > lal::linarr::min_sum_edge_lengths_planar ( const graphs::free_tree & t )

noexcept

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

This function implements the algorithm published in [6].

Computes an optimal planar linear arrangement for free trees. A planar linear arrangement is an arrangement in which there are no edge crossings. This problem was originally tackled by Iordanskii [22] and later by Hochberg and Stallmann [20]. See [6] for a review.

Parameters

t	Input free tree.

Returns: The minimum value of \(D\) and an optimum 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< uint32_t, linear_arrangement > lal::linarr::min_sum_edge_lengths_planar ( const graphs::rooted_tree & t )

inlinenoexcept

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

This function implements the algorithm published in [6].

Computes an optimal planar linear arrangement for free trees. A planar linear arrangement is an arrangement in which there are no edge crossings. This problem was originally tackled by Iordanskii [22] and later by Hochberg and Stallmann [20]. See [6] for a review.

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

Parameters

t	Input rooted tree.

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

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

◆ min_sum_edge_lengths_projective()

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

noexcept

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

Computes an optimal projective linear arrangement for rooted trees. A projective linear arrangement is an arrangement in which there are no edge crossings and the root is not covered by any edge.

This function implements the algorithm in [6]. A non-linear time algorithm to solve this problem was oulined in [15].

Parameters

t	Input rooted tree.

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

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

◆ num_crossings() [1/4]

uint32_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]

uint32_t lal::linarr::num_crossings	(	const graphs::directed_graph &	G,
		const linear_arrangement &	pi,
		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.
pi	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]

uint32_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]

uint32_t lal::linarr::num_crossings	(	const graphs::undirected_graph &	G,
		const linear_arrangement &	pi,
		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.
pi	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< uint32_t > lal::linarr::num_crossings_list	(	const graphs::directed_graph &	G,
		const std::vector< linear_arrangement > &	pis,
		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.
pis	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< uint32_t > lal::linarr::num_crossings_list	(	const graphs::undirected_graph &	G,
		const std::vector< linear_arrangement > &	pis,
		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.
pis	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 &	pi = {} )

noexcept

Approximates the number of crossings.

See lal::linarr::predicted_num_crossings_rational for details.

Parameters

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

Returns: The return value is a floating point value.

◆ predicted_num_crossings() [2/2]

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

noexcept

Approximates the number of crossings.

See lal::linarr::predicted_num_crossings_rational for details.

Parameters

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

Returns: The return value is a floating point value.

◆ predicted_num_crossings_rational() [1/2]

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

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 [13]. If the arrangement is not specified, the identity arrangement is used.

Parameters

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

Returns: Approximation of the number of crossings \(E_s[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 &	pi = {} )

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 [13]. If the arrangement is not specified, the identity arrangement is used.

Parameters

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

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

◆ sum_edge_lengths() [1/2]

uint32_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]

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

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.

Classes

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ algorithms_C

◆ algorithms_Dmin

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

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