lal::linarr Namespace Reference

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

Classes
class	chunk
	Definition of a chunk. More...
class	chunk_sequence
	Chunk sequence of a syntactic dependency tree. More...
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_chunking { Anderson , Macutek }
	The different algorithms for chunking a syntactic dependency tree. 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_tree_type {   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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
uint64_t	is_num_crossings_lesseq_than (const graphs::directed_graph &G, const 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?
uint64_t	is_num_crossings_lesseq_than (const graphs::undirected_graph &G, const 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?
uint64_t	is_num_crossings_lesseq_than (const graphs::directed_graph &G, const linear_arrangement &arr, const 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?
uint64_t	is_num_crossings_lesseq_than (const graphs::undirected_graph &G, const linear_arrangement &arr, const 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?
std::vector< uint64_t >	is_num_crossings_lesseq_than_list (const graphs::directed_graph &G, const std::vector< linear_arrangement > &arrs, const 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?
std::vector< uint64_t >	is_num_crossings_lesseq_than_list (const graphs::undirected_graph &G, const std::vector< linear_arrangement > &arrs, const 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?
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?
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?
numeric::rational	predicted_num_crossings_rational (const graphs::undirected_graph &g, const linear_arrangement &arr={}) noexcept
	Predicts the number of crossings.
numeric::rational	predicted_num_crossings_rational (const graphs::directed_graph &g, const linear_arrangement &arr={}) noexcept
	Predicts the number of crossings.
double	predicted_num_crossings (const graphs::undirected_graph &g, const linear_arrangement &arr={}) noexcept
	Approximates the number of crossings.
double	predicted_num_crossings (const graphs::directed_graph &g, const linear_arrangement &arr={}) noexcept
	Approximates the number of crossings.
graphs::rooted_tree	make_tree_from_chunk_sequence (const chunk_sequence &seq) noexcept
	Constructs a rooted tree from the given chunk sequence.
graphs::rooted_tree	chunk_syntactic_dependency_tree (const graphs::rooted_tree &rt, const algorithms_chunking &algo) noexcept
	Chunks a syntactic dependency tree according to the algorithm passed as parameter.
graphs::rooted_tree	chunk_syntactic_dependency_tree (const graphs::rooted_tree &rt, const linear_arrangement &arr, const algorithms_chunking &algo) noexcept
	Chunks a syntactic dependency tree according to the algorithm passed as parameter.
chunk_sequence	chunk_syntactic_dependency_tree_as_sequence (const graphs::rooted_tree &rt, const algorithms_chunking &algo) noexcept
	Chunks a syntactic dependency tree according to the algorithm passed as parameter.
chunk_sequence	chunk_syntactic_dependency_tree_as_sequence (const graphs::rooted_tree &rt, const linear_arrangement &arr, const algorithms_chunking &algo) noexcept
	Chunks a syntactic dependency tree according to the algorithm passed as parameter.
std::ostream &	operator<< (std::ostream &os, const chunk &c) noexcept
	Standard output operator for chunks.
std::ostream &	operator<< (std::ostream &os, const chunk_sequence &seq) noexcept
	Standard output operator for chunk sequences.
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.
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.
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< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const std::vector< std::vector< node > > &orbits, const properties::bipartite_graph_coloring &c, const std::vector< properties::branchless_path > &bps, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const std::vector< std::vector< node > > &orbits, const std::vector< properties::branchless_path > &bps, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const properties::bipartite_graph_coloring &c, const std::vector< properties::branchless_path > &bps, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const std::vector< std::vector< node > > &orbits, const properties::bipartite_graph_coloring &c, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const std::vector< properties::branchless_path > &bps, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const properties::bipartite_graph_coloring &c, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const std::vector< std::vector< node > > &orbits, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, std::vector< linear_arrangement > >	max_sum_edge_lengths_all (const graphs::free_tree &t, const std::size_t num_threads=1) noexcept
	Calculates all the linear arrangements that yield the maximum sum of edge lengths.
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_1_le_thistle (const graphs::free_tree &t, const properties::bipartite_graph_coloring &c, const std::vector< properties::branchless_path > &bps) noexcept
	Calculates the solution to \(\le 1\)-thistle MaxLA.
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_1_le_thistle (const graphs::free_tree &t, const std::vector< properties::branchless_path > &bps) noexcept
	Calculates the solution to \(\le 1\)-thistle MaxLA.
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_1_le_thistle (const graphs::free_tree &t, const properties::bipartite_graph_coloring &c) noexcept
	Calculates the solution to \(\le 1\)-thistle MaxLA.
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_1_le_thistle (const graphs::free_tree &t) noexcept
	Calculates the solution to \(\le1\)-thistle MaxLA.
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_1_eq_thistle (const graphs::free_tree &t, const std::vector< properties::branchless_path > &bps) noexcept
	Calculates the solution to \(=1\)-thistle MaxLA.
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_1_eq_thistle (const graphs::free_tree &t) noexcept
	Calculates the solution to \(=1\)-thistle MaxLA.
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_bipartite (const graphs::undirected_graph &g, const properties::bipartite_graph_coloring &c) noexcept
	Calculates the solution to Bipartite MaxLA as defined in [8].
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_bipartite (const graphs::undirected_graph &g) noexcept
	Calculates the solution to Bipartite MaxLA as defined in [8].
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_bipartite (const graphs::directed_graph &g, const properties::bipartite_graph_coloring &c) noexcept
	Calculates the solution to Bipartite MaxLA as defined in [8].
std::pair< uint64_t, linear_arrangement >	max_sum_edge_lengths_bipartite (const graphs::directed_graph &g) noexcept
	Calculates the solution to Bipartite MaxLA as defined in [8].
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.
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.
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.
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.
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.
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.
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.
std::pair< uint64_t, linear_arrangement >	min_sum_edge_lengths_bipartite (const graphs::free_tree &t, const properties::bipartite_graph_coloring &c) noexcept
	Computes the minimum value of \(D\) in trees over bipartite arrangements.
std::pair< uint64_t, linear_arrangement >	min_sum_edge_lengths_bipartite (const graphs::free_tree &t) noexcept
	Computes the minimum value of \(D\) in trees over bipartite arrangements.
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.
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.
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.
std::vector< dependency_flux >	dependency_flux_compute (const graphs::free_tree &t, const linear_arrangement &pi={}) noexcept
	Computes the flux of a dependency tree.
std::vector< dependency_flux >	dependency_flux_compute (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 graph_t >
bool	is_arrangement (const graph_t &g, const linear_arrangement &arr) noexcept
	Is a given arrangement valid?
bool	is_bipartite (const graphs::undirected_graph &g, const properties::bipartite_graph_coloring &c, const linear_arrangement &arr={}) noexcept
	Is a given arrangement bipartite?
bool	is_bipartite (const graphs::directed_graph &g, const properties::bipartite_graph_coloring &c, const linear_arrangement &arr={}) noexcept
	Is a given arrangement bipartite?
bool	is_bipartite (const graphs::undirected_graph &g, const linear_arrangement &arr={}) noexcept
	Is a given arrangement bipartite?
bool	is_bipartite (const graphs::directed_graph &g, const linear_arrangement &arr={}) noexcept
	Is a given arrangement bipartite?
template<class graph_t >
bool	is_planar (const graph_t &g, const linear_arrangement &arr={}) noexcept
	Is a given arrangement planar?
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?
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.
std::array< bool, __syntactic_dependency_tree_size >	syntactic_dependency_tree_classify (const graphs::rooted_tree &t, const uint64_t C, const linear_arrangement &pi={}) noexcept
	Computes the type of syntactic dependency tree.
std::array< bool, __syntactic_dependency_tree_size >	syntactic_dependency_tree_classify (const graphs::rooted_tree &t, const linear_arrangement &pi={}) noexcept
	Computes the type of syntactic dependency tree.

Variables
constexpr std::size_t	__syntactic_dependency_tree_size
	Number of elements within enumeration syntactic_dependency_tree_type.

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;

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

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.

See Properties that can be defined in linear arrangements for the definition of edge crossings.

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

algorithms_chunking

enum class lal::linarr::algorithms_chunking

strong

The different algorithms for chunking a syntactic dependency tree.

Chunking is the art of grouping nodes (a.k.a. words) of a syntactic dependency tree in such a way that the resulting groups share common properties. This enumeration lists all the chunking algorithms implemented in this library.

Here we use 'chunking' as an umbrella term for all the algorithms that group nodes in units in a systematic way. Some researchers may not use this term.

Enumerator
Anderson	Chunking algorithm by Anderson. For further details see [12] and [11].
Macutek	Chunking algorithm by Mačutek. Mačutek et al. termed chunks as Linear Dependency Sequences (LDSs). For further details see [35]. Note: the implementation of Mačutek's algorithm in LAL does not take clauses into account when computing an LDS.

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 [43], but the implementation applies the correction published in [19].
Chung_2	Fan Chung's quadratic algorithm. Fan Chung's quadratic algorithm \(O(n^2)\). Said algorithm was published in [15]. 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 [6]. 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 [30], however, the implementation uses the correction in [6]. 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 [6]. 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 [30], however, the implementation uses the correction in [6]. This algorithm's complexity is \(O(n)\).

syntactic_dependency_tree_type

enum class lal::linarr::syntactic_dependency_tree_type

strong

The different types of syntactic dependency tree structures.

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

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 [42] 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 lal::linarr::syntactic_dependency_tree_type::planar and the root is not covered by any dependency.
WG1	Well nested trees with maximum gap-degree 1. All trees classified (by this library) as \(WG_1\) are not in \(WG_0\) (notice that \(WG_0\) is the class of projective trees). For further details and thorough definitions of \(WG_k\), see [27].
unknown	The structure could not be classified.

Function Documentation

chunk_syntactic_dependency_tree() [1/2]

graphs::rooted_tree lal::linarr::chunk_syntactic_dependency_tree ( const graphs::rooted_tree & rt, const algorithms_chunking & algo )

nodiscardnoexcept

Chunks a syntactic dependency tree according to the algorithm passed as parameter.

This function assumes the identity arrangement to chunk this tree.

Parameters

rt	Input syntactic dependency tree.
algo	Algorithm of choice.

Returns

A syntactic dependency tree result of the chosen chunking algorithm.

chunk_syntactic_dependency_tree() [2/2]

graphs::rooted_tree lal::linarr::chunk_syntactic_dependency_tree ( const graphs::rooted_tree & rt, const linear_arrangement & arr, const algorithms_chunking & algo )

nodiscardnoexcept

Chunks a syntactic dependency tree according to the algorithm passed as parameter.

Parameters

rt	Input syntactic dependency tree.
arr	Non-empty input linear arrangement.
algo	Algorithm of choice.

Returns

A syntactic dependency tree result of the chosen chunking algorithm.

chunk_syntactic_dependency_tree_as_sequence() [1/2]

chunk_sequence lal::linarr::chunk_syntactic_dependency_tree_as_sequence ( const graphs::rooted_tree & rt, const algorithms_chunking & algo )

nodiscardnoexcept

Chunks a syntactic dependency tree according to the algorithm passed as parameter.

This function assumes the identity arrangement to chunk this tree.

Parameters

rt	Input syntactic dependency tree.
algo	Algorithm of choice.

Returns

The sequence of chunks as a simple collection of nodes plus parent node for each chunk.

chunk_syntactic_dependency_tree_as_sequence() [2/2]

chunk_sequence lal::linarr::chunk_syntactic_dependency_tree_as_sequence ( const graphs::rooted_tree & rt, const linear_arrangement & arr, const algorithms_chunking & algo )

nodiscardnoexcept

Chunks a syntactic dependency tree according to the algorithm passed as parameter.

Parameters

rt	Input syntactic dependency tree.
arr	Non-empty input linear arrangement.
algo	Algorithm of choice.

Returns

The sequence of chunks as a simple collection of nodes plus parent node for each chunk.

dependency_flux_compute() [1/2]

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

nodiscardnoexcept

Computes the flux of a dependency tree.

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

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

dependency_flux_compute() [2/2]

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

inlinenodiscardnoexcept

Computes the flux of a dependency tree.

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

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

head_initial()

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

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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_bipartite() [1/4]

bool lal::linarr::is_bipartite ( const graphs::directed_graph & g, const linear_arrangement & arr = {} )

nodiscardnoexcept

Is a given arrangement bipartite?

See Types of arrangements for the definition of bipartite arrangement.

Parameters

g	Input directed graph.
arr	Input linear arrangement.

Returns

Whether or not the input arrangment of g is bipartite.

Precondition

The underlying undirected graph is bipartite, but needs not be connected.

is_bipartite() [2/4]

bool lal::linarr::is_bipartite ( const graphs::directed_graph & g, const properties::bipartite_graph_coloring & c, const linear_arrangement & arr = {} )

nodiscardnoexcept

Is a given arrangement bipartite?

See Types of arrangements for the definition of bipartite arrangement.

Parameters

g	Input directed graph.
c	Coloring of the input graph.
arr	Input linear arrangement.

Returns

Whether or not the input arrangment of g is bipartite.

Precondition

The underlying undirected graph is bipartite and connected.

is_bipartite() [3/4]

bool lal::linarr::is_bipartite ( const graphs::undirected_graph & g, const linear_arrangement & arr = {} )

nodiscardnoexcept

Is a given arrangement bipartite?

See Types of arrangements for the definition of bipartite arrangement.

Parameters

g	Input undirected graph.
arr	Input linear arrangement.

Returns

Whether or not the input arrangment of g is bipartite.

Precondition

The input graph is bipartite, and needs not be connected.

is_bipartite() [4/4]

bool lal::linarr::is_bipartite ( const graphs::undirected_graph & g, const properties::bipartite_graph_coloring & c, const linear_arrangement & arr = {} )

nodiscardnoexcept

Is a given arrangement bipartite?

See Types of arrangements for the definition of bipartite arrangement.

Parameters

g	Input undirected graph.
c	Coloring of the input graph.
arr	Input linear arrangement.

Returns

Whether or not the input arrangment of g is bipartite.

Precondition

The input graph is bipartite and connected.

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, const uint64_t upper_bound, const algorithms_C & A = algorithms_C::ladder )

nodiscardnoexcept

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, const uint64_t upper_bound, const algorithms_C & A = algorithms_C::ladder )

nodiscardnoexcept

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, const uint64_t upper_bound, const algorithms_C & A = algorithms_C::ladder )

nodiscardnoexcept

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, const uint64_t upper_bound, const algorithms_C & A = algorithms_C::ladder )

nodiscardnoexcept

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 )

nodiscardnoexcept

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, const uint64_t upper_bound, const algorithms_C & A = algorithms_C::ladder )

nodiscardnoexcept

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 )

nodiscardnoexcept

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, const uint64_t upper_bound, const algorithms_C & A = algorithms_C::ladder )

nodiscardnoexcept

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

inlinenodiscardnoexcept

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

nodiscardnoexcept

Is a given arrangement planar?

See Types of arrangements for the definition of planar arrangement.

Parameters

g	Input graph.
arr	Input linear arrangement.

Returns

Whether or not the input arrangment of g is planar.

is_projective()

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

inlinenodiscardnoexcept

Is a given arrangement projective?

See Types of arrangements for the definition of projective arrangement.

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 input arrangment of rt 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 )

nodiscardnoexcept

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

See Properties that can be defined in linear arrangements for the definition of vertex covering.

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

make_tree_from_chunk_sequence()

graphs::rooted_tree lal::linarr::make_tree_from_chunk_sequence ( const chunk_sequence & seq )

nodiscardnoexcept

Constructs a rooted tree from the given chunk sequence.

Parameters

seq	Chunk sequence

Returns

A rooted tree.

max_sum_edge_lengths_1_eq_thistle() [1/2]

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

nodiscardnoexcept

Calculates the solution to \(=1\)-thistle MaxLA.

It computes a maximal non-bipartite arrangement of a tree constrained to the arrangement having only one thistle vertex. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.

Precondition

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

Returns

A maximal non-bipartite arrangement with exactly one thistle vertex.

max_sum_edge_lengths_1_eq_thistle() [2/2]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_1_eq_thistle ( const graphs::free_tree & t, const std::vector< properties::branchless_path > & bps )

nodiscardnoexcept

Calculates the solution to \(=1\)-thistle MaxLA.

It computes a maximal either bipartite or non-bipartite arrangement of a tree constrained to having at most one thistle vertex. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.
bps	All branchless paths of the tree.

Returns

A maximal arrangement with at most one thistle vertex.

Precondition

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

max_sum_edge_lengths_1_le_thistle() [1/4]

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

nodiscardnoexcept

Calculates the solution to \(\le1\)-thistle MaxLA.

It computes a maximal either bipartite or non-bipartite arrangement of a tree constrained to having at most one thistle vertex. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.

Returns

A maximal arrangement with at most one thistle vertex.

Precondition

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

max_sum_edge_lengths_1_le_thistle() [2/4]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_1_le_thistle ( const graphs::free_tree & t, const properties::bipartite_graph_coloring & c )

nodiscardnoexcept

Calculates the solution to \(\le 1\)-thistle MaxLA.

It computes a maximal either bipartite or non-bipartite arrangement of a tree constrained to having at most one thistle vertex. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.
c	Bipartite coloring of the input tree.

Returns

A maximal arrangement with at most one thistle vertex.

Precondition

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

max_sum_edge_lengths_1_le_thistle() [3/4]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_1_le_thistle ( const graphs::free_tree & t, const properties::bipartite_graph_coloring & c, const std::vector< properties::branchless_path > & bps )

nodiscardnoexcept

Calculates the solution to \(\le 1\)-thistle MaxLA.

It computes a maximal either bipartite or non-bipartite arrangement of a tree constrained to having at most one thistle vertex. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.
c	Bipartite coloring of the input tree.
bps	All branchless paths of the tree.

Returns

A maximal arrangement with at most one thistle vertex.

Precondition

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

max_sum_edge_lengths_1_le_thistle() [4/4]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_1_le_thistle ( const graphs::free_tree & t, const std::vector< properties::branchless_path > & bps )

nodiscardnoexcept

Calculates the solution to \(\le 1\)-thistle MaxLA.

It computes a maximal either bipartite or non-bipartite arrangement of a tree constrained to having at most one thistle vertex. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.
bps	All branchless paths of the tree.

Precondition

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

Returns

A maximal arrangement with at most one thistle vertex.

Precondition

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

max_sum_edge_lengths_all() [1/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const properties::bipartite_graph_coloring & c, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
c	Bipartite coloring of the input tree.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_all() [2/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const properties::bipartite_graph_coloring & c, const std::vector< properties::branchless_path > & bps, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
c	Bipartite coloring of the input tree.
bps	All branchless paths of the tree.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_all() [3/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_all() [4/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const std::vector< properties::branchless_path > & bps, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
bps	All branchless paths of the tree.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_all() [5/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const std::vector< std::vector< node > > & orbits, const properties::bipartite_graph_coloring & c, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
orbits	The orbits of the input graph.
c	Bipartite coloring of the input tree.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_all() [6/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const std::vector< std::vector< node > > & orbits, const properties::bipartite_graph_coloring & c, const std::vector< properties::branchless_path > & bps, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
orbits	The orbits of the input graph.
c	Bipartite coloring of the input tree.
bps	All branchless paths of the tree.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_all() [7/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const std::vector< std::vector< node > > & orbits, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
orbits	The orbits of the input graph.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_all() [8/8]

std::pair< uint64_t, std::vector< linear_arrangement > > lal::linarr::max_sum_edge_lengths_all ( const graphs::free_tree & t, const std::vector< std::vector< node > > & orbits, const std::vector< properties::branchless_path > & bps, const std::size_t num_threads = 1 )

nodiscardnoexcept

Calculates all the linear arrangements that yield the maximum sum of edge lengths.

This function runs a Branch and Bound algorithm that finds al arrangements (up to level isomorphism) that yield the maximum sum of edge lengths over the entire set of \(n!\) arrangements.

This function implements the Branch and Bound algorithm described in [7].

See Arrangement isomorphism for the definition of level isomorphism.

Parameters

t	Input free tree.
orbits	The orbits of the input graph.
bps	All branchless paths of the tree.
num_threads	Number of threads to use.

Returns

All maximum arrangements up to level isomorphism.

Precondition

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

max_sum_edge_lengths_bipartite() [1/4]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_bipartite ( const graphs::directed_graph & g )

nodiscardnoexcept

Calculates the solution to Bipartite MaxLA as defined in [8].

It computes a maximal bipartite arrangement of a bipartite graph. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

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

Parameters

g	Input directed graph.

Returns

A maximal bipartite arrangement.

Precondition

The input graph g is a connected bipartite graph (ignoring orientation of edges).

max_sum_edge_lengths_bipartite() [2/4]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_bipartite ( const graphs::directed_graph & g, const properties::bipartite_graph_coloring & c )

nodiscardnoexcept

Calculates the solution to Bipartite MaxLA as defined in [8].

It computes a maximal bipartite arrangement of a bipartite graph. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

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

Parameters

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

Returns

A maximal bipartite arrangement.

Precondition

The input graph g is a connected bipartite graph (ignoring orientation of edges).

max_sum_edge_lengths_bipartite() [3/4]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_bipartite ( const graphs::undirected_graph & g )

nodiscardnoexcept

Calculates the solution to Bipartite MaxLA as defined in [8].

It computes a maximal bipartite arrangement of a bipartite graph. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

g	Input undirected graph.

Returns

A maximal bipartite arrangement.

Precondition

The input graph g is a connected bipartite graph.

max_sum_edge_lengths_bipartite() [4/4]

std::pair< uint64_t, linear_arrangement > lal::linarr::max_sum_edge_lengths_bipartite ( const graphs::undirected_graph & g, const properties::bipartite_graph_coloring & c )

nodiscardnoexcept

Calculates the solution to Bipartite MaxLA as defined in [8].

It computes a maximal bipartite arrangement of a bipartite graph. This function implements the algorithm described in [7].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

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

Returns

A maximal bipartite arrangement.

Precondition

The input graph g is a connected bipartite graph.

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 )

nodiscardnoexcept

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

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 )

inlinenodiscardnoexcept

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

This function converts the input rooted tree 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 )

nodiscardnoexcept

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

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 )

nodiscardnoexcept

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

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 )

inlinenodiscardnoexcept

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

This function converts the input rooted tree 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 = {} )

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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 [31]). 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 = {} )

nodiscardnoexcept

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

nodiscardnoexcept

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 )

inlinenodiscardnoexcept

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

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

nodiscardnoexcept

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

Calculates the minimum value of \(D\) over all bipartite arrangements of the input tree. This function also returns the linear arrangement that yields the minimum value. This function implements the algorithm described in [10].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.

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

std::pair< uint64_t, linear_arrangement > lal::linarr::min_sum_edge_lengths_bipartite ( const graphs::free_tree & t, const properties::bipartite_graph_coloring & c )

nodiscardnoexcept

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

Calculates the minimum value of \(D\) over all bipartite arrangements of the input tree. This function also returns the linear arrangement that yields the minimum value. This function implements the algorithm described in [10].

See Types of arrangements for the definition of bipartite arrangement.

Parameters

t	Input free tree.
c	Coloring of the input graph.

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

nodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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.

operator<<() [1/2]

std::ostream & lal::linarr::operator<< ( std::ostream & os, const chunk & c )

inlinenoexcept

Standard output operator for chunks.

Usable by lal::linarr::chunk.

Parameters

os	ostream C++ object.
c	Input chunk.

Returns

The output stream.

operator<<() [2/2]

std::ostream & lal::linarr::operator<< ( std::ostream & os, const chunk_sequence & seq )

inlinenoexcept

Standard output operator for chunk sequences.

Usable by lal::linarr::chunk_sequence.

Parameters

os	ostream C++ object.
seq	Input chunk sequence.

Returns

The output stream.

predicted_num_crossings() [1/2]

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

nodiscardnoexcept

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

nodiscardnoexcept

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 [22]. 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 = {} )

nodiscardnoexcept

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 [22]. 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 = {} )

nodiscardnoexcept

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

nodiscardnoexcept

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

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

nodiscardnoexcept

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 sets the corresponding position for lal::linarr::syntactic_dependency_tree_type::unknown.

syntactic_dependency_tree_classify() [2/2]

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

nodiscardnoexcept

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 sets the corresponding position for lal::linarr::syntactic_dependency_tree_type::unknown.