MySQL 8.4.3
Source Code Documentation
|
#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... | |
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.
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. |