Detail namespace. More...

Namespaces
namespace	bipartite_opt_utils
	Utilities for the various optimal linear arrangement algorithms.

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	arrangement_wrapper
	A wrapper to easily use identity arrangements. More...

struct	array
	Wrapper of a C array for automatic deallocation of memory. More...

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

class	chunks_Anderson
	Implementation of Anderson's algorithm for chunking. More...

class	chunks_generic
	Basic algorithms existent in every definition of chunking. More...

class	chunks_Macutek
	Implementation of Mačutek's algorithm for chunking. More...

struct	conditional_list
	Generalization of std::conditional_list. 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...

class	level_signature
	A class that implements level signatures of an array. More...

struct	node_size
	Struct used in many algorithms to sort vertices according to some integer value. More...

class	queue_array
	Simple array-like fixed-size queue. More...

class	set_array
	A set-like data structure implemented with an array. More...

struct	type_sequence
	A sequence of types. More...

Typedefs
typedef level_signature< level_signature_type::per_vertex >	level_signature_per_vertex
	A useful typedef for level signatures per vertex.

typedef level_signature< level_signature_type::per_position >	level_signature_per_position
	A useful typedef for level signatures per position.

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	arrangement_type { identity , nonidentity }
	Type of arrangement. More...

enum class	level_signature_type { per_vertex , per_position }
	Types of level signature. 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
arrangement_wrapper< arrangement_type::identity >	identity_arr (const linear_arrangement &arr) noexcept
	Shorthand for an identity arrangement.

arrangement_wrapper< arrangement_type::nonidentity >	nonidentity_arr (const linear_arrangement &arr) noexcept
	Shorthand for a nonidentity arrangement.

template<class container >
void	make_arrangement_permutations (const graphs::rooted_tree &T, const node r, const container &data, position &pos, linear_arrangement &arr) noexcept
	Make an arrangement using permutations.

template<class container >
linear_arrangement	make_arrangement_permutations (const graphs::rooted_tree &T, const container &data) noexcept
	Make an arrangement using permutations.

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.

template<class container >
linear_arrangement	make_arrangement_permutations (const graphs::free_tree &T, node root, const container &data) noexcept
	Make an arrangement using permutations.

template<class graph_t >
graph_t	from_edge_list_to_graph (const edge_list &edge_list, const bool normalize, const bool check) noexcept
	Converts an edge list into a graph.

template<class graph_t >
graph_t	from_head_vector_to_graph (const head_vector &hv, const bool normalize, const bool check) noexcept
	Transforms a head vector in a directed graph.

template<typename tree_t , bool ensure_root_is_returned, bool free_tree_plus_root = ensure_root_is_returned and std::is_same_v<tree_t, graphs::free_tree>>
std::conditional_t< free_tree_plus_root, std::pair< tree_t, node >, tree_t >	from_head_vector_to_tree (std::stringstream &ss) noexcept
	Transforms a head vector in a 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 > >	from_head_vector_to_tree (const head_vector &hv, const bool normalize, const bool check) noexcept
	Converts a head vector into a tree.

template<class arrangement_t >
head_vector	from_tree_to_head_vector (const graphs::rooted_tree &t, const arrangement_t &arr) noexcept
	Constructs the head vector representation of a tree.

template<class arrangement_t >
head_vector	from_tree_to_head_vector (const graphs::free_tree &t, const arrangement_t &arr, const node r) noexcept
	Constructs the head vector representation of a tree.

template<class tree_t >
tree_t	from_level_sequence_to_tree_small (const uint64_t *const L, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the level sequence of a tree into a graph structure.

template<class tree_t >
tree_t	from_level_sequence_to_tree_large (const uint64_t *const L, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the level sequence of a tree into a graph structure.

template<class tree_t >
tree_t	from_level_sequence_to_tree (const uint64_t *const L, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the level sequence of a tree into a graph structure.

template<class tree_t >
tree_t	from_level_sequence_to_tree_small (const std::vector< uint64_t > &L, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the level sequence of a tree into a graph structure.

template<class tree_t >
tree_t	from_level_sequence_to_tree_large (const std::vector< uint64_t > &L, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the level sequence of a tree into a graph structure.

template<class tree_t >
tree_t	from_level_sequence_to_tree (const std::vector< uint64_t > &L, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the level sequence of a tree into a graph structure.

graphs::free_tree	from_Prufer_sequence_to_ftree (const uint64_t *const seq, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the Prüfer sequence of a labelled tree into a tree structure.

graphs::free_tree	from_Prufer_sequence_to_ftree (const std::vector< uint64_t > &seq, const uint64_t n, const bool normalize, const bool check) noexcept
	Converts the Prüfer sequence of a labelled tree into a tree structure.

bool	find_cycle (const graphs::directed_graph &g, const node u, char const __restrict__ visited, char const __restrict__ in_stack) noexcept
	Returns true if, and only if, the graph has cycles.

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.

bool	has_directed_cycles (const graphs::directed_graph &g) noexcept
	Returns true if, and only if, the graph has DIRECTED cycles.

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.

template<class graph_t >
bool	has_undirected_cycles (const graph_t &g) noexcept
	Returns true if, and only if, the graph has UNDIRECTED cycles.

template<class graph_t >
std::vector< edge >	set_edges (const graph_t &g) noexcept
	Enumerate the set of edges of the input graph g.

template<class graph_t >
std::vector< edge_pair >	set_pairs_independent_edges (const graph_t &g, const uint64_t qs) noexcept
	Enumerate the set of pairs of independent edges of the input graph g.

template<class graph_t >
bool	is_graph_a_tree (const graph_t &g) noexcept
	Is the input graph a tree?

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?

template<bool get_subsizes>
std::pair< std::vector< edge >, uint64_t * >	get_edges_subtree (const graphs::rooted_tree &T, const node u, const bool relabel) noexcept
	Retrieves the edges of a subtree.

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.

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 r, uint64_t *const sizes) noexcept
	Calculate the size of every subtree of tree t.

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

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.

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 > &tree_types) noexcept
	Classify a tree into one of the types graphs::tree_type.

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 the addition of an edge.

template<class tree_t >
void	update_unionfind_after_add_edges (const tree_t &t, const edge_list &edges, node const root_of, uint64_t const root_size) noexcept
	Update the Union-Find data structure after the addition of several edges.

template<class tree_t >
void	update_unionfind_after_add_rem_edges_bulk (const tree_t &t, node const root_of, uint64_t const root_size) noexcept
	Update the Union-Find data structure after several edges have been operated in bulk.

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 the removal of an edge.

template<class tree_t >
void	update_unionfind_after_remove_edges (const tree_t &t, const edge_list &edges, node const root_of, uint64_t const root_size) noexcept
	Update the Union-Find data structure after the addition of several edges.

template<class tree_t >
void	update_unionfind_before_remove_edges_incident_to (BFS< tree_t > &bfs, const node v, node const root_of, uint64_t const root_size) noexcept
	Update Union-Find after the removal of a vertex.

template<typename tree_t >
void	update_unionfind_before_remove_edges_incident_to (const tree_t &t, const node u, node const root_of, uint64_t const root_size) noexcept
	Update Union-Find after a vertex removal.

template<class graph_t , typename char_type , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t > and std::is_integral_v< char_type >, bool > = true>
void	get_bool_neighbors (const graph_t &g, const node u, char_type *const neighs) noexcept
	Retrieves the neighbors of a node in an undirected graph as a list of 0-1 values.

void	append_adjacency_lists (std::vector< neighbourhood > &target, const std::vector< neighbourhood > &source) noexcept
	Append adjacency list 'source' to list 'target'.

template<bool decide>
std::conditional_t< decide, bool, std::vector< io::head_vector_error > >	find_errors (const head_vector &hv) noexcept
	Find errors in a head vector.

template<bool decide>
std::conditional_t< decide, bool, std::vector< io::head_vector_error > >	find_errors (const std::string &current_line) noexcept
	Find errors in a line of a treebank.

template<bool decide>
std::conditional_t< decide, bool, io::treebank_file_report >	check_correctness_treebank (const std::string &treebank_filename) noexcept
	Find errors in a treebank file.

template<bool decide>
std::conditional_t< decide, bool, io::treebank_collection_report >	check_correctness_treebank_collection (const std::string &main_file_name, const std::size_t n_threads) noexcept
	Find errors in a treebank collection.

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?

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?

template<class graph_t >
uint64_t	is_n_C_brute_force_lesseq_than (const graph_t &g, const linear_arrangement &arr, const uint64_t upper_bound) noexcept
	Returns whether the number of crossings is less than a given constant.

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

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.

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?

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?

template<class graph_t >
uint64_t	is_n_C_dynamic_programming_lesseq_than (const graph_t &g, const linear_arrangement &arr, const uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound.

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.

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?

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?

template<class graph_t >
uint64_t	is_n_C_ladder_lesseq_than (const graph_t &g, const linear_arrangement &arr, const uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound.

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.

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?

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?

template<class graph_t >
uint64_t	is_n_C_stack_based_lesseq_than (const graph_t &g, const linear_arrangement &arr, const uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound.

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 uint64_t upper_bound) noexcept
	Fast calculation of \(C\) if it is less than or equal to an upper bound.

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.

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.

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.

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.

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.

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

template<class graph_t , level_signature_type t>
bool	is_level_signature_nonincreasing (const graph_t &g, const level_signature< t > &levels, const linear_arrangement &arr) noexcept
	Returns true if the level sequence follows that of a maximum arrangement.

template<class graph_t , level_signature_type t>
bool	no_two_adjacent_vertices_have_same_level (const graph_t &g, const level_signature< t > &levels, const linear_arrangement &arr) noexcept
	Returns true if no two adjacent vertices (in the graph) have the same level value.

template<class graph_t , level_signature_type t>
bool	no_vertex_in_antenna_is_thistle (const graph_t &g, const std::vector< properties::branchless_path > &bps, const level_signature< t > &levels, const linear_arrangement &arr) noexcept
	Returns true if none of the vertices in the antennas of the graph is a thistle.

template<class graph_t , level_signature_type t>
bool	at_most_one_thistle_in_bridges (const graph_t &g, const std::vector< properties::branchless_path > &bps, const level_signature< t > &levels, const linear_arrangement &arr) noexcept
	Returns true if none of the vertices in the antennas of the graph is a thistle.

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, const position cur_pos, std::vector< depflux > &flux, std::vector< edge > &cur_deps) noexcept
	Calculate the dependencies and their span.

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.

template<class arrangement_t >
bool	is_root_covered (const graphs::rooted_tree &rt, const arrangement_t &arr) noexcept
	Is the root of a rooted tree covered in a given arrangement?

template<class arrangement_t >
bool	is_projective (const graphs::rooted_tree &rt, const arrangement_t &arr) noexcept
	Is a given arrangement projective?

template<class arrangement_t >
bool	is_bipartite__connected (const properties::bipartite_graph_coloring &c, const arrangement_t &arr) noexcept
	Is a given arrangement bipartite?

template<class graph_t , class arrangement_t >
bool	is_bipartite (const graph_t &g, const arrangement_t &arr) noexcept
	Is a given arrangement bipartite?

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.

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.

constexpr bool	is_per_vertex (const level_signature_type &t) noexcept
	Returns true if the template parameter is lal::detail::level_signature_type::per_vertex.

constexpr bool	is_per_position (const level_signature_type &t) noexcept
	Returns true if the template parameter is lal::detail::level_signature_type::per_position.

template<level_signature_type t, class graph_t >
bool	is_thistle_vertex (const graph_t &g, const level_signature< t > &levels, const node_t u, const linear_arrangement &arr={}) noexcept
	Returns whether or not the input vertex is a thistle vertex.

template<level_signature_type t, class graph_t >
void	calculate_level_signature (const graph_t &g, const linear_arrangement &arr, level_signature< t > &L) noexcept
	Calculates the level signature of an arrangement of a graph.

template<level_signature_type t, class graph_t >
level_signature< t >	calculate_level_signature (const graph_t &g, const linear_arrangement &arr) noexcept
	Calculates the level signature of an arrangement of a graph.

template<class level_signature_t >
level_signature_t	mirror_level_signature (const level_signature_t &L) noexcept
	Mirrors a level signature.

constexpr std::string_view	syntactic_dependency_tree_to_string (const linarr::syntactic_dependency_tree_type &tt) noexcept

template<typename T >
constexpr uint64_t	to_uint64 (const T &t) noexcept
	Conversion to uint64_t.

template<typename T >
constexpr int64_t	to_int64 (const T &t) noexcept
	Conversion to int64_t.

template<typename T >
constexpr uint32_t	to_uint32 (const T &t) noexcept
	Conversion to uint32_t.

template<typename T >
constexpr int32_t	to_int32 (const T &t) noexcept
	Conversion to int32_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 iterator_t , typename value_t >
iterator_t	find_sorted (const iterator_t begin, const iterator_t end, const std::size_t size, const value_t &v, const std::size_t min_size=64) noexcept
	Finds an element within the sorted range [begin, end).

template<typename iterator_t , typename value_t >
bool	exists_sorted (const iterator_t begin, const iterator_t end, const std::size_t size, const value_t &v, const std::size_t min_size=64) noexcept
	Finds an element within the sorted range [begin, end).

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.

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 initialized at a given value.

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.

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.

void	mpz_divide_mpq (mpq_t &r, const mpz_t &k) noexcept
	Rational-Integer division.

void	mpq_divide_mpq (mpq_t &num, const mpq_t &den) noexcept
	Rational-Rational division.

void	operate_power (mpq_t &r, uint64_t p) noexcept
	Power operation.

void	operate_power (mpq_t &r, const mpz_t &p) noexcept
	Power operation.

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 >
void	expand_branchless_path (const tree_t &t, const node u, const node v, BFS< tree_t > &bfs, std::vector< properties::branchless_path > &res, properties::branchless_path &p) noexcept
	Completes the branchless path.

template<class tree_t >
std::vector< properties::branchless_path >	branchless_paths_compute (const tree_t &t) noexcept
	Finds all branchless paths in a tree.

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, const node X) noexcept
	Calculate the centre of the connected component that has node x.

constexpr bool	is_m1 (const centroid_results &m) noexcept
	Is mode m equal to lal::detail::centroid_results::only_one_centroidal.

constexpr bool	is_m2 (const centroid_results &m) noexcept
	Is mode m equal to lal::detail::centroid_results::full_centroid.

constexpr bool	is_m3 (const centroid_results &m) noexcept
	Is mode m equal to lal::detail::centroid_results::full_centroid_plus_subtree_sizes.

constexpr bool	is_m4 (const centroid_results &m) noexcept
	Is mode m equal to lal::detail::centroid_results::full_centroid_plus_edge_sizes.

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< is_m1(mode), is_m2(mode), is_m3(mode), is_m4(mode) >, type_sequence< node, std::pair< node, node >, std::pair< std::pair< node, node >, array< uint64_t > >, std::pair< std::pair< node, node >, array< edge_size > > > >	find_centroidal_vertex (const tree_t &t, const node x) noexcept
	Calculates the centroid of a tree.

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, const node x, std::vector< std::vector< node_size > > &L) noexcept
	Calculates the centroid and the corresponding rooted 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 >	retrieve_centroid (const tree_t &t, const node x=0) noexcept
	Calculate the centroid of the connected component that has node x.

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, const node x) noexcept
	Calculate the diameter of a tree.

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.

void	assign_name_and_keep (const graphs::rooted_tree &t, const node u, std::size_t idx, array< std::string > &aux_memory_for_names, array< std::string > &keep_name_of) noexcept
	Assigns a name to node 'u', root of the current subtree.

std::string	assign_name (const graphs::rooted_tree &t, const node u, array< std::string > &names, std::size_t idx) noexcept
	Assigns a name to node 'u', root of the current subtree.

bool	are_rooted_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_tree_type, linarr::__syntactic_dependency_tree_size >	array_of_syntactic_dependency_trees
	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

◆ arrangement_type

enum class lal::detail::arrangement_type

strong

Type of arrangement.

Used to call functions that have arrangements as input parameters.

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

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

◆ level_signature_type

enum class lal::detail::level_signature_type

strong

Types of level signature.

Enumerator

per_vertex

Given per vertex.

The level value is queried via a vertex u, "L[u]".

per_position

Given per position.

The level value is queried via a position p, "L[p]".

Function Documentation

◆ alpha()

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

inlinenodiscardconstexprnoexcept

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.

◆ are_rooted_trees_isomorphic()

bool lal::detail::are_rooted_trees_isomorphic	(	const graphs::rooted_tree &	t1,
		const graphs::rooted_tree &	t2 )

inlinenodiscardnoexcept

Test whether two rooted trees are isomorphic or not.

Parameters

t1	First rooted tree.
t2	Second rooted tree.

Returns: True or false.

◆ assign_name()

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

inlinenodiscardnoexcept

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,
		const node	u,
		std::size_t	idx,
		array< std::string > &	aux_memory_for_names,
		array< std::string > &	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 better be safe than sorry.

◆ at_most_one_thistle_in_bridges()

template<class graph_t , level_signature_type t>

bool lal::detail::at_most_one_thistle_in_bridges	(	const graph_t &	g,
		const std::vector< properties::branchless_path > &	bps,
		const level_signature< t > &	levels,
		const linear_arrangement &	arr )

inlinenodiscardnoexcept

Returns true if none of the vertices in the antennas of the graph is a thistle.

Checks that no vertex in any antenna of the tree is a thistle vertex in the input arrangement. This is a necessary condition for an arrangement to be maximum (in sum of edge lengths), as shown in [7].

When the level signature is defined on a 'per vertex' basis, the arrangement is not needed.

Template Parameters

t	Level signature type.
graph_t	Type of graph.

Parameters

g	Input graph.
arr	Input arrangement.
levels	signature of the arrangement.
bps	All Branchless Paths of the tree.

Returns: Whether or not the level sequence satisfies the condition.

◆ beta()

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

inlinenodiscardconstexprnoexcept

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.

◆ branchless_paths_compute()

template<class tree_t >

std::vector< properties::branchless_path > lal::detail::branchless_paths_compute ( const tree_t & t )

nodiscardnoexcept

Finds all branchless paths in a tree.

Template Parameters

tree_t Type of tree.

Parameters

t	Input tree.

Returns: The list of all branchless paths.

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

nodiscardnoexcept

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

inlinenoexcept

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 [30] (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 lal::graphs::free_tree t = ... ;
std::vector<pair<edge,uint64_t>> sizes_edges(2*t.get_num_edges());
auto it = sizes_edges.begin();
lal::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,
		const 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_level_signature() [1/2]

template<level_signature_type t, class graph_t >

level_signature< t > lal::detail::calculate_level_signature	(	const graph_t &	g,
		const linear_arrangement &	arr )

nodiscardnoexcept

Calculates the level signature of an arrangement of a graph.

Template Parameters

t	Level signature type.
graph_t	Type of graph.

Parameters

g	Input graph.
arr	Input arrangement.

Returns: The level sequence of an arrangement per vertex.

◆ calculate_level_signature() [2/2]

template<level_signature_type t, class graph_t >

void lal::detail::calculate_level_signature	(	const graph_t &	g,
		const linear_arrangement &	arr,
		level_signature< t > &	L )

noexcept

Calculates the level signature of an arrangement of a graph.

Template Parameters

t	Level signature type.
graph_t	Type of graph.

Parameters

	g	Input graph.
	arr	Input arrangement.
[out]	L	Level signature of the arrangement of the input graph.

Precondition: Parameter L is initialized at 0.

◆ calculate_weight()

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

inlinenodiscardnoexcept

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,
		const node	x,
		std::vector< std::vector< node_size > > &	L )

nodiscardnoexcept

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, io::treebank_file_report > lal::detail::check_correctness_treebank ( const std::string & treebank_filename )

nodiscardnoexcept

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, io::treebank_collection_report > lal::detail::check_correctness_treebank_collection	(	const std::string &	main_file_name,
		const std::size_t	n_threads )

nodiscardnoexcept

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 > &	tree_types )

noexcept

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

Template Parameters

tree_t Type of tree.

Parameters

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

◆ exists_sorted()

template<typename iterator_t , typename value_t >

bool lal::detail::exists_sorted	(	const iterator_t	begin,
		const iterator_t	end,
		const std::size_t	size,
		const value_t &	v,
		const std::size_t	min_size = 64 )

inlinenodiscardnoexcept

Finds an element within the sorted range [begin, end).

Template Parameters

iterator_t	Iterator type.
value_t	Value type.

Parameters

begin	Pointer at the first element of the range.
end	Pointer at the last element of the range.
size	The number of elements within the range.
v	The value to search for.
min_size	The minimum number of elements for the function to choose std::lower_bound over std::find.

Returns: Whether v exists in the range or not.

Precondition: The range [begin, end) is entirely sorted.

◆ expand_branchless_path()

template<class tree_t >

void lal::detail::expand_branchless_path	(	const tree_t &	t,
		const node	u,
		const node	v,
		BFS< tree_t > &	bfs,
		std::vector< properties::branchless_path > &	res,
		properties::branchless_path &	p )

noexcept

Completes the branchless path.

The first vertex of degree different from 2 is vertex u. And the next vertex in the sequence is vertex v.

Template Parameters

tree_t Type of tree.

Parameters

t	Input tree.
u	First vertex of the path.
v	Second vertex of the path.
bfs	Breadth-First Search traversal object.
res	Vector containing all branchless paths.
p	Current branchless path.

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

nodiscardnoexcept

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< is_m1(mode), is_m2(mode), is_m3(mode), is_m4(mode) >, type_sequence< node, std::pair< node, node >, std::pair< std::pair< node, node >, array< uint64_t > >, std::pair< std::pair< node, node >, array< edge_size > > > > lal::detail::find_centroidal_vertex	(	const tree_t &	t,
		const node	x )

nodiscardnoexcept

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 == lal::detail::centroid_results::only_one_centroidal, the result of the function is a node.
mode == lal::detail::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 == lal::detail::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 == lal::detail::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,
		const node	u,
		char *const __restrict__	visited,
		char *const __restrict__	in_stack )

inlinenodiscardnoexcept

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::head_vector_error > > lal::detail::find_errors ( const head_vector & hv )

nodiscardnoexcept

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.

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::head_vector_error > > lal::detail::find_errors ( const std::string & current_line )

nodiscardnoexcept

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.

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

◆ find_sorted()

template<typename iterator_t , typename value_t >

iterator_t lal::detail::find_sorted	(	const iterator_t	begin,
		const iterator_t	end,
		const std::size_t	size,
		const value_t &	v,
		const std::size_t	min_size = 64 )

inlinenodiscardnoexcept

Finds an element within the sorted range [begin, end).

Template Parameters

iterator_t	Iterator type.
value_t	Value type.

Parameters

begin	Pointer at the first element of the range.
end	Pointer at the last element of the range.
size	The number of elements within the range.
v	The value to search for.
min_size	The minimum number of elements for the function to choose std::lower_bound over std::find.

Returns: An iterator to the element v within the input range.

Precondition: The range [begin, end) is entirely sorted.

◆ from_edge_list_to_graph()

template<class graph_t >

graph_t lal::detail::from_edge_list_to_graph	(	const edge_list &	edge_list,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

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.
normalize	Should the graph be normalized?
check	In case the graph is not to be normalized, 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_graph()

template<class graph_t >

graph_t lal::detail::from_head_vector_to_graph	(	const head_vector &	hv,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

Transforms a head vector in a directed graph.

Template Parameters

graph_t The type of graph.

Parameters

hv	The input head vector.
normalize	Normalize the grpah or not?
check	Check whether the graph is normalized or not?

Returns: A graph.

◆ from_head_vector_to_tree() [1/2]

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,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

Converts a head vector into a tree.

Template Parameters

tree_t Type of input tree

Parameters

hv	Input head vector.
normalize	Normalize the resulting tree.
check	Check whether the constructed tree is normalized.

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

◆ from_head_vector_to_tree() [2/2]

template<typename tree_t , bool ensure_root_is_returned, bool free_tree_plus_root = ensure_root_is_returned and std::is_same_v<tree_t, graphs::free_tree>>

std::conditional_t< free_tree_plus_root, std::pair< tree_t, node >, tree_t > lal::detail::from_head_vector_to_tree ( std::stringstream & ss )

nodiscardnoexcept

Transforms a head vector in a tree.

Reads the head vector from a stream object.

Template Parameters

tree_t The type of tree.

Parameters

ss	Stream to read the head vector from.

Returns: Either a pair of free tree and its root, or a rooted tree.

◆ from_level_sequence_to_tree() [1/2]

template<class tree_t >

tree_t lal::detail::from_level_sequence_to_tree	(	const std::vector< uint64_t > &	L,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

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

See lal::detail::from_level_sequence_to_tree for further details.

◆ from_level_sequence_to_tree() [2/2]

template<class tree_t >

tree_t lal::detail::from_level_sequence_to_tree	(	const uint64_t *const	L,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

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

Template Parameters

tree_t The type of tree.

Parameters

L	The level sequence, in preorder.
n	Number of nodes of the tree.
normalize	Should the tree be normalized?
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.

◆ from_level_sequence_to_tree_large() [1/2]

template<class tree_t >

tree_t lal::detail::from_level_sequence_to_tree_large	(	const std::vector< uint64_t > &	L,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

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

See lal::detail::from_level_sequence_to_tree for further details.

◆ from_level_sequence_to_tree_large() [2/2]

template<class tree_t >

tree_t lal::detail::from_level_sequence_to_tree_large	(	const uint64_t *const	L,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

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

Template Parameters

tree_t The type of tree.

Parameters

L	The level sequence, in preorder.
n	Number of nodes of the tree.
normalize	Should the tree be normalized?
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.

◆ from_level_sequence_to_tree_small() [1/2]

template<class tree_t >

tree_t lal::detail::from_level_sequence_to_tree_small	(	const std::vector< uint64_t > &	L,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

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

See lal::detail::from_level_sequence_to_tree for further details.

◆ from_level_sequence_to_tree_small() [2/2]

template<class tree_t >

tree_t lal::detail::from_level_sequence_to_tree_small	(	const uint64_t *const	L,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

nodiscardnoexcept

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

Template Parameters

tree_t The type of tree.

Parameters

L	The level sequence, in preorder.
n	Number of nodes of the tree.
normalize	Should the tree be normalized?
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.

◆ from_Prufer_sequence_to_ftree() [1/2]

graphs::free_tree lal::detail::from_Prufer_sequence_to_ftree	(	const std::vector< uint64_t > &	seq,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

inlinenodiscardnoexcept

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

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

Parameters

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

Returns: The tree built with seq.

◆ from_Prufer_sequence_to_ftree() [2/2]

graphs::free_tree lal::detail::from_Prufer_sequence_to_ftree	(	const uint64_t *const	seq,
		const uint64_t	n,
		const bool	normalize,
		const bool	check )

inlinenodiscardnoexcept

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

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

Parameters

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

Returns: The tree built with seq.

◆ from_tree_to_head_vector() [1/2]

template<class arrangement_t >

head_vector lal::detail::from_tree_to_head_vector	(	const graphs::free_tree &	t,
		const arrangement_t &	arr,
		const node	r )

nodiscardnoexcept

Constructs the head vector representation of a tree.

Template Parameters

arrangement_t 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<class arrangement_t >

head_vector lal::detail::from_tree_to_head_vector	(	const graphs::rooted_tree &	t,
		const arrangement_t &	arr )

nodiscardnoexcept

Constructs the head vector representation of a tree.

Template Parameters

arrangement_t Type of arrangement.

Parameters

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

Returns: A head vector encoding the tree.

◆ get_bool_neighbors()

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

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

inlinenoexcept

Retrieves the neighbors 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 neighbors 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,
		const node	u,
		const bool	relabel )

nodiscardnoexcept

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	r,
		uint64_t *const	sizes )

inlinenoexcept

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.

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

◆ has_directed_cycles() [1/2]

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

inlinenodiscardnoexcept

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 )

inlinenodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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

template<class graph_t , class arrangement_t >

bool lal::detail::is_bipartite	(	const graph_t &	g,
		const arrangement_t &	arr )

nodiscardnoexcept

Is a given arrangement bipartite?

See Types of arrangements for details on bipartite arrangements.

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

Template Parameters

arrangement_t Type of arrangement.

Parameters

g	Input graph.
arr	Input linear arrangement.

Returns: Whether or not the input arrangement is bipartite.

◆ is_bipartite__connected()

template<class arrangement_t >

bool lal::detail::is_bipartite__connected	(	const properties::bipartite_graph_coloring &	c,
		const arrangement_t &	arr )

nodiscardnoexcept

Is a given arrangement bipartite?

See Types of arrangements for details on bipartite arrangements.

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

Template Parameters

arrangement_t Type of arrangement.

Parameters

c	Coloring of a bipartite graph.
arr	Input linear arrangement.

Returns: Whether or not the input arrangement is bipartite.

Precondition: Input arr is an arrangement of a connected bipartite graph.

◆ is_graph_a_tree()

template<class graph_t >

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

nodiscardnoexcept

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

template<class graph_t , level_signature_type t>

bool lal::detail::is_level_signature_nonincreasing	(	const graph_t &	g,
		const level_signature< t > &	levels,
		const linear_arrangement &	arr )

inlinenodiscardnoexcept

Returns true if the level sequence follows that of a maximum arrangement.

Checks whether or not the level signature is non-increasing, that is, whether the sequence of level values (in a per position distribution) is non-increasing.

This is a necessary condition for an arrangement to be maximum, as shown in [18] [39] and [7].

When the level signature is defined on a 'per position' basis, the arrangement is not needed.

Template Parameters

t	Level signature type.
graph_t	Type of graph.

Parameters

g	Input graph.
arr	Input arrangement.
levels	signature of the arrangement.

Returns: Whether or not the level sequence satisfies the condition.

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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

nodiscardnoexcept

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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

nodiscardnoexcept

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 )

inlinenodiscardnoexcept

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<class arrangement_t >

bool lal::detail::is_projective	(	const graphs::rooted_tree &	rt,
		const arrangement_t &	arr )

nodiscardnoexcept

Is a given arrangement projective?

See Types of arrangements for details on projective arrangements.

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

Template Parameters

arrangement_t 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<class arrangement_t >

bool lal::detail::is_root_covered	(	const graphs::rooted_tree &	rt,
		const arrangement_t &	arr )

nodiscardnoexcept

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

See Properties that can be defined in linear arrangements for details on vertex covering in an arrangement.

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

Template Parameters

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

◆ is_thistle_vertex()

template<level_signature_type t, class graph_t >

bool lal::detail::is_thistle_vertex	(	const graph_t &	g,
		const level_signature< t > &	levels,
		const node_t	u,
		const linear_arrangement &	arr = {} )

nodiscardnoexcept

Returns whether or not the input vertex is a thistle vertex.

Template Parameters

t	Level signature type
graph_t	Type of graph.

Parameters

g	Input graph.
arr	Input arrangement.
levels	Level signature of the arrangement.
u	Vertex to check.

Returns: Whether or not the input vertex is a thistle.

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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,
		const 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>

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

nodiscardconstexprnoexcept

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>

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

nodiscardconstexprnoexcept

Returns an array initialized 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>

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

nodiscardconstexprnoexcept

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<class result_t , class graph_t , class arrangement_t >

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

nodiscardnoexcept

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.

◆ mirror_level_signature()

template<class level_signature_t >

level_signature_t lal::detail::mirror_level_signature ( const level_signature_t & L )

nodiscardnoexcept

Mirrors a level signature.

Template Parameters

level_signature_t Level signature type.

Parameters

L	Input level signature.

Returns: A mirrored copy of the input level signature.

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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.

◆ no_two_adjacent_vertices_have_same_level()

template<class graph_t , level_signature_type t>

bool lal::detail::no_two_adjacent_vertices_have_same_level	(	const graph_t &	g,
		const level_signature< t > &	levels,
		const linear_arrangement &	arr )

inlinenodiscardnoexcept

Returns true if no two adjacent vertices (in the graph) have the same level value.

Checks that no edge \(uv\in E(G)\) is such that \(l_{\pi}(u) = l_{\pi}(v)\). This is a necessary condition for an arrangement to be maximum (in sum of edge lengths), as shown in [18] [39] and [7].

When the level signature is defined on a 'per vertex' basis, the arrangement is not needed.

Template Parameters

t	Level signature type.
graph_t	Type of graph.

Parameters

g	Input graph.
arr	Input arrangement.
levels	signature of the arrangement.

Returns: Whether or not the level sequence satisfies the condition.

◆ no_vertex_in_antenna_is_thistle()

template<class graph_t , level_signature_type t>

bool lal::detail::no_vertex_in_antenna_is_thistle	(	const graph_t &	g,
		const std::vector< properties::branchless_path > &	bps,
		const level_signature< t > &	levels,
		const linear_arrangement &	arr )

inlinenodiscardnoexcept

Returns true if none of the vertices in the antennas of the graph is a thistle.

Checks that no vertex in any antenna of the tree is a thistle vertex in the input arrangement. This is a necessary condition for an arrangement to be maximum (in sum of edge lengths), as shown in [7].

When the level signature is defined on a 'per vertex' basis, the arrangement is not needed.

Template Parameters

t	Level signature type.
graph_t	Type of graph.

Parameters

g	Input graph.
arr	Input arrangement.
levels	signature of the arrangement.
bps	All Branchless Paths of the tree.

Returns: Whether or not the level sequence satisfies the condition.

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

inlinenodiscardnoexcept

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

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

◆ 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,
		const node	X )

nodiscardnoexcept

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

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 = 0 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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 )

nodiscardnoexcept

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

nodiscardnoexcept

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 )

nodiscardnoexcept

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

std::string_view lal::detail::syntactic_dependency_tree_to_string ( const linarr::syntactic_dependency_tree_type & tt )

nodiscardconstexprnoexcept

Converts a value of the enumeration lal::linarr::syntactic_dependency_tree_type 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,
		const node	x )

nodiscardnoexcept

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 the addition of an edge.

This function updates the Union-Find data structure of a tree after the addition of an edge between vertices u and v.

Template Parameters

tree_t Type of input tree. A derived class of lal::graphs::free_tree or a derived class of lal::graphs::rooted_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_add_edges()

template<class tree_t >

void lal::detail::update_unionfind_after_add_edges	(	const tree_t &	t,
		const edge_list &	edges,
		node *const	root_of,
		uint64_t *const	root_size )

noexcept

Update the Union-Find data structure after the addition of several edges.

Template Parameters

tree_t Type of tree

Parameters

t	Input tree
edges	Edges added to the tree
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_add_rem_edges_bulk()

template<class tree_t >

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

noexcept

Update the Union-Find data structure after several edges have been operated in bulk.

Template Parameters

tree_t Type of tree

Parameters

t	Input tree
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 the removal of an edge.

This function updates the Union-Find data structure of a tree after the removal of the edge between vertices u and v.

Template Parameters

tree_t Type of input tree. A derived class of lal::graphs::free_tree or a derived class of lal::graphs::rooted_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_edges()

template<class tree_t >

void lal::detail::update_unionfind_after_remove_edges	(	const tree_t &	t,
		const edge_list &	edges,
		node *const	root_of,
		uint64_t *const	root_size )

noexcept

Update the Union-Find data structure after the addition of several edges.

Template Parameters

tree_t Type of input tree. A derived class of lal::graphs::free_tree or a derived class of lal::graphs::rooted_tree.

Parameters

t	Input tree
edges	Edges added to the tree
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,
		const node	v,
		node *const	root_of,
		uint64_t *const	root_size )

noexcept

Update Union-Find after the removal of a vertex.

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

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

Template Parameters

tree_t Type of input tree. A derived class of lal::graphs::free_tree or a derived class of lal::graphs::rooted_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,
		const 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).

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

Template Parameters

tree_t Type of input tree. A derived class of lal::graphs::free_tree or a derived class of lal::graphs::rooted_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.

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ arrangement_type

◆ centroid_results

◆ level_signature_type

Function Documentation

◆ alpha()

◆ append_adjacency_lists()

◆ are_rooted_trees_isomorphic()

◆ assign_name()

◆ assign_name_and_keep()

◆ at_most_one_thistle_in_bridges()

◆ beta()

◆ branchless_paths_compute()

◆ calculate_bidirectional_sizes() [1/2]

◆ calculate_bidirectional_sizes() [2/2]

◆ calculate_dependencies_and_span()

◆ calculate_level_signature() [1/2]

◆ calculate_level_signature() [2/2]

◆ calculate_weight()

◆ centroidal_vertex_plus_adjacency_list()

◆ check_correctness_treebank()

◆ check_correctness_treebank_collection()

◆ classify_tree()

◆ exists_sorted()

◆ expand_branchless_path()

◆ fast_non_iso()

◆ find_centroidal_vertex()

◆ find_cycle()

◆ find_errors() [1/2]

◆ find_errors() [2/2]

◆ find_sorted()

◆ from_edge_list_to_graph()

◆ from_head_vector_to_graph()

◆ from_head_vector_to_tree() [1/2]

◆ from_head_vector_to_tree() [2/2]

◆ from_level_sequence_to_tree() [1/2]

◆ from_level_sequence_to_tree() [2/2]

◆ from_level_sequence_to_tree_large() [1/2]

◆ from_level_sequence_to_tree_large() [2/2]

◆ from_level_sequence_to_tree_small() [1/2]

◆ from_level_sequence_to_tree_small() [2/2]

◆ from_Prufer_sequence_to_ftree() [1/2]

◆ from_Prufer_sequence_to_ftree() [2/2]

◆ from_tree_to_head_vector() [1/2]

◆ from_tree_to_head_vector() [2/2]

◆ get_bool_neighbors()

◆ get_edges_subtree()

◆ get_size_subtrees() [1/2]

◆ get_size_subtrees() [2/2]

◆ has_directed_cycles() [1/2]

◆ has_directed_cycles() [2/2]

◆ has_undirected_cycles() [1/2]

◆ has_undirected_cycles() [2/2]

◆ head_initial()

◆ is_bipartite()

◆ is_bipartite__connected()

◆ is_graph_a_tree()

◆ is_level_signature_nonincreasing()

◆ is_n_C_brute_force_lesseq_than() [1/3]

◆ is_n_C_brute_force_lesseq_than() [2/3]

◆ is_n_C_brute_force_lesseq_than() [3/3]

◆ is_n_C_dynamic_programming_lesseq_than() [1/3]

◆ is_n_C_dynamic_programming_lesseq_than() [2/3]

◆ is_n_C_dynamic_programming_lesseq_than() [3/3]

◆ is_n_C_ladder_lesseq_than() [1/3]

◆ is_n_C_ladder_lesseq_than() [2/3]

◆ is_n_C_ladder_lesseq_than() [3/3]

◆ is_n_C_stack_based_lesseq_than() [1/3]

◆ is_n_C_stack_based_lesseq_than() [2/3]

◆ is_n_C_stack_based_lesseq_than() [3/3]

◆ is_node_reachable_from()

◆ is_projective()

◆ is_root_covered()