Namespace for the graphs data structures. More...

Classes
class	directed_graph
	Directed graph class. More...

class	free_tree
	Free tree graph class. More...

class	graph
	Abstract class for graphs. More...

class	rooted_tree
	Rooted tree graph class. More...

class	tree
	Tree graph class. More...

class	undirected_graph
	Undirected graph class. More...

Enumerations
enum class	tree_type { bistar , caterpillar , linear , quasistar , spider , star , unknown }
	Enumeration of several types of trees. More...

Functions
std::pair< free_tree, node >	from_head_vector_to_free_tree (const head_vector &hv, bool normalise=true, bool check=true) noexcept
	Converts a head vector into a rooted tree.

rooted_tree	from_head_vector_to_rooted_tree (const head_vector &hv, bool normalise=true, bool check=true) noexcept
	Converts a head vector into a rooted tree.

template<class G >
G	from_edge_list_to_graph (const std::vector< edge > &edge_list, bool normalise=true, bool check=true) noexcept
	Converts an edge list into a graph.

rooted_tree	from_edge_list_to_rooted_tree (const std::vector< edge > &edge_list, bool normalise=true, bool check=true) noexcept
	Converts an edge list into a rooted tree.

free_tree	from_edge_list_to_free_tree (const std::vector< edge > &edge_list, bool normalise=true, bool check=true) noexcept
	Converts an edge list into a rooted tree.

directed_graph	from_edge_list_to_directed_graph (const std::vector< edge > &edge_list, bool normalise=true, bool check=true) noexcept
	Converts an edge list into a directed graph.

undirected_graph	from_edge_list_to_undirected_graph (const std::vector< edge > &edge_list, bool normalise=true, bool check=true) noexcept
	Converts an edge list into an undirected graph.

std::ostream &	operator<< (std::ostream &os, const undirected_graph &g)
	Standard output operator for undirected graphs.

std::ostream &	operator<< (std::ostream &os, const directed_graph &g)
	Standard output operator for directed graphs.

std::ostream &	operator<< (std::ostream &os, const rooted_tree &g)
	Standard output operator for directed rooted trees.

Variables
constexpr std::size_t	__tree_type_size
	Number of elements within enumeration lal::graphs::tree_type.

Detailed Description

Namespace for the graphs data structures.

This namespace contains the data structures that implement graphs. Note that, although we do not support labelled graphs, the nodes of these graphs carry a label, a number between \(0\) and \(n-1\), where \(n\) is the number of nodes of the graph.

The functions (in other namespaces) that return a lal::node will always use a value greater than or equal to \(n\) to denote that the node index is invalid.

Enumeration Type Documentation

◆ tree_type

enum class lal::graphs::tree_type

strong

Enumeration of several types of trees.

Classifies a tree into not necessarily disjoint classes of trees.

Enumerator
bistar	Bi-star trees. These trees are made of two star trees joined by an edge at their centers.
caterpillar	Caterpillar trees. These are the trees such that a linear tree is produced when its leaves are removed [18].
linear	Linear trees. A linear tree has only two leaves, and the rest of the vertices have degree exactly two. This is, precisely, a path graph.
quasistar	Quasi star trees. Also quasi star graphs, trees where all vertices but two have degree 1. One of these two vertices has degree exactly two, the other has degree at least two.
spider	Spider trees. A spider tree has a unique vertex of degree greater than or equal to 3. The other vertices have degree 2 or 1 [8].
star	Star trees. Also star graphs, trees where all vertices but one have degree 1.
unknown	The tree could not be classified.

Function Documentation

◆ from_edge_list_to_directed_graph()

directed_graph lal::graphs::from_edge_list_to_directed_graph	(	const std::vector< edge > &	edge_list,
		bool	normalise = true,
		bool	check = true )

inlinenoexcept

Converts an edge list into a directed graph.

An edge list is a list of pairs of indices, each index in the pair being different and in \([0,n-1]\)., where \(n\) is the number of vertices of the tree.

Methods lal::io::read_edge_list read an edge list from a file in disk.

Parameters

edge_list	An edge list.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns: Returns a lal::graphs::rooted_tree obtained from the head vector.

Precondition: No edge in the list is repeated.

◆ from_edge_list_to_free_tree()

free_tree lal::graphs::from_edge_list_to_free_tree	(	const std::vector< edge > &	edge_list,
		bool	normalise = true,
		bool	check = true )

inlinenoexcept

Converts an edge list into a rooted tree.

An edge list is a list of pairs of indices, each index in the pair being different and in \([0,n-1]\)., where \(n\) is the number of vertices of the tree.

Methods lal::io::read_edge_list read an edge list from a file in disk.

Parameters

edge_list	An edge list.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns: Returns a lal::graphs::rooted_tree obtained from the head vector.

Precondition: No edge in the list is repeated.; The maximum index in the list must be equal to the number of edges in the list.

◆ from_edge_list_to_graph()

template<class G >

G lal::graphs::from_edge_list_to_graph	(	const std::vector< edge > &	edge_list,
		bool	normalise = true,
		bool	check = true )

noexcept

Converts an edge list into a graph.

An edge list is a list of pairs of indices, each index in the pair being different and in \([0,n-1]\)., where \(n\) is the number of vertices of the tree.

Methods lal::io::read_edge_list read an edge list from a file in disk.

Parameters

edge_list	An edge list.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns: Returns a lal::graphs::rooted_tree obtained from the head vector.

Precondition: No edge in the list is repeated.

◆ from_edge_list_to_rooted_tree()

rooted_tree lal::graphs::from_edge_list_to_rooted_tree	(	const std::vector< edge > &	edge_list,
		bool	normalise = true,
		bool	check = true )

inlinenoexcept

Converts an edge list into a rooted tree.

An edge list is a list of pairs of indices, each index in the pair being different and in \([0,n-1]\)., where \(n\) is the number of vertices of the tree.

Methods lal::io::read_edge_list read an edge list from a file in disk.

Parameters

edge_list	An edge list.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns: Returns a lal::graphs::rooted_tree obtained from the head vector.

Precondition: No edge in the list is repeated.; The maximum index in the list must be equal to the number of edges in the list.

◆ from_edge_list_to_undirected_graph()

undirected_graph lal::graphs::from_edge_list_to_undirected_graph	(	const std::vector< edge > &	edge_list,
		bool	normalise = true,
		bool	check = true )

inlinenoexcept

Converts an edge list into an undirected graph.

An edge list is a list of pairs of indices, each index in the pair being different and in \([0,n-1]\)., where \(n\) is the number of vertices of the tree.

Methods lal::io::read_edge_list read an edge list from a file in disk.

Parameters

edge_list	An edge list.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns: Returns a lal::graphs::rooted_tree obtained from the head vector.

Precondition: No edge in the list is repeated.

◆ from_head_vector_to_free_tree()

std::pair< free_tree, node > lal::graphs::from_head_vector_to_free_tree	(	const head_vector &	hv,
		bool	normalise = true,
		bool	check = true )

noexcept

Converts a head vector into a 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).

Methods lal::io::read_head_vector read a head vector from a file in disk.

Parameters

hv	A head vector as specified above.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns: Returns a lal::graphs::rooted_tree obtained from the head vector.

◆ from_head_vector_to_rooted_tree()

rooted_tree lal::graphs::from_head_vector_to_rooted_tree	(	const head_vector &	hv,
		bool	normalise = true,
		bool	check = true )

noexcept

Converts a head vector into a 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).

Methods lal::io::read_head_vector read a head vector from a file in disk.

Parameters

hv	A head vector as specified above.
normalise	Should the graph be normalised?
check	In case the graph is not to be normalised, should we check whether it is nor not?

Returns: Returns a lal::graphs::rooted_tree obtained from the head vector.

◆ operator<<() [1/3]

std::ostream & lal::graphs::operator<<	(	std::ostream &	os,
		const directed_graph &	g )

inline

Standard output operator for directed graphs.

Usable only by lal::graphs::directed_graph.

Parameters

os	ostream C++ object.
g	Input graph.

Returns: The output stream.

◆ operator<<() [2/3]

std::ostream & lal::graphs::operator<<	(	std::ostream &	os,
		const rooted_tree &	g )

inline

Standard output operator for directed rooted trees.

Usable by lal::graphs::rooted_tree.

Parameters

os	ostream C++ object.
g	Input graph.

Returns: The output stream.

◆ operator<<() [3/3]

std::ostream & lal::graphs::operator<<	(	std::ostream &	os,
		const undirected_graph &	g )

inline

Standard output operator for undirected graphs.

Usable by lal::graphs::undirected_graph, lal::graphs::free_tree.

Parameters

os	ostream C++ object.
g	Input graph.

Returns: The output stream.

Classes

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ tree_type

Function Documentation

◆ from_edge_list_to_directed_graph()

◆ from_edge_list_to_free_tree()

◆ from_edge_list_to_graph()

◆ from_edge_list_to_rooted_tree()

◆ from_edge_list_to_undirected_graph()

◆ from_head_vector_to_free_tree()

◆ from_head_vector_to_rooted_tree()

◆ operator<<() [1/3]

◆ operator<<() [2/3]

◆ operator<<() [3/3]