lal::detail Namespace Reference

Detail namespace. More...

Namespaces
namespace	crossings
	Namespace for the algorithms that compute the number of crossings.
namespace	DMax
	Namespace for algorithms to calculate the maximum sum of edge lengths.
namespace	DMax_utils
	Utilities for the various maximum linear arrangement algorithms.
namespace	Dmin
	Namespace for algorithms to calculate the minimum sum of edge lengths.
namespace	Dmin_utils
	Utilities for the various minimum linear arrangement algorithms.
namespace	Dopt_utils
	Utilities for the various optimal linear arrangement algorithms.
namespace	maximum_subtrees
	Algorithms to find maximum subtrees.
namespace	sorting
	Sorting algorithms.

Classes
class	AVL
	Simple class that implements an AVL tree. More...
class	BFS
	Abstract graph Breadth-First Search traversal. More...
struct	bool_sequence
	A sequence of Boolean values. More...
struct	conditional_list
	Generalization of std::conditional_list. More...
struct	data_array
	Wrapper of a C array for autmatic deallocation of memory. More...
struct	edge_size
	Struct used in many algorithms to sort edges according to some integer value. More...
struct	first_true
	From a list of Boolean values, find the first that is set to true. More...
struct	is_pointer_iterator
	Decide if a type is a pointer or iterator to another. More...
struct	ith_type
	Selection of the ith type of a list of types. More...
struct	ith_type< ith_idx, type_sequence< Ts... > >
	Partial template specialization of ith_type for type_sequence. More...
struct	linarr_wrapper
	A wrapper to easily use identity arrangements. More...
class	linear_queue
	Simple array-like fixed-size queue. More...
struct	node_size
	Struct used in many algorithms to sort vertices according to some integer value. More...
struct	type_sequence
	A sequence of types. More...

Typedefs
template<typename bool_seq , typename type_seq >
using	conditional_list_t = typename conditional_list< bool_seq, type_seq >::type
	Shorthand for conditional_list.
template<std::size_t ith_idx, typename... Ts>
using	ith_type_t = typename ith_type< ith_idx, Ts... >::type
	Shorthand for ith_type::type.

Enumerations
enum class	linarr_type { identity , nonident }
	Type of arrangement. More...
enum class	centroid_results { only_one_centroidal , full_centroid , full_centroid_plus_subtree_sizes , full_centroid_plus_edge_sizes }
	The different types of results. More...

Functions
template<class container >
void	make_arrangement_permutations (const graphs::rooted_tree &T, node r, const container &data, position &pos, linear_arrangement &arr) noexcept
	Make an arrangement using permutations. More...
template<class container >
linear_arrangement	make_arrangement_permutations (const graphs::rooted_tree &T, const container &data) noexcept
	Make an arrangement using permutations. More...
template<class container >
void	make_arrangement_permutations (const graphs::free_tree &T, node parent, node u, const container &data, position &pos, linear_arrangement &arr) noexcept
	Make an arrangement using permutations. More...
template<class container >
linear_arrangement	make_arrangement_permutations (const graphs::free_tree &T, node root, const container &data) noexcept
	Make an arrangement using permutations. More...
template<class graph_t >
graph_t	from_edge_list_to_graph (const std::vector< edge > &edge_list, bool normalise=true, bool check=true) noexcept
	Converts an edge list into a graph. More...
template<detail::linarr_type arr_type>
head_vector	from_tree_to_head_vector (const graphs::rooted_tree &t, const detail::linarr_wrapper< arr_type > &arr) noexcept
	Constructs the head vector representation of a tree. More...
template<detail::linarr_type arr_type>
head_vector	from_tree_to_head_vector (const graphs::free_tree &t, const detail::linarr_wrapper< arr_type > &arr, node r) noexcept
	Constructs the head vector representation of a tree. More...
template<class tree_t , bool is_rooted = std::is_base_of_v<graphs::rooted_tree, tree_t>>
std::conditional_t< is_rooted, graphs::rooted_tree, std::pair< graphs::free_tree, node > >	from_head_vector_to_tree (const head_vector &hv, bool normalise, bool check) noexcept
	Converts a head vector into a tree. More...
graphs::free_tree	level_sequence_to_ftree (const uint64_t *const L, uint64_t n, bool normalise=true, bool check=true) noexcept
	Converts the level sequence of a tree into a graph structure. More...
graphs::free_tree	level_sequence_to_ftree (const std::vector< uint64_t > &L, uint64_t n, bool normalise=true, bool check=true) noexcept
	Converts the level sequence of a tree into a graph structure. More...
graphs::free_tree	Prufer_sequence_to_ftree (const uint64_t *const seq, uint64_t n, bool normalise=true, bool check=true) noexcept
	Converts the Prüfer sequence of a labelled tree into a tree structure. More...
graphs::free_tree	Prufer_sequence_to_ftree (const std::vector< uint64_t > &seq, uint64_t n, bool normalise=true, bool check=true) noexcept
	Converts the Prüfer sequence of a labelled tree into a tree structure. More...
bool	find_cycle (const graphs::directed_graph &g, node u, char *const __restrict__ visited, char *const __restrict__ in_stack) noexcept
	Returns true if, and only if, the graph has cycles. More...
bool	has_directed_cycles (const graphs::directed_graph &g, char *const __restrict__ vis, char *const __restrict__ in_stack) noexcept
	Returns true if, and only if, the graph has DIRECTED cycles. More...
bool	has_directed_cycles (const graphs::directed_graph &g) noexcept
	Returns true if, and only if, the graph has DIRECTED cycles. More...
template<class graph_t >
bool	has_undirected_cycles (const graph_t &g, BFS< graph_t > &bfs) noexcept
	Returns true if, and only if, the graph has UNDIRECTED cycles. More...
template<class graph_t >
bool	has_undirected_cycles (const graph_t &g) noexcept
	Returns true if, and only if, the graph has UNDIRECTED cycles. More...
template<class graph_t >
std::vector< edge >	set_edges (const graph_t &g) noexcept
	Enumerate the set of edges of the input graph g. More...
template<class graph_t >
std::vector< edge_pair >	set_pairs_independent_edges (const graph_t &g, uint64_t qs) noexcept
	Enumerate the set of pairs of independent edges of the input graph g. More...
template<class graph_t >
bool	is_graph_a_tree (const graph_t &g) noexcept
	Is the input graph a tree? More...
template<class graph_t >
bool	is_node_reachable_from (const graph_t &g, const node source, const node target) noexcept
	Is a node reachable from another? More...
template<bool get_subsizes>
std::pair< std::vector< edge >, uint64_t * >	get_edges_subtree (const graphs::rooted_tree &T, node u, bool relabel) noexcept
	Retrieves the edges of a subtree. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
void	get_size_subtrees (const tree_t &t, const node u, const node v, uint64_t *const sizes) noexcept
	Calculate the size of every subtree of the tree t. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
void	get_size_subtrees (const tree_t &t, node r, uint64_t *const sizes) noexcept
	Calculate the size of every subtree of tree t. More...
template<class tree_t , typename iterator_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t > and is_pointer_iterator_v< edge_size, iterator_t >, bool > = true>
uint64_t	calculate_bidirectional_sizes (const tree_t &t, const uint64_t n, const node u, const node v, iterator_t &it) noexcept
	Calculates the values \(s(u,v)\) for the edges \((s,t)\) reachable from \(v\) in the subtree \(T^u_v\). More...
template<class tree_t , typename iterator_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t > and is_pointer_iterator_v< edge_size, iterator_t >, bool > = true>
void	calculate_bidirectional_sizes (const tree_t &t, const uint64_t n, const node x, iterator_t it) noexcept
	Calculates the values \(s_u(v)\) for the edges \((u,v)\) reachable from vertex x. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
void	classify_tree (const tree_t &t, std::array< bool, graphs::__tree_type_size > &array) noexcept
	Classify a tree into one of the types lal::graphs::tree_type. More...
constexpr std::string_view	tree_type_string (const graphs::tree_type &tt) noexcept
	Converts to a string a value of the enumeration lal::graphs::tree_type.
template<class tree_t >
void	update_unionfind_after_add_edge (const tree_t &t, const node u, const node v, node *const root_of, uint64_t *const root_size) noexcept
	Update the Union-Find data structure after an edge addition to a tree. More...
template<class tree_t >
void	update_unionfind_after_remove_edge (const tree_t &t, const node u, const node v, node *const root_of, uint64_t *const root_size) noexcept
	Updates Union-Find after an edge removal. More...
template<class tree_t >
void	update_unionfind_before_remove_edges_incident_to (BFS< tree_t > &bfs, node v, node *const root_of, uint64_t *const root_size) noexcept
	Update Union-Find after a vertex removal. More...
template<typename tree_t >
void	update_unionfind_before_remove_edges_incident_to (const tree_t &t, node u, node *const root_of, uint64_t *const root_size) noexcept
	Update Union-Find after a vertex removal. More...
template<class graph_t , typename char_type , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t > &&std::is_integral_v< char_type >, bool > = true>
void	get_bool_neighbours (const graph_t &g, node u, char_type *const neighs) noexcept
	Retrieves the neighbours of a node in an undirected graph as a list of 0-1 values. More...
void	append_adjacency_lists (std::vector< neighbourhood > &target, const std::vector< neighbourhood > &source) noexcept
	Append adjacency list 'source' to list 'target'. More...
linarr_wrapper< linarr_type::identity >	identity_arr (const linear_arrangement &arr) noexcept
	Shorthand for an identity arrangement.
linarr_wrapper< linarr_type::nonident >	nonident_arr (const linear_arrangement &arr) noexcept
	Shorthand for a nonidentity arrangement.
graphs::directed_graph	head_vector_to_directed_graph (const head_vector &hv) noexcept
	Transforms a head vector in a directed graph.
template<bool decide>
std::conditional_t< decide, bool, std::vector< io::report_treebank_file > >	find_errors (const head_vector &hv, const std::size_t line) noexcept
	Find errors in a head vector. More...
template<bool decide>
std::conditional_t< decide, bool, std::vector< io::report_treebank_file > >	find_errors (const std::string &current_line, const std::size_t line) noexcept
	Find errors in a line of a treebank. More...
template<bool decide>
std::conditional_t< decide, bool, std::vector< io::report_treebank_file > >	check_correctness_treebank (const std::string &treebank_filename) noexcept
	Find errors in a treebank file. More...
template<bool decide>
std::conditional_t< decide, bool, std::vector< io::report_treebank_collection > >	check_correctness_treebank_collection (const std::string &main_file_name, std::size_t n_threads) noexcept
	Find errors in a treebank collection. More...
template<class graph_t >
uint64_t	n_C_brute_force (const graph_t &g, const linear_arrangement &arr) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
std::vector< uint64_t >	n_C_brute_force (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
uint64_t	is_n_C_brute_force_lesseq_than (const graph_t &g, const linear_arrangement &arr, uint64_t upper_bound) noexcept
	Returns whether the number of crossings is less than a given constant. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_brute_force_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Returns whether the number of crossings is less than a given constant. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_brute_force_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Returns whether the number of crossings is less than a given constant. More...
template<class graph_t >
uint64_t	n_C_dynamic_programming (const graph_t &g, const linear_arrangement &arr) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
std::vector< uint64_t >	n_C_dynamic_programming (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
uint64_t	is_n_C_dynamic_programming_lesseq_than (const graph_t &g, const linear_arrangement &arr, uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_dynamic_programming_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_dynamic_programming_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
uint64_t	n_C_ladder (const graph_t &g, const linear_arrangement &arr) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
std::vector< uint64_t >	n_C_ladder (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
uint64_t	is_n_C_ladder_lesseq_than (const graph_t &g, const linear_arrangement &arr, uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_ladder_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_ladder_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
uint64_t	n_C_stack_based (const graph_t &g, const linear_arrangement &arr) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
std::vector< uint64_t >	n_C_stack_based (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Is the number of crossings in the linear arrangement less than a constant? More...
template<class graph_t >
uint64_t	is_n_C_stack_based_lesseq_than (const graph_t &g, const linear_arrangement &arr, uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_stack_based_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class graph_t >
std::vector< uint64_t >	is_n_C_stack_based_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound. More...
template<class depflux , class arrangement_t >
void	calculate_dependencies_and_span (const graphs::free_tree &t, const arrangement_t &arr, const std::vector< std::pair< edge_t, uint64_t > > &edge_with_max_pos_at, position cur_pos, std::vector< depflux > &flux, std::vector< edge > &cur_deps) noexcept
	Calculate the dependencies and their span. More...
uint64_t	calculate_weight (const std::vector< edge > &dependencies, graphs::undirected_graph &ug) noexcept
	Calculates the weight of a set of dependencies in a flux. More...
template<detail::linarr_type arr_type>
bool	is_root_covered (const graphs::rooted_tree &rt, const detail::linarr_wrapper< arr_type > &arr) noexcept
	Is the root of a rooted tree covered in a given arrangement? More...
template<detail::linarr_type arr_type>
bool	is_projective (const graphs::rooted_tree &rt, const detail::linarr_wrapper< arr_type > &arr) noexcept
	Is a given arrangement projective? More...
template<class arrangement_t >
uint64_t	right_branching_edges (const graphs::directed_graph &g, const arrangement_t &arr) noexcept
	Number of right branching edges in a directed graph. More...
template<typename result_t , class arrangement_t >
result_t	head_initial (const graphs::directed_graph &g, const arrangement_t &arr) noexcept
	Proposition of right branching edges in a directed graph. More...
constexpr uint64_t	alpha (const int64_t n, const int64_t d1, const int64_t d2) noexcept
	Amount of crossings pairs of edges of given lengths. More...
constexpr uint64_t	beta (const int64_t n, const int64_t d1, const int64_t d2) noexcept
	Amount of pairs of edges of given lengths. More...
template<typename result_t , class graph_t , class arrangement_t >
result_t	predict_C_using_edge_lengths (const graph_t &g, const arrangement_t &arr) noexcept
	Predicted number of crossings based on the sum of edge lengths. More...
template<class graph_t , class arrangement_t >
uint64_t	sum_edge_lengths (const graph_t &g, const arrangement_t &arr) noexcept
	Sum of edge lengths in a graph. More...
template<typename result_t , class graph_t , class arrangement_t >
result_t	mean_sum_edge_lengths (const graph_t &g, const arrangement_t &arr) noexcept
	Average sum of edge lengths in a graph. More...
constexpr std::string_view	syntactic_dependency_structure_to_string (const linarr::syntactic_dependency_structure &tt) noexcept
template<typename T >
constexpr int64_t	to_int64 (const T &t) noexcept
	Conversion to int64_t.
template<typename T >
constexpr uint64_t	to_uint64 (const T &t) noexcept
	Conversion to uint64_t.
template<typename T >
constexpr double	to_double (const T &t) noexcept
	Conversion to double.
template<typename T >
constexpr T	abs_diff (const T &t1, const T &t2) noexcept
	Absolute difference of two values.
template<typename T , std::size_t size, T v, std::size_t... I>
constexpr std::array< T, size >	make_array_with_value_impl (std::index_sequence< I... >) noexcept
	Implementation of lal::detail::make_array_with_value. More...
template<typename T , std::size_t array_size, T value_to_fill_with>
constexpr std::array< T, array_size >	make_array_with_value () noexcept
	Returns an array initialised at a given value. More...
template<typename T , T... ARGS>
constexpr std::array< T, sizeof...(ARGS)>	make_array () noexcept
	Make an array with the values given as parameters of the template. More...
void	mpz_pow_mpz (mpz_t &r, const mpz_t &b, const mpz_t &e) noexcept
	Computes the exponentiation of a big integer to another big integer. More...
void	mpz_divide_mpq (mpq_t &r, const mpz_t &k) noexcept
	Rational-Integer division. More...
void	mpq_divide_mpq (mpq_t &num, const mpq_t &den) noexcept
	Rational-Rational division. More...
void	operate_power (mpq_t &r, uint64_t p) noexcept
	Power operation. More...
void	operate_power (mpq_t &r, const mpz_t &p) noexcept
	Power operation. More...
std::size_t	mpz_bytes (const mpz_t &v) noexcept
	Returns the amount of bytes of a gmp's integer value.
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
std::pair< node, node >	retrieve_centre (const tree_t &t, node X) noexcept
	Calculate the centre of the connected component that has node x. More...
template<centroid_results mode, class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
conditional_list_t< bool_sequence< m1(mode), m2(mode), m3(mode), m4(mode) >, type_sequence< node, std::pair< lal::node, lal::node >, std::pair< std::pair< lal::node, lal::node >, data_array< uint64_t > >, std::pair< std::pair< lal::node, lal::node >, data_array< edge_size > > > >	find_centroidal_vertex (const tree_t &t, node x) noexcept
	Calculates the centroid of a tree. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
std::pair< node, node >	centroidal_vertex_plus_adjacency_list (const tree_t &t, node x, std::vector< std::vector< node_size > > &L) noexcept
	Calculates the centroid and the corresponding rooted adjacency list. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
std::pair< node, node >	retrieve_centroid (const tree_t &t, const node x) noexcept
	Calculate the centroid of the connected component that has node x. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
std::pair< node, node >	retrieve_centroid (const tree_t &t) noexcept
	Calculate the centroid of the tree t. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
uint64_t	tree_diameter (const tree_t &t, node x) noexcept
	Calculate the diameter of a tree. More...
template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
char	fast_non_iso (const tree_t &t1, const tree_t &t2) noexcept
	Fast tree non-isomorphism test. More...
void	assign_name_and_keep (const graphs::rooted_tree &t, node u, std::size_t idx, std::string *const aux_memory_for_names, std::string *const keep_name_of) noexcept
	Assigns a name to node 'u', root of the current subtree. More...
std::string	assign_name (const graphs::rooted_tree &t, node u, std::string *const names, std::size_t idx) noexcept
	Assigns a name to node 'u', root of the current subtree. More...
bool	are_full_trees_isomorphic (const graphs::rooted_tree &t1, const graphs::rooted_tree &t2) noexcept
	Test whether two rooted trees are isomorphic or not.

Variables
constexpr std::array< graphs::tree_type, graphs::__tree_type_size >	array_of_tree_types
	The array of all types of trees.
constexpr std::array< linarr::syntactic_dependency_structure, linarr::__syntactic_dependency_structure_size >	array_of_syntactic_dependency_structures
	The array of all types of syntact dependency structures.
template<bool... conds>
static constexpr std::size_t	first_true_v = first_true<conds...>::value
	Shorthand for first_true.
template<typename Iterated_Type , typename Iterator >
constexpr bool	is_pointer_iterator_v
	Shorthand for is_pointer_iterator.

Detailed Description

Detail namespace.

Most algorithms are included here. Unless you have a really good reason to use the algorithms in this namespace, please, refrain from doing so.

Enumeration Type Documentation

centroid_results

enum class lal::detail::centroid_results

strong

The different types of results.

Enumerator
only_one_centroidal	Returns only one centroidal vertex. No weights.
full_centroid	Returns the full centroid of the tree. No weights.
full_centroid_plus_subtree_sizes	Returns the full centroid of the tree. Also returns the weights.
full_centroid_plus_edge_sizes	Returns the full centroid of the tree. Also returns the edge_size array.

linarr_type

enum class lal::detail::linarr_type

strong

Type of arrangement.

Used to call functions that have arrangements as input parameters.

Enumerator
identity	Identity arrangement. \(\pi(i)=i\).
nonident	Non-identity arrangement. An arrangement that is not the identity.

Function Documentation

alpha()

constexpr uint64_t lal::detail::alpha ( const int64_t  n, const int64_t  d1, const int64_t  d2  )

inlineconstexprnoexcept

Amount of crossings pairs of edges of given lengths.

Complexity: constant time.

Parameters

n	Number of edges in the linear arrangement.
d1	Length of the first edge.
d2	Length of the second edge.

Returns

The amount of pairs of edges of lengths d1 and d2 respectively that can cross in a linear arrangement.

append_adjacency_lists()

void lal::detail::append_adjacency_lists ( std::vector< neighbourhood > &  target, const std::vector< neighbourhood > &  source  )

inlinenoexcept

Append adjacency list 'source' to list 'target'.

Parameters

target	List into which source will be appended to.
source	List to append to target.

assign_name()

std::string lal::detail::assign_name ( const graphs::rooted_tree &  t, node  u, std::string *const  names, std::size_t  idx  )

inlinenoexcept

Assigns a name to node 'u', root of the current subtree.

For further details on the algorithm, see [1] for further details.

Parameters

t	Input rooted tree
u	Root of the subtree whose name we want to calculate
names	An array of strings where the names are stored (as in a dynamic programming algorithm). The size of this array must be at least the number of vertices in the subtree of 't' rooted at 'u'. Actually, less memory suffices, but I don't know how much less: better be safe than sorry.
idx	A pointer to the position within names that will contain the name of the first child of 'u'. The position names[idx+1] will contain the name of the second child of 'u'.

Returns

The code for the subtree rooted at 'u'.

assign_name_and_keep()

void lal::detail::assign_name_and_keep ( const graphs::rooted_tree &  t, node  u, std::size_t  idx, std::string *const  aux_memory_for_names, std::string *const  keep_name_of  )

inlinenoexcept

Assigns a name to node 'u', root of the current subtree.

This function stores the names of every node in the subtree rooted at 'u'. This is useful if we want to make lots of comparisons between subtrees

For further details on the algorithm, see [1].

Parameters

t	Input rooted tree
u	Root of the subtree whose name we want to calculate
idx	A pointer to the position within names that will contain the name of the first child of 'u'. The position names[idx+1] will contain the name of the second child of 'u'.
aux_memory_for_names	Auxiliary memory used to sort names of subtrees.
keep_name_of	An array of strings where the names are stored (as in a dynamic programming algorithm). The size of this array must be at least the number of vertices in the subtree of 't' rooted at 'u'. Actually, less memory suffices, but I don't know how much less: better be safe than sorry.

beta()

constexpr uint64_t lal::detail::beta ( const int64_t  n, const int64_t  d1, const int64_t  d2  )

inlineconstexprnoexcept

Amount of pairs of edges of given lengths.

Complexity: constant time.

Parameters

n	Number of edges in the linear arrangement.
d1	Length of the first edge.
d2	Length of the second edge.

Returns

The amount of pairs of edges of lengths d1 and d2 respectively that can cross in a linear arrangement.

calculate_bidirectional_sizes() [1/2]

template<class tree_t , typename iterator_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t > and is_pointer_iterator_v< edge_size, iterator_t >, bool > = true>

uint64_t lal::detail::calculate_bidirectional_sizes ( const tree_t &  t, const uint64_t  n, const node  u, const node  v, iterator_t &  it  )

noexcept

Calculates the values \(s(u,v)\) for the edges \((s,t)\) reachable from \(v\) in the subtree \(T^u_v\).

This function calculates the 'map' relating each edge \((u, v)\) with the size of the subtree rooted at \(v\) with respect to the hypothetical root \(u\). This is an implementation of the algorithm described in [24] (proof of lemma 8 (page 63), and the beginning of section 6 (page 65)).

Notice that the values are not stored in an actual map (std::map, or similar), but in a vector.

Template Parameters

iterated_t	The type that stores the sizes.
iterator_t	The type of the iterator on a container containing values of type iterated_t.

Parameters

t	Input tree.
n	Size of the connected component to which edge \((u,v)\) belongs to.
u	First vertex of the edge.
v	Second vertex of the edge.
it	An iterator to the container that holds the size values. Such container must have size equal to twice the number of edges in the connected component of u and v.

Precondition

Vertices u and v belong to the same connected component.

calculate_bidirectional_sizes() [2/2]

template<class tree_t , typename iterator_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t > and is_pointer_iterator_v< edge_size, iterator_t >, bool > = true>

void lal::detail::calculate_bidirectional_sizes ( const tree_t &  t, const uint64_t  n, const node  x, iterator_t  it  )

noexcept

Calculates the values \(s_u(v)\) for the edges \((u,v)\) reachable from vertex x.

Calculates the values \(s_u(v)\) for all edges \((u,v)\) in linear time. This is an implementation of the algorithm described in [24] (proof of lemma 8 (page 63), and the beginning of section 6 (page 65)).

For any edge \((u,v)\) let \(T^u\) be the tree \(T\) rooted at \(u\). The value \(s_u(v)\) is the size of the subtree of \(T^u\) rooted at \(v\), i.e., \(s_u(v)=|V(T^u_v)|\).

Example of usage (mind the vector! its initial size is \(2*m\)).

const free_tree t = ... ;
vector<pair<edge,uint64_t>> sizes_edges(2*t.get_num_edges());
auto it = sizes_edges.begin();
detail::calculate_bidirectional_sizes(t, t.get_num_nodes(), 0, it);

Template Parameters

tree_t	Type of the tree. Must be 'rooted_tree' or 'free_tree'.
iterated_t	The type that stores the sizes.
iterator_t	The type of the iterator on a container containing values of type iterated_t.

Parameters

t	Input tree
n	Number of nodes in the connected component of vertex x
x	Node of the connected component for which we want to calculate the bidirectional sizes
it	An iterator to the container that holds the size values. Such container must have size equal to twice the number of edges in the connected component of u and v.

calculate_dependencies_and_span()

template<class depflux , class arrangement_t >

void lal::detail::calculate_dependencies_and_span ( const graphs::free_tree &  t, const arrangement_t &  arr, const std::vector< std::pair< edge_t, uint64_t > > &  edge_with_max_pos_at, position  cur_pos, std::vector< depflux > &  flux, std::vector< edge > &  cur_deps  )

noexcept

Calculate the dependencies and their span.

Template Parameters

arrangement_t

Type of arrangement.

Parameters

	t	Input tree.
	arr	Input linear arrangement.
	edge_with_max_pos_at
	cur_pos	Current position in the arrangement for which we calculate the dependencies.
[out]	flux	The flux at this position.
[out]	cur_deps	The dependencies crossing this position.

calculate_weight()

uint64_t lal::detail::calculate_weight ( const std::vector< edge > &  dependencies, graphs::undirected_graph &  ug  )

inlinenoexcept

Calculates the weight of a set of dependencies in a flux.

Parameters

dependencies	Input dependencies.
ug	Input undirected graph.

Returns

The size of the largest subset of independent dependencies.

centroidal_vertex_plus_adjacency_list()

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

std::pair< node, node > lal::detail::centroidal_vertex_plus_adjacency_list ( const tree_t &  t, node  x, std::vector< std::vector< node_size > > &  L  )

noexcept

Calculates the centroid and the corresponding rooted adjacency list.

Template Parameters

t	Treer type.

Parameters

	t	Input tree.
	x	Node belonging to a connected component whose centroid we want.
[out]	L	Adjacency list-like data structure. \(L[u]\) is a list of pairs \((v, s_u(v))\) where \(v\) is a neighbour (with respect to a fictional root taken to be a centroidal vertex of the tree) of \(u\) and \(n_u(v)=|V(T^u_v)|\) is the size of the subtree \(T^u_v\) in vertices.

check_correctness_treebank()

template<bool decide>

std::conditional_t< decide, bool, std::vector< io::report_treebank_file > > lal::detail::check_correctness_treebank ( const std::string &  treebank_filename )

noexcept

Find errors in a treebank file.

Template Parameters

decide

When true, return a value as soon as an error is found.

Parameters

treebank_filename

Name of the treebank file.

Returns

A Boolean if decide is true, a list of errors if otherwise.

check_correctness_treebank_collection()

template<bool decide>

std::conditional_t< decide, bool, std::vector< io::report_treebank_collection > > lal::detail::check_correctness_treebank_collection ( const std::string &  main_file_name, std::size_t  n_threads  )

noexcept

Find errors in a treebank collection.

Template Parameters

decide

When true, return a value as soon as an error is found.

Parameters

main_file_name	Name of the collection's main file.
n_threads	Number of threads that this function can use.

Returns

A Boolean if decide is true, a list of errors if otherwise.

classify_tree()

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

void lal::detail::classify_tree ( const tree_t &  t, std::array< bool, graphs::__tree_type_size > &  array  )

noexcept

Classify a tree into one of the types lal::graphs::tree_type.

Template Parameters

tree_t

Type of tree.

Parameters

	t	Input tree.
[out]	array	A set of bits (or flags) each indicating whether or not t is of a certain tree type.

fast_non_iso()

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

char lal::detail::fast_non_iso ( const tree_t &  t1, const tree_t &  t2  )

noexcept

Fast tree non-isomorphism test.

Template Parameters

tree_t

Tree type.

Parameters

t1	One tree.
t2	Another tree.

Returns

Whether the input trees are, might be, or are not isomorphic.

0 if the trees ARE isomorphic

1 if the trees ARE NOT isomorphic:

• number of vertices do not coincide,
• number of leaves do not coincide,
• second moment of degree do not coincide,
• maximum vertex degrees do not coincide,

2 if the trees MIGHT BE isomorphic

find_centroidal_vertex()

template<centroid_results mode, class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

conditional_list_t< bool_sequence< m1(mode), m2(mode), m3(mode), m4(mode) >, type_sequence< node, std::pair< lal::node, lal::node >, std::pair< std::pair< lal::node, lal::node >, data_array< uint64_t > >, std::pair< std::pair< lal::node, lal::node >, data_array< edge_size > > > > lal::detail::find_centroidal_vertex ( const tree_t &  t, node  x  )

noexcept

Calculates the centroid of a tree.

See Centre and centroid of a tree for details on what the centroid of a tree is.

If subtree sizes are to be returned, they come in an array of size the number of vertices of the tree.

Template Parameters

mode

Indicates the value to be returned by this function. If: mode == centroid_results::only_one_centroidal, the result of the function is a node. mode == centroid_results::full_centroid, the result of the function is a pair of (possibly) two nodes. The second node may have an invalid value, indicating that the tree has only one centroidal vertex. mode == centroid_results::full_centroid_plus_subtree_sizes, the result of the function is a pair of (possibly) two nodes and the sizes of all the subtrees with respect to the first centroidal node in the pair. mode == centroid_results::full_centroid_plus_edge_sizes, the result of the function is a pair of (possibly) two nodes and an array of the form \((u,v, s(u,v))\) for all directed edges \((u,v)\) that point away from the first centroidal node in the pair.

tree_t

Type of tree.

Parameters

t	Input tree.
x	Node belonging to a connected component whose centroid we want.

find_cycle()

bool lal::detail::find_cycle ( const graphs::directed_graph &  g, node  u, char *const __restrict__  visited, char *const __restrict__  in_stack  )

inlinenoexcept

Returns true if, and only if, the graph has cycles.

Parameters

g	Input graph.
u	Node of the directed graph
visited	For each node, has it been visited?
in_stack	For each node, is it in the recursion stack?

find_errors() [1/2]

template<bool decide>

std::conditional_t< decide, bool, std::vector< io::report_treebank_file > > lal::detail::find_errors ( const head_vector &  hv, const std::size_t  line  )

noexcept

Find errors in a head vector.

The head vector may correspond to the contents of a line in a treebank file.

Template Parameters

decide

When true, return a value as soon as an error is found.

Parameters

hv	Input head vector.
line	Line number of the treebank, if appropriate.

Returns

A Boolean if decide is true, a list of errors if otherwise.

find_errors() [2/2]

template<bool decide>

std::conditional_t< decide, bool, std::vector< io::report_treebank_file > > lal::detail::find_errors ( const std::string &  current_line, const std::size_t  line  )

noexcept

Find errors in a line of a treebank.

Template Parameters

decide

When true, return a value as soon as an error is found.

Parameters

current_line	The line being analyzed.
line	Line number of the treebank.

Returns

A Boolean if decide is true, a list of errors if otherwise.

from_edge_list_to_graph()

template<class graph_t >

graph_t lal::detail::from_edge_list_to_graph ( const std::vector< edge > &  edge_list, bool  normalise = true, bool  check = true  )

noexcept

Converts an edge list into a graph.

An edge list is a list of pairs of indices, each index in the pair being different and in \([0,n-1]\)., where \(n\) is the number of vertices of the tree.

Methods lal::io::read_edge_list read an edge list from a file in disk.

Parameters

edge_list	An edge list.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns

Returns a lal::graphs::rooted_tree obtained from the head vector.

Precondition

No edge in the list is repeated.

from_head_vector_to_tree()

template<class tree_t , bool is_rooted = std::is_base_of_v<graphs::rooted_tree, tree_t>>

std::conditional_t< is_rooted, graphs::rooted_tree, std::pair< graphs::free_tree, node > > lal::detail::from_head_vector_to_tree ( const head_vector &  hv, bool  normalise, bool  check  )

noexcept

Converts a head vector into a tree.

Template Parameters

tree_t

Type of input tree

Parameters

hv	Input head vector.
normalise	Normalise the resulting tree.
check	Check whether the constructed tree is normalised.

Returns

A lal::graphs::rooted_tree or a pair of lal::graphs::free_tree and the root encoded in the head vector.

from_tree_to_head_vector() [1/2]

template<detail::linarr_type arr_type>

head_vector lal::detail::from_tree_to_head_vector ( const graphs::free_tree &  t, const detail::linarr_wrapper< arr_type > &  arr, node  r  )

noexcept

Constructs the head vector representation of a tree.

Template Parameters

arr_type

Type of arrangement.

Parameters

t	Input free tree.
r	Root of the tree.
arr	Linear arrangement of the vertices.

Returns

A head vector

from_tree_to_head_vector() [2/2]

template<detail::linarr_type arr_type>

head_vector lal::detail::from_tree_to_head_vector ( const graphs::rooted_tree &  t, const detail::linarr_wrapper< arr_type > &  arr  )

noexcept

Constructs the head vector representation of a tree.

Template Parameters

arr_type

Type of arrangement.

Parameters

t	Input rooted tree.
arr	Linear arrangement of the vertices.

Returns

A head vector encoding the tree.

get_bool_neighbours()

template<class graph_t , typename char_type , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t > &&std::is_integral_v< char_type >, bool > = true>

void lal::detail::get_bool_neighbours ( const graph_t &  g, node  u, char_type *const  neighs  )

noexcept

Retrieves the neighbours of a node in an undirected graph as a list of 0-1 values.

Sets to 1 the positions in neighs that correspond to the nodes neighours of u.

Parameters

g	Input graph.
u	Input node.
neighs	0-1 list of neighbours of u in g.

Precondition

The contents of neighs must be all 0 (or false).

get_edges_subtree()

template<bool get_subsizes>

std::pair< std::vector< edge >, uint64_t * > lal::detail::get_edges_subtree ( const graphs::rooted_tree &  T, node  u, bool  relabel  )

noexcept

Retrieves the edges of a subtree.

Template Parameters

get_subsizes

Should the result also keep the sizes of the subtrees?

Parameters

T	Input rooted tree.
u	Root of the subtree.
relabel	Relabel the vertices? If so, vertex 'u' is relabelled to 0

Returns

A pair consisting of the list of edges and, optionally, a raw pointer to memory containing the sizes of the subtrees.

Precondition

The tree is a valid rooted tree.

The tree has vertex 'u'.

Postcondition

The function has NO ownership of the raw pointer returned in the pair.

The pointer returned is not nullptr only when T.size_subtrees_valid() AND the boolean parameter sizes are BOTH true.

get_size_subtrees() [1/2]

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

void lal::detail::get_size_subtrees ( const tree_t &  t, const node  u, const node  v, uint64_t *const  sizes  )

noexcept

Calculate the size of every subtree of the tree t.

Parameters

t	Input tree.
u	Parent node (the first call should be an invalid value (e.g., n+1)).
v	Next node in the exploration of the tree.
sizes	The size of the subtree rooted at every reachable node from r.

Precondition

Parameter sizes has size the number of vertices.

get_size_subtrees() [2/2]

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

void lal::detail::get_size_subtrees ( const tree_t &  t, node  r, uint64_t *const  sizes  )

noexcept

Calculate the size of every subtree of tree t.

The method starts calculating the sizes at node r. Since rooted trees have directed edges, starting at a node different from the tree's root may not calculate every subtree's size.

Parameters

t	Input rooted tree.
r	Start calculating sizes of subtrees at this node.
sizes	The size of the subtree rooted at every reachable node from r.

Precondition

Parameter sizes has size the number of vertices.

has_directed_cycles() [1/2]

bool lal::detail::has_directed_cycles ( const graphs::directed_graph &  g )

inlinenoexcept

Returns true if, and only if, the graph has DIRECTED cycles.

Parameters

g	Input graph.

Returns

Whether the graph has cycles or not.

has_directed_cycles() [2/2]

bool lal::detail::has_directed_cycles ( const graphs::directed_graph &  g, char *const __restrict__  vis, char *const __restrict__  in_stack  )

inlinenoexcept

Returns true if, and only if, the graph has DIRECTED cycles.

Parameters

g	Input graph.
vis	Array of size 'n', where 'n' is the number of vertices of 'g'.
in_stack	Array of size 'n', where 'n' is the number of vertices of 'g'.

Returns

Whether the graph has cycles or not.

has_undirected_cycles() [1/2]

template<class graph_t >

bool lal::detail::has_undirected_cycles ( const graph_t &  g )

noexcept

Returns true if, and only if, the graph has UNDIRECTED cycles.

In case the input graph is a directed graph, reverse edges are considered.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.

Returns

Whether the graph has cycles or not.

has_undirected_cycles() [2/2]

template<class graph_t >

bool lal::detail::has_undirected_cycles ( const graph_t &  g, BFS< graph_t > &  bfs  )

noexcept

Returns true if, and only if, the graph has UNDIRECTED cycles.

In case the input graph is a directed graph, reverse edges are considered.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
bfs	Breadth-First Search object.

Returns

Whether the graph has cycles or not.

head_initial()

template<typename result_t , class arrangement_t >

result_t lal::detail::head_initial ( const graphs::directed_graph &  g, const arrangement_t &  arr  )

noexcept

Proposition of right branching edges in a directed graph.

Template Parameters

result_t	Type of return value.
arrangement_t	Type of arrangement.

Parameters

g	Input directed graph.
arr	Input linear arrangement.

is_graph_a_tree()

template<class graph_t >

bool lal::detail::is_graph_a_tree ( const graph_t &  g )

noexcept

Is the input graph a tree?

By definition, an undirected graph is a tree if it does not contain cycles and has one single connected component. Note that isloated nodes count as single connected components. Directed graphs are allowed.

Parameters

g	Input graph.

Returns

True if, and only if, the graph is a tree.

is_n_C_brute_force_lesseq_than() [1/3]

template<class graph_t >

uint64_t lal::detail::is_n_C_brute_force_lesseq_than ( const graph_t &  g, const linear_arrangement &  arr, uint64_t  upper_bound  )

noexcept

Returns whether the number of crossings is less than a given 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.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arr	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_n_C_brute_force_lesseq_than() [2/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_brute_force_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, const std::vector< uint64_t > &  upper_bounds  )

noexcept

Returns whether the number of crossings is less than a given 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 is applied to every linear arrangement in pi. To each arrangement corresponds only one upper bound.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.
upper_bounds	List of constants (each an upper bound).

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.

is_n_C_brute_force_lesseq_than() [3/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_brute_force_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, uint64_t  upper_bound  )

noexcept

Returns whether the number of crossings is less than a given 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 is applied to every linear arrangement in pi. The upper bound upper_bound is applied to all linear arrangements.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_n_C_dynamic_programming_lesseq_than() [1/3]

template<class graph_t >

uint64_t lal::detail::is_n_C_dynamic_programming_lesseq_than ( const graph_t &  g, const linear_arrangement &  arr, uint64_t  upper_bound  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 is applied to every linear arrangement in pi. The upper bound upper_bound is applied to all linear arrangements.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arr	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_n_C_dynamic_programming_lesseq_than() [2/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_dynamic_programming_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, const std::vector< uint64_t > &  upper_bounds  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 is applied to every linear arrangement in pi. To each arrangement corresponds only one upper bound.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.
upper_bounds	List of constants (each an upper bound).

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.

is_n_C_dynamic_programming_lesseq_than() [3/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_dynamic_programming_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, uint64_t  upper_bound  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 is applied to every linear arrangement in pi. To each arrangement corresponds only one upper bound.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_n_C_ladder_lesseq_than() [1/3]

template<class graph_t >

uint64_t lal::detail::is_n_C_ladder_lesseq_than ( const graph_t &  g, const linear_arrangement &  arr, uint64_t  upper_bound  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arr	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_n_C_ladder_lesseq_than() [2/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_ladder_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, const std::vector< uint64_t > &  upper_bounds  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 is applied to every linear arrangement in pi. To each arrangement corresponds only one upper bound.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.
upper_bounds	List of constants (each an upper bound).

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.

is_n_C_ladder_lesseq_than() [3/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_ladder_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, uint64_t  upper_bound  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 is applied to every linear arrangement in pi. The upper bound upper_bound is applied to all linear arrangements.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_n_C_stack_based_lesseq_than() [1/3]

template<class graph_t >

uint64_t lal::detail::is_n_C_stack_based_lesseq_than ( const graph_t &  g, const linear_arrangement &  arr, uint64_t  upper_bound  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arr	Linear arrangement of the nodes. When omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_n_C_stack_based_lesseq_than() [2/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_stack_based_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, const std::vector< uint64_t > &  upper_bounds  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 is applied to every linear arrangement in pi. To each arrangement corresponds only one upper bound.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.
upper_bounds	List of constants (each an upper bound).

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.

is_n_C_stack_based_lesseq_than() [3/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::is_n_C_stack_based_lesseq_than ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs, uint64_t  upper_bound  )

noexcept

Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 is applied to every linear arrangement in pi. The upper bound upper_bound is applied to all linear arrangements.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.
upper_bound	Constant (upper bound).

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.

is_node_reachable_from()

template<class graph_t >

bool lal::detail::is_node_reachable_from ( const graph_t &  g, const node  source, const node  target  )

noexcept

Is a node reachable from another?

Parameters

g	Input graph.
source	Node where the search starts at.
target	The node we want to know whether it is reachable from source or not.

Returns

True if, and only if, node target is reachable from node source.

is_projective()

template<detail::linarr_type arr_type>

bool lal::detail::is_projective ( const graphs::rooted_tree &  rt, const detail::linarr_wrapper< arr_type > &  arr  )

noexcept

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 lal::linarr::is_planar for further details on the definition of planar arrangements.

Template Parameters

arr_type

Type of arrangement.

Parameters

rt	Input rooted tree
arr	Input linear arrangement.

Returns

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

Precondition

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

is_root_covered()

template<detail::linarr_type arr_type>

bool lal::detail::is_root_covered ( const graphs::rooted_tree &  rt, const detail::linarr_wrapper< arr_type > &  arr  )

noexcept

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

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

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

Template Parameters

arr_type

Type of arrangement.

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

level_sequence_to_ftree() [1/2]

graphs::free_tree lal::detail::level_sequence_to_ftree ( const std::vector< uint64_t > &  L, uint64_t  n, bool  normalise = true, bool  check = true  )

inlinenoexcept

Converts the level sequence of a tree into a graph structure.

See lal::detail::level_sequence_to_ftree(const uint64_t*, uint64_t, bool, bool) for further details.

level_sequence_to_ftree() [2/2]

graphs::free_tree lal::detail::level_sequence_to_ftree ( const uint64_t *const  L, uint64_t  n, bool  normalise = true, bool  check = true  )

inlinenoexcept

Converts the level sequence of a tree into a graph structure.

Examples of level sequences:

• linear tree of n nodes:

      0 1 2 3 4 ... (n-1) n

• star tree of n nodes

      0 1 2 2 2 .... 2 2
         |------------| > (n-1) two's

Parameters

L	The level sequence, in preorder.
n	Number of nodes of the tree.
normalise	Should the tree be normalised?
check	Should it be checked whether the tree is normalized or not?

Returns

The tree built with the sequence level L.

Precondition

n >= 2.

The size of L is exactly n + 1.

The first value of a sequence must be a zero.

The second value of a sequence must be a one.

make_arrangement_permutations() [1/4]

template<class container >

void lal::detail::make_arrangement_permutations ( const graphs::free_tree &  T, node  parent, node  u, const container &  data, position &  pos, linear_arrangement &  arr  )

noexcept

Make an arrangement using permutations.

Template Parameters

container

Object containing the permutations.

Parameters

	T	Input rooted tree.
	parent	Parent of node u.
	u	Root of the current subtree.
	data	The permutations used to construct the arrangement.
[out]	pos	Current position in the arrangement.
[out]	arr	Arrangement constructed.

make_arrangement_permutations() [2/4]

template<class container >

linear_arrangement lal::detail::make_arrangement_permutations ( const graphs::free_tree &  T, node  root, const container &  data  )

noexcept

Make an arrangement using permutations.

Template Parameters

container

Object containing the permutations.

Parameters

T	Input rooted tree.
root	Node used as root.
data	The permutations to construct the arrangement from.

Returns

The arrangement constructed with the permutations.

make_arrangement_permutations() [3/4]

template<class container >

linear_arrangement lal::detail::make_arrangement_permutations ( const graphs::rooted_tree &  T, const container &  data  )

noexcept

Make an arrangement using permutations.

Template Parameters

container

Object containing the permutations.

Parameters

T	Input rooted tree.
data	The permutations to construct the arrangement from.

Returns

The arrangement constructed with the permutations.

make_arrangement_permutations() [4/4]

template<class container >

void lal::detail::make_arrangement_permutations ( const graphs::rooted_tree &  T, node  r, const container &  data, position &  pos, linear_arrangement &  arr  )

noexcept

Make an arrangement using permutations.

Template Parameters

container

Object containing the permutations.

Parameters

	T	Input rooted tree.
	r	Root of the current subtree.
	data	The permutations used to construct the arrangement.
[out]	pos	Current position in the arrangement.
[out]	arr	Arrangement constructed.

make_array()

template<typename T , T... ARGS>

constexpr std::array< T, sizeof...(ARGS)> lal::detail::make_array ( )

constexprnoexcept

Make an array with the values given as parameters of the template.

Template Parameters

T	Type of the array
ARGS	List of values to be stored in the array.

make_array_with_value()

template<typename T , std::size_t array_size, T value_to_fill_with>

constexpr std::array< T, array_size > lal::detail::make_array_with_value ( )

constexprnoexcept

Returns an array initialised at a given value.

Template Parameters

T	Type of the array's elements.
array_size	Size of the array.
value_to_fill_with	The value to fill the array with.

make_array_with_value_impl()

template<typename T , std::size_t size, T v, std::size_t... I>

constexpr std::array< T, size > lal::detail::make_array_with_value_impl ( std::index_sequence< I... >  )

constexprnoexcept

Implementation of lal::detail::make_array_with_value.

Function used by lal::detail::make_array_with_value().

Template Parameters

T	Type of the value.
size	Size of the array.
v	Value to use.
I	Index sequence.

Returns

An array of the given size where all elements are equal to v.

mean_sum_edge_lengths()

template<typename result_t , class graph_t , class arrangement_t >

result_t lal::detail::mean_sum_edge_lengths ( const graph_t &  g, const arrangement_t &  arr  )

noexcept

Average sum of edge lengths in a graph.

Template Parameters

result_t	Type of return value.
graph_t	Type of graph.
arrangement_t	Type of arrangement.

Parameters

g	Input directed graph.
arr	Input linear arrangement.

mpq_divide_mpq()

void lal::detail::mpq_divide_mpq ( mpq_t &  num, const mpq_t &  den  )

inlinenoexcept

Rational-Rational division.

Divide a rational \(r_1\) by another rational \(r_2\).

Parameters

[out]	num	The rational to be divided by \(k\). Result is \(r_1 := r_1/r_2\).
[in]	den	The rational that divides the rational.

mpz_divide_mpq()

void lal::detail::mpz_divide_mpq ( mpq_t &  r, const mpz_t &  k  )

inlinenoexcept

Rational-Integer division.

Divide a rational \(r\) by an integer \(k\).

Parameters

[out]	r	The rational to be divided by \(k\). Result is \(r := r/k\).
[in]	k	The integer that divides the rational.

mpz_pow_mpz()

void lal::detail::mpz_pow_mpz ( mpz_t &  r, const mpz_t &  b, const mpz_t &  e  )

inlinenoexcept

Computes the exponentiation of a big integer to another big integer.

Fast exponentiation algorithm.

This function has, as an exception, its output parameter as its first parameter.

Parameters

[out]	r	Result. \(r = b^e\).
[in]	b	Base.
[in]	e	Exponent.

n_C_brute_force() [1/2]

template<class graph_t >

uint64_t lal::detail::n_C_brute_force ( const graph_t &  g, const linear_arrangement &  arr  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

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

Returns

The number of crossings \(C\).

n_C_brute_force() [2/2]

template<class graph_t >

std::vector< uint64_t > lal::detail::n_C_brute_force ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.

Returns

A list \(L\) where \(L_i = C_{\pi_i}(g)\).

Precondition

None of the arrangements is empty.

n_C_dynamic_programming() [1/2]

template<class graph_t >

uint64_t lal::detail::n_C_dynamic_programming ( const graph_t &  g, const linear_arrangement &  arr  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

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

Returns

The number of crossings \(C\).

n_C_dynamic_programming() [2/2]

template<class graph_t >

std::vector< uint64_t > lal::detail::n_C_dynamic_programming ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.

Returns

A list \(L\) where \(L_i = C_{\pi_i}(g)\).

Precondition

None of the arrangements is empty.

n_C_ladder() [1/2]

template<class graph_t >

uint64_t lal::detail::n_C_ladder ( const graph_t &  g, const linear_arrangement &  arr  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

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

Returns

The number of crossings \(C\).

n_C_ladder() [2/2]

template<class graph_t >

std::vector< uint64_t > lal::detail::n_C_ladder ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.

Returns

A list \(L\) where \(L_i = C_{\pi_i}(g)\).

Precondition

None of the arrangements is empty.

n_C_stack_based() [1/2]

template<class graph_t >

uint64_t lal::detail::n_C_stack_based ( const graph_t &  g, const linear_arrangement &  arr  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

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

Returns

The number of crossings \(C\).

n_C_stack_based() [2/2]

template<class graph_t >

std::vector< uint64_t > lal::detail::n_C_stack_based ( const graph_t &  g, const std::vector< linear_arrangement > &  arrs  )

noexcept

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

Given a graph, and a linear arrangement of its nodes, computes by brute force the number of edges that cross in such linear arrangement. If the arrangement is not specified, the identity arrangement is used.

Template Parameters

graph_t

Type of graph.

Parameters

g	Input graph.
arrs	List of \(k\) linear arrangements of the nodes \(\Pi = \{\pi_i\}_{i=1}^k\). When one is omitted, \(\pi_I\) is used.

Returns

A list \(L\) where \(L_i = C_{\pi_i}(g)\).

Precondition

None of the arrangements is empty.

operate_power() [1/2]

void lal::detail::operate_power ( mpq_t &  r, const mpz_t &  p  )

inlinenoexcept

Power operation.

Raise a rational value \(r\) to a certain power \(p\).

Parameters

[out]	r	Rational value. Result is \(r = r^p\).
[in]	p	Exponent.

operate_power() [2/2]

void lal::detail::operate_power ( mpq_t &  r, uint64_t  p  )

inlinenoexcept

Power operation.

Raise a rational value \(r\) to a certain power \(p\).

Parameters

[out]	r	Rational value. Result is \(r = r^p\).
[in]	p	Exponent.

predict_C_using_edge_lengths()

template<typename result_t , class graph_t , class arrangement_t >

result_t lal::detail::predict_C_using_edge_lengths ( const graph_t &  g, const arrangement_t &  arr  )

noexcept

Predicted number of crossings based on the sum of edge lengths.

See [16] for further details. This functions implements \(E_2[C]\).

Template Parameters

result_t	Type of the return value.
graph_t	Type of graph.
arrangement_t	Type of arrangement.

Parameters

g	Input graph.
arr	Input arrangement.

Returns

The value of \(E_2[C]\).

Prufer_sequence_to_ftree() [1/2]

graphs::free_tree lal::detail::Prufer_sequence_to_ftree ( const std::vector< uint64_t > &  seq, uint64_t  n, bool  normalise = true, bool  check = true  )

inlinenoexcept

Converts the Prüfer sequence of a labelled tree into a tree structure.

For details on Prüfer sequences, see [32].

Parameters

seq	The Prufer sequence sequence.
n	Number of nodes of the tree.
normalise	Should the tree be normalised?
check	Should it be checked whether the tree is normalized or not?

Returns

The tree built with seq.

Prufer_sequence_to_ftree() [2/2]

graphs::free_tree lal::detail::Prufer_sequence_to_ftree ( const uint64_t *const  seq, uint64_t  n, bool  normalise = true, bool  check = true  )

inlinenoexcept

Converts the Prüfer sequence of a labelled tree into a tree structure.

For details on Prüfer sequences, see [32].

Parameters

seq	The Prufer sequence sequence.
n	Number of nodes of the tree.
normalise	Should the tree be normalised?
check	Should it be checked whether the tree is normalized or not?

Returns

The tree built with seq.

retrieve_centre()

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

std::pair< node, node > lal::detail::retrieve_centre ( const tree_t &  t, node  X  )

noexcept

Calculate the centre of the connected component that has node x.

See Centre and centroid of a tree for details on what the centre of a tree is.

A graph of type lal::graphs::tree may lack some edges tree so it has several connected components. Vertex x belongs to one of these connected components.

This method finds the central nodes of the connected components node 'x' belongs to.

Template Parameters

tree_t

type of tree.

Parameters

t	Input tree.
X	Input node.

Precondition

Input tree t may be a forest.

Returns

A tuple of the two nodes in the centre. If the tree has a single central node, only the first node is valid and the second is assigned an invalid vertex index. It is guaranteed that the first vertex has smaller index value than the second.

retrieve_centroid() [1/2]

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

std::pair< node, node > lal::detail::retrieve_centroid ( const tree_t &  t )

noexcept

Calculate the centroid of the tree t.

See page Centre and centroid of a tree for a definition of centre and centroid.

Template Parameters

tree_t

Type of the input tree.

Parameters

t	Input tree.

Returns

A tuple of two values: the nodes in the centroid. If the tree has a single centroidal node, only the first node is valid and the second is assigned an invalid vertex index. It is guaranteed that the first vertex has smaller index value than the second.

retrieve_centroid() [2/2]

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

std::pair< node, node > lal::detail::retrieve_centroid ( const tree_t &  t, const node  x  )

noexcept

Calculate the centroid of the connected component that has node x.

For details on the parameters and return value see documentation of the function above.

Template Parameters

tree_t

Type of tree.

Parameters

t	Input tree
x	Node belonging to a connected component whose centroid we want.

Returns

A tuple of two values: the nodes in the centroid. If the tree has a single centroidal node, only the first node is valid and the second is assigned an invalid vertex index. It is guaranteed that the first vertex has smaller index value than the second.

right_branching_edges()

template<class arrangement_t >

uint64_t lal::detail::right_branching_edges ( const graphs::directed_graph &  g, const arrangement_t &  arr  )

noexcept

Number of right branching edges in a directed graph.

Template Parameters

arrangement_t

Type of arrangement.

Parameters

g	Input directed graph.
arr	Input linear arrangement.

set_edges()

template<class graph_t >

std::vector< edge > lal::detail::set_edges ( const graph_t &  g )

noexcept

Enumerate the set of edges of the input graph g.

Parameters

g	Input graph.

Returns

A vector with all g's edges.

set_pairs_independent_edges()

template<class graph_t >

std::vector< edge_pair > lal::detail::set_pairs_independent_edges ( const graph_t &  g, uint64_t  qs  )

noexcept

Enumerate the set of pairs of independent edges of the input graph g.

Parameters

g	Input graph.
qs	Total amount of pairs of independent edges.

Returns

A vector with all g's pairs of independent edges.

sum_edge_lengths()

template<class graph_t , class arrangement_t >

uint64_t lal::detail::sum_edge_lengths ( const graph_t &  g, const arrangement_t &  arr  )

noexcept

Sum of edge lengths in a graph.

Template Parameters

graph_t	Type of graph.
arrangement_t	Type of arrangement.

Parameters

g	Input directed graph.
arr	Input linear arrangement.

syntactic_dependency_structure_to_string()

constexpr std::string_view lal::detail::syntactic_dependency_structure_to_string ( const linarr::syntactic_dependency_structure &  tt )

constexprnoexcept

Converts a value of the enumeration lal::linarr::syntactic_dependency_structure into a string.

tree_diameter()

template<class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

uint64_t lal::detail::tree_diameter ( const tree_t &  t, node  x  )

noexcept

Calculate the diameter of a tree.

See Diameter of a tree for details on the definition of the diameter of a tree.

The diameter of the connected component to which node x belongs to.

Template Parameters

tree_t

Type of tree.

Parameters

t	Input tree.
x	Input node.

Returns

The diameter of the tree.

update_unionfind_after_add_edge()

template<class tree_t >

void lal::detail::update_unionfind_after_add_edge ( const tree_t &  t, const node  u, const node  v, node *const  root_of, uint64_t *const  root_size  )

noexcept

Update the Union-Find data structure after an edge addition to a tree.

This function updates the union-find data structure of a tree after the addition of the edge between the edges 'u' and 'v'.

Template Parameters

tree_t

Type of tree.

Parameters

t	Input tree
u	Node
v	Node
root_of	Pointer to an array where root_of[s] = t if the root of the connected component of s is t
root_size	Sizes of each connected component.

Precondition

The edge \(\{u,v\}\) must exist.

update_unionfind_after_remove_edge()

template<class tree_t >

void lal::detail::update_unionfind_after_remove_edge ( const tree_t &  t, const node  u, const node  v, node *const  root_of, uint64_t *const  root_size  )

noexcept

Updates Union-Find after an edge removal.

This function updates the union-find data structure of a tree after the removal of the edge between the edges 'u' and 'v'.

Template Parameters

tree_t

Type of tree.

Parameters

t	Input tree
u	Node
v	Node
root_of	Pointer to an array where root_of[s] = t if the root of the connected component of s is t
root_size	Sizes of each connected component.

Precondition

The edge \(\{u,v\}\) must exist.

update_unionfind_before_remove_edges_incident_to() [1/2]

template<class tree_t >

void lal::detail::update_unionfind_before_remove_edges_incident_to ( BFS< tree_t > &  bfs, node  v, node *const  root_of, uint64_t *const  root_size  )

noexcept

Update Union-Find after a vertex removal.

This function updates the union-find data structure of a tree prior to the removal of the edge (u,v).

This function is called by the function lal::detail::UnionFind_update_roots_before_remove_all_incident_to

In particular, it updates the information associated to the vertices found in the direction (u,v).

Template Parameters

tree_t

Type of tree.

Parameters

bfs	Breadth-First Search object.
v	Node to be removed.
root_of	Pointer to an array where root_of[s] = t if the root of the connected component of s is t
root_size	Sizes of each connected component.

update_unionfind_before_remove_edges_incident_to() [2/2]

template<typename tree_t >

void lal::detail::update_unionfind_before_remove_edges_incident_to ( const tree_t &  t, node  u, node *const  root_of, uint64_t *const  root_size  )

noexcept

Update Union-Find after a vertex removal.

This function updates the union-find data structure of a tree prior to the removal of the edge (u,v).

This function is called by the function lal::detail::UnionFind_update_roots_before_remove_all_incident_to

In particular, it updates the information associated to the vertices found in the direction (u,v).

Template Parameters

tree_t

Type of tree.

Parameters

t	Input tree.
u	Node to be removed.
root_of	Pointer to an array where root_of[s] = t if the root of the connected component of s is t
root_size	Sizes of each connected component.