lal::detail::crossings::dyn_prog Namespace Reference

Namespace for the dynamic programming algorithm to calculate \(C\). More...

Functions
template<bool decide_upper_bound, class graph_t , linarr_type arr_type>
uint64_t	compute (const graph_t &g, const linarr_wrapper< arr_type > &arr, unsigned char *const __restrict__ bn, uint64_t *const __restrict__ M, uint64_t *const __restrict__ K, uint64_t upper_bound) noexcept
	Dynamic programming computation of \(C\) for undirected graphs. More...

Detailed Description

Namespace for the dynamic programming algorithm to calculate \(C\).

See [8].

Function Documentation

compute()

template<bool decide_upper_bound, class graph_t , linarr_type arr_type>

uint64_t lal::detail::crossings::dyn_prog::compute ( const graph_t &  g, const linarr_wrapper< arr_type > &  arr, unsigned char *const __restrict__  bn, uint64_t *const __restrict__  M, uint64_t *const __restrict__  K, uint64_t  upper_bound  )

noexcept

Dynamic programming 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.
arr_type	Type of arrangement.

Parameters

g	Input graph.
arr	Input arrangement.
bn	Array of size n. Boolean neighbourhood of a vertex u: bn[i] is 1 if vertex u and vertex i are adjacent.
M	See [8] for details. Also, see the end of the corresponding file.
K	See [8] for details. Also, see the end of the corresponding file.
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.