lal::linear_arrangement Class Reference

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.
	linear_arrangement (const std::vector< position > &dir_arr) noexcept
	Constructor with direct arrangement.
	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.
position	operator[] (const node_t &u) const noexcept
	Returns the position of node u.
node	operator[] (const position_t &p) const noexcept
	Returns the node at position p.
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.
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.
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.
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.
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.
void	update_inverse () noexcept
	Updates the inverse arrangement using the direct arrangement.
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.
template<typename It >
static linear_arrangement	from_direct (It begin, It end) noexcept
	Construct a linear arrangement from a direct arrangement.
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.
static linear_arrangement	from_inverse (const std::vector< node > &v) noexcept
	Construct a linear arrangement from an inverse arrangement.
template<typename It >
static linear_arrangement	from_inverse (It begin, It end) noexcept
	Construct a linear arrangement from an inverse arrangement.
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.
static linear_arrangement	identity (std::size_t n) noexcept
	Constructs an identity linear arrangement.

Protected Attributes
detail::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
	Sets m_direct and m_inverse appropriately.
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.

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);

or initialize it

lal::linear_arrangement arr;
arr.resize(n);

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.

Postcondition

m_inverse is updated.

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.

Postcondition

m_inverse is updated.

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.

Postcondition

m_inverse is updated.

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.

Postcondition

m_inverse is updated.

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.

Postcondition

m_direct is updated.

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.

Postcondition

m_direct is updated.

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.

Postcondition

m_direct is updated.

get_node_at()

node lal::linear_arrangement::get_node_at ( const position p ) const

inlinenoexcept

Returns the node at position p.

Parameters

p

Position.

Returns

The node at position p.

Precondition

The p-th index of m_inverse is up to date.

The value of p must be strictly less than the size of the arrangement (see m_n).

get_position_of()

position lal::linear_arrangement::get_position_of ( const node u ) const

inlinenoexcept

Returns the position of node u.

Parameters

u

Node.

Returns

The position of node u.

Precondition

The u-th index of m_direct is up to date.

The value of u must be strictly less than the size of the arrangement (see m_n).

identity() [1/2]

void lal::linear_arrangement::identity ( )

inlinenoexcept

Makes this arrangement an identity arrangement.

This is the arrangement in which vertex 0 is assigned to position 0, vertex 1 is assigned to position 1, and so on.

identity() [2/2]

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

inlinestaticnoexcept

Constructs an identity linear arrangement.

This is the arrangement in which vertex 0 is assigned to position 0, vertex 1 is assigned to position 1, and so on.

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], ...

Precondition

All nodes to have been assigned to a position.

operator[]() [1/2]

position lal::linear_arrangement::operator[] ( const node_t & u ) const

inlinenoexcept

Returns the position of node u.

Parameters

u

Node.

Returns

The position of node u.

Precondition

The u-th index of m_direct is up to date.

The value of u must be strictly less than the size of the arrangement (see m_n).

operator[]() [2/2]

node lal::linear_arrangement::operator[] ( const position_t & p ) const

inlinenoexcept

Returns the node at position p.

Parameters

p

Position.

Returns

The node at position p.

Precondition

The p-th index of m_inverse is up to date.

The value of p must be strictly less than the size of the arrangement (see m_n).

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 m_direct and m_inverse appropriately.

Sets the pointers m_direct and m_inverse to appropriate locations of m_memory.

shift_left()

void lal::linear_arrangement::shift_left ( )

inlinenoexcept

Shifts the vertices one position to the left.

Precondition

All nodes to have been assigned to a position.

shift_right()

void lal::linear_arrangement::shift_right ( )

inlinenoexcept

Shifts the vertices one position to the right.

Precondition

All nodes to have been assigned to a position.

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.

Precondition

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

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::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 (see m_n).

---

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

• lal/linear_arrangement.hpp