GraphAlgorithms_Paths.inl File Reference

Go to the source code of this file.

Functions
template<typename VertexDataMap , typename Visitor = DoNothingGraphVisitor<VertexID>, typename SourceList = std::vector<VertexID>>
TracebackResult	singleTraceback (const SourceList &sources, const VertexID &sink, const VertexDataMap &vertex_data, Visitor &&visitor={}) const
template<typename Graph , typename IsTarget , typename AcceptPath = AlwaysTrue, typename Visitor = DoNothingGraphVisitor<VertexID>, typename InitialList = std::vector<VertexID>>
PathList	findNShortestPaths (std::ptrdiff_t max_paths, Graph &&graph, const InitialList &initial_list, IsTarget &&is_target, Visitor &&visitor={}, AcceptPath &&acceptPath={}) const
template<typename Graph , typename IsTarget , typename Visitor = DoNothingGraphVisitor<VertexID>, typename InitialList = std::vector<VertexID>>
PathList	findNShortestSimplePaths (std::ptrdiff_t max_paths, Graph &&graph, const InitialList &initial_list, IsTarget &&is_target, Visitor &&visitor) const

Function Documentation

findNShortestPaths()

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

PathList findNShortestPaths	(	std::ptrdiff_t	max_paths,
		Graph &&	graph,
		const InitialList &	initial_list,
		IsTarget &&	is_target,
		Visitor &&	visitor = {},
		AcceptPath &&	acceptPath = {}
	)		const

Similar to a breadth-first search, but paths are the "vertices". Finds up to max_paths number of non-intersecting paths in graph between any vertex in initial_list to any vertex where is_target evaluates to true. max_paths < 0 will result in all paths being returned. Should be performed on a limited graph, otherwise memory + time may explode. Perhaps use a fanin graph generated by a breadth first search?

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}} };

GraphAlgorithms<int> g_algos;

// should return (order may be different): {{2,3}, {2,0}, {2,3,0}, {2,3,1,0}} g_algos.findNShortestPaths(-1, g, {2}, [](auto&& n) { return n == 0 || n == 3; });

Definition at line 98 of file GraphAlgorithms_Paths.inl.

findNShortestSimplePaths()

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

PathList findNShortestSimplePaths	(	std::ptrdiff_t	max_paths,
		Graph &&	graph,
		const InitialList &	initial_list,
		IsTarget &&	is_target,
		Visitor &&	visitor
	)		const

Definition at line 205 of file GraphAlgorithms_Paths.inl.

singleTraceback()

template<typename VertexDataMap , typename Visitor = DoNothingGraphVisitor<VertexID>, typename SourceList = std::vector<VertexID>>

TracebackResult singleTraceback	(	const SourceList &	sources,
		const VertexID &	sink,
		const VertexDataMap &	vertex_data,
		Visitor &&	visitor = {}
	)		const

Find a path from one of sources to sink through the fanin graph specified by vertex_data Essentially a completely greedy depth-first search, that returns a path instead of a fanin graph. Starting at sink, it repeatedly takes the first non-ignored fanin, until a member of sources is found. If sink is a member of sources, then this will not exit immediately; any returned path will be at least 2 nodes, adjacent nodes in the path will always form edges present in @vertex_data. If this function encounters a dead end, it still returns the partial path, so be sure to check the success property of the return value.

Definition at line 21 of file GraphAlgorithms_Paths.inl.