lal Namespace Reference

Main namespace of the library. More...

Namespaces
namespace	generate
	Generation of different classes of objects.
namespace	graphs
	Namespace for the graphs data structures.
namespace	io
	Input/Output functions and processing of treebanks.
namespace	iterators
	Iterators namespace.
namespace	linarr
	Namespace for all linear-arrangement-dependent algorithms.
namespace	numeric
	Numeric namespace.
namespace	properties
	Namespace for all linear-arrangement-independent algorithms.
namespace	utilities
	Set of utilities.

Typedefs
typedef uint32_t	node
	Node type.
typedef uint32_t	position
	Node's position type.
typedef std::vector< position >	linear_arrangement
	A linear arrangement of the nodes of a graph.
typedef std::pair< node, node >	edge
	Edge type.
typedef std::pair< edge, edge >	edge_pair
	Edge pair type.
typedef std::vector< node >	neighbourhood
	List of nodes.
typedef std::vector< uint32_t >	head_vector
	A head vector representation of a (usually) rooted tree.

Variables
constexpr std::string_view	__lal_major_verno = "21.07"
	Major version number of the library's current state. The year and month in which it was released.
constexpr std::string_view	__lal_patch_verno = "01"
	Patch version number of the library's current state.

Detailed Description

Main namespace of the library.

This namespace groups all namespaces of the library. Each namespace classifies the classes and functions in categories.

Typedef Documentation

head_vector

typedef std::vector<uint32_t> lal::head_vector

A head vector representation of a (usually) rooted tree.

A head vector of an n-vertex tree is a list of non-negative integer numbers. The number at position i denotes the parent node of the vertex at said position. Value '0' denotes the root. In this case, the vertex corresponding to the value '0' is not labelled as a root.

Each tree is formatted as a list of whole, positive numbers (including zero), each representing a node of the tree. The number 0 denotes the root of the tree, and a number at a certain position indicates its parent node. For example, when number 4 is at position 9 it means that node 9 has parent node 4. Therefore, if number 0 is at position 1 it means that node 1 is the root of the tree. A complete example of such a tree's representation is the following

  0 3 4 1 6 3

which should be interpreted as

(a) predecessor:       0 3 4 1 6 3
(b) node of the tree:  1 2 3 4 5 6

Note that lines like these are not valid:

(1) 0 2 2 2 2 2
(2) 2 0 0

Line (1) is not valid due to a self-reference in the second position, and (2) is not valid since it contains two '0' (i.e., two roots).

linear_arrangement

typedef std::vector<position> lal::linear_arrangement

A linear arrangement of the nodes of a graph.

If pi is a linear arrangement of n nodes:

lal::linearrgmnt pi(n);

then the u-th position gives the position of node u in the arrangement:

position pu = pi[u];

For the sake of simplicity, we refer to the arrangement \( \pi[i]=i \), where \(i\) denotes both the nodes of the graph and a position in the linear arrangement, as the identity arrangement and is denoted by \(\pi_I\).