MySQL 8.4.3
Source Code Documentation
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_vertexA vertex to start a search from.
visitor_startA method or lambda that will be called when a specified vertex starts to be processed, the vertex is supplied as the only argument.
visitor_endA 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_neighborsA 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_setA 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.