Tree graph class. More...

#include <tree.hpp>

Inheritance diagram for lal::graphs::tree:

Public Member Functions
	tree () noexcept
	Empty constructor.

	tree (const tree &t) noexcept
	Copy constructor.

	tree (tree &&t) noexcept
	Move constructor.

virtual	~tree () noexcept
	Destructor.

tree &	operator= (const tree &t) noexcept
	Copy assignment operator.

tree &	operator= (tree &&t) noexcept
	Move assignment operator.

virtual void	calculate_tree_type () noexcept=0
	Calculates the type of tree.

virtual void	finish_bulk_add_complete (const bool norm=true, const bool check=true) noexcept=0
	Completes the inner structure of the tree after adding edges in bulk.

virtual void	finish_bulk_remove_complete (const bool norm=true, const bool check=true) noexcept=0
	Completes the inner structure of the tree after removing edges in bulk.

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

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

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

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

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.

virtual void	normalize () noexcept
	Normalizes the graph.

virtual bool	check_normalized () noexcept
	Checks if the graph is normalized.

virtual void	finish_bulk_add (const bool norm=true, const bool check=true) noexcept=0
	Completes the inner structure of the graph after adding a bulk of edges.

virtual void	finish_bulk_remove (const bool norm=true, const bool check=true) noexcept=0
	Completes the inner structure of the graph after removing edges in bulk.

void	set_normalized (const bool v=true) noexcept
	Sets whether this graph is normalized or not.

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

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

virtual bool	has_edge (const node u, const node v) const =0
	Returns true if the undirected edge (u, v) exists in the 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.

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

bool	is_normalized () const noexcept
	Returns whether this graph is normalized or not.

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

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

Protected Member Functions
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.

virtual 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=0
	Update the union find data structure after an edge addition.

virtual void	update_union_find_after_add_edges (const edge_list &edges, uint64_t const root_of, uint64_t const root_size) const noexcept=0
	Update the union find data structure after the addition of a set of edges.

virtual void	update_union_find_after_add_edges_bulk (uint64_t const root_of, uint64_t const root_size) const noexcept=0
	Update the union find data structure after the addition of several edges.

virtual void	update_union_find_after_remove_edges_bulk (uint64_t const root_of, uint64_t const root_size) const noexcept=0
	Update the union find data structure after the removal of several edges.

virtual 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=0
	Update the union find data structure after an edge removal.

virtual void	update_union_find_after_remove_edges (const edge_list &edges, uint64_t const root_of, uint64_t const root_size) const noexcept=0
	Update the union find data structure after the removal of a set of edges.

virtual void	update_union_find_before_remove_incident_edges_to (const node u, uint64_t const root_of, uint64_t const root_size) const noexcept=0
	Update the union find data structure before the removal of all edges incident to a node.

virtual void	_init (const uint64_t n) noexcept
	Initializes memory of graph class.

virtual void	_clear () noexcept
	Clears memory for the graph class.

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.

virtual void	actions_after_add_edge (const node u, const node v) noexcept
	Do some extra work after the addition of an edge.

virtual void	actions_after_add_edges (const edge_list &e) noexcept
	Do some extra work after the addition of several edges.

virtual void	actions_after_add_edges_bulk () noexcept
	Do some extra work after the addition of several edges in bulk.

virtual void	actions_after_remove_edge (const node u, const node v) noexcept
	Do some extra work after the removal of an edge.

virtual void	actions_after_remove_edges (const edge_list &e) noexcept
	Do some extra work after the removal of several edges.

virtual void	actions_after_remove_edges_bulk () noexcept
	Do some extra work after the removal of several edges in bulk.

virtual void	actions_before_remove_edges_incident_to (const node u) noexcept
	Do some work before all edges incident to a node is removed.

virtual void	actions_after_remove_node (const node u) noexcept
	Do some work before the removal of a vertex.

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::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?

Detailed Description

Tree graph class.

This is an abstract class for those tree-like graphs. Classes that implement different abstractions of trees and that inherit from this class are: free_tree, rooted_tree.

In these classes the addition of edges is constrained so as to ensure that the edges added actually yield trees, i.e., that cycles are never produced. For the sake of efficiency, only debug compilations of the library (compilations where the DEBUG symbol is defined) check that such additions do not produce cycles. In case of doubt, one can query the class using methods can_add_edge or can_add_edges prior to adding one or several edges.

Constructor & Destructor Documentation

◆ tree() [1/2]

lal::graphs::tree::tree ( const tree & t )

inlinenoexcept

Copy constructor.

Parameters

t Tree.

◆ tree() [2/2]

lal::graphs::tree::tree ( tree && t )

inlinenoexcept

Move constructor.

Parameters

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

◆ _init()

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

inlineprotectedvirtualnoexceptinherited

Initializes memory of graph class.

Parameters

n	Number of nodes.

Precondition: The graph is cleared.

Reimplemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_after_add_edge()

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

protectedvirtualnoexceptinherited

Do some extra work after the addition of an edge.

Parameters

u	Node of the edge
v	Node of the edge

Reimplemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_after_add_edges()

virtual void lal::graphs::graph::actions_after_add_edges ( const edge_list & e )

protectedvirtualnoexceptinherited

Do some extra work after the addition of several edges.

Parameters

e	List of edges.

Reimplemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_after_add_edges_bulk()

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

protectedvirtualnoexceptinherited

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 in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_after_remove_edge()

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

protectedvirtualnoexceptinherited

Do some extra work after the removal of an edge.

Parameters

u	Node of the edge
v	Node of the edge

Reimplemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_after_remove_edges()

virtual void lal::graphs::graph::actions_after_remove_edges ( const edge_list & e )

protectedvirtualnoexceptinherited

Do some extra work after the removal of several edges.

Parameters

e	List of edges.

Reimplemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_after_remove_edges_bulk()

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

protectedvirtualnoexceptinherited

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 in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_after_remove_node()

virtual void lal::graphs::graph::actions_after_remove_node ( const node u )

protectedvirtualnoexceptinherited

Do some work before the removal of a vertex.

Parameters

u	Node to be removed.

Reimplemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ actions_before_remove_edges_incident_to()

virtual void lal::graphs::graph::actions_before_remove_edges_incident_to ( const node u )

protectedvirtualnoexceptinherited

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

Parameters

u	Node whose incident edges are to be removed.

Reimplemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ are_nodes_in_same_component()

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

inlinenodiscardnoexcept

Checks if two nodes are in the same connected component.

Parameters

u	First node.
v	Second node.

Returns: True or false.

◆ calculate_tree_type()

virtual void lal::graphs::tree::calculate_tree_type ( )

pure virtualnoexcept

Calculates the type of tree.

See tree_type for the list of different tree types.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ can_add_edge()

virtual bool lal::graphs::tree::can_add_edge	(	node const	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 in lal::graphs::rooted_tree.

◆ can_add_edges()

virtual bool lal::graphs::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 in lal::graphs::rooted_tree.

◆ check_normalized()

virtual bool lal::graphs::graph::check_normalized ( )

virtualnoexceptinherited

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 in lal::graphs::directed_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.

◆ fill_union_find()

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

inlineprotectednoexcept

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

◆ finish_bulk_add()

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

pure virtualnoexceptinherited

Completes the inner structure of the graph after adding a bulk of edges.

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

Parameters

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

Implemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ finish_bulk_add_complete()

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

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

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ finish_bulk_remove()

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

pure virtualnoexceptinherited

Completes the inner structure of the graph 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.

Parameters

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

Implemented in lal::graphs::directed_graph, lal::graphs::free_tree, lal::graphs::rooted_tree, and lal::graphs::undirected_graph.

◆ finish_bulk_remove_complete()

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

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

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ get_component_representative()

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

inlinenodiscardnoexcept

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

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

inlinenodiscardnoexcept

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

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

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

Implemented in lal::graphs::directed_graph, and lal::graphs::undirected_graph.

◆ get_tree_type_list()

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

nodiscardnoexcept

Returns the list of types as a list of strings.

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

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

◆ 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

inlinenodiscardnoexcept

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

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

inlinenodiscardnoexcept

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

inlinenodiscardnoexcept

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.

◆ normalize()

virtual void lal::graphs::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 in lal::graphs::directed_graph.

◆ operator=() [1/2]

tree & lal::graphs::tree::operator= ( const tree & t )

inlinenoexcept

Copy assignment operator.

Parameters

t Tree.

◆ operator=() [2/2]

tree & lal::graphs::tree::operator= ( tree && t )

inlinenoexcept

Move assignment operator.

Parameters

t Tree.

◆ tree_only_actions_after_add_edge()

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

protectednoexcept

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 )

protectednoexcept

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

protectednoexcept

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

protectednoexcept

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 )

protectednoexcept

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 )

protectednoexcept

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

protectednoexcept

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

protectednoexcept

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 )

protectednoexcept

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 )

protectednoexcept

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

inlineprotectednoexcept

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 )

inlineprotectednoexcept

Initializes only the memory of class tree.

Parameters

n	Number of vertices.

◆ tree_only_invalidate()

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

inlineprotectednoexcept

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 )

protectednoexcept

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

protectednoexcept

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

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

protectedpure virtualnoexcept

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.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ update_union_find_after_add_edges()

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

protectedpure virtualnoexcept

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.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ update_union_find_after_add_edges_bulk()

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

protectedpure virtualnoexcept

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.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ update_union_find_after_remove_edge()

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

protectedpure virtualnoexcept

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.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ update_union_find_after_remove_edges()

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

protectedpure virtualnoexcept

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.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ update_union_find_after_remove_edges_bulk()

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

protectedpure virtualnoexcept

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.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_tree.

◆ update_union_find_before_remove_incident_edges_to()

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

protectedpure virtualnoexcept

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.

Implemented in lal::graphs::free_tree, and lal::graphs::rooted_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

protected

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_union_find__root_size

std::vector<uint64_t> lal::graphs::tree::m_union_find__root_size

protected

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/tree.hpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ tree() [1/2]

◆ tree() [2/2]

Member Function Documentation

◆ __disjoint_union()

◆ _init()

◆ actions_after_add_edge()

◆ actions_after_add_edges()

◆ actions_after_add_edges_bulk()

◆ actions_after_remove_edge()

◆ actions_after_remove_edges()

◆ actions_after_remove_edges_bulk()

◆ actions_after_remove_node()

◆ actions_before_remove_edges_incident_to()

◆ are_nodes_in_same_component()

◆ calculate_tree_type()

◆ can_add_edge()

◆ can_add_edges()

◆ check_normalized()

◆ clear()

◆ fill_union_find()

◆ finish_bulk_add()

◆ finish_bulk_add_complete()

◆ finish_bulk_remove()

◆ finish_bulk_remove_complete()

◆ get_component_representative()

◆ get_num_nodes_component()

◆ get_Q()

◆ get_tree_type_list()

◆ init()

◆ is_normalized()

◆ is_of_tree_type()

◆ is_tree()

◆ is_tree_type_valid()

◆ normalize()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ tree_only_actions_after_add_edge()

◆ tree_only_actions_after_add_edges()

◆ tree_only_actions_after_add_edges_bulk()

◆ tree_only_actions_after_add_edges_bulk_complete()

◆ tree_only_actions_after_remove_edge()

◆ tree_only_actions_after_remove_edges()

◆ tree_only_actions_after_remove_edges_bulk()

◆ tree_only_actions_after_remove_edges_bulk_complete()

◆ tree_only_actions_after_remove_node()

◆ tree_only_actions_before_remove_edges_incident_to()

◆ tree_only_add_node()

◆ tree_only_init()

◆ tree_only_invalidate()

◆ tree_only_remove_node()

◆ tree_only_set_edges()

◆ update_union_find_after_add_edge()

◆ update_union_find_after_add_edges()

◆ update_union_find_after_add_edges_bulk()

◆ update_union_find_after_remove_edge()

◆ update_union_find_after_remove_edges()

◆ update_union_find_after_remove_edges_bulk()

◆ update_union_find_before_remove_incident_edges_to()

Member Data Documentation

◆ m_is_normalized

◆ m_is_tree_type_valid

◆ m_union_find__root_size