Utilities for the various optimal linear arrangement algorithms. More...

Functions
template<bool make_arrangement, sorting::sort_type type, class graph_t , class bipartite_coloring_t >
std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t >	optimal_bipartite_arrangement_AEF (const graph_t &g, const bipartite_coloring_t &c) noexcept
	Optimal bipartite arrangement.

Detailed Description

Utilities for the various optimal linear arrangement algorithms.

Function Documentation

template<bool make_arrangement, sorting::sort_type type, class graph_t , class bipartite_coloring_t >

std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t > lal::detail::bipartite_opt_utils::optimal_bipartite_arrangement_AEF	(	const graph_t &	g,
		const bipartite_coloring_t &	c )

nodiscardnoexcept

Optimal bipartite arrangement.

This function implements the "common" algorithm to construct minimum or maximum bipartite arrangements given in [7] and [10].

Template Parameters

make_arrangement	Boolean value that indicates whether or not the minimum arrangement should be returned.
sorting_type_t	The type of sorting for the vertices. For minimum arrangements, this must be lal::detail::sorting::sort_type::non_increasing. For maximum arrangements, this must be lal::detail::sorting::sort_type::non_decreasing.
graph_t	Type of graph. Any subclass of lal::graphs::graph.

Parameters

g	Input (bipartite) graph.
c	Coloring of the input graph.

Returns: The cost of a maximal bipartite arrangement and possibly the arrangement that attains it.