depth_first_search.h File Reference

#include <functional>
#include <set>
#include <stack>
#include <tuple>

Go to the source code of this file.

Functions
template<typename TVertex , typename TVisit_start , typename TVisit_end , typename TGet_neighbors , typename TVertex_less = std::less<TVertex>>
void	depth_first_search (TVertex start_vertex, TVisit_start visitor_start, TVisit_end visitor_end, TGet_neighbors get_neighbors, std::set< TVertex > &visited_set=std::set< TVertex >{})
	Performs a Depth First Search algorithm on a graph defined by a set of vertices being an subset of universum of values of TVertex type and, and set of directed edges generated on demand by get_neighbors() method supplied. More...

Function Documentation

depth_first_search()

template<typename TVertex , typename TVisit_start , typename TVisit_end , typename TGet_neighbors , typename TVertex_less = std::less<TVertex>>

void depth_first_search	(	TVertex	start_vertex,
		TVisit_start	visitor_start,
		TVisit_end	visitor_end,
		TGet_neighbors	get_neighbors,
		std::set< TVertex > &	visited_set = std::set<TVertex>{}
	)

Performs a Depth First Search algorithm on a graph defined by a set of vertices being an subset of universum of values of TVertex type and, and set of directed edges generated on demand by get_neighbors() method supplied.

Search starts with a selected vertex, for each vertex that is encountered a visitor_start() method supplied is called and when the DFS finishes traversal from that vertex, a visitor_end() method is called. The set of visited nodes is maintained, so the input graph don't have to be a Directed Acyclic Graph.

Parameters

	start_vertex	A vertex to start a search from.
	visitor_start	A method or lambda that will be called when a specified vertex starts to be processed, the vertex is supplied as the only argument.
	visitor_end	A method or lambda that will be called when a specified vertex ends to be processed, i.e. all its neighbors were already processed, the vertex is supplied as the only argument.
	get_neighbors	A method or lambda that takes a vertex as an argument and returns a enumerable list of all vertices to which the edges exists.
[in,out]	visited_set	A set of vertices that were visited. This can be used to run multiple DFS runs and assure any vertex will not be visited more than once.