lal::detail::crossings::stack_based Namespace Reference

Namespace for the stack-based algorithm to calculate \(C\). More...

Typedefs
typedef std::pair< uint64_t, lal::edge >	indexed_edge
	Useful typedef.

Functions
template<class graph_t , linarr_type arr_type>
void	fill_adjP_adjN (const graph_t &g, const linarr_wrapper< arr_type > &arr, std::vector< neighbourhood > &adjP, std::vector< std::vector< indexed_edge > > &adjN, uint64_t *const size_adjN_u) noexcept
	Auxiliary function to sort edges as a function of the arrangement. More...
template<bool decide_upper_bound, class graph_t , linarr_type arr_type>
uint64_t	compute_C_stack_based (const graph_t &g, const linarr_wrapper< arr_type > &arr, uint64_t *const size_adjN_u, uint64_t upper_bound) noexcept
	Stack based computation of \(C\) for undirected graphs. More...

Detailed Description

Namespace for the stack-based algorithm to calculate \(C\).

See [8].

Function Documentation

compute_C_stack_based()

template<bool decide_upper_bound, class graph_t , linarr_type arr_type>

uint64_t lal::detail::crossings::stack_based::compute_C_stack_based ( const graph_t &  g, const linarr_wrapper< arr_type > &  arr, uint64_t *const  size_adjN_u, uint64_t  upper_bound  )

noexcept

Stack based computation of \(C\) for undirected graphs.

When template parameter decide_upper_bound is false, the function returns the number of crossings.

Template Parameters

decide_upper_bound	Boolean value to choose the nature of the return type.
graph_t	Type of graph.
arr_type	Type of arrangement.

Parameters

g	Input graph.
arr	Input arrangement.
size_adjN_u	See [8] for details.
upper_bound	Upper bound on the number of crossings.

Returns

When decide_upper_bound is true, the return value is:

• one unit larger than the upper bound passed as parameter if \(C>\) upper bound.
• \(C\) if the number of crossings is less or equal than the upper bound.

fill_adjP_adjN()

template<class graph_t , linarr_type arr_type>

void lal::detail::crossings::stack_based::fill_adjP_adjN ( const graph_t &  g, const linarr_wrapper< arr_type > &  arr, std::vector< neighbourhood > &  adjP, std::vector< std::vector< indexed_edge > > &  adjN, uint64_t *const  size_adjN_u  )

noexcept

Auxiliary function to sort edges as a function of the arrangement.

See [8] for details on the correctness and behaviour.

Template Parameters

graph_t	Type of graph.
arr_type	Type of arrangement.

Parameters

g	Input graph.
arr	Input arrangement.
adjP	adjP[v] contains the list of vertices u that form edges (u,v) such that arr[u] < arr[v] sorted nondecreasingly by edge length.
adjN	adjN[v] contains the list of vertices u that form edges (u,v) such that arr[v] < arr[u] sorted nonincreasingly by edge length.
size_adjN_u	Auxiliary memory array of size n.