Details of algorithm for 1-Thistle MaxLA. More...

Typedefs
template<bool make_arrangement>
using	result_t
	Result type of the function.

Functions
template<typename iterator_t >
bool	next_binary (iterator_t begin, iterator_t end) noexcept
	Next binary combination of 0's and 1's.

static constexpr char	other_side (char side) noexcept
	The other side. "Right" if 'side' is "left"; "left" if 'side' is "right".

void	construct_initial_arrangement (const graphs::free_tree &t, const node thistle, const int64_t thistle_level, const array< char > &thistle_side_per_vertex, level_signature_per_vertex &levels_per_vertex, array< node > &inv_arr) noexcept
	Construct the initial arrangement that will later be improved.

void	sort_level_sequences (const uint64_t n, const node thistle, const array< char > &is_thistle_neighbor, const level_signature_per_vertex &levels_per_vertex, array< node > &inv_arr) noexcept
	Sorts the intervals of vertices of equal level value.

void	shift_vertex_to_right (const graphs::free_tree &t, const node thistle, position_t p, linear_arrangement &arr) noexcept
	Moves the vertex at position p to the right of the thistle vertex.

void	adjust_nonneighbors_of_thistle_smart (const graphs::free_tree &t, const int64_t thistle_level, const node thistle, const array< char > &is_thistle_neighbor, const level_signature_per_vertex &levels_per_vertex, linear_arrangement &arr) noexcept
	Adjust misplaced nonneighbors of the thistle vertex in a smart way.

template<bool make_arrangement>
void	merge_arrangements (const graphs::free_tree &t, const node thistle, const int64_t thistle_level, const array< char > &is_thistle_neighbor, const array< char > &thistle_side_per_vertex, linear_arrangement &arr, array< node > &inv_arr, level_signature_per_vertex &levels_per_vertex, result_t< make_arrangement > &res) noexcept
	Tries to make a maximal arrangement with a given thistle vertex of a given level value.

template<bool make_arrangement>
void	choose_orientations_for_thistle_neighbors (const graphs::free_tree &t, const node thistle, const array< char > &is_thistle_neighbor, linear_arrangement &arr, array< node > &inv_arr, level_signature_per_vertex &level_per_vertex, array< char > &thistle_side_per_vertex, result_t< make_arrangement > &res) noexcept
	Tries to make a maximal arrangement with a given thistle vertex of a given level value.

Variables
static constexpr auto	blue = properties::bipartite_graph_coloring::blue
	Typedef for properties::bipartite_graph_coloring::blue.

static constexpr auto	red = properties::bipartite_graph_coloring::red
	Typedef for properties::bipartite_graph_coloring::red.

static constexpr char	LEFT_SIDE = 0
	Left side of the thistle vertex.

static constexpr char	RIGHT_SIDE = 1
	Right side of the thistle vertex.

Detailed Description

Details of algorithm for 1-Thistle MaxLA.

Function Documentation

◆ adjust_nonneighbors_of_thistle_smart()

void lal::detail::DMax::thistle_1::bits::adjust_nonneighbors_of_thistle_smart	(	const graphs::free_tree &	t,
		const int64_t	thistle_level,
		const node	thistle,
		const array< char > &	is_thistle_neighbor,
		const level_signature_per_vertex &	levels_per_vertex,
		linear_arrangement &	arr )

inlinenoexcept

Adjust misplaced nonneighbors of the thistle vertex in a smart way.

This function stops moving vertices as soon as one moving operation decreases the cost of the arrangement (without actually applying it).

Parameters

	t	Input tree
	thistle_level	Level of the thistle
	thistle	Thistle vertex
	is_thistle_neighbor	Array to query if a vertex is a neighbor of the thisle.
	levels_per_vertex	Array containing the level value of each vertex of the tree.
[out]	arr	Arrangement to be manipulated.

◆ choose_orientations_for_thistle_neighbors()

template<bool make_arrangement>

void lal::detail::DMax::thistle_1::bits::choose_orientations_for_thistle_neighbors	(	const graphs::free_tree &	t,
		const node	thistle,
		const array< char > &	is_thistle_neighbor,
		linear_arrangement &	arr,
		array< node > &	inv_arr,
		level_signature_per_vertex &	level_per_vertex,
		array< char > &	thistle_side_per_vertex,
		result_t< make_arrangement > &	res )

inlinenoexcept

Tries to make a maximal arrangement with a given thistle vertex of a given level value.

Parameters arr, inv_arr, level_per_vertex are temporary memory passed as parameters to avoid constant allocations and deallocations.

Template Parameters

make_arrangement Should the arrangement be returned?

Parameters

	t	Input free tree.
	thistle	Thistle vertex.
	is_thistle_neighbor	Is a given vertex a neighbor of thistle?
	arr	Linear arrangement (used to evaluate the cost of the distribution).
	inv_arr	Inverse linear arrangement (used to evaluate the cost of the distribution).
	level_per_vertex	Array containing the level value of each vertex of the tree.
	thistle_side_per_vertex	For each vertex, the side of the thistle at which they are to be placed.
[in,out]	res	Contains the best arrangement produced here if it is better than the one it already contains.

◆ construct_initial_arrangement()

void lal::detail::DMax::thistle_1::bits::construct_initial_arrangement	(	const graphs::free_tree &	t,
		const node	thistle,
		const int64_t	thistle_level,
		const array< char > &	thistle_side_per_vertex,
		level_signature_per_vertex &	levels_per_vertex,
		array< node > &	inv_arr )

inlinenoexcept

Construct the initial arrangement that will later be improved.

Parameters

	t	Input free tree.
	thistle	Thistle vertex.
	thistle_level	Level value for thistle.
	thistle_side_per_vertex	Side of thistle in which each vertex have to be placed at in the first arrangement.
[out]	levels_per_vertex	Array containing the level value of each vertex of the tree.
[out]	inv_arr	Inverse linear arrangement (used to evaluate the cost of the distribution).

◆ merge_arrangements()

template<bool make_arrangement>

void lal::detail::DMax::thistle_1::bits::merge_arrangements	(	const graphs::free_tree &	t,
		const node	thistle,
		const int64_t	thistle_level,
		const array< char > &	is_thistle_neighbor,
		const array< char > &	thistle_side_per_vertex,
		linear_arrangement &	arr,
		array< node > &	inv_arr,
		level_signature_per_vertex &	levels_per_vertex,
		result_t< make_arrangement > &	res )

inlinenoexcept

Tries to make a maximal arrangement with a given thistle vertex of a given level value.

Parameters arr, inv_arr, levels_per_vertex are temporary memory passed as parameters to avoid constant allocations and deallocations.

Template Parameters

make_arrangement Should the arrangement be returned?

Parameters

	t	Input free tree.
	thistle	Thistle vertex.
	thistle_level	Level value for thistle.
	is_thistle_neighbor	Array to query if a vertex is a neighbor of the thisle.
	thistle_side_per_vertex	Side of thistle in which each vertex have to be placed at in the first arrangement.
[out]	arr	Linear arrangement (used to evaluate the cost of the distribution).
[out]	inv_arr	Inverse linear arrangement (used to evaluate the cost of the distribution).
[out]	levels_per_vertex	Array containing the level value of each vertex of the tree.
[in,out]	res	Contains the best arrangement produced here if it is better than the one it already contains.

◆ next_binary()

template<typename iterator_t >

bool lal::detail::DMax::thistle_1::bits::next_binary	(	iterator_t	begin,
		iterator_t	end )

inlinenodiscardnoexcept

Next binary combination of 0's and 1's.

Template Parameters

iterator_t Type of pointer to a sequence.

Parameters

begin	Start of the sequence.
end	End of the sequence.

Returns: Whether or not there are more configurations

◆ shift_vertex_to_right()

void lal::detail::DMax::thistle_1::bits::shift_vertex_to_right	(	const graphs::free_tree &	t,
		const node	thistle,
		position_t	p,
		linear_arrangement &	arr )

inlinenoexcept

Moves the vertex at position p to the right of the thistle vertex.

This is implemented as a series of consecutive swaps starting at towards the thistle between consecutive vertices in the arrangement.

Parameters

	t	Input tree.
	thistle	Thistle vertex.
	p	Position of the vertex to move.
[out]	arr	Actual linear arrangement.

Precondition: The thistle vertex is at a position q such that \(p < q\).

Postcondition: The arrangement is updated.

◆ sort_level_sequences()

void lal::detail::DMax::thistle_1::bits::sort_level_sequences	(	const uint64_t	n,
		const node	thistle,
		const array< char > &	is_thistle_neighbor,
		const level_signature_per_vertex &	levels_per_vertex,
		array< node > &	inv_arr )

inlinenoexcept

Sorts the intervals of vertices of equal level value.

In such a way that, for positive (>= 0) level values

the neighbors of the thistle are placed to the leftmost positions,
then comes the thistle,
and then the remaining vertices are placed in the rightmost positions. for negative (< 0) level values
then the remaining vertices are placed in the leftmost positions,
then comes the thistle,
and the neighbors of the thistle are placed to the rightmost positions.

This is Ok thanks to Nurse and De Vos [18] [39].

Parameters

	n	Number of vertices
	thistle	Thistle vertex.
	is_thistle_neighbor	Array to query if a vertex is a neighbor of the thisle.
	levels_per_vertex	Array containing the level value of each vertex of the tree.
[out]	inv_arr	Inverse linear arrangement.

Typedefs

Functions

Variables

Detailed Description

Function Documentation

◆ adjust_nonneighbors_of_thistle_smart()

◆ choose_orientations_for_thistle_neighbors()

◆ construct_initial_arrangement()

◆ merge_arrangements()

◆ next_binary()

◆ shift_vertex_to_right()

◆ sort_level_sequences()