Linear arrangement of vertices. More...

#include <linear_arrangement.hpp>

Public Member Functions
	linear_arrangement () noexcept=default
	Default constructor.

	linear_arrangement (std::size_t n) noexcept
	Constructor with size. More...

	linear_arrangement (const std::vector< position > &dir_arr) noexcept
	Constructor with direct arrangement. More...

	linear_arrangement (const linear_arrangement &arr) noexcept
	Copy constructor.

linear_arrangement &	operator= (const linear_arrangement &arr) noexcept
	Copy assignment operator.

linear_arrangement &	operator= (const std::vector< position > &dir_arr) noexcept
	Copy assignment operator.

	linear_arrangement (linear_arrangement &&arr) noexcept
	Move constructor.

linear_arrangement &	operator= (linear_arrangement &&arr) noexcept
	Move assignment operator.

virtual	~linear_arrangement () noexcept=default
	Default destructor.

bool	operator< (const linear_arrangement &arr) const noexcept
	Lexicographic comparison of two linear arrangements.

node	operator[] (const node_t &u) const noexcept
	Access to linear arrangement using a type-safe node.

position	operator[] (const position_t &p) const noexcept
	Access to linear arrangement using a type-safe position.

void	clear () noexcept
	Frees the memory used by the linear arrangement.

position	get_position_of (const node u) const noexcept
	Returns the position of node u.

node	get_node_at (const position p) const noexcept
	Returns the node at position p.

void	resize (std::size_t n) noexcept
	Changes the size of the arrangement. More...

template<typename NODE , typename POSITION , std::enable_if_t<(std::is_integral_v< NODE > or std::is_same_v< NODE, node_t >) and(std::is_integral_v< POSITION > or std::is_same_v< POSITION, position_t >), bool > = true>
void	assign (const NODE u, const POSITION p) noexcept
	Assigns a node u to position p. More...

template<typename what , std::enable_if_t< std::is_same_v< what, node_t > or std::is_same_v< what, position_t >, bool > = true>
void	swap (const what u_t, const what v_t) noexcept
	Swaps the position of two vertices or of two positions. More...

void	shift_left () noexcept
	Shifts the vertices one position to the left.

void	shift_right () noexcept
	Shifts the vertices one position to the right.

void	mirror () noexcept
	Mirror the arrangement. More...

std::size_t	size () const noexcept
	Size of the arrangement (number of nodes in the arrangement).

void	identity () noexcept
	Makes this arrangement an identity arrangement.

void	update_direct () noexcept
	Updates the direct arrangement using the inverse arrangement. More...

void	update_inverse () noexcept
	Updates the inverse arrangement using the direct arrangement. More...

node *	begin_direct () noexcept
	Pointer to beginning of direct arrangement.

const node *	begin_direct () const noexcept
	Pointer to beginning of direct arrangement.

node *	end_direct () noexcept
	Pointer to end of direct arrangement.

const node *	end_direct () const noexcept
	Pointer to end of direct arrangement.

node *	begin_inverse () noexcept
	Pointer to beginning of inverse arrangement.

const node *	begin_inverse () const noexcept
	Pointer to beginning of inverse arrangement.

node *	end_inverse () noexcept
	Pointer to end of inverse arrangement.

const node *	end_inverse () const noexcept
	Pointer to end of inverse arrangement.

std::vector< position >	direct_as_vector () const noexcept
	Constructs a std::vector from the direct arrangement.

std::vector< node >	inverse_as_vector () const noexcept
	Constructs a std::vector from the inverse arrangement.

Static Public Member Functions
static linear_arrangement	from_direct (const std::vector< position > &v) noexcept
	Construct a linear arrangement from a direct arrangement. More...

template<typename It >
static linear_arrangement	from_direct (It begin, It end) noexcept
	Construct a linear arrangement from a direct arrangement. More...

template<typename It >
static linear_arrangement	from_direct (It begin, It end, std::size_t size) noexcept
	Construct a linear arrangement from a direct arrangement. More...

static linear_arrangement	from_inverse (const std::vector< node > &v) noexcept
	Construct a linear arrangement from an inverse arrangement. More...

template<typename It >
static linear_arrangement	from_inverse (It begin, It end) noexcept
	Construct a linear arrangement from an inverse arrangement. More...

template<typename It >
static linear_arrangement	from_inverse (It begin, It end, std::size_t size) noexcept
	Construct a linear arrangement from an inverse arrangement. More...

static linear_arrangement	identity (std::size_t n) noexcept
	Constructs a linear arrangement from an inverse arrangement. More...

Protected Attributes
detail::data_array< uint64_t >	m_memory

std::size_t	m_n = 0
	Size of the arrangement (number of nodes in the arrangement).

position *	m_direct = nullptr
	Pointer to the direct arrangement values.

node *	m_inverse = nullptr
	Pointer to the inverse arrangement values.

Private Member Functions
void	set_pointers () noexcept

template<bool from_direct_arr, typename It >
void	from_data (const It begin, const It end) noexcept
	Initializes this arrangement from a direct or inverse arrangement. More...

Detailed Description

Linear arrangement of vertices.

A linear arrangement is a pair of two functions that relate vertices to a distinct position in a linear ordering.

This concept is further explained in page Linear Arrangement.

Now, this class's usage is simple enough. Declare a linear arrangement with a given number of vertices

lal::linear_arrangement arr(n);

lal::linear_arrangement

Linear arrangement of vertices.

Definition: linear_arrangement.hpp:103

or initialize it

lal::linear_arrangement arr;

arr.resize(n);

lal::linear_arrangement::resize

void resize(std::size_t n) noexcept

Changes the size of the arrangement.

Definition: linear_arrangement.hpp:317

Assign a vertex to a given position using the method assign. Retrieving a vertex's position can be done using either the method get_position_of or using the operator[] passing to it a lal::node_t object. Likewise, use the method get_node_at or the operator[] with a lal::position_t to retrieve the vertex at a given position. Therefore, the following loops are equivalent

lal::linear_arrangement(n);
// ...
for (lal::node u = 0; u < n; ++u) {
   const lal::position p = arr.get_position_of(u);
   // ...
}
for (lal::node_t u = 0; u < n; ++u) {
   const lal::position p = arr[u];
}

Types lal::node_t and lal::position_t are useful also in swapping vertices in the arrangement (see swap).

Linear arrangements can be transformed. For example, an arrangement can be

shifted to the left (see lal::linear_arrangement::shift_left),
shifted to the right (see lal::linear_arrangement::shift_right),
mirrored (see lal::linear_arrangement::mirror).
in case the inverse arrangement was manipulated, the directed can be updated (see lal::linear_arrangement::update_direct).
in case the direct arrangement was manipulated, the inverse can be updated (see lal::linear_arrangement::update_inverse).

Constructor & Destructor Documentation

◆ linear_arrangement() [1/2]

lal::linear_arrangement::linear_arrangement ( std::size_t n )

inlinenoexcept

Constructor with size.

Parameters

n	Number of nodes in the arrangement.

◆ linear_arrangement() [2/2]

lal::linear_arrangement::linear_arrangement ( const std::vector< position > & dir_arr )

inlinenoexcept

Constructor with direct arrangement.

Constructs a linear arrangement assuming that the parameter is a direct arrangement, i.e., dir_arr[u]=p if the position of vertex u is p.

This helps the conversion from python's list to this object.

Parameters

dir_arr Direct arrangement.

Member Function Documentation

◆ assign()

template<typename NODE , typename POSITION , std::enable_if_t<(std::is_integral_v< NODE > or std::is_same_v< NODE, node_t >) and(std::is_integral_v< POSITION > or std::is_same_v< POSITION, position_t >), bool > = true>

void lal::linear_arrangement::assign	(	const NODE	u,
		const POSITION	p
	)

inlinenoexcept

Assigns a node u to position p.

Template Parameters

NODE	A type that must be convertible to node_t.
POSITION	A type that must be convertible to position_t.

Parameters

u	Node.
p	Position.

Precondition: Values u and p must both be strictly less than the size of the arrangement (see m_n).

◆ from_data()

template<bool from_direct_arr, typename It >

void lal::linear_arrangement::from_data	(	const It	begin,
		const It	end
	)

inlineprivatenoexcept

Initializes this arrangement from a direct or inverse arrangement.

Template Parameters

from_direct_arr If true, parameter v is interpreted as a direct arrangement; as an inverse arrangement if otherwise.

Parameters

begin	Pointer to beginning of data.
end	Pointer to ending of data.

Precondition: Pointers m_direct and m_inverse must have been set appropriately.

◆ from_direct() [1/3]

static linear_arrangement lal::linear_arrangement::from_direct ( const std::vector< position > & v )

inlinestaticnoexcept

Construct a linear arrangement from a direct arrangement.

A direct arrangement gives the position of every node.

Parameters

v	A direct arrangement. This gives the position of every node.

Returns: A linear arrangement object constructed from v.

◆ from_direct() [2/3]

template<typename It >

static linear_arrangement lal::linear_arrangement::from_direct	(	It	begin,
		It	end
	)

inlinestaticnoexcept

Construct a linear arrangement from a direct arrangement.

A direct arrangement gives the position of every node.

Parameters

begin	A pointer to the beginning of the direct arrangement.
end	A pointer to the end of the direct arrangement.

Returns: A linear arrangement object constructed from v.

◆ from_direct() [3/3]

template<typename It >

static linear_arrangement lal::linear_arrangement::from_direct	(	It	begin,
		It	end,
		std::size_t	size
	)

inlinestaticnoexcept

Construct a linear arrangement from a direct arrangement.

A direct arrangement gives the position of every node.

Parameters

begin	A pointer to the beginning of the direct arrangement.
end	A pointer to the end of the direct arrangement.
size	The size of the container pointer by begin and end.

Returns: A linear arrangement object constructed from v.

◆ from_inverse() [1/3]

static linear_arrangement lal::linear_arrangement::from_inverse ( const std::vector< node > & v )

inlinestaticnoexcept

Construct a linear arrangement from an inverse arrangement.

Parameters

v	An inverse arrangement. This gives the node for every position.

Returns: A linear arrangement object constructed from v.

◆ from_inverse() [2/3]

template<typename It >

static linear_arrangement lal::linear_arrangement::from_inverse	(	It	begin,
		It	end
	)

inlinestaticnoexcept

Construct a linear arrangement from an inverse arrangement.

A direct arrangement gives the node for every position.

Parameters

begin	A pointer to the beginning of the inverse arrangement.
end	A pointer to the end of the inverse arrangement.

Returns: A linear arrangement object constructed from v.

◆ from_inverse() [3/3]

template<typename It >

static linear_arrangement lal::linear_arrangement::from_inverse	(	It	begin,
		It	end,
		std::size_t	size
	)

inlinestaticnoexcept

Construct a linear arrangement from an inverse arrangement.

A direct arrangement gives the node for every position.

Parameters

begin	A pointer to the beginning of the inverse arrangement.
end	A pointer to the end of the inverse arrangement.
size	The size of the container pointer by begin and end.

Returns: A linear arrangement object constructed from v.

◆ identity()

static linear_arrangement lal::linear_arrangement::identity ( std::size_t n )

inlinestaticnoexcept

Constructs a linear arrangement from an inverse arrangement.

Parameters

n	Number of vertices.

◆ mirror()

void lal::linear_arrangement::mirror ( )

inlinenoexcept

Mirror the arrangement.

Swaps the vertices so that the first is placed at the last position, the second at the second to last, ... More formally, swaps arr[1] with arr[n], arr[2] with arr[n-1], ...

◆ resize()

void lal::linear_arrangement::resize ( std::size_t n )

inlinenoexcept

Changes the size of the arrangement.

Parameters

n	New size of the arrangement.

Postcondition: Sets the position of each node to \(n+1\), and the node at each position is also \(n+1\).

◆ set_pointers()

void lal::linear_arrangement::set_pointers ( )

inlineprivatenoexcept

Sets the pointers m_direct and m_inverse appropriate locations of the memory allocated by m_memory.

◆ swap()

template<typename what , std::enable_if_t< std::is_same_v< what, node_t > or std::is_same_v< what, position_t >, bool > = true>

void lal::linear_arrangement::swap	(	const what	u_t,
		const what	v_t
	)

inlinenoexcept

Swaps the position of two vertices or of two positions.

Updates m_direct and m_inverse so that the vertices are effectively swapped.

The two parameters have to be of the same type: either lal::node_t or lal::position_t.

Template Parameters

what	Swap either vertices or positions.

Parameters

u_t	Value indicating the first object.
v_t	Value indicating the second object.

◆ update_direct()

void lal::linear_arrangement::update_direct ( )

inlinenoexcept

Updates the direct arrangement using the inverse arrangement.

This function is only useful when there have been changes to the inverse arrangement not via the assign function.

◆ update_inverse()

void lal::linear_arrangement::update_inverse ( )

inlinenoexcept

Updates the inverse arrangement using the direct arrangement.

This function is only useful when there have been changes to the direct arrangement not via the assign function.

Member Data Documentation

◆ m_memory

detail::data_array<uint64_t> lal::linear_arrangement::m_memory

protected

Memory of the linear arrangement. Holds twice as many elements as vertices there are in the arrangement.

The documentation for this class was generated from the following file:

lal/linear_arrangement.hpp

Public Member Functions

Static Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ linear_arrangement() [1/2]

◆ linear_arrangement() [2/2]

Member Function Documentation

◆ assign()

◆ from_data()

◆ from_direct() [1/3]

◆ from_direct() [2/3]

◆ from_direct() [3/3]

◆ from_inverse() [1/3]

◆ from_inverse() [2/3]

◆ from_inverse() [3/3]

◆ identity()

◆ mirror()

◆ resize()

◆ set_pointers()

◆ swap()

◆ update_direct()

◆ update_inverse()

Member Data Documentation

◆ m_memory