Graph class. More...

#include <Graph.hpp>

Public Types
using	VisitFunc = std::function<VisitResult(const T&, const T&, const W&)>
	Visit function for DFS and BFS.

using	PathsFunc
	Function to call on each path found.

Public Member Functions
void	AddEdge (const T &u, const T &v, bool bidirectional=true)
	Add an edge to the graph from vertex `u` to vertex `v`.

bool	AddEdge (const T &u, const T &v, const W &weight, bool bidirectional=true)
	Add an edge to the graph from vertex `u` to vertex `v`.

void	AddVertex (const T &v)
	Add a vertex `v` to the graph.

bool	HasEdge (const T &u, const T &v) const
	Check if the graph contains an edge from vertex `u` to vertex `v`.

bool	HasEdges (const T &u) const
	Check if there are any positive number of vertexes starting from vertex `u`.

const W *	GetEdgeWeight (const T &u, const T &v) const
	Get a pointer to the weight of the edge from vertex `u` to vertex `v`.

const std::unordered_map< T, AdjSet > &	adj_list () const
	Return the adjacency list of the graph.

void	RemoveEdge (const T &u, const T &v, bool bidirectional=true)
	Remove an edge from vertex `u` to vertex `v`.

void	RemoveVertex (const T &v)
	Remove a vertex `v` from the graph.

void	Clear ()
	Clear the graph, removing all vertices and edges.

void	ClearEdges ()
	Clear the graph, removing only the edges and leaving the vertices.

size_t	Size () const
	Return the number of vertices in the graph.

bool	IsEmpty () const
	Check if the graph is empty.

void	DFS (const T &start, const VisitFunc &func)
	Explore the graph using depth-first search starting from vertex `start`.

void	DFS (const T &start, const VisitFunc &func, std::unordered_set< T > &visited)
	Explore the graph using depth-first search starting from vertex `start`.

void	BFS (const T &start, const VisitFunc &func)
	Explore the graph using breadth-first search starting from vertex `start`.

void	BFS (const T &start, const VisitFunc &func, std::unordered_set< T > &visited)
	Explore the graph using breadth-first search starting from vertex `start`.

void	AllPaths (const T &start, const T &end, const PathsFunc &func)
	Find all paths from vertex `start` to vertex `end`.

void	AllPaths (const T &start, const T &end, const PathsFunc &func, std::unordered_set< T > &visited)
	Find all paths from vertex `start` to vertex `end`.

Private Attributes
std::unordered_map< T, AdjSet >	adj_list_
	Adjacency list of the graph.

Detailed Description

template<class T, std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>
class dlinear::Graph< T, W, EdgeHash, EdgeEqual >

Graph class.

Generic implementation that can be used to represent a graph with vertices of type T.

Template Parameters

T	element type of the vertices.
W	element type of the edge weights.
EdgeHash	hash function for the edges.
EdgeEqual	equality function for the edges. It implements basic graph operations such as adding and removing vertices and edges, as well as graph traversal algorithms such as depth-first search Graph::DFS and breadth-first search Graph::BFS.

Definition at line 66 of file Graph.hpp.

Member Typedef Documentation

◆ PathsFunc

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

using dlinear::Graph< T, W, EdgeHash, EdgeEqual >::PathsFunc

Initial value:

std::function<VisitResult(

std::vector<T>&)>

dlinear::VisitResult

VisitResult

Result returned by the visit function.

Definition Graph.hpp:31

Function to call on each path found.

It will be called on each path found with the following parameter:

path: vector of vertices in the path

Its return value will determine the behavior of the search:

VisitResult::CONTINUE : continue the search
VisitResult::SKIP | VisitResult::STOP : stop the search after the first path is found

See also: VisitResult

Definition at line 84 of file Graph.hpp.

◆ VisitFunc

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

using dlinear::Graph< T, W, EdgeHash, EdgeEqual >::VisitFunc = std::function<VisitResult(const T&, const T&, const W&)>

Visit function for DFS and BFS.

It will be called on each vertex visited with the following parameters:

previous vertex
current vertex
weight of the edge

When called on the starting vertex, previous and current vertex will be the same and weight have a default value.

Its return value will determine the behavior of the search:

VisitResult::CONTINUE : continue the search as usual and add the adjacent vertices to the stack/queue
VisitResult::SKIP : skip adding the adjacent vertices to the stack/queue, but continue the search
VisitResult::STOP : stop the search altogether

See also: VisitResult

Definition at line 70 of file Graph.hpp.

Member Function Documentation

◆ AddEdge() [1/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::AddEdge	(	const T &	u,
		const T &	v,
		bool	bidirectional = true )

inline

Add an edge to the graph from vertex u to vertex v.

If the edge already exists no operation is performed.

Parameters

u	from vertex
v	to vertex
bidirectional	whether to add another edge from `v` to `u`

Definition at line 104 of file Graph.hpp.

◆ AddEdge() [2/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

bool dlinear::Graph< T, W, EdgeHash, EdgeEqual >::AddEdge	(	const T &	u,
		const T &	v,
		const W &	weight,
		bool	bidirectional = true )

inline

Add an edge to the graph from vertex u to vertex v.

If the edge already exists, the weight is updated.

Parameters

u	from vertex
v	to vertex
weight	weight of the edge
bidirectional	whether to add another edge from `v` to `u`

Returns: true if the edge was updated with a new weight; false if the edge was absent or if it was already present and the weight is the same

Definition at line 121 of file Graph.hpp.

◆ AddVertex()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::AddVertex ( const T & v )

inline

Add a vertex v to the graph.

The edge set for the vertex is initialized to an empty set.

Parameters

v	vertex to add

Definition at line 147 of file Graph.hpp.

◆ adj_list()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

const std::unordered_map< T, AdjSet > & dlinear::Graph< T, W, EdgeHash, EdgeEqual >::adj_list ( ) const

inline

Return the adjacency list of the graph.

Returns: a map from vertex to the set of vertices that are adjacent to it

Definition at line 189 of file Graph.hpp.

◆ AllPaths() [1/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::AllPaths	(	const T &	start,
		const T &	end,
		const PathsFunc &	func )

inline

Find all paths from vertex start to vertex end.

Each path will be encountered exactly once and the function func is called on each one. Some path may contain the same vertexes but in different order. The return value of func will determine whether the search continues or should stop after the first path is found.

Note: If start or end are not in the graph, the search stops immediately

Warning: The path is passed to the function by reference. It should not be modified unless that is the intended behavior.

Parameters

start	starting vertex
end	ending vertex
func	function to call on each path

See also: PathsFunc; VisitResult

Definition at line 373 of file Graph.hpp.

◆ AllPaths() [2/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::AllPaths	(	const T &	start,
		const T &	end,
		const PathsFunc &	func,
		std::unordered_set< T > &	visited )

inline

Find all paths from vertex start to vertex end.

Each path will be encountered exactly once and the function func is called on each one. Some path may contain the same vertexes but in different order. The function exposes the visited set, which can be used to keep track of visited vertices or to change the behavior of the search. The return value of func will determine whether the search continues or should stop after the first path is found.

Note: If start or end are not in the graph, the search stops immediately

Warning: The path is passed to the function by reference. It should not be modified unless that is the intended behavior.

Parameters

start	starting vertex
end	ending vertex
func	function to call on each path
visited	set of visited vertices

See also: PathsFunc; VisitResult

Definition at line 396 of file Graph.hpp.

◆ BFS() [1/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::BFS	(	const T &	start,
		const VisitFunc &	func )

inline

Explore the graph using breadth-first search starting from vertex start.

Each vertex is visited exactly once and the function func is called on each one. The return value of func will determine whether the search continues, skips adding the adjacent vertices to the stack, or stops altogether.

Note: When visiting start, both the previous and current vertex will be start and the weight will be default; If start is not in the graph, the search stops immediately

Parameters

start	starting vertex
func	function to call on each vertex upon visiting it

See also: VisitFunc; VisitResult

Definition at line 308 of file Graph.hpp.

◆ BFS() [2/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::BFS	(	const T &	start,
		const VisitFunc &	func,
		std::unordered_set< T > &	visited )

inline

Explore the graph using breadth-first search starting from vertex start.

Each vertex is visited exactly once and the function func is called on each one. The function exposes the visited set, which can be used to keep track of visited vertices or to change the behavior of the search. The return value of func will determine whether the search continues, skips adding the adjacent vertices to the stack, or stops altogether.

Note: When visiting start, both the previous and current vertex will be start and the weight will be default; If start is not in the graph, the search stops immediately

Parameters

start	starting vertex
func	function to call on each vertex upon visiting it
visited	set of visited vertices

See also: VisitFunc; VisitResult

Definition at line 328 of file Graph.hpp.

◆ DFS() [1/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::DFS	(	const T &	start,
		const VisitFunc &	func )

inline

Explore the graph using depth-first search starting from vertex start.

Each vertex is visited exactly once and the function func is called on each one. The return value of func will determine whether the search continues, skips adding the adjacent vertices to the stack, or stops altogether.

Note: When visiting start, both the previous and current vertex will be start and the weight will be default; If start is not in the graph, the search stops immediately

Parameters

start	starting vertex
func	function to call on each vertex upon visiting it

See also: VisitFunc; VisitResult

Definition at line 247 of file Graph.hpp.

◆ DFS() [2/2]

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::DFS	(	const T &	start,
		const VisitFunc &	func,
		std::unordered_set< T > &	visited )

inline

Explore the graph using depth-first search starting from vertex start.

Each vertex is visited exactly once and the function func is called on each one. The function exposes the visited set, which can be used to keep track of visited vertices or to change the behavior of the search. The return value of func will determine whether the search continues, skips adding the adjacent vertices to the stack, or stops altogether.

Note: When visiting start, both the previous and current vertex will be start and the weight will be default; If start is not in the graph, the search stops immediately

Parameters

start	starting vertex
func	function to call on each vertex upon visiting it. The return value will determine the behavior of the search
visited	set of visited vertices

See also: VisitFunc; VisitResult

Definition at line 268 of file Graph.hpp.

◆ GetEdgeWeight()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

const W * dlinear::Graph< T, W, EdgeHash, EdgeEqual >::GetEdgeWeight	(	const T &	u,
		const T &	v ) const

inline

Get a pointer to the weight of the edge from vertex u to vertex v.

Parameters

u	from vertex
v	to vertex

Returns: pointer to the weight of the edge from u to v; nullptr if either u or v is not in the graph or if there is no edge from u to v

Definition at line 176 of file Graph.hpp.

◆ HasEdge()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

bool dlinear::Graph< T, W, EdgeHash, EdgeEqual >::HasEdge	(	const T &	u,
		const T &	v ) const

inline

Check if the graph contains an edge from vertex u to vertex v.

Parameters

u	from vertex
v	to vertex

Returns: true if the graph contains an edge from u to v; false if either u or v is not in the graph or if there is no edge from u to v

Definition at line 158 of file Graph.hpp.

◆ HasEdges()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

bool dlinear::Graph< T, W, EdgeHash, EdgeEqual >::HasEdges ( const T & u ) const

inline

Check if there are any positive number of vertexes starting from vertex u.

Parameters

u	from vertex

Returns: true if there is at least a vertex starting from u; false if there is no vertex starting from u

Definition at line 167 of file Graph.hpp.

◆ IsEmpty()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

bool dlinear::Graph< T, W, EdgeHash, EdgeEqual >::IsEmpty ( ) const

inlinenodiscard

Check if the graph is empty.

Returns: true if the graph is empty; false if the graph is not empty

Definition at line 232 of file Graph.hpp.

◆ RemoveEdge()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::RemoveEdge	(	const T &	u,
		const T &	v,
		bool	bidirectional = true )

inline

Remove an edge from vertex u to vertex v.

Parameters

u	from vertex
v	to vertex
bidirectional	whether to remove the edge from `v` to `u` too

Definition at line 197 of file Graph.hpp.

◆ RemoveVertex()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

void dlinear::Graph< T, W, EdgeHash, EdgeEqual >::RemoveVertex ( const T & v )

inline

Remove a vertex v from the graph.

Parameters

v	vertex to remove

Definition at line 206 of file Graph.hpp.

◆ Size()

template<class T , std::default_initializable W, class EdgeHash = EdgeHash_<T, W>, class EdgeEqual = EdgeEqual_<T, W>>

size_t dlinear::Graph< T, W, EdgeHash, EdgeEqual >::Size ( ) const

inlinenodiscard

Return the number of vertices in the graph.

Returns: number of vertices

Definition at line 222 of file Graph.hpp.

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

dlinear/util/Graph.hpp

Public Types

Public Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ PathsFunc

◆ VisitFunc

Member Function Documentation

◆ AddEdge() [1/2]

◆ AddEdge() [2/2]

◆ AddVertex()

◆ adj_list()

◆ AllPaths() [1/2]

◆ AllPaths() [2/2]

◆ BFS() [1/2]

◆ BFS() [2/2]

◆ DFS() [1/2]

◆ DFS() [2/2]

◆ GetEdgeWeight()

◆ HasEdge()

◆ HasEdges()

◆ IsEmpty()

◆ RemoveEdge()

◆ RemoveVertex()

◆ Size()