Undirected graph class. More...

#include <undirected_graph.hpp>

Inheritance diagram for lal::graphs::undirected_graph:

Public Member Functions
	undirected_graph () noexcept
	Empty constructor.

	undirected_graph (uint64_t n) noexcept
	Constructor with number of nodes. More...

	undirected_graph (const undirected_graph &g) noexcept
	Copy constructor. More...

	undirected_graph (undirected_graph &&g) noexcept
	Move constructor. More...

virtual	~undirected_graph () noexcept
	Destructor.

undirected_graph &	operator= (const undirected_graph &g) noexcept
	Copy assignment operator. More...

undirected_graph &	operator= (undirected_graph &&g) noexcept
	Move assignment operator. More...

virtual undirected_graph &	remove_node (node u, bool norm=true, bool check_norm=true) noexcept
	Remove a node from this graph. More...

virtual undirected_graph &	add_edge (node s, node t, bool norm=true, bool check_norm=true) noexcept
	Adds an edge to the graph. More...

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

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

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

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

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

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

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

void	disjoint_union (const undirected_graph &g) noexcept
	Disjoint union of graphs. More...

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

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

const neighbourhood &	get_neighbours (node u) const noexcept
	Returns the neighbourhood of node u. More...

uint64_t	get_degree (node u) const noexcept
	Returns the number of neighbours of u. More...

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

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.

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

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

virtual void	normalise () noexcept
	Normalises the graph. More...

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

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

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

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_normalised () const noexcept
	Returns whether this graph is normalised or not. More...

Protected Member Functions
virtual void	_init (uint64_t n) noexcept
	Initialises memory of undirected_graph and graph classes.

virtual void	_clear () noexcept
	Clears the memory of undirected_graph and graph classes.

void	copy_full_undirected_graph (const undirected_graph &u) noexcept
	Copies all members of this class and the parent class.

void	move_full_undirected_graph (undirected_graph &&u) noexcept
	Moves all members of this class and the parent 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	__disjoint_union (const graph &g) noexcept
	Disjoint union of graphs. More...

virtual void	actions_after_remove_node (node u) noexcept
	Do some work before an node is removed. More...

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

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

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

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

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

Protected Attributes
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_normalised = true
	Is this graph normalised? More...

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

Detailed Description

Undirected graph class.

Class implementing an undirected graph, using the adjacency list data structure.

An object of this class must be initialised either with its constructor or with the init(uint64_t) method. Edges can then be added one by one (see add_edge(node,node,bool,bool) ) or all at the same time (see add_edges(const std::vector<edge>&, bool, bool) ).

Constructor & Destructor Documentation

◆ undirected_graph() [1/3]

lal::graphs::undirected_graph::undirected_graph ( uint64_t n )

inlinenoexcept

Constructor with number of nodes.

Parameters

n	Number of nodes.

◆ undirected_graph() [2/3]

lal::graphs::undirected_graph::undirected_graph ( const undirected_graph & g )

inlinenoexcept

Copy constructor.

Parameters

g	Undirected graph.

◆ undirected_graph() [3/3]

lal::graphs::undirected_graph::undirected_graph ( undirected_graph && g )

inlinenoexcept

Move constructor.

Parameters

g	Undirected graph.

Member Function Documentation

◆ __disjoint_union()

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

protectednoexceptinherited

Disjoint union of graphs.

Given a graph, append it to the current graph.

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

Parameters

g	Input graph.

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

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

◆ actions_after_add_edge()

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

protectedvirtualnoexceptinherited

Do some extra work after an edge has been added.

Parameters

u	Node of the edge
v	Node of the edge

Reimplemented in lal::graphs::tree.

◆ actions_after_remove_edge()

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

protectedvirtualnoexceptinherited

Do some extra work after an edge has been removed.

Parameters

u	Node of the edge
v	Node of the edge

Reimplemented in lal::graphs::tree.

◆ actions_after_remove_node()

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

protectedvirtualnoexceptinherited

Do some work before an node is removed.

Parameters

u	Node to be removed.

Reimplemented in lal::graphs::tree.

◆ actions_before_remove_edges_incident_to()

virtual void lal::graphs::graph::actions_before_remove_edges_incident_to ( 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::tree.

◆ add_edge()

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

virtualnoexcept

Adds an edge to the graph.

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 normalised?
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

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

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

Reimplemented in lal::graphs::free_tree.

◆ add_edge_bulk()

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

noexcept

Adds an edge to the graph.

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

Parameters

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

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

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

◆ add_edges()

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

virtualnoexcept

Adds a list of edges to the graph.

This operation is faster than calling add_edge(node,node,bool,bool) since the edges are added in bulk.

For developers: method lal::graphs::graph::actions_after_add_edge is called for every edge added.

Parameters

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

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

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

Reimplemented in lal::graphs::free_tree.

◆ check_normalised()

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

virtualnoexceptinherited

Checks if the graph is normalised.

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

Reimplemented 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 normalised. The number of edges is 0.

◆ disjoint_union()

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

noexcept

Disjoint union of graphs.

Given a graph, append it to the current graph.

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

Parameters

g	Input graph.

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

◆ finish_bulk_add()

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

virtualnoexcept

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.

Also, the graph must have been completely constructed after all the bulk additions of edges to the graph.

Parameters

norm	Normalise the graph.
check	Check wether the graph is normalised or not.

Implements lal::graphs::graph.

◆ get_degree()

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

inlinenoexcept

Returns the number of neighbours of u.

Parameters

u	Node to be queried.

Returns: The number of adjacent nodes.

◆ get_neighbours()

const neighbourhood & lal::graphs::undirected_graph::get_neighbours ( node u ) const

inlinenoexcept

Returns the neighbourhood of node u.

Parameters

u Node.

Returns: The list of nodes adjacent to node u.

◆ get_Q()

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

virtualnoexcept

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.

◆ init()

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

virtualnoexceptinherited

Allocates the necessary memory for this class.

See _init for details.

Parameters

n	Number of nodes.

◆ is_normalised()

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

inlinenoexceptinherited

Returns whether this graph is normalised or not.

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

Returns: The value of m_normalised.

◆ normalise()

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

virtualnoexceptinherited

Normalises the graph.

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

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

Postcondition: Method is_normalised evaluates to true.

Reimplemented in lal::graphs::directed_graph.

◆ operator=() [1/2]

undirected_graph & lal::graphs::undirected_graph::operator= ( const undirected_graph & g )

inlinenoexcept

Copy assignment operator.

Parameters

g	Undirected graph.

◆ operator=() [2/2]

undirected_graph & lal::graphs::undirected_graph::operator= ( undirected_graph && g )

inlinenoexcept

Move assignment operator.

Parameters

g	Undirected graph.

◆ remove_edge()

virtual undirected_graph & lal::graphs::undirected_graph::remove_edge	(	node	s,
		node	t,
		bool	norm = `true`,
		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	Normalise the graph after the deletion.
check_norm	If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.

Precondition: The edge must exist.

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

Reimplemented in lal::graphs::free_tree.

◆ remove_edges()

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

virtualnoexcept

Remove an edge from this graph.

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

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

Parameters

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

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

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

Reimplemented in lal::graphs::free_tree.

◆ remove_edges_incident_to()

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

virtualnoexcept

Remove all edges incident to a given vertex.

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

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

Parameters

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

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

Reimplemented in lal::graphs::free_tree.

◆ remove_node()

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

virtualnoexcept

Remove a node from this graph.

Parameters

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

Precondition: The node must exist.

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

Reimplemented in lal::graphs::free_tree.

◆ remove_single_edge()

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

privatenoexcept

Removes a single edge.

Parameters

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

◆ set_edges()

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

virtualnoexcept

Sets the edges to the graph.

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

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

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

Parameters

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

Precondition: The graph has been initialized with as many nodes as vertices in the list of edges.; There are no repeated edges in the list.

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

Reimplemented in lal::graphs::free_tree.

Member Data Documentation

◆ m_normalised

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

protectedinherited

Is this graph normalised?

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

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

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

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

lal/graphs/undirected_graph.hpp

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ undirected_graph() [1/3]

◆ undirected_graph() [2/3]

◆ undirected_graph() [3/3]

Member Function Documentation

◆ __disjoint_union()

◆ actions_after_add_edge()

◆ actions_after_remove_edge()

◆ actions_after_remove_node()

◆ actions_before_remove_edges_incident_to()

◆ add_edge()

◆ add_edge_bulk()

◆ add_edges()

◆ check_normalised()

◆ clear()

◆ disjoint_union()

◆ finish_bulk_add()

◆ get_degree()

◆ get_neighbours()

◆ get_Q()

◆ init()

◆ is_normalised()

◆ normalise()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove_edge()

◆ remove_edges()

◆ remove_edges_incident_to()

◆ remove_node()

◆ remove_single_edge()

◆ set_edges()

Member Data Documentation

◆ m_normalised