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 { empty , singleton , caterpillar , linear , bistar , quasistar , star , spider , two_linear , unknown }
	Enumeration of several types of trees. More...

Functions
undirected_graph	from_head_vector_to_undirected_graph (const head_vector &hv, const bool normalize=true, const bool check=true) noexcept
	Converts a head vector into an undirected graph.

directed_graph	from_head_vector_to_directed_graph (const head_vector &hv, const bool normalize=true, const bool check=true) noexcept
	Converts a head vector into a directed graph.

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

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

rooted_tree	from_edge_list_to_rooted_tree (const edge_list &el, const bool normalize=true, const bool check=true) noexcept
	Converts an edge list into a rooted tree.

free_tree	from_edge_list_to_free_tree (const edge_list &el, const bool normalize=true, const bool check=true) noexcept
	Converts an edge list into a rooted tree.

directed_graph	from_edge_list_to_directed_graph (const edge_list &el, const bool normalize=true, const bool check=true) noexcept
	Converts an edge list into a directed graph.

undirected_graph	from_edge_list_to_undirected_graph (const edge_list &el, const bool normalize=true, const bool check=true) noexcept
	Converts an edge list into an undirected graph.

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

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

std::ostream &	operator<< (std::ostream &os, const rooted_tree &g) noexcept
	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.

See the concepts in Graph Theory page of this documentation for further details.

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.

The description of each class can be found in The different types of trees.

Enumerator
empty	Empty tree. This is a tree with no vertices.
singleton	Singleton tree. This is a tree with a single vertex.
caterpillar	Caterpillar trees. These are the trees which, after removing their leaves, only a path graph remains [28].
linear	Linear trees. Also known as path graphs, a tree where all vertices have degree \(\le 2\).
bistar	Bi-star trees. These trees have two vertex hubs, \(h_1\) and \(h_2\), which are the only vertices that can have degree \(\ge 2\). If \(deg(h_1) = 1\) then the tree is an instance of a lal::graphs::tree_type::star tree. If \(deg(h_1) = 2\) then the tree is an instance of a lal::graphs::tree_type::quasistar tree.
quasistar	Quasi star trees. A lal::graphs::tree_type::bistar tree where \(deg(h_1) = 2\). These are a specific instance of lal::graphs::tree_type::caterpillar trees and lal::graphs::tree_type::spider trees.
star	Star trees. A lal::graphs::tree_type::bistar tree where \(deg(h_1) = 1\). These are a specific instance of lal::graphs::tree_type::quasistar trees, lal::graphs::tree_type::caterpillar trees and lal::graphs::tree_type::spider trees.
spider	Spider trees. A tree where one vertex (the hub) has degree \(\ge 3\) and the rest have degree \(\le 2\) [13]. This type of trees have as particular instances: lal::graphs::tree_type::star tree lal::graphs::tree_type::quasistar tree
two_linear	2-linear trees. Trees that have exactly two vertices of degree \(\ge 3\) [47]. Equivalently, these trees are two lal::graphs::tree_type::spider trees whose hubs are joined with a lal::graphs::tree_type::linear tree by the hubs. These trees have as specific instance lal::graphs::tree_type::bistar trees, but not lal::graphs::tree_type::star or lal::graphs::tree_type::quasistar trees.
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 edge_list &	el,
		const bool	normalize = true,
		const bool	check = true )

nodiscardnoexcept

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

el	An edge list.
normalize	Should the graph be normalized?
check	In case the graph is not to be normalized, 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 edge_list &	el,
		const bool	normalize = true,
		const bool	check = true )

nodiscardnoexcept

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

el	An edge list.
normalize	Should the graph be normalized?
check	In case the graph is not to be normalized, 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_rooted_tree()

rooted_tree lal::graphs::from_edge_list_to_rooted_tree	(	const edge_list &	el,
		const bool	normalize = true,
		const bool	check = true )

nodiscardnoexcept

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

el	An edge list.
normalize	Should the graph be normalized?
check	In case the graph is not to be normalized, 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 edge_list &	el,
		const bool	normalize = true,
		const bool	check = true )

nodiscardnoexcept

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

el	An edge list.
normalize	Should the graph be normalized?
check	In case the graph is not to be normalized, 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_directed_graph()

directed_graph lal::graphs::from_head_vector_to_directed_graph	(	const head_vector &	hv,
		const bool	normalize = true,
		const bool	check = true )

nodiscardnoexcept

Converts a head vector into a directed graph.

See Head vector for the definition of head vector.

The difference with methods lal::graphs::from_head_vector_to_free_tree and lal::graphs::from_head_vector_to_rooted_tree is that these methods require the head vector to be that of a (free or rooted) tree. This method does not impose any requirement on the head vector.

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

Parameters

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

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

◆ from_head_vector_to_free_tree()

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

nodiscardnoexcept

Converts a head vector into a rooted tree.

See Head vector for the definition of head vector.

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

Parameters

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

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

Precondition: The head vector must be of a valid rooted tree.

◆ from_head_vector_to_rooted_tree()

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

nodiscardnoexcept

Converts a head vector into a rooted tree.

See Head vector for the definition of head vector.

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

Parameters

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

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

Precondition: The head vector must be of a valid rooted tree.

◆ from_head_vector_to_undirected_graph()

undirected_graph lal::graphs::from_head_vector_to_undirected_graph	(	const head_vector &	hv,
		const bool	normalize = true,
		const bool	check = true )

nodiscardnoexcept

Converts a head vector into an undirected graph.

See Head vector for the definition of head vector.

The difference with methods lal::graphs::from_head_vector_to_free_tree and lal::graphs::from_head_vector_to_rooted_tree is that these methods require the head vector to be that of a (free or rooted) tree. This method does not impose any requirement on the head vector.

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

Parameters

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

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

◆ operator<<() [1/3]

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

inlinenoexcept

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 )

inlinenoexcept

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 )

inlinenoexcept

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_rooted_tree()

◆ from_edge_list_to_undirected_graph()

◆ from_head_vector_to_directed_graph()

◆ from_head_vector_to_free_tree()

◆ from_head_vector_to_rooted_tree()

◆ from_head_vector_to_undirected_graph()

◆ operator<<() [1/3]

◆ operator<<() [2/3]

◆ operator<<() [3/3]