Abstract class for graphs. More...

#include <graph.hpp>

Inheritance diagram for lal::graphs::graph:

Public Member Functions
	graph () noexcept
	Empty constructor.

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

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

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

virtual	~graph () noexcept
	Destructor.

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

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

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

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

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

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

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

virtual bool	has_edge (node u, 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_normalised () const noexcept
	Returns whether this graph is normalised or not. More...

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
virtual void	_init (uint64_t n) noexcept
	Initialises 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	__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...

Detailed Description

Abstract class for graphs.

Class used as an interface for all types of graphs. This means that this class cannot be instantiated. The classes that can be instantiated are undirected_graph, directed_graph, free_tree, rooted_tree.

A usual way of initialising classes inheriting from this one is to use one of the init methods available. Depending on the subclass, this method admits either the number of nodes of the graph or a whole other graph and further information (see rooted_tree::init_rooted(const free_tree&,node). While these classes' internal memory can be initialised, it can also be cleared using method clear. Each class reimplements this method to carry this task appropriately.

Constructor & Destructor Documentation

◆ graph() [1/3]

lal::graphs::graph::graph ( uint64_t n )

inlinenoexcept

Constructor with number of nodes.

Parameters

n	Number of nodes.

◆ graph() [2/3]

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

inlinenoexcept

Copy constructor.

Parameters

g Graph.

◆ graph() [3/3]

lal::graphs::graph::graph ( graph && g )

inlinenoexcept

Move constructor.

Parameters

g Graph.

Member Function Documentation

◆ __disjoint_union()

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

protectednoexcept

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
	)

protectedvirtualnoexcept

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
	)

protectedvirtualnoexcept

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 )

protectedvirtualnoexcept

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 )

protectedvirtualnoexcept

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.

◆ check_normalised()

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

virtualnoexcept

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

virtualnoexcept

Frees the memory occupied by this graph.

See _clear for details.

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

◆ finish_bulk_add()

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

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

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

◆ get_Q()

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

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

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

◆ init()

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

virtualnoexcept

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

inlinenoexcept

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

virtualnoexcept

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]

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

inlinenoexcept

Copy assignment operator.

Parameters

g Graph.

◆ operator=() [2/2]

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

inlinenoexcept

Move assignment operator.

Parameters

g Graph.

Member Data Documentation

◆ m_normalised

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

protected

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

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ graph() [1/3]

◆ graph() [2/3]

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

◆ check_normalised()

◆ clear()

◆ finish_bulk_add()

◆ get_Q()

◆ init()

◆ is_normalised()

◆ normalise()

◆ operator=() [1/2]

◆ operator=() [2/2]

Member Data Documentation

◆ m_normalised