lal::graphs::rooted_tree Class Reference

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 (const uint64_t n) noexcept
	Constructor with number of nodes and root node.
	rooted_tree (const directed_graph &t) noexcept
	Copy constructor with directed graph.
	rooted_tree (directed_graph &&t) noexcept
	Move constructor with directed graph.
	rooted_tree (const rooted_tree &r) noexcept
	Copy constructor.
	rooted_tree (rooted_tree &&r) noexcept
	Move constructor.
	rooted_tree (const free_tree &t, const node r, const bool norm=true, const bool check_norm=true) noexcept
	Constructor with free tree and root node.
	rooted_tree (free_tree &&t, const node r, const bool norm=true, const bool check_norm=true) noexcept
	Constructor with tree and root node.
	~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.
void	init_rooted (const free_tree &t, const node r, const bool norm=true, const bool check_norm=true) noexcept
	Initializer with tree and root node.
void	init_rooted (free_tree &&t, const node r, const bool norm=true, const bool check_norm=true) noexcept
	Initializer with tree and root node.
rooted_tree &	add_node () noexcept
	Adds a node to the graph.
rooted_tree &	remove_node (const node u, const bool connect=false, const bool norm=true, const bool check_norm=true) noexcept
	Remove a node from this tree.
rooted_tree &	add_edge (const node s, const node t, const bool norm=true, const bool check_norm=true) noexcept
	Adds an edge to the tree.
rooted_tree &	add_edge_bulk (const node s, const node t) noexcept
	Adds an edge to the graph.
void	finish_bulk_add (const bool norm=true, const bool check=true) noexcept
	Finishes adding edges in bulk.
void	finish_bulk_add_complete (const bool norm=true, const bool check=true) noexcept
	Completes the inner structure of the tree after adding edges in bulk.
rooted_tree &	add_edges (const std::vector< edge > &edges, const bool norm=true, const bool check_norm=true) noexcept
	Adds a list of edges to the graph.
rooted_tree &	set_edges (const std::vector< edge > &edges, const bool norm=true, const bool check_norm=true) noexcept
	Sets the edges to the graph.
rooted_tree &	remove_edge (const node s, const node t, const bool norm=false, const bool check_norm=true) noexcept
	Remove an edge from this graph.
rooted_tree &	remove_edge_bulk (const node s, const node t) noexcept
	Removes an edge from the tree.
void	finish_bulk_remove (const bool norm=true, const bool check=true) noexcept
	Finishes removing edges in bulk.
void	finish_bulk_remove_complete (const bool norm=true, const bool check=true) noexcept
	Completes the inner structure of the tree after removing edges in bulk.
rooted_tree &	remove_edges (const std::vector< edge > &edges, const bool norm=true, const bool check_norm=true) noexcept
	Remove an edge from this graph.
rooted_tree &	remove_edges_incident_to (const node u, const bool norm=true, const bool check_norm=true) noexcept
	Remove all edges incident to a given vertex.
rooted_tree &	disjoint_union (const rooted_tree &t, const bool connect_roots=true) noexcept
	Disjoint union of trees.
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 (const node r) noexcept
	Set the root of this tree.
bool	is_root_valid (const node r) const noexcept
	Is the root valid?
bool	can_add_edge (const node s, const 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?
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?
node	get_root () const noexcept
	Return the root of this tree.
bool	has_root () const noexcept
uint64_t	get_num_nodes_subtree (const 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 (const node u, const bool relab=false) const noexcept
	Retrieve the edges of the subtree rooted at u.
rooted_tree	get_subtree (const node u) const noexcept
	Retrieve the subtree rooted at node u.
free_tree	to_free_tree (const bool norm=true, const bool check=true) const noexcept
	Converts this rooted tree into a free tree (see free_tree).
head_vector	get_head_vector (const linear_arrangement &arr={}) const noexcept
	Converts a rooted tree into a head vector.
bool	subtree_contains_node (const node r, const node u) const noexcept
	Does the subtree rooted at r contain node u?
bool	are_nodes_siblings (const node u, const node v) const noexcept
	Are two nodes siblings?
bool	node_has_parent (const node u) const noexcept
	Does a node have a parent vertex?
node	get_parent_node (const node u) const noexcept
	Parent vertex of a node.
void	reserve_in_degree (const node u, const uint64_t d) noexcept
	Predicts that the in-degree of node u is d.
void	reserve_out_degree (const node u, const uint64_t d) noexcept
	Predicts that the out-degree of node u is d.
void	normalize () noexcept
	Normalizes the graph.
bool	check_normalized () noexcept
	Checks if the graph is normalized.
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 (const node u, const node v) const noexcept
	Returns true if the edge \((u,v)\) exists in the graph.
const neighbourhood &	get_out_neighbors (const node u) const noexcept
	Returns the out-neighbors of node u.
const neighbourhood &	get_in_neighbors (const node u) const noexcept
	Returns the in-neighbors of node u.
uint64_t	get_degree (const node u) const noexcept
	Returns the in-degree plus the out-degree of this vertex.
uint64_t	get_out_degree (const node u) const noexcept
	Returns the out-degree of a node.
uint64_t	get_in_degree (const 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 (const bool norm=true, const bool check=true) const noexcept
	Converts this directed graph into an undirected graph.
std::vector< directed_graph >	get_connected_components () const noexcept
	Returns all the connected components of this graph as individual graphs.
bool	is_tree () const noexcept
	Is this graph an actual tree?
uint64_t	get_component_representative (const node u) const noexcept
	Representative node of the connected component in which u belongs.
bool	are_nodes_in_same_component (const node u, const node v) const noexcept
	Checks if two nodes are in the same connected component.
uint64_t	get_num_nodes_component (const 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 (const uint64_t n) noexcept
	Allocates the necessary memory for this class.
virtual void	clear () noexcept
	Frees the memory occupied by this graph.
void	set_normalized (const bool v=true) noexcept
	Sets whether this graph is normalized or not.
bool	has_node (const node u) const noexcept
	Returns true if node u is in this graph.
uint64_t	get_num_nodes () const noexcept
	Returns the number of ndoes.
uint64_t	get_num_edges () const noexcept
	Returns the number of edges.
bool	is_normalized () const noexcept
	Returns whether this graph is normalized or not.

Protected Member Functions
void	_init (const uint64_t n) noexcept
	Initializes the memory in the graph hierarchy.
void	_clear () noexcept
	Clears the memory in the graph hierarchy.
void	actions_after_add_edge (const node u, const node v) noexcept
	Do some extra work after the addition of an edge.
void	actions_after_add_edges (const edge_list &e) noexcept
	Do some extra work after the addition of several edges.
void	actions_after_add_edges_bulk () noexcept
	Do some extra work after the addition of several edges in bulk.
void	actions_after_remove_edge (const node u, const node v) noexcept
	Do some extra work after the removal of an edge.
void	actions_after_remove_edges (const edge_list &e) noexcept
	Do some extra work after the removal of several edges.
void	actions_after_remove_edges_bulk () noexcept
	Do some extra work after the removal of several edges in bulk.
void	actions_before_remove_edges_incident_to (const node u) noexcept
	Do some work before all edges incident to a node is removed.
void	actions_after_remove_node (const node u) noexcept
	Do some work before the removal of a vertex.
void	update_union_find_after_add_edge (const node u, const node v, uint64_t *const root_of, uint64_t *const root_size) const noexcept
	Update the union find data structure after an edge addition.
void	update_union_find_after_add_edges (const edge_list &edges, uint64_t *const root_of, uint64_t *const root_size) const noexcept
	Update the union find data structure after the addition of a set of edges.
void	update_union_find_after_add_edges_bulk (uint64_t *const root_of, uint64_t *const root_size) const noexcept
	Update the union find data structure after the addition of several edges.
void	update_union_find_after_remove_edge (const node u, const node v, uint64_t *const root_of, uint64_t *const root_size) const noexcept
	Update the union find data structure after an edge removal.
void	update_union_find_after_remove_edges (const edge_list &edges, uint64_t *const root_of, uint64_t *const root_size) const noexcept
	Update the union find data structure after the removal of a set of edges.
void	update_union_find_after_remove_edges_bulk (uint64_t *const root_of, uint64_t *const root_size) const noexcept
	Update the union find data structure after the removal of several edges.
void	update_union_find_before_remove_incident_edges_to (const node u, uint64_t *const root_of, uint64_t *const root_size) const noexcept
	Update the union find data structure before the removal of all edges incident to a node.
void	copy_full_rooted_tree (const rooted_tree &r) noexcept
	Copies all members of this class and the parent classes.
void	move_full_rooted_tree (rooted_tree &&r) noexcept
	Moves all members of this class and the parent classes.
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 (const uint64_t n) noexcept
	Initializes 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	tree_only_add_node () noexcept
	Adds a node to this tree.
void	tree_only_invalidate () noexcept
	Invalidates the aggregated information of the tree.
void	tree_only_actions_after_add_edge (const node u, const node v) noexcept
	Do some work after the addition of an edge.
void	tree_only_actions_after_add_edges (const edge_list &e) noexcept
	Do some work after the addition of several edges.
void	tree_only_actions_after_add_edges_bulk () noexcept
	Do some work after the addition of several edges in bulk.
void	tree_only_actions_after_add_edges_bulk_complete () noexcept
	Do some work after the addition of several edges in bulk.
void	tree_only_actions_after_remove_edges_bulk () noexcept
	Do some work after the removal of several edges in bulk.
void	tree_only_actions_after_remove_edges_bulk_complete () noexcept
	Do some work after the removal of several edges in bulk.
void	tree_only_actions_after_remove_edge (const node u, const node v) noexcept
	Do some work after the removal of an edge.
void	tree_only_actions_after_remove_edges (const edge_list &e) noexcept
	Do some work after the removal of several edges.
void	tree_only_actions_after_remove_node (const node u) noexcept
	Do some work before the removal of a vertex.
void	tree_only_actions_before_remove_edges_incident_to (const node u) noexcept
	Do some work before the removal of all edges incident to a vertex.
void	tree_only_set_edges () noexcept
	Updates the data structures of a tree after the graph structure has had its set of edges set.
void	tree_only_remove_node (const node u) noexcept
	Removes a vertex from the union-find data structure.
void	fill_union_find () noexcept
void	empty_union_find () noexcept
	Empties the Union-Find data structure assuming that the tree has no edges.
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	__add_node () noexcept
	Adds a node to the graph.
void	__disjoint_union (const graph &g) noexcept
	Disjoint union of graphs.
void	normalize_after_edge_addition (const bool norm, const bool check) noexcept
	Normalize the graph after one (or more) edges have been added.
void	normalize_after_edge_removal (const bool norm, const bool check) noexcept
	Normalize the graph after one (or more) edges have been removed.

Protected Attributes
std::optional< node >	m_root
	Root of the tree.
std::vector< uint64_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-neighbors for every node.
std::vector< node >	m_union_find__root_of
	The root of every vertex in the union-find data structure.
std::vector< uint64_t >	m_union_find__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.
uint64_t	m_num_edges = 0
	Amount of edges of this graph.
bool	m_is_normalized = true
	Is this graph normalized?

Private Member Functions
directed_graph &	disjoint_union (const directed_graph &g) noexcept
	Disjoint union of graphs.
virtual directed_graph &	remove_node (const node u, const bool norm=true, const bool check_norm=true) noexcept
	Remove a node from this graph.
void	remove_single_edge (const node u, const 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 (see is_rooted_tree).

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 (either rooted_tree(const lal::graphs::free_tree&, node, bool, bool) or rooted_tree(lal::graphs::free_tree&&, node, bool, bool)). Alternatively, one can use the method init_rooted, which has the same set of parameters.
• Adding edge after edge. In this class, as in lal::graphs::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.

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). Therefore, consider the use of methods can_add_edge or can_add_edges. 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). Not every vertex can be a root of the tree: in general, only those vertices with in-degree 0 can (see is_root_valid).

This class allows flexibility of use of rooted trees regarding the root's choice (within the valid possibilities). Method set_root allows changing the root of rooted trees multiple times and at any time. However, when the tree has all of its edges then only one vertex can be the root (that with in-degree 0). For this reason, in case a user wants to build "different rooted trees on different roots", it is strongly recommended that first a lal::graphs::free_tree is built, and then create a rooted tree using one of the two constructors with a free tree (either rooted_tree(const lal::graphs::free_tree&, node, bool, bool), or rooted_tree(lal::graphs::free_tree&&, node, bool, bool)), or the method init_rooted.

Constructor & Destructor Documentation

rooted_tree() [1/7]

lal::graphs::rooted_tree::rooted_tree ( const uint64_t n )

inlinenoexcept

Constructor with number of nodes and root node.

Parameters

n	Number of vertices.

rooted_tree() [2/7]

lal::graphs::rooted_tree::rooted_tree ( const directed_graph & t )

noexcept

Copy constructor with directed graph.

Parameters

t	A directed graph.

Precondition

Graph t is a tree.

rooted_tree() [3/7]

lal::graphs::rooted_tree::rooted_tree ( directed_graph && t )

noexcept

Move constructor with directed graph.

Parameters

t	A directed graph.

Precondition

Graph t is a tree.

rooted_tree() [4/7]

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

inlinenoexcept

Copy constructor.

Parameters

r	Rooted tree.

rooted_tree() [5/7]

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

inlinenoexcept

Move constructor.

Parameters

r	Rooted tree.

rooted_tree() [6/7]

lal::graphs::rooted_tree::rooted_tree ( const free_tree & t, const node r, const bool norm = true, const bool check_norm = true )

inlinenoexcept

Constructor with free tree and root node.

Parameters

t	Free tree.
r	Root node.
norm	Normalize the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. If norm is true then check_norm is ignored.

Precondition

Tree t is a valid free tree.

rooted_tree() [7/7]

lal::graphs::rooted_tree::rooted_tree ( free_tree && t, const node r, const bool norm = true, const bool check_norm = true )

inlinenoexcept

Constructor with tree and root node.

Parameters

t	Free tree.
r	Root node.
norm	Normalize the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. If norm is true then check_norm is ignored.

Precondition

Tree t is a valid free tree.

Postcondition

Tree t is moved and should not be used.

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 normalized only if it was normalized before the call and g is also normalized.

_clear()

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

inlineprotectedvirtualnoexcept

Clears the memory in the graph hierarchy.

Clears the memory of lal::graphs::free_tree, lal::graphs::undirected_graph and lal::graphs::graph classes.

Reimplemented from lal::graphs::directed_graph.

_init()

void lal::graphs::rooted_tree::_init ( const uint64_t n )

inlineprotectedvirtualnoexcept

Initializes the memory in the graph hierarchy.

Initializes memory of lal::graphs::free_tree, lal::graphs::undirected_graph and lal::graphs::graph classes.

Parameters

n	Number of nodes.

Precondition

The graph is cleared.

Reimplemented from lal::graphs::directed_graph.

actions_after_add_edge()

void lal::graphs::rooted_tree::actions_after_add_edge ( const node u, const node v )

protectedvirtualnoexcept

Do some extra work after the addition of an edge.

Parameters

u	Node of the edge
v	Node of the edge

Reimplemented from lal::graphs::directed_graph.

actions_after_add_edges()

void lal::graphs::rooted_tree::actions_after_add_edges ( const edge_list & e )

protectedvirtualnoexcept

Do some extra work after the addition of several edges.

Parameters

e	List of edges.

Reimplemented from lal::graphs::directed_graph.

actions_after_add_edges_bulk()

void lal::graphs::rooted_tree::actions_after_add_edges_bulk ( )

protectedvirtualnoexcept

Do some extra work after the addition of several edges in bulk.

This method should only be called after several calls to undirected_graph::add_edge_bulk or directed_graph::add_edge_bulk.

Reimplemented from lal::graphs::directed_graph.

actions_after_remove_edge()

void lal::graphs::rooted_tree::actions_after_remove_edge ( const node u, const node v )

protectedvirtualnoexcept

Do some extra work after the removal of an edge.

Parameters

u	Node of the edge
v	Node of the edge

Reimplemented from lal::graphs::directed_graph.

actions_after_remove_edges()

void lal::graphs::rooted_tree::actions_after_remove_edges ( const edge_list & e )

protectedvirtualnoexcept

Do some extra work after the removal of several edges.

Parameters

e	List of edges.

Reimplemented from lal::graphs::directed_graph.

actions_after_remove_edges_bulk()

void lal::graphs::rooted_tree::actions_after_remove_edges_bulk ( )

protectedvirtualnoexcept

Do some extra work after the removal of several edges in bulk.

This method should only be called after several calls to undirected_graph::remove_edge_bulk or directed_graph::remove_edge_bulk.

Reimplemented from lal::graphs::directed_graph.

actions_after_remove_node()

void lal::graphs::rooted_tree::actions_after_remove_node ( const node u )

protectedvirtualnoexcept

Do some work before the removal of a vertex.

Parameters

u	Node to be removed.

Reimplemented from lal::graphs::directed_graph.

actions_before_remove_edges_incident_to()

void lal::graphs::rooted_tree::actions_before_remove_edges_incident_to ( const node u )

protectedvirtualnoexcept

Do some work before all edges incident to a node is removed.

Parameters

u	Node whose incident edges are to be removed.

Reimplemented from lal::graphs::directed_graph.

add_edge()

rooted_tree & lal::graphs::rooted_tree::add_edge ( const node s, const node t, const bool norm = true, const 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 lal::graphs::graph::actions_after_add_edge 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 normalized?
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. 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 normalized after the addition of the edge.

Reimplemented from lal::graphs::directed_graph.

add_edge_bulk()

rooted_tree & lal::graphs::rooted_tree::add_edge_bulk ( const node s, const 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 normalized after the addition of the edge.

add_edges()

rooted_tree & lal::graphs::rooted_tree::add_edges ( const std::vector< edge > & edges, const bool norm = true, const 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.

Parameters

edges	The edges to be added.
norm	Normalize the graph after the insertions.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. 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 normalized after the addition of the edges.

Reimplemented from lal::graphs::directed_graph.

are_nodes_in_same_component()

bool lal::graphs::tree::are_nodes_in_same_component ( const node u, const node v ) const

inlinenodiscardnoexceptinherited

Checks if two nodes are in the same connected component.

Parameters

u	First node.
v	Second node.

Returns

True or false.

are_nodes_siblings()

bool lal::graphs::rooted_tree::are_nodes_siblings ( const node u, const node v ) const

inlinenodiscardnoexcept

Are two nodes siblings?

Do to two nodes share the same parent?

Parameters

u	A node.
v	Another node.

Returns

True if the nodes are siblings. False, if they are not.

are_size_subtrees_valid()

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

inlinenodiscardnoexcept

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.

can_add_edge()

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

nodiscardvirtualnoexcept

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.

In a rooted tree, an edge can only be added if the in-degree of vertex t (see directed_graph::get_in_degree) is exactly 1 after adding the edge.

Parameters

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

Returns

Whether or not this edge can be added to the tree without producing cycles.

Reimplemented from lal::graphs::tree.

can_add_edges()

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

nodiscardvirtualnoexcept

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.

In a rooted tree, edges \((s,t)\) can only be added if the in-degree of vertex t (see directed_graph::get_in_degree) is exactly 1 after adding the edge.

Parameters

edges

List of edges.

Returns

Whether or not these edges can be added to the tree without producing cycles.

Reimplemented from lal::graphs::tree.

check_normalized()

bool lal::graphs::directed_graph::check_normalized ( )

nodiscardvirtualnoexceptinherited

Checks if the graph is normalized.

Checks, whether the graph's adjacency structure is normalized or not. In case it is, attribute m_is_normalized is set to true, so method is_normalized 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 normalized. The number of edges is 0.

disjoint_union() [1/2]

directed_graph & 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 normalized only if it was normalized before the call and g is also normalized.

disjoint_union() [2/2]

rooted_tree & lal::graphs::rooted_tree::disjoint_union ( const rooted_tree & t, const 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 whole input tree (and its state) is simply copied into this tree.

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.

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 normalized only if the two graphs were normalized prior to the union.

The type of tree is invalidated.

fill_union_find()

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

inlineprotectednoexceptinherited

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

finish_bulk_add()

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

virtualnoexcept

Finishes adding edges in bulk.

This method updates the Union-Find data structure and all the necessary members after several calls to add_edge_bulk.

Parameters

norm	Normalize the tree.
check	Check whether the tree is normalized or not.

Reimplemented from lal::graphs::directed_graph.

finish_bulk_add_complete()

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

virtualnoexcept

Completes the inner structure of the tree after adding edges in bulk.

This is meant to be used after several calls to undirected_graph::add_edge_bulk, directed_graph::add_edge_bulk.

This method completes the Union-Find data structure and the other necessary members assuming that the tree is now complete.

Parameters

norm	Normalize the graph.
check	Check wether the graph is normalized or not.

Precondition

All edges have been added with method undirected_graph::add_edge_bulk or directed_graph::add_edge_bulk.

Implements lal::graphs::tree.

finish_bulk_remove()

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

virtualnoexcept

Finishes removing edges in bulk.

This method updates the Union-Find data structure and all the necessary members after several calls to remove_edge_bulk.

Parameters

norm	Normalize the tree.
check	Check whether the tree is normalized or not.

Reimplemented from lal::graphs::directed_graph.

finish_bulk_remove_complete()

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

virtualnoexcept

Completes the inner structure of the tree after removing edges in bulk.

This is meant to be used after several calls to undirected_graph::remove_edge_bulk, directed_graph::remove_edge_bulk.

This method completes the Union-Find data structure and the other necessary members assuming that the tree is now empty.

Parameters

norm	Normalize the graph.
check	Check wether the graph is normalized or not.

Precondition

All edges have been added with method undirected_graph::remove_edge_bulk or directed_graph::remove_edge_bulk.

Implements lal::graphs::tree.

get_component_representative()

uint64_t lal::graphs::tree::get_component_representative ( const node u ) const

inlinenodiscardnoexceptinherited

Representative node of the connected component in which u belongs.

If the current graph lacks some edges then it is clearly a forest, i.e., a series of disconnected components. This function returns a representative node of the connected component to which node u belongs.

Further, let \(cc(u)\) be the connected component of vertex u, and \(rep(cc(u))\) be the representative node of \(cc(u)\). For every other node \(v\in cc(u)\), this function will return the same representative node \(rep(cc(u))\). Therefore, \(rep(cc(u))=rep(cc(v))\) for every \(v\in cc(u)\).

Parameters

u	Input node.

Returns

The representative node of node u's component.

get_degree()

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

inlinenodiscardnoexceptinherited

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 ( const node u, const bool relab = false ) const

nodiscardnoexcept

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.

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", or, for the mathematically inclined \((1,3), (1,4)\).

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 linear_arrangement & arr = {} ) const

nodiscardnoexcept

Converts a rooted tree into a head vector.

See Head vector page for a definition of 'head vector'.

Parameters

arr	Linear arrangement of the tree.

Returns

The head vector representation of this tree.

Precondition

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

get_in_neighbors()

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

inlinenodiscardnoexceptinherited

Returns the in-neighbors of node u.

Parameters

u

Node

Returns

The list of nodes entering at node u.

get_num_nodes_component()

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

inlinenodiscardnoexceptinherited

Amount of nodes in a connected component of the tree.

If the current graph lacks some edges then it is clearly a forest, i.e., a series of disconnected components. This function returns the size of the component node u belongs to.

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

Parameters

u	Input node.

Returns

The size of the connected component of u.

get_num_nodes_subtree()

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

inlinenodiscardnoexcept

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

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

inlinenodiscardnoexceptinherited

Returns the out-neighbors of node u.

Parameters

u

Node

Returns

The list of nodes leaving node u.

get_parent_node()

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

inlinenodiscardnoexcept

Parent vertex of a node.

Parameters

u	Input node.

Returns

The parent vertex of a node.

Precondition

Method node_has_parent must return true.

get_Q()

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

nodiscardvirtualnoexceptinherited

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 ( const node u ) const

nodiscardnoexcept

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

get_tree_type_list()

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

nodiscardnoexceptinherited

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

inlinenodiscardnoexcept

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

init()

virtual void lal::graphs::graph::init ( const uint64_t n )

virtualnoexceptinherited

Allocates the necessary memory for this class.

See _init for details.

Parameters

n	Number of nodes.

init_rooted() [1/2]

void lal::graphs::rooted_tree::init_rooted ( const free_tree & t, const node r, const bool norm = true, const bool check_norm = true )

noexcept

Initializer 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 rooted tree. A node of g.
norm	Normalize the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. If norm is true then check_norm is ignored.

Precondition

Parameter t must be a tree (see is_tree).

Postcondition

Method is_rooted_tree returns true.

init_rooted() [2/2]

void lal::graphs::rooted_tree::init_rooted ( free_tree && t, const node r, const bool norm = true, const bool check_norm = true )

noexcept

Initializer 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 rooted tree. A node of g.
norm	Normalize the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. If norm is true then check_norm is ignored.

Precondition

Parameter t must be a tree (see is_tree).

Postcondition

Method is_rooted_tree returns true.

is_normalized()

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

inlinenodiscardnoexceptinherited

Returns whether this graph is normalized or not.

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

Returns

The value of m_is_normalized.

is_of_tree_type()

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

inlinenodiscardnoexceptinherited

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 graphs::tree_type).

Returns

True if this tree is of type tt.

is_root_valid()

bool lal::graphs::rooted_tree::is_root_valid ( const node r ) const

inlinenodiscardnoexcept

Is the root valid?

A root is valid if it has in-degree 0. This is calculated as a function of the current state of the tree.

Parameters

r	Given node.

Returns

Whether or not the node passed as parameter is a valid root.

is_rooted_tree()

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

inlinenodiscardnoexcept

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

Returns

Whether this tree is a valid rooted tree or not.

is_tree()

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

inlinenodiscardnoexceptinherited

Is this graph 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. That is, since it is constrained (behind the scenes) 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 [29] (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

inlinenodiscardnoexceptinherited

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 graphs::tree_type::unknown and that the tree type may remain graphs::tree_type::unknown even after the type has been calculated. Nevertheless, users should be suspicious of a tree being of 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.

node_has_parent()

bool lal::graphs::rooted_tree::node_has_parent ( const node u ) const

inlinenodiscardnoexcept

Does a node have a parent vertex?

Parameters

u	Input node.

Returns

If the node has a parent vertex.

normalize()

void lal::graphs::directed_graph::normalize ( )

virtualnoexceptinherited

Normalizes the graph.

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

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

Postcondition

Method is_normalized 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 ( const node s, const node t, const bool norm = false, const bool check_norm = true )

virtualnoexcept

Remove an edge from this graph.

For developers: method lal::graphs::graph::actions_after_remove_edge 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	Normalize the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. 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 normalized after the addition of the edge.

Reimplemented from lal::graphs::directed_graph.

remove_edge_bulk()

rooted_tree & lal::graphs::rooted_tree::remove_edge_bulk ( const node s, const node t )

virtualnoexcept

Removes an edge from the tree.

This method only removes 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 normalized after the removal of the edge.

Reimplemented from lal::graphs::directed_graph.

remove_edges()

rooted_tree & lal::graphs::rooted_tree::remove_edges ( const std::vector< edge > & edges, const bool norm = true, const 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.

Parameters

edges	The edges to be deleted.
norm	Normalize the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. 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 normalized after the addition of the edge.

Reimplemented from lal::graphs::directed_graph.

remove_edges_incident_to()

rooted_tree & lal::graphs::rooted_tree::remove_edges_incident_to ( const node u, const bool norm = true, const 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.

Parameters

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

Postcondition

If norm is true the graph is guaranteed to be normalized after the addition of the edge.

Reimplemented from lal::graphs::directed_graph.

remove_node() [1/2]

rooted_tree & lal::graphs::rooted_tree::remove_node ( const node u, const bool connect = false, const bool norm = true, const bool check_norm = true )

noexcept

Remove a node from this tree.

Parameters

u	Valid node index: \(0 \le u < n\).
connect	If connect is true then the parent of u is connected to the children of u, if both parent and children exist.
norm	Normalize the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. If norm is true then check_norm is ignored.

Precondition

The node must exist.

Postcondition

If norm is true the graph is guaranteed to be normalized after the removal of the node.

If u is the root of this tree, then this tree no longer has a root.

remove_node() [2/2]

virtual directed_graph & lal::graphs::directed_graph::remove_node ( const node u, const bool norm = true, const bool check_norm = true )

privatevirtualnoexcept

Remove a node from this graph.

Parameters

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

Precondition

The node must exist.

Postcondition

If norm is true the graph is guaranteed to be normalized after the addition of the edge.

Reimplemented from lal::graphs::directed_graph.

remove_single_edge()

void lal::graphs::directed_graph::remove_single_edge ( const node u, const 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.

reserve_in_degree()

void lal::graphs::directed_graph::reserve_in_degree ( const node u, const uint64_t d )

inlinenoexceptinherited

Predicts that the in-degree of node u is d.

Memory of size d is reserved so that adding edges is done more efficiently.

Parameters

u	Node to reserve the degree for.
d	The amount of memory to reserve.

Precondition

The graph must have been initialized.

reserve_out_degree()

void lal::graphs::directed_graph::reserve_out_degree ( const node u, const uint64_t d )

inlinenoexceptinherited

Predicts that the out-degree of node u is d.

Memory of size d is reserved so that adding edges is done more efficiently.

Parameters

u	Node to reserve the degree for.
d	The amount of memory to reserve.

Precondition

The graph must have been initialized.

set_edges()

rooted_tree & lal::graphs::rooted_tree::set_edges ( const std::vector< edge > & edges, const bool norm = true, const 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	Normalize the graph after the insertions.
check_norm	If norm is false then, should we check whether the result is normalized or not? This might be useful in case the resulting graph is normalized. 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, there must be no cycles, and every vertex has in-degree at most 1.

Postcondition

If norm is true the graph is guaranteed to be normalized 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.

Method is_rooted_tree returns true.

Reimplemented from lal::graphs::directed_graph.

set_root()

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

inlinenoexcept

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.

Precondition

The adjacency list must have been initialized.

Postcondition

Method has_root returns true.

The type of rooted tree and the size of the subtrees are invalidated.

subtree_contains_node()

bool lal::graphs::rooted_tree::subtree_contains_node ( const node r, const node u ) const

nodiscardnoexcept

Does the subtree rooted at r contain node u?

Parameters

r	The root of the subtree. Notice that if r is the actual root of the subtree, the tree certainly contains u.
u	Node to query within the subtree.

Returns

Whether or not the subtree rooted at r contains node łe u.

Precondition

Node r belongs to the tree (see has_node).

Node u belongs to the tree (see has_node).

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

to_free_tree()

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

nodiscardnoexcept

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

Parameters

norm	Normalize the tree.
check	Chech whether the resulting graph is normalized or not.

to_undirected()

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

nodiscardnoexceptinherited

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	Normalize the graph.
check	Chech whether the resulting graph is normalized or not.

Returns

This graph in which the edges are undirected.

tree_only_actions_after_add_edge()

void lal::graphs::tree::tree_only_actions_after_add_edge ( const node u, const node v )

protectednoexceptinherited

Do some work after the addition of an edge.

Parameters

u	First node of the edge.
v	Second node of the edge.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_add_edges()

void lal::graphs::tree::tree_only_actions_after_add_edges ( const edge_list & e )

protectednoexceptinherited

Do some work after the addition of several edges.

Parameters

e	List of edges.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_add_edges_bulk()

void lal::graphs::tree::tree_only_actions_after_add_edges_bulk ( )

protectednoexceptinherited

Do some work after the addition of several edges in bulk.

To be called only after veral calls to undirected_graph::add_edge_bulk or directed_graph::add_edge_bulk.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_add_edges_bulk_complete()

void lal::graphs::tree::tree_only_actions_after_add_edges_bulk_complete ( )

protectednoexceptinherited

Do some work after the addition of several edges in bulk.

To be called only after veral calls to undirected_graph::add_edge_bulk or directed_graph::add_edge_bulk.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_remove_edge()

void lal::graphs::tree::tree_only_actions_after_remove_edge ( const node u, const node v )

protectednoexceptinherited

Do some work after the removal of an edge.

Parameters

u	First node of the edge.
v	Second node of the edge.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_remove_edges()

void lal::graphs::tree::tree_only_actions_after_remove_edges ( const edge_list & e )

protectednoexceptinherited

Do some work after the removal of several edges.

Parameters

e	List of edges.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_remove_edges_bulk()

void lal::graphs::tree::tree_only_actions_after_remove_edges_bulk ( )

protectednoexceptinherited

Do some work after the removal of several edges in bulk.

To be called only after veral calls to undirected_graph::remove_edge_bulk or directed_graph::remove_edge_bulk.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_remove_edges_bulk_complete()

void lal::graphs::tree::tree_only_actions_after_remove_edges_bulk_complete ( )

protectednoexceptinherited

Do some work after the removal of several edges in bulk.

To be called only after veral calls to undirected_graph::remove_edge_bulk or directed_graph::remove_edge_bulk.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_after_remove_node()

void lal::graphs::tree::tree_only_actions_after_remove_node ( const node u )

protectednoexceptinherited

Do some work before the removal of a vertex.

Parameters

u	Node to be removed.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_actions_before_remove_edges_incident_to()

void lal::graphs::tree::tree_only_actions_before_remove_edges_incident_to ( const node u )

protectednoexceptinherited

Do some work before the removal of all edges incident to a vertex.

Parameters

u	Node whose incident edges are to be removed.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_add_node()

void lal::graphs::tree::tree_only_add_node ( )

inlineprotectednoexceptinherited

Adds a node to this tree.

Updates all the internal data structures.

tree_only_init()

void lal::graphs::tree::tree_only_init ( const uint64_t n )

inlineprotectednoexceptinherited

Initializes only the memory of class tree.

Parameters

n	Number of vertices.

tree_only_invalidate()

void lal::graphs::tree::tree_only_invalidate ( )

inlineprotectednoexceptinherited

Invalidates the aggregated information of the tree.

Invalidates:

• m_is_tree_type_valid.

tree_only_remove_node()

void lal::graphs::tree::tree_only_remove_node ( const node u )

protectednoexceptinherited

Removes a vertex from the union-find data structure.

Parameters

u	Node that was removed.

Postcondition

The tree type is invalidated.

Updated union-find.

tree_only_set_edges()

void lal::graphs::tree::tree_only_set_edges ( )

protectednoexceptinherited

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

Postcondition

The tree type is invalidated.

Updated union-find.

update_union_find_after_add_edge()

void lal::graphs::rooted_tree::update_union_find_after_add_edge ( const node u, const node v, uint64_t *const root_of, uint64_t *const root_size ) const

protectedvirtualnoexcept

Update the union find data structure after an edge addition.

This is a helper method to be able to call lal::detail::update_unionfind_after_add_edge 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.

update_union_find_after_add_edges()

void lal::graphs::rooted_tree::update_union_find_after_add_edges ( const edge_list & edges, uint64_t *const root_of, uint64_t *const root_size ) const

protectedvirtualnoexcept

Update the union find data structure after the addition of a set of edges.

This is a helper method to be able to call lal::detail::update_unionfind_after_add_edges which updates the Union-Find data structure under addition of an edge.

Parameters

edges	A set of edges.
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.

update_union_find_after_add_edges_bulk()

void lal::graphs::rooted_tree::update_union_find_after_add_edges_bulk ( uint64_t *const root_of, uint64_t *const root_size ) const

protectedvirtualnoexcept

Update the union find data structure after the addition of several edges.

This is a helper method to be able to call lal::detail::update_unionfind_after_add_rem_edges_bulk which updates the Union-Find data structure after addition of several edges.

Parameters

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.

update_union_find_after_remove_edge()

void lal::graphs::rooted_tree::update_union_find_after_remove_edge ( const node u, const node v, uint64_t *const root_of, uint64_t *const root_size ) const

protectedvirtualnoexcept

Update the union find data structure after an edge removal.

This is a helper method to be able to call lal::detail::update_unionfind_after_remove_edge 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.

update_union_find_after_remove_edges()

void lal::graphs::rooted_tree::update_union_find_after_remove_edges ( const edge_list & edges, uint64_t *const root_of, uint64_t *const root_size ) const

protectedvirtualnoexcept

Update the union find data structure after the removal of a set of edges.

This is a helper method to be able to call lal::detail::update_unionfind_after_remove_edges which updates the Union-Find data structure under removal of an edge.

Parameters

edges	A set of edges.
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.

update_union_find_after_remove_edges_bulk()

void lal::graphs::rooted_tree::update_union_find_after_remove_edges_bulk ( uint64_t *const root_of, uint64_t *const root_size ) const

protectedvirtualnoexcept

Update the union find data structure after the removal of several edges.

This is a helper method to be able to call lal::detail::update_unionfind_after_add_rem_edges_bulk which updates the Union-Find data structure under removal of several edges.

Parameters

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.

update_union_find_before_remove_incident_edges_to()

void lal::graphs::rooted_tree::update_union_find_before_remove_incident_edges_to ( const node u, uint64_t *const root_of, uint64_t *const root_size ) const

protectedvirtualnoexcept

Update the union find data structure before the removal of all edges incident to a node.

This is a helper method to be able to call lal::detail::update_unionfind_before_remove_edges_incident_to which updates the Union-Find data structure under removal of all incident edges to a node.

Parameters

u	Node whose incident edges are to be removed.
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.

Member Data Documentation

m_is_normalized

bool lal::graphs::graph::m_is_normalized = true

protectedinherited

Is this graph normalized?

An undirected graph is normalized 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-neighbors and in-neighbors of nodes be sorted.

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

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_size_subtrees

std::vector<uint64_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.

m_union_find__root_size

std::vector<uint64_t> lal::graphs::tree::m_union_find__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_union_find__root_of[w] = u.

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

---

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

• lal/graphs/rooted_tree.hpp