Namespace for the algorithms that compute the number of crossings. More...

Namespaces
namespace	brute_force
	Namespace for the brute force algorithm to calculate \(C\).

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

namespace	ladder
	Namespace for the "ladder" algorithm to calculate \(C\).

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

Functions
template<class graph_t , class arrangement_t >
uint64_t	n_C_brute_force (const graph_t &g, const arrangement_t &arr) noexcept
	Brute force computation of \(C\). More...

template<class graph_t >
std::vector< uint64_t >	n_C_brute_force (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Brute force computation of \(C\). More...

template<class graph_t , class arrangement_t >
uint64_t	is_n_C_brute_force_lesseq_than (const graph_t &g, const arrangement_t &arr, uint64_t upper_bound) noexcept
	Brute force computation of \(C\) with early termination. More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_brute_force_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Brute force computation of \(C\) with early termination. More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_brute_force_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Brute force computation of \(C\) with early termination. More...

template<class graph_t , class arrangement_t >
uint64_t	n_C_dynamic_programming (const graph_t &g, const arrangement_t &arr) noexcept
	Dynamic programming computation of \(C\). More...

template<class graph_t >
std::vector< uint64_t >	n_C_dynamic_programming (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Dynamic programming computation of \(C\). More...

template<class graph_t , class arrangement_t >
uint64_t	is_n_C_dynamic_programming_lesseq_than (const graph_t &g, const arrangement_t &arr, uint64_t upper_bound) noexcept
	Dynamic programming computation of \(C\). More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_dynamic_programming_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Dynamic programming computation of \(C\) with early termination. More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_dynamic_programming_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Dynamic programming computation of \(C\) with early termination. More...

template<class graph_t , class arrangement_t >
uint64_t	n_C_ladder (const graph_t &g, const arrangement_t &arr) noexcept
	Ladder computation of \(C\). More...

template<class graph_t >
std::vector< uint64_t >	n_C_ladder (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Ladder computation of \(C\). More...

template<class graph_t , class arrangement_t >
uint64_t	is_n_C_ladder_lesseq_than (const graph_t &g, const arrangement_t &arr, uint64_t upper_bound) noexcept
	Ladder computation of \(C\) with early termination. More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_ladder_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Ladder computation of \(C\) with early termination. More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_ladder_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Ladder computation of \(C\) with early termination. More...

template<class graph_t , class arrangement_t >
uint64_t	n_C_stack_based (const graph_t &g, const arrangement_t &arr) noexcept
	Stack based computation of \(C\). More...

template<class graph_t >
std::vector< uint64_t >	n_C_stack_based (const graph_t &g, const std::vector< linear_arrangement > &arrs) noexcept
	Stack based computation of \(C\). More...

template<class graph_t , class arrangement_t >
uint64_t	is_n_C_stack_based_lesseq_than (const graph_t &g, const arrangement_t &arr, uint64_t upper_bound) noexcept
	Stack based computation of \(C\) with early termination. More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_stack_based_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, uint64_t upper_bound) noexcept
	Stack based computation of \(C\) with early termination. More...

template<class graph_t >
std::vector< uint64_t >	is_n_C_stack_based_lesseq_than (const graph_t &g, const std::vector< linear_arrangement > &arrs, const std::vector< uint64_t > &upper_bounds) noexcept
	Stack based computation of \(C\) with early termination. More...

Detailed Description

Namespace for the algorithms that compute the number of crossings.

Function Documentation

◆ is_n_C_brute_force_lesseq_than() [1/3]

template<class graph_t , class arrangement_t >

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

noexcept

Brute force computation of \(C\) with early termination.

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of input arrangement.

Parameters

g	Input graph.
arr	Input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on the input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_brute_force_lesseq_than() [2/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::crossings::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

Brute force computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bounds	List of bounds used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the corresponding upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_brute_force_lesseq_than() [3/3]

template<class graph_t >

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

noexcept

Brute force computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_dynamic_programming_lesseq_than() [1/3]

template<class graph_t , class arrangement_t >

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

noexcept

Dynamic programming computation of \(C\).

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of input arrangement.

Parameters

g	Input graph.
arr	Input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on the input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_dynamic_programming_lesseq_than() [2/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::crossings::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

Dynamic programming computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bounds	List of bounds used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the corresponding upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_dynamic_programming_lesseq_than() [3/3]

template<class graph_t >

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

noexcept

Dynamic programming computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_ladder_lesseq_than() [1/3]

template<class graph_t , class arrangement_t >

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

noexcept

Ladder computation of \(C\) with early termination.

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of input arrangement.

Parameters

g	Input graph.
arr	Input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on the input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_ladder_lesseq_than() [2/3]

template<class graph_t >

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

noexcept

Ladder computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bounds	List of bounds used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the corresponding upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_ladder_lesseq_than() [3/3]

template<class graph_t >

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

noexcept

Ladder computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_stack_based_lesseq_than() [1/3]

template<class graph_t , class arrangement_t >

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

noexcept

Stack based computation of \(C\) with early termination.

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of input arrangement.

Parameters

g	Input graph.
arr	Input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on the input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_stack_based_lesseq_than() [2/3]

template<class graph_t >

std::vector< uint64_t > lal::detail::crossings::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

Stack based computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bounds	List of bounds used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the corresponding upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ is_n_C_stack_based_lesseq_than() [3/3]

template<class graph_t >

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

noexcept

Stack based computation of \(C\) with early termination.

Template Parameters

graph_t Type of input graph

Parameters

g	Input graph.
arrs	List of input arrangement.
upper_bound	Bound used for early termination.

Returns: \(C_{\pi}(G)\) on every input arrangement if it is less than the upper bound. It returns a value one unit larger than the upper bound otherwise.

◆ n_C_brute_force() [1/2]

template<class graph_t , class arrangement_t >

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

noexcept

Brute force computation of \(C\).

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of arrangement.

Parameters

g	Input graph.
arr	Input arrangement.

Returns: \(C_{\pi}(G)\) on the input arrangement.

◆ n_C_brute_force() [2/2]

template<class graph_t >

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

noexcept

Brute force computation of \(C\).

Template Parameters

graph_t Type of input graph.

Parameters

g	Input graph.
arrs	List of input arrangement.

Returns: \(C_{\pi}(G)\) on every input arrangement.

◆ n_C_dynamic_programming() [1/2]

template<class graph_t , class arrangement_t >

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

noexcept

Dynamic programming computation of \(C\).

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of input arrangement.

Parameters

g	Input graph.
arr	Input arrangement.

Returns: \(C_{\pi}(G)\) on the input arrangement.

◆ n_C_dynamic_programming() [2/2]

template<class graph_t >

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

noexcept

Dynamic programming computation of \(C\).

Template Parameters

graph_t Type of input graph.

Parameters

g	Input graph.
arrs	List of input arrangement.

Returns: \(C_{\pi}(G)\) on every input arrangement.

◆ n_C_ladder() [1/2]

template<class graph_t , class arrangement_t >

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

noexcept

Ladder computation of \(C\).

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of arrangement.

Parameters

g	Input graph.
arr	Input arrangement.

Returns: \(C_{\pi}(G)\) on the input arrangement.

◆ n_C_ladder() [2/2]

template<class graph_t >

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

noexcept

Ladder computation of \(C\).

Template Parameters

graph_t Type of input graph.

Parameters

g	Input graph.
arrs	List of input arrangement.

Returns: \(C_{\pi}(G)\) on every input arrangement.

◆ n_C_stack_based() [1/2]

template<class graph_t , class arrangement_t >

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

noexcept

Stack based computation of \(C\).

Template Parameters

graph_t	Type of input graph.
arrangement_t	Type of input arrangement.

Parameters

g	Input graph.
arr	Input arrangement.

Returns: \(C_{\pi}(G)\) on the input arrangement.

◆ n_C_stack_based() [2/2]

template<class graph_t >

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

noexcept

Stack based computation of \(C\).

Template Parameters

graph_t Type of input graph.

Parameters

g	Input graph.
arrs	List of input arrangement.

Returns: \(C_{\pi}(G)\) on every input arrangement.

Namespaces

Functions

Detailed Description

Function Documentation

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

◆ n_C_brute_force() [1/2]

◆ n_C_brute_force() [2/2]

◆ n_C_dynamic_programming() [1/2]

◆ n_C_dynamic_programming() [2/2]

◆ n_C_ladder() [1/2]

◆ n_C_ladder() [2/2]

◆ n_C_stack_based() [1/2]

◆ n_C_stack_based() [2/2]