Functions
template<typename Graph , typename InitialList , typename Visitor = DoNothingGraphVisitor<VertexID>>
auto	breadthFirstVisit (Graph &&graph, const InitialList &initial_list, Visitor &&visitor={}) const

template<typename Graph , typename InitialList , typename VertexCoster , typename Visitor = DoNothingGraphVisitor<VertexID>>
auto	dijkstraVisit (Graph &&graph, const InitialList &initial_list, VertexCoster &&vertex_coster, Visitor &&visitor={}) const

template<typename Graph , typename IsTarget , typename Visitor = DoNothingGraphVisitor<VertexID>, typename InitialList = std::vector<VertexID>>
auto	wavedBreadthFirstVisit (Graph &&graph, const InitialList &initial_list, IsTarget &&is_target, Visitor &&visitor={}) const

template<typename Graph , typename Source , typename IsTarget , typename Visitor = DoNothingGraphVisitor<VertexID>>
auto	depthFirstVisit (Graph &&graph, const Source &source, IsTarget &&is_target, Visitor &&visitor={}) const

Function Documentation

◆ breadthFirstVisit()

template<typename Graph , typename InitialList , typename Visitor = DoNothingGraphVisitor<VertexID>>

auto breadthFirstVisit	(	Graph &&	graph,
		const InitialList &	initial_list,
		Visitor &&	visitor = `{}`
	)		const

A single-threaded breadth-first visit over graph, starting at the vertices in initial_list.

Definition at line 16 of file GraphAlgorithms_Searching.inl.

◆ depthFirstVisit()

template<typename Graph , typename Source , typename IsTarget , typename Visitor = DoNothingGraphVisitor<VertexID>>

auto depthFirstVisit	(	Graph &&	graph,
		const Source &	source,
		IsTarget &&	is_target,
		Visitor &&	visitor = `{}`
	)		const

A single-threaded depth-first visit of graph, starting at the vertex source, terminating if is_target evaluates to true on any vertex. is_target should be a unary functor that accepts a vertex as its only argument

An example follows, and see the tests for more: struct Graph { std::vector<std::vector<int>> fanout_lists; const std::vector<int>& fanout(int ndesc) const { return fanout_lists.at(ndesc); } } g { {{1}, {2,0}, {3,0}, {1,0}} };

struct Visitor : DoNothingGraphVisitor<int> { void onExamine(int ndesc) { std::cout << ndesc << ' '; } } v;

GraphAlgorithms<int> g_algos;

// this should print: 1 2 3 0 g_algos.depthFirstVisit(g, {1}, [](auto&&) { return false; }, v); // this should print: 1 2 g_algos.depthFirstVisit(g, {1}, [](auto&& n) { return n == 2; }, v);

Definition at line 320 of file GraphAlgorithms_Searching.inl.

◆ dijkstraVisit()

template<typename Graph , typename InitialList , typename VertexCoster , typename Visitor = DoNothingGraphVisitor<VertexID>>

auto dijkstraVisit	(	Graph &&	graph,
		const InitialList &	initial_list,
		VertexCoster &&	vertex_coster,
		Visitor &&	visitor = `{}`
	)		const

A single-threaded visit in dijkstra's algorithm-order over graph, starting at the vertices in initial_list.

Definition at line 64 of file GraphAlgorithms_Searching.inl.

◆ wavedBreadthFirstVisit()

template<typename Graph , typename IsTarget , typename Visitor = DoNothingGraphVisitor<VertexID>, typename InitialList = std::vector<VertexID>>

auto wavedBreadthFirstVisit	(	Graph &&	graph,
		const InitialList &	initial_list,
		IsTarget &&	is_target,
		Visitor &&	visitor = `{}`
	)		const

A (optionally) parallel breadth-first visit of graph, starting at the vertices in initial_list, terminating if is_target evaluates to true on any vertex. is_target should be a unary functor that accepts a vertex as its only argument

Parallelism is achieved by splitting the current expansion wave into num_threads segments, and expanding those in separate threads. No threads are created if num_threads == 1. All visitor functions should be thread-safe when running with num_threads > 1

This function returns a fanin graph that includes all edges discovered. A fanin that is closer to the begin of the fanin was discovered at the same time or earlier in the search. So, if you want a BFS spanning tree, follow fanin.begin()