Rooted tree graph class. More...

#include <rooted_tree.hpp>

Inheritance diagram for lal::graphs::rooted_tree:

Public Member Functions
	rooted_tree () noexcept
	Empty constructor.

	rooted_tree (uint32_t n) noexcept
	Constructor with number of nodes and root node.

	rooted_tree (const rooted_tree &r) noexcept
	Copy constructor.

	rooted_tree (rooted_tree &&r) noexcept
	Move constructor.

	rooted_tree (const free_tree &t, node r) noexcept
	Constructor with tree and root node.

virtual	~rooted_tree () noexcept
	Destructor.

rooted_tree &	operator= (const rooted_tree &r) noexcept
	Copy assignment operator.

rooted_tree &	operator= (rooted_tree &&r) noexcept
	Move assignment operator.

rooted_tree &	add_edge (node s, node t, bool norm=true, bool check_norm=true) noexcept
	Adds an edge to the tree.

rooted_tree &	add_edge_bulk (node s, node t) noexcept
	Adds an edge to the graph.

void	finish_bulk_add (bool norm=true, bool check=true) noexcept
	Finishes adding edges in bulk.

rooted_tree &	add_edges (const std::vector< edge > &edges, bool norm=true, bool check_norm=true) noexcept
	Adds a list of edges to the graph.

rooted_tree &	set_edges (const std::vector< edge > &edges, bool norm=true, bool check_norm=true) noexcept
	Sets the edges to the graph.

rooted_tree &	remove_edge (node s, node t, bool norm=false, bool check_norm=true) noexcept
	Remove an edge from this graph.

rooted_tree &	remove_edges (const std::vector< edge > &edges, bool norm=true, bool check_norm=true) noexcept
	Remove an edge from this graph.

virtual rooted_tree &	remove_edges_incident_to (node u, bool norm=true, bool check_norm=true) noexcept
	Remove all edges incident to a given vertex.

void	disjoint_union (const rooted_tree &t, bool connect_roots=true) noexcept
	Disjoint union of trees.

bool	find_edge_orientation () noexcept
	Finds the orientation of the edges.

void	set_valid_orientation (bool valid) noexcept
	Sets wether the type of the rooted tree is valid or not.

void	init_rooted (const free_tree &t, node r) noexcept
	Initialiser with tree and root node.

void	calculate_size_subtrees () noexcept
	Calculates the number of nodes at every rooted subtree.

void	calculate_tree_type () noexcept
	Calculates the type of tree.

void	set_root (node r) noexcept
	Set the root of this tree.

bool	is_rooted () const noexcept
	Returns whether this tree is a rooted tree.

bool	is_rooted_tree () const noexcept
	Is this tree a valid rooted tree?

bool	is_orientation_valid () const noexcept
	Is the orientation of the edges valid?

node	get_root () const noexcept
	Return the root of this tree.

bool	has_root () const noexcept

uint32_t	get_num_nodes_subtree (node u) const noexcept
	Get the size of a subtree rooted at a given node.

bool	are_size_subtrees_valid () const noexcept
	Is a recalculation of the subtree's sizes needed?

std::vector< edge >	get_edges_subtree (node u, bool relab=false) const noexcept
	Retrieve the edges of the subtree rooted at u.

rooted_tree	get_subtree (node u) const noexcept
	Retrieve the subtree rooted at node u.

free_tree	to_free_tree (bool norm=true, bool check=true) const noexcept
	Converts this rooted tree into a free tree (see free_tree).

head_vector	get_head_vector () const noexcept
	Converts a rooted tree into a head vector.

void	normalise () noexcept
	Normalises the graph.

bool	check_normalised () noexcept
	Checks if the graph is normalised.

std::vector< edge_pair >	get_Q () const noexcept
	Returns all independent pairs of edges of this graph.

std::vector< edge >	get_edges () const noexcept
	Returns all edges of this graph.

bool	has_edge (node u, node v) const noexcept
	Returns true if the edge \((u,v)\) exists in the graph.

const neighbourhood &	get_out_neighbours (node u) const noexcept
	Returns the out-neighbours of node u.

const neighbourhood &	get_in_neighbours (node u) const noexcept
	Returns the in-neighbours of node u.

uint32_t	get_degree (node u) const noexcept
	Returns the in-degree plus the out-degree of this vertex.

uint32_t	get_out_degree (node u) const noexcept
	Returns the out-degree of a node.

uint32_t	get_in_degree (node u) const noexcept
	Returns the in-degree of a node.

bool	is_directed () const noexcept
	Returns whether this graph is directed or not.

bool	is_undirected () const noexcept
	Returns whether this graph is undirected or not.

undirected_graph	to_undirected (bool norm=true, bool check=true) const noexcept
	Converts this directed graph into an undirected graph.

bool	is_tree () const noexcept
	Is this graph is an actual tree?

bool	can_add_edge (node s, node t) const noexcept
	Can this edge be added?

bool	can_add_edges (const std::vector< edge > &edges) const noexcept
	Can these edges be added?

uint32_t	get_num_nodes_component (node u) const noexcept
	Amount of nodes in a connected component of the tree.

bool	is_of_tree_type (const tree_type &tt) const noexcept
	Returns whether this tree is of type tt.

bool	is_tree_type_valid () const noexcept
	Is the type of this tree valid?

std::vector< std::string >	get_tree_type_list () const noexcept
	Returns the list of types as a list of strings.

virtual void	init (uint32_t n) noexcept
	Allocates the necessary memory for this class.

virtual void	clear () noexcept
	Frees the memory occupied by this graph.

void	set_normalised (bool v=true) noexcept
	Sets whether this graph is normalised or not.

bool	has_node (node u) const noexcept
	Returns true if node u is in this graph.

uint32_t	get_num_nodes () const noexcept
	Returns the number of ndoes.

uint32_t	get_num_edges () const noexcept
	Returns the number of edges.

bool	is_normalised () const noexcept
	Returns whether this graph is normalised or not.

Protected Member Functions
virtual void	_init (uint32_t n) noexcept

virtual void	_clear () noexcept

void	call_union_find_after_add (node u, node v, uint32_t const root_of, uint32_t const root_size) noexcept
	A call to the union find method.

void	call_union_find_after_add (node u, node v, uint32_t const root_of, uint32_t const root_size) const noexcept
	A const call to the union find method.

void	call_union_find_after_remove (node u, node v, uint32_t const root_of, uint32_t const root_size) noexcept
	A call to the union find method.

void	call_union_find_after_remove (node u, node v, uint32_t const root_of, uint32_t const root_size) const noexcept
	A const call to the union find method.

void	copy_full_rooted_tree (const rooted_tree &r) noexcept
	Copies all members of this class and the parent class.

void	move_full_rooted_tree (rooted_tree &&r) noexcept
	Moves all members of this class and the parent class.

void	copy_full_directed_graph (const directed_graph &d) noexcept
	Copies all members of this class and the parent class.

void	move_full_directed_graph (directed_graph &&d) noexcept
	Moves all members of this class and the parent class.

void	tree_only_init (uint32_t n) noexcept
	Initialises only the memory of class tree.

void	tree_only_clear () noexcept
	Clears the memory used by only class tree.

void	tree_only_copy (const tree &t) noexcept
	Copies only members of class tree.

void	tree_only_move (tree &&t) noexcept
	Moves only members of class tree.

void	extra_work_per_edge_add (node u, node v) noexcept
	Do some extra work after an edge has been added.

void	extra_work_per_edge_remove (node u, node v) noexcept
	Do some extra work after an edge has been removed.

void	tree_only_extra_work_edges_set () noexcept

void	fill_union_find () noexcept

void	copy_full_graph (const graph &g) noexcept
	Copies all members of this class.

void	move_full_graph (graph &&g) noexcept
	Moves all members of this class.

void	__disjoint_union (const graph &g) noexcept
	Disjoint union of graphs.

void	normalise_after_add (bool norm, bool check) noexcept
	Normalise the graph after one (or more) edges have been added.

void	normalise_after_remove (bool norm, bool check) noexcept
	Normalise the graph after one (or more) edges have been removed.

Protected Attributes
node	m_root = 0
	Root of the tree.

bool	m_has_root = false
	Has the root been set?

bool	m_valid_orientation = false
	Is the orientation of the edges valid?

std::vector< uint32_t >	m_size_subtrees
	Number of nodes of the subtrees rooted at a certain node.

bool	m_are_size_subtrees_valid = false
	Are the contents of m_size_subtrees valid?

std::vector< neighbourhood >	m_in_adjacency_list
	In-neighbours for every node.

std::vector< node >	m_root_of
	The root of every vertex in the union-find data structure.

std::vector< uint32_t >	m_root_size
	The size of the connected component that a root belongs to.

std::array< bool, __tree_type_size >	m_tree_type
	The type of this tree.

bool	m_is_tree_type_valid = false
	Is the type of this tree valid?

std::vector< neighbourhood >	m_adjacency_list
	Data structure that implements the graph.

uint32_t	m_num_edges = 0
	Amount of edges of this graph.

bool	m_normalised = true
	Is this graph normalised?

Private Member Functions
void	disjoint_union (const directed_graph &g) noexcept
	Disjoint union of graphs.

void	remove_single_edge (node u, node v, neighbourhood &out_u, neighbourhood &in_v) noexcept
	Removes a single edge.

Detailed Description

Rooted tree graph class.

This class provides its users with an abstraction of rooted trees. Rooted trees are free trees in which one vertex has been designated as the root. Furthermore, in the context of this library, these trees' edges are always oriented towards the leaves (away from the root); this is known as an arborescence. Many methods require objects of this class to be valid rooted trees: the object must be a tree (see is_tree), must have a root (see has_root), and be a valid rooted tree (be an arborescence, that is, see is_orientation_valid).

Rooted trees can be constructed in two different ways:

Using an already-constructed free tree via a class constructor, where users have to indicate the root (see rooted_tree(const free_tree&, node)). Alternatively, one can use the method init_rooted, which has the same set of parameters.
Adding edge after edge. In this class, as in free_tree, this addition is constrained so that the underlying undirected graph does not contain cycles. Before (or after) the addition of all the edges, it is recommended the root be set using set_root. If the edges have been added in a systematic fashion – so it is known whether the tree is an arborescence or not –, it is recommended that the validity of the edges' orientation be set by the user via method set_valid_orientation. If it is not known (or it can't be guaranteed) that the resulting tree is an arborescence, use method find_edge_orientation.

Adding edges one by one has a serious drawback. In case the edges do not have a consistent orientation (either always pointing away from the root or always pointing towards it), the resulting graph is not considered to be a valid rooted tree (see is_rooted_tree). Due to efficiency reasons, orientation of edges is not checked before or after their addition. Recall that removal of edges is allowed at every moment.

The root allows defining further properties on these graphs. For example, the user can query information regarding subtrees of a particular rooted tree (see methods get_num_nodes_subtree, calculate_size_subtrees, get_edges_subtree, and get_subtree).

This class allows flexibility of use of rooted trees regarding the root's choice. Method set_root allows changing the root of rooted trees multiple times and at any time. However, any information dependent on the root becomes invalid upon any change of the root. This information includes, and may not be limited to, the type of rooted tree and the size of the subtrees (see get_num_nodes_subtree). For this reason, is is strongly recommended to build a free tree first and use the constructor rooted_tree(const free_tree&, node), or the method init_rooted, in order to build rooted trees.

Constructor & Destructor Documentation

◆ rooted_tree() [1/3]

lal::graphs::rooted_tree::rooted_tree ( uint32_t n )

inlinenoexcept

Constructor with number of nodes and root node.

Parameters

n	Number of vertices.

◆ rooted_tree() [2/3]

lal::graphs::rooted_tree::rooted_tree ( const rooted_tree & r )

inlinenoexcept

Copy constructor.

Parameters

r	Rooted tree.

◆ rooted_tree() [3/3]

lal::graphs::rooted_tree::rooted_tree ( rooted_tree && r )

inlinenoexcept

Move constructor.

Parameters

r	Rooted tree.

Member Function Documentation

◆ __disjoint_union()

void lal::graphs::graph::__disjoint_union ( const graph & g )

protectednoexceptinherited

Disjoint union of graphs.

Given a graph, append it to the current graph.

All the nodes in g are relabelled starting at n, the number of nodes of the current graph.

Parameters

g	Input graph.

Precondition: This graph and g must be of the same type (both must be either undirected, or both directed).

Postcondition: The graph is normalised only if it was normalised before the call and g is also normalised.

◆ _clear()

virtual void lal::graphs::rooted_tree::_clear ( )

protectedvirtualnoexcept

Clears the memory of rooted_tree, undirected_graph and graph classes.

Reimplemented from lal::graphs::directed_graph.

◆ _init()

virtual void lal::graphs::rooted_tree::_init ( uint32_t n )

protectedvirtualnoexcept

Initialises memory of rooted_tree, undirected_graph and graph classes.

Reimplemented from lal::graphs::directed_graph.

◆ add_edge()

rooted_tree & lal::graphs::rooted_tree::add_edge	(	node	s,
		node	t,
		bool	norm = true,
		bool	check_norm = true )

virtualnoexcept

Adds an edge to the tree.

This operation checks that the edge added does not produce cycles only in a debug compilation of the library. For a more controlled addition of the edges, see can_add_edge.

For developers: method graph::extra_work_per_edge_add is called after the edge has been added.

Parameters

s	Valid node index: \(0 \le s < n\).
t	Valid node index: \(0 \le t < n\).
norm	Should the graph be normalised?
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

Precondition: \(s \neq t\); Edge \(\{s,t\}\) is not part of the graph.

Postcondition: If norm is true the graph is guaranteed to be normalised after the addition of the edge.

Reimplemented from lal::graphs::directed_graph.

◆ add_edge_bulk()

rooted_tree & lal::graphs::rooted_tree::add_edge_bulk	(	node	s,
		node	t )

noexcept

Adds an edge to the graph.

This method only adds an edge, and does no other work: normalisation is not checked, and no extra work per edge is done.

Parameters

s	Valid node index: \(0 \le s < n\).
t	Valid node index: \(0 \le t < n\).

Precondition: \(u \neq v\).; The edge \(\{s,t\}\) is not part of the graph.

Postcondition: If norm is true the graph is guaranteed to be normalised after the addition of the edge.

◆ add_edges()

rooted_tree & lal::graphs::rooted_tree::add_edges	(	const std::vector< edge > &	edges,
		bool	norm = true,
		bool	check_norm = true )

virtualnoexcept

Adds a list of edges to the graph.

This function checks that edges will not produce cycles only in a debug compilation of the library. Moreover, this operation is faster than calling add_edge since the edges are added in bulk. For a more controlled addition of the edges, see can_add_edges.

For developers: method graph::extra_work_per_edge_add is called after each edge has been added.

Parameters

edges	The edges to be added.
norm	Normalise the graph after the insertions.
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

Precondition: All the edges in edges must meet the precondition of method add_edge.; None of the subsets of the list of edges can produce cycles when added.

Postcondition: If norm is true the graph is guaranteed to be normalised after the addition of the edges.

Reimplemented from lal::graphs::directed_graph.

◆ are_size_subtrees_valid()

bool lal::graphs::rooted_tree::are_size_subtrees_valid ( ) const

inlinenoexcept

Is a recalculation of the subtree's sizes needed?

If the method returns false then the user should call calculate_size_subtrees so that the size of every rooted subtree is recalculated. This information must be calculated prior to calling many functions of this library.

Returns: Whether m_size_subtrees should be recalculated or not.

◆ calculate_size_subtrees()

void lal::graphs::rooted_tree::calculate_size_subtrees ( )

noexcept

Calculates the number of nodes at every rooted subtree.

Precondition: The object must be a tree (see is_tree()).; The tree must have a root (see has_root()).

Postcondition: Method are_size_subtrees_valid returns true.

◆ calculate_tree_type()

void lal::graphs::rooted_tree::calculate_tree_type ( )

virtualnoexcept

Calculates the type of tree.

See tree_type for the list of different tree types.

Implements lal::graphs::tree.

◆ call_union_find_after_add() [1/2]

void lal::graphs::rooted_tree::call_union_find_after_add	(	node	u,
		node	v,
		uint32_t *const	root_of,
		uint32_t *const	root_size ) const

protectedvirtualnoexcept

A const call to the union find method.

This is a helper method to be able to call a template in the lal::internal namespace which updates the union find data structure under addition of an edge.

Parameters

u	Node that is connected to v.
v	Node that is connected to u.
root_of	Array of n elements relating each vertex to its root in the union find data structure.
root_size	Array of n elements relating each vertex to the size of the connected component it belongs to.

Implements lal::graphs::tree.

◆ call_union_find_after_add() [2/2]

void lal::graphs::rooted_tree::call_union_find_after_add	(	node	u,
		node	v,
		uint32_t *const	root_of,
		uint32_t *const	root_size )

protectedvirtualnoexcept

A call to the union find method.

This is a helper method to be able to call a template in the lal::internal namespace which updates the union find data structure under addition of an edge.

Parameters

u	Node that is connected to v.
v	Node that is connected to u.
root_of	Array of n elements relating each vertex to its root in the union find data structure.
root_size	Array of n elements relating each vertex to the size of the connected component it belongs to.

Implements lal::graphs::tree.

◆ call_union_find_after_remove() [1/2]

void lal::graphs::rooted_tree::call_union_find_after_remove	(	node	u,
		node	v,
		uint32_t *const	root_of,
		uint32_t *const	root_size ) const

protectedvirtualnoexcept

A const call to the union find method.

This is a helper method to be able to call a template in the lal::internal namespace which updates the union find data structure under removal of an edge.

Parameters

u	Node that is connected to v.
v	Node that is connected to u.
root_of	Array of n elements relating each vertex to its root in the union find data structure.
root_size	Array of n elements relating each vertex to the size of the connected component it belongs to.

Implements lal::graphs::tree.

◆ call_union_find_after_remove() [2/2]

void lal::graphs::rooted_tree::call_union_find_after_remove	(	node	u,
		node	v,
		uint32_t *const	root_of,
		uint32_t *const	root_size )

protectedvirtualnoexcept

A call to the union find method.

This is a helper method to be able to call a template in the lal::internal namespace which updates the union find data structure under removal of an edge.

Parameters

u	Node that is connected to v.
v	Node that is connected to u.
root_of	Array of n elements relating each vertex to its root in the union find data structure.
root_size	Array of n elements relating each vertex to the size of the connected component it belongs to.

Implements lal::graphs::tree.

◆ can_add_edge()

bool lal::graphs::tree::can_add_edge	(	node	s,
		node	t ) const

noexceptinherited

Can this edge be added?

In a tree, an edge can only be added if it does not produce cycles, and it has not been added before.

Parameters

s	First node of the edge.
t	Second node of the edge.

Returns: Whether the addition of this new edge can be added to the tree without producing cycles.

◆ can_add_edges()

bool lal::graphs::tree::can_add_edges ( const std::vector< edge > & edges ) const

noexceptinherited

Can these edges be added?

In a tree, a set of edges can only be added if their addition to the tree do not produce cycles and none of them have been added before.

Parameters

edges List of edges.

Returns: Whether the addition of these new edges can be added to the tree without producing cycles.

◆ check_normalised()

bool lal::graphs::directed_graph::check_normalised ( )

virtualnoexceptinherited

Checks if the graph is normalised.

Checks, whether the graph's adjacency structure is normalised or not. In case it is, attribute m_normalised is set to true, so method is_normalised evaluates to true.

Reimplemented from lal::graphs::graph.

◆ clear()

virtual void lal::graphs::graph::clear ( )

virtualnoexceptinherited

Frees the memory occupied by this graph.

See _clear for details.

Postcondition: The graph is normalised. The number of edges is 0.

◆ disjoint_union() [1/2]

void lal::graphs::directed_graph::disjoint_union ( const directed_graph & g )

privatenoexcept

Disjoint union of graphs.

Given a graph, append it to the current graph.

All the nodes in g are relabelled starting at n, the number of nodes of the current graph.

Parameters

g	Input graph.

Postcondition: The graph is normalised only if it was normalised before the call and g is also normalised.

◆ disjoint_union() [2/2]

void lal::graphs::rooted_tree::disjoint_union	(	const rooted_tree &	t,
		bool	connect_roots = true )

noexcept

Disjoint union of trees.

Append a rooted tree to this tree. All the nodes in t are relabelled starting at n, the number of nodes of the current tree. If the current graph has no vertices, then the contents of t are simply copied into this graph.

Parameters

t	Input tree.
connect_roots	The root of the current tree and the root of t are joined by an edge.

Precondition: If connect_roots is true then both trees need to have a root (see method has_root).

Postcondition

The root (if set) of the current tree is kept.

Copying the edges of t into this tree retains their original orientation.

The size of the subtrees might need recalculating:

If method are_size_subtrees_valid() returns true for both trees then the subtree sizes are updated and do not need to be recalculated and method are_size_subtrees_valid() still returns true.
If for one of the two graphs the method are_size_subtrees_valid() returns false then it will still return false after this operation.

The graph resulting from the union is normalised only if the two graphs were normalised prior to the union.

◆ fill_union_find()

void lal::graphs::tree::fill_union_find ( )

protectednoexceptinherited

Fills the Union-Find data structure assuming that the graph structure has all of its edges.

◆ find_edge_orientation()

bool lal::graphs::rooted_tree::find_edge_orientation ( )

noexcept

Finds the orientation of the edges.

It is mandatory that this tree be an arborescence. Therefore, when the tree has been built by adding edges (see add_edge, add_edges), the user must tell this class whether what has been built is an arborescence or not. One can do this by calling method find_edge_orientation or by setting the type directly using method set_valid_orientation.

This method examines the orientation of the tree's edges with respect to the root and to the leaves, i.e., it determines whether all edges are oriented towards the leaves (away from the root).

Returns: True if the tree is an arborescence. Returns false otherwise.

Precondition: This object is a tree (see is_tree).; This tree has a root (see has_root).

Postcondition: Method is_orientation_valid evaluates to true if the tree is an arborescence, or to false if it not an arborescence.

◆ finish_bulk_add()

void lal::graphs::rooted_tree::finish_bulk_add	(	bool	norm = true,
		bool	check = true )

virtualnoexcept

Finishes adding edges in bulk.

Parameters

norm	Normalise the tree.
check	Check whether the tree is normalised or not.

Precondition: All edges have been added.

Reimplemented from lal::graphs::directed_graph.

◆ get_degree()

uint32_t lal::graphs::directed_graph::get_degree ( node u ) const

inlinenoexceptinherited

Returns the in-degree plus the out-degree of this vertex.

Returns the degree of this vertex in its underlying undirected structure. Same as get_in_degree + get_out_degree.

Parameters

u Vertex

Returns: The (in + out) degree of this vertex.

◆ get_edges_subtree()

std::vector< edge > lal::graphs::rooted_tree::get_edges_subtree	(	node	u,
		bool	relab = false ) const

noexcept

Retrieve the edges of the subtree rooted at u.

The list of edges returned contains labels that depend on the parameter relab. If relab is true then the nodes are relabelled to numbers in \([0, n_u)\), where \(n_u\) is the number of nodes of the subtree rooted at u, rather than keeping the original labelling of numbers in \([0,n)\), where n is the number of nodes of the tree.

In case of directed trees, the subtree is extracted regardless of the orientation of the edges. For example, consider the following complete binary tree of 7 nodes, whose edges are

0 -> 1 -> 3
       -> 4
  -> 2 -> 5
       -> 6

The edges of the subtree rooted at 1 are "1 -> 3" and "1 -> 4". Moreover, the orientation of the edges in the new tree is kept.

This method can be seen as a way of relabelling nodes when u is the root of the tree and relab is true.

Parameters

u	Root node of the subtree.
relab	Should the nodes be relabelled?

Returns: A list of edges.

Precondition: The object must be a valid rooted tree (see is_rooted_tree).

Postcondition: Whenever relab is true, the label of the first node of the first edge is guaranteed to be node '0'.

◆ get_head_vector()

head_vector lal::graphs::rooted_tree::get_head_vector ( ) const

noexcept

Converts a rooted tree into a head vector.

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.

Returns: The head vector representation of this tree.

Precondition: This tree is a valid rooted tree (see is_rooted_tree).

◆ get_in_neighbours()

const neighbourhood & lal::graphs::directed_graph::get_in_neighbours ( node u ) const

inlinenoexceptinherited

Returns the in-neighbours of node u.

Parameters

u Node

Returns: The list of nodes entering at node u.

◆ get_num_nodes_component()

uint32_t lal::graphs::tree::get_num_nodes_component ( node u ) const

inlinenoexceptinherited

Amount of nodes in a connected component of the tree.

When tree has had an edge removed, or when it is not completely built, i.e., it lack some edges, the resulting graph is clearly a forest. This function returns the size of the forest node u belongs to.

In directed trees one has to see this amount as the number of nodes of the component in the undirected version of the forest.

Parameters

u	Input node.

Returns: The size of the connected component of u.

◆ get_num_nodes_subtree()

uint32_t lal::graphs::rooted_tree::get_num_nodes_subtree ( node u ) const

inlinenoexcept

Get the size of a subtree rooted at a given node.

Parameters

u	Vertex of the tree.

Returns: The number of nodes of the subtree rooted at u.

Precondition: Method are_size_subtrees_valid returns true.

◆ get_out_neighbours()

const neighbourhood & lal::graphs::directed_graph::get_out_neighbours ( node u ) const

inlinenoexceptinherited

Returns the out-neighbours of node u.

Parameters

u Node

Returns: The list of nodes leaving node u.

◆ get_Q()

std::vector< edge_pair > lal::graphs::directed_graph::get_Q ( ) const

virtualnoexceptinherited

Returns all independent pairs of edges of this graph.

The set \(Q(G)\) is defined as the pairs of edges of \(G\), \(E(G) \times E(G)\), that are independent, that is, that share no nodes.

Implements lal::graphs::graph.

◆ get_subtree()

rooted_tree lal::graphs::rooted_tree::get_subtree ( node u ) const

noexcept

Retrieve the subtree rooted at node u.

Parameters

u	Root of the subtree.

Returns: A tree containing the nodes of the subtree rooted at node u.

Precondition: The object must be a valid rooted tree (see is_rooted_tree).

Postcondition: The subtree keeps the orientation of the edges in the original tree.

◆ get_tree_type_list()

std::vector< std::string > lal::graphs::tree::get_tree_type_list ( ) const

noexceptinherited

Returns the list of types as a list of strings.

Returns: The list of types as a list of strings.

◆ has_root()

bool lal::graphs::rooted_tree::has_root ( ) const

inlinenoexcept

Returns whether this rooted tree's root has been set or not (see set_root).

◆ init()

virtual void lal::graphs::graph::init ( uint32_t n )

virtualnoexceptinherited

Allocates the necessary memory for this class.

See _init for details.

Parameters

n	Number of nodes.

◆ init_rooted()

void lal::graphs::rooted_tree::init_rooted	(	const free_tree &	t,
		node	r )

noexcept

Initialiser with tree and root node.

Constructs a rooted tree from a free tree and one of its nodes as the root of the rooted tree.

Since the edges are oriented, method is_tree must be true on parameter t (otherwise, some edges might not be reachable from the root and hence completely undirectable).

Parameters

t	Undirected tree.
r	Root of the directed tree. A node of g.

Precondition: Parameter t must be a tree (see is_tree).

Postcondition: Method is_rooted_tree returns true.

◆ is_normalised()

bool lal::graphs::graph::is_normalised ( ) const

inlinenoexceptinherited

Returns whether this graph is normalised or not.

A graph is normalised if every node's adjacency list is sorted increasingly. For this, use method normalise().

Returns: The value of m_normalised.

◆ is_of_tree_type()

bool lal::graphs::tree::is_of_tree_type ( const tree_type & tt ) const

inlinenoexceptinherited

Returns whether this tree is of type tt.

See method calculate_tree_type to know how to calculate a tree's type.

Parameters

tt	Type of tree (see lal::graphs::tree_type).

Returns: True if this tree is of type tt.

◆ is_orientation_valid()

bool lal::graphs::rooted_tree::is_orientation_valid ( ) const

inlinenoexcept

Is the orientation of the edges valid?

The edges' orientation is valid if they are all oriented towards the leaves (away from the root).

This function returns the value of private attribute m_valid_orientation.

Returns: The whether the orientation is valid or not.

◆ is_rooted_tree()

bool lal::graphs::rooted_tree::is_rooted_tree ( ) const

inlinenoexcept

Is this tree a valid rooted tree?

A tree is a valid rooted tree when:

the underlying undirected graph is connected and does not contain cycles (see is_tree()),
the tree has a root (see has_root, set_root, get_root),
the orientation of the edges is valid (see is_orientation_valid).

Returns: Whether this tree is a valid rooted tree or not.

◆ is_tree()

bool lal::graphs::tree::is_tree ( ) const

inlinenoexceptinherited

Is this graph is an actual tree?

Returns true if the number of edges is one less than the number of nodes. Note that this would not really be true if the addition of edges was not constrained. Since it is constrained in a way that no cycles can be produced (for example, see free_tree::add_edge, or free_tree::add_edges), then we only need to check for the number of edges.

For further characterisations of a tree see [19] (chapter 4, pages 32-33).

Returns: True or false depending on whether this graph fits the defintion of tree.

◆ is_tree_type_valid()

bool lal::graphs::tree::is_tree_type_valid ( ) const

inlinenoexceptinherited

Is the type of this tree valid?

This function enables users determine when this tree's type should be calculated.

In case this function returns false, users should call function calculate_tree_type in order to obtain a valid tree type. Note, however, that prior to calling the function the type of this tree might be lal::graphs::tree_type::unknown and that the tree type may remain lal::graphs::tree_type::unknown even after the type has been calculated. Nevertheless, users should be suspicious of a tree being of lal::graphs::tree_type::unknown (in fact, of any) type if this method returns false, yet they should be sure of it if the type was calculated via method calculate_tree_type.

Returns: True or false depending on whether the tree type was calculated or not.

◆ normalise()

void lal::graphs::directed_graph::normalise ( )

virtualnoexceptinherited

Normalises the graph.

Sorts this graph's adjacency list structure in increasing order.

Besides expensive, this method may be unnecessary. Method check_normalised() checks whether the graph is normalised or not; in case it is, using this method is completely unnecessary.

Postcondition: Method is_normalised evaluates to true.

Reimplemented from lal::graphs::graph.

◆ operator=() [1/2]

rooted_tree & lal::graphs::rooted_tree::operator= ( const rooted_tree & r )

inlinenoexcept

Copy assignment operator.

Parameters

r	Rooted tree.

◆ operator=() [2/2]

rooted_tree & lal::graphs::rooted_tree::operator= ( rooted_tree && r )

inlinenoexcept

Move assignment operator.

Parameters

r	Rooted tree.

◆ remove_edge()

rooted_tree & lal::graphs::rooted_tree::remove_edge	(	node	s,
		node	t,
		bool	norm = false,
		bool	check_norm = true )

virtualnoexcept

Remove an edge from this graph.

For developers: method graph::extra_work_per_edge_remove is called after the edge has been removed.

Parameters

s	Valid node index: \(0 \le s < n\).
t	Valid node index: \(0 \le t < n\).
norm	Normalise the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

Precondition: The edge must exist.

Postcondition: If norm is true the graph is guaranteed to be normalised after the addition of the edge.; The validity of rooted tree and the size of the subtrees are invalidated, i.e., methods is_orientation_valid and are_size_subtrees_valid return false.

Reimplemented from lal::graphs::directed_graph.

◆ remove_edges()

rooted_tree & lal::graphs::rooted_tree::remove_edges	(	const std::vector< edge > &	edges,
		bool	norm = true,
		bool	check_norm = true )

virtualnoexcept

Remove an edge from this graph.

This operation is faster than removing edges one by one with remove_edge(node,node,bool,bool) since the edges are removed in bulk.

For developers: method graph::extra_work_per_edge_remove is called after each edge has been removed.

Parameters

edges	The edges to be deleted.
norm	Normalise the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

Precondition: All the edges in edges must meet the precondition of method add_edge(node,node,bool,bool).

Postcondition: If norm is true the graph is guaranteed to be normalised after the addition of the edge.; The validity of the rooted tree and the size of the subtrees are invalidated, i.e., methods is_orientation_valid and are_size_subtrees_valid return false.

Reimplemented from lal::graphs::directed_graph.

◆ remove_edges_incident_to()

virtual rooted_tree & lal::graphs::rooted_tree::remove_edges_incident_to	(	node	u,
		bool	norm = true,
		bool	check_norm = true )

virtualnoexcept

Remove all edges incident to a given vertex.

This operation is faster than removing edges one by one with remove_edge(node,node,bool,bool) since the edges are removed in bulk.

For developers: method lal::graphs::graph::extra_work_per_edge_remove is called after each edge has been removed.

Parameters

u	The node whose incident vertices are to be removed.
norm	Normalise the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

Postcondition: If norm is true the graph is guaranteed to be normalised after the addition of the edge.

Reimplemented from lal::graphs::directed_graph.

◆ remove_single_edge()

void lal::graphs::directed_graph::remove_single_edge	(	node	u,
		node	v,
		neighbourhood &	out_u,
		neighbourhood &	in_v )

privatenoexceptinherited

Removes a single edge.

Parameters

u	First node of edge.
v	Second node of edge.
out_u	Out-neighbourhood of node u.
in_v	In-neighbourhood of node v.

◆ set_edges()

rooted_tree & lal::graphs::rooted_tree::set_edges	(	const std::vector< edge > &	edges,
		bool	norm = true,
		bool	check_norm = true )

virtualnoexcept

Sets the edges to the graph.

Sets the edges of this graph assuming that the nodes indexed in the list are, at most, the number of nodes of this graph.

This list of edges is assumed to be all the edges that are going to be added to this graph. This means that the internal data structures are constructed more efficiently than when adding edges one by one (see add_edge) or in several chunks (see add_edges). For a more controlled addition of the edges, see can_add_edges.

Moreover, the current structure of the graph is cleared before setting the new edges.

Parameters

edges	The edges to be added.
norm	Normalise the graph after the insertions.
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

Precondition: The graph has been initialized with as many nodes as vertices in the list of edges.; There are no repeated edges in the list.; The list of edges must form a valid rooted tree, i.e., there must be a unique vertex with no in-going edges, and there must be no cycles.

Postcondition: If norm is true the graph is guaranteed to be normalised after the addition of the edge.; The tree has a valid root which is, potentially, different from the previous root it had. Therefore, method has_root returns true.; The tree has a valid edge orientation, i.e., method is_orientation_valid returns true.; Method is_rooted_tree returns true.

Reimplemented from lal::graphs::directed_graph.

◆ set_root()

void lal::graphs::rooted_tree::set_root ( node r )

noexcept

Set the root of this tree.

Changing the root of a rooted tree invalidates information dependant on the tree. See the postconditions for details.

Parameters

r	Vertex that represents the root.

Postcondition: Method has_root returns true.; The type of rooted tree and the size of the subtrees are invalidated.

◆ set_valid_orientation()

void lal::graphs::rooted_tree::set_valid_orientation ( bool valid )

inlinenoexcept

Sets wether the type of the rooted tree is valid or not.

It is mandatory that this tree be an arborescence. Therefore, when the tree has been built by adding edges (see add_edge, add_edges), the user must tell this class whether what has been built is an arborescence or not. One can do this by calling method find_edge_orientation or by setting the type directly using method set_valid_orientation.

Parameters

valid Boolean value telling whether the tree is valid or not.

Postcondition: Method is_orientation_valid returns the value set by this function.

◆ to_free_tree()

free_tree lal::graphs::rooted_tree::to_free_tree	(	bool	norm = true,
		bool	check = true ) const

noexcept

Converts this rooted tree into a free tree (see free_tree).

Parameters

norm	Normalise the tree.
check	Chech whether the resulting graph is normalised or not.

◆ to_undirected()

undirected_graph lal::graphs::directed_graph::to_undirected	(	bool	norm = true,
		bool	check = true ) const

noexceptinherited

Converts this directed graph into an undirected graph.

The undirected graph returned connects two vertices \(u,v\) if these two vertices are connected by a directed edge ( \((u,v)\) or \((v,u)\)) in this graph. In other words, if two vertices are connected by a single directed edge, the direction is dropped. If two edges are connected by two directed edges (of opposite directions) then the two are merged into a single undirected edge.

Parameters

norm	Normalise the graph.
check	Chech whether the resulting graph is normalised or not.

Returns: This graph in which the edges are undirected.

◆ tree_only_extra_work_edges_set()

void lal::graphs::tree::tree_only_extra_work_edges_set ( )

protectednoexceptinherited

Updates the data structures of a tree after the graph structure has had its set of edges set.

◆ tree_only_init()

void lal::graphs::tree::tree_only_init ( uint32_t n )

protectednoexceptinherited

Initialises only the memory of class tree.

Parameters

n	Number of vertices.

Member Data Documentation

◆ m_is_tree_type_valid

bool lal::graphs::tree::m_is_tree_type_valid = false

protectedinherited

Is the type of this tree valid?

This attribute keeps track of whether or not the function calculate_tree_type should be called before querying the type of this tree via function is_of_tree_type.

◆ m_normalised

bool lal::graphs::graph::m_normalised = true

protectedinherited

Is this graph normalised?

An undirected graph is normalised iff every node's adjacency list is sorted in increasing order.

In directed graphs, however, it is necessary that the adjacency lists of the out-neighbours and in-neighbours of nodes be sorted.

This attribute is set to 'true' in all graph's initialisation and destruction (when clear() method is called).

◆ m_root_size

std::vector<uint32_t> lal::graphs::tree::m_root_size

protectedinherited

The size of the connected component that a root belongs to.

Formally, m_size_of[v] is the size of the connected component of a root vertex v. A vertex u is a root vertex if there exists a vertex w such that m_root_of[w] = u.

In this context, root is within the union-find data structure.

◆ m_size_subtrees

std::vector<uint32_t> lal::graphs::rooted_tree::m_size_subtrees

protected

Number of nodes of the subtrees rooted at a certain node.

Given a node u, m_size_subtrees[u] gives the number of nodes of the subtree rooted at u.

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

lal/graphs/rooted_tree.hpp

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ rooted_tree() [1/3]

◆ rooted_tree() [2/3]

◆ rooted_tree() [3/3]

Member Function Documentation

◆ __disjoint_union()

◆ _clear()

◆ _init()

◆ add_edge()

◆ add_edge_bulk()

◆ add_edges()

◆ are_size_subtrees_valid()

◆ calculate_size_subtrees()

◆ calculate_tree_type()

◆ call_union_find_after_add() [1/2]

◆ call_union_find_after_add() [2/2]

◆ call_union_find_after_remove() [1/2]

◆ call_union_find_after_remove() [2/2]

◆ can_add_edge()

◆ can_add_edges()

◆ check_normalised()

◆ clear()

◆ disjoint_union() [1/2]

◆ disjoint_union() [2/2]

◆ fill_union_find()

◆ find_edge_orientation()

◆ finish_bulk_add()

◆ get_degree()

◆ get_edges_subtree()

◆ get_head_vector()

◆ get_in_neighbours()

◆ get_num_nodes_component()

◆ get_num_nodes_subtree()

◆ get_out_neighbours()

◆ get_Q()

◆ get_subtree()

◆ get_tree_type_list()

◆ has_root()

◆ init()

◆ init_rooted()

◆ is_normalised()

◆ is_of_tree_type()

◆ is_orientation_valid()

◆ is_rooted_tree()

◆ is_tree()

◆ is_tree_type_valid()

◆ normalise()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove_edge()

◆ remove_edges()

◆ remove_edges_incident_to()

◆ remove_single_edge()

◆ set_edges()

◆ set_root()

◆ set_valid_orientation()

◆ to_free_tree()

◆ to_undirected()

◆ tree_only_extra_work_edges_set()

◆ tree_only_init()

Member Data Documentation

◆ m_is_tree_type_valid

◆ m_normalised

◆ m_root_size

◆ m_size_subtrees