Graphs and graph algorithms. More...

Namespaces
namespace	hdf5
namespace	multicut
namespace	multicut_lifted
namespace	twocut_lifted

Classes
class	Adjacency
	The adjacency of a vertex consists of a vertex and a connecting edge. More...
class	BreadthFirstSearchData
struct	BridgesBuffers
class	CompleteGraph
	Complete graph. More...
struct	ComponentsBySearch
	Connected component labeling by breadth-first-search (labels start at 0). More...
struct	ComponentsByPartition
	Connected component labeling using disjoint sets (labels start at 0). More...
struct	CutVerticesBuffers
class	DepthFirstSearchData
class	Digraph
	Directed graph, implemented as an adjacency list. More...
struct	UnitEdgeValueIterator
	Return 1 for every edge. More...
class	Graph
	Undirected graph, implemented as an adjacency list. More...
class	GridGraph
	D-dimensional grid graph. More...
class	MaxFlowPushRelabel
	Push-Relabel Algorithm for computing the maximum s-t-flow of a Digraph. More...
class	MaxFlowEdmondsKarp
	Edmonds-Karp Algorithm for computing the maximum s-t-flow of a Digraph. More...
struct	DijkstraIdleVisitor
	Idle visitor for Dijkstra's algorithm. More...
struct	DefaultSubgraphMask
	An entire graph. More...
struct	IdleGraphVisitor
	Visitors can be used to follow the indices of vertices and edges. More...
struct	VerboseGraphVisitor
	Visitors can be used to follow the indices of vertices and edges. More...

Enumerations
enum	LiftingMetric

Functions
template<typename GRAPH , typename CALLBACK >
void	breadthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &callback)
template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	breadthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &&callback)
template<typename GRAPH , typename CALLBACK >
void	breadthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &callback, BreadthFirstSearchData< std::size_t > &data)
template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	breadthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &&callback, BreadthFirstSearchData< std::size_t > &data)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >
void	breadthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &callback)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	breadthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &&callback)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >
void	breadthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &callback, BreadthFirstSearchData< std::size_t > &data)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	breadthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &&callback, BreadthFirstSearchData< std::size_t > &data)
template<typename GRAPH , typename ARRAY >
void	findBridges (const GRAPH &graph, ARRAY &is_bridge)
	Find, by Tarjan's algorithm, bridges (cut edges) in an undirected graph.
template<typename GRAPH , typename ARRAY >
void	findBridges (const GRAPH &graph, ARRAY &is_bridge, BridgesBuffers< GRAPH > &buffer)
	Find, by Tarjan's algorithm, bridges (cut edges) in an undirected graph.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findBridges (const GRAPH &graph, const SUBGRAPH &subgraph_mask, ARRAY &is_bridge)
	Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findBridges (const GRAPH &graph, const SUBGRAPH &subgraph_mask, ARRAY &is_bridge, BridgesBuffers< GRAPH > &buffer)
	Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findBridges (const GRAPH &graph, const SUBGRAPH &subgraph_mask, std::size_t starting_vertex, ARRAY &is_bridge)
	Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph containing a vertex.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findBridges (const GRAPH &graph, const SUBGRAPH &subgraph_mask, std::size_t starting_vertex, ARRAY &is_bridge, BridgesBuffers< GRAPH > &buffer)
	Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph containing a vertex.
template<class GRAPH , class ITERATOR >
std::size_t	labelComponents (const GRAPH &graph, ITERATOR labeling)
	Connected component labeling by breadth-first-search (labels start at 0).
template<class GRAPH , class SUBGRAPH_MASK , class ITERATOR >
std::size_t	labelComponents (const GRAPH &graph, const SUBGRAPH_MASK &mask, ITERATOR labeling)
	Connected component labeling by breadth-first-search (labels start at 0).
template<typename GRAPH , typename ARRAY >
void	findCutVertices (const GRAPH &graph, ARRAY &is_cut_vertex)
	Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in an undirected graph.
template<typename GRAPH , typename ARRAY >
void	findCutVertices (const GRAPH &graph, ARRAY &is_cut_vertex, CutVerticesBuffers< GRAPH > &buffer)
	Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in an undirected graph.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findCutVertices (const GRAPH &graph, const SUBGRAPH &subgraph_mask, ARRAY &is_cut_vertex)
	Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findCutVertices (const GRAPH &graph, const SUBGRAPH &subgraph_mask, ARRAY &is_cut_vertex, CutVerticesBuffers< GRAPH > &buffer)
	Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findCutVertices (const GRAPH &graph, const SUBGRAPH &subgraph_mask, std::size_t starting_vertex, ARRAY &is_cut_vertex)
	Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph containing a vertex.
template<typename GRAPH , typename SUBGRAPH , typename ARRAY >
void	findCutVertices (const GRAPH &graph, const SUBGRAPH &subgraph_mask, std::size_t starting_vertex, ARRAY &is_cut_vertex, CutVerticesBuffers< GRAPH > &buffer)
	Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph containing a vertex.
template<typename GRAPH , typename CALLBACK >
void	depthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &callback)
template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	depthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &&callback)
template<typename GRAPH , typename CALLBACK >
void	depthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &callback, DepthFirstSearchData< std::size_t > &data)
template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	depthFirstSearch (const GRAPH &g, const std::size_t start_vertex, CALLBACK &&callback, DepthFirstSearchData< std::size_t > &data)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >
void	depthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &callback)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	depthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &&callback)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >
void	depthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &callback, DepthFirstSearchData< std::size_t > &data)
template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>
void	depthFirstSearch (const GRAPH &g, const SUBGRAPH &subgraph_mask, const std::size_t start_vertex, CALLBACK &&callback, DepthFirstSearchData< std::size_t > &data)
template<class INPUT_GRAPH , class OUTPUT_GRAPH >
void	lift (const INPUT_GRAPH &inputGraph, OUTPUT_GRAPH &outputGraph, const std::size_t distanceUpperBound, const std::size_t distanceLowerBound=0)
	Lift a graph.
template<class INPUT_GRAPH_VISITOR , class OUTPUT_GRAPH >
void	lift (const GridGraph< 2, INPUT_GRAPH_VISITOR > &inputGraph, OUTPUT_GRAPH &outputGraph, const std::size_t distanceUpperBound, const std::size_t distanceLowerBound=0, LiftingMetric metric=LiftingMetric::PathLength)
	Lift a grid graph - a faster implementation using the grid structure.
template<typename GRAPH , typename ECA , typename PRED , typename FUNC = Identity<typename ECA::value_type>>
ECA::value_type	findMSTPrim (const GRAPH &graph, const ECA &edge_weights, PRED &predecessor, const FUNC &f)
	Find, by Prim's algorithm, the minimum spanning forest of an undirected graph.
template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>
ECA::value_type	findMSTPrim (const GRAPH &graph, const ECA &edge_weights, const SUBGRAPH &subgraph_mask, PRED &predecessor, const FUNC &f)
	Find, by Prim's algorithm, the minimum spanning forest of a subgraph of an undirected graph.
template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>
ECA::value_type	findMSTPrim (const GRAPH &graph, const ECA &edge_weights, const SUBGRAPH &subgraph_mask, std::size_t starting_vertex, PRED &predecessor, const FUNC &f)
	Find, by Prim's algorithm, the MST of the component of a subgraph of an undirected graph containing a (root) vertex.
template<typename GRAPH , typename ECA , typename PRED , typename FUNC = Identity<typename ECA::value_type>>
ECA::value_type	findMSTDynamicProgramming (const GRAPH &graph, const ECA &edge_weights, PRED &predecessor, const FUNC &f)
	Find, by dynamic programming, the minimum spanning forest of an undirected graph.
template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>
ECA::value_type	findMSTDynamicProgramming (const GRAPH &graph, const ECA &edge_weights, const SUBGRAPH &subgraph_mask, PRED &predecessor, const FUNC &f)
	Find, by Prim's algorithm, the minimum spanning forest of a subgraph of an undirected graph.
template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>
ECA::value_type	findMSTDynamicProgramming (const GRAPH &graph, const ECA &edge_weights, const SUBGRAPH &subgraph_mask, std::size_t starting_vertex, PRED &predecessor, const FUNC &f)
	Find, by dynamic programming, the MST of the component of a subgraph of an undirected graph containing a (root) vertex.
template<class GRAPH , class ITERATOR >
std::pair< bool, std::size_t >	findChord (const GRAPH &graph, ITERATOR begin, ITERATOR end, const bool ignoreEdgeBetweenFirstAndLast=false)
	Search a path for a chord.
template<class GRAPH , class SUBGRAPH_MASK , class ITERATOR >
std::pair< bool, std::size_t >	findChord (const GRAPH &graph, const SUBGRAPH_MASK &mask, ITERATOR begin, ITERATOR end, const bool ignoreEdgeBetweenFirstAndLast=false)
	Search a path for a chord.
template<class GRAPH >
bool	spsp (const GRAPH &g, const std::size_t vs, const std::size_t vt, std::deque< std::size_t > &path, std::vector< std::ptrdiff_t > &parents)
	Search for a shortest path from one to another vertex in an unweighted graph using breadth-first-search.
template<class GRAPH >
bool	spsp (const GRAPH &, const std::size_t, const std::size_t, std::deque< std::size_t > &)
template<class GRAPH , class SUBGRAPH_MASK >
bool	spsp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, std::deque< std::size_t > &path)
	Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.
template<class GRAPH , class SUBGRAPH_MASK >
bool	spsp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, std::deque< std::size_t > &path, std::vector< std::ptrdiff_t > &parents)
	Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.
template<class GRAPH , class EDGE_VALUE_ITERATOR , class T >
void	spsp (const GRAPH &g, const std::size_t vs, const std::size_t vt, EDGE_VALUE_ITERATOR edgeWeights, std::deque< std::size_t > &path, T &distance)
	Search for a shortest path from one to another vertex in a graph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T >
void	spsp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, EDGE_VALUE_ITERATOR edgeWeights, std::deque< std::size_t > &path, T &distance)
	Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class DISTANCE_ITERATOR >
void	sssp (const GRAPH &g, const std::size_t vs, DISTANCE_ITERATOR distances)
	Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.
template<class GRAPH , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	sssp (const GRAPH &g, const std::size_t vs, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR >
void	sssp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, DISTANCE_ITERATOR distances)
	Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	sssp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.
template<class GRAPH , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	sssp (const GRAPH &g, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in a graph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	sssp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR , class VISITOR >
void	sssp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents, VISITOR &visitor)
	Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm with a visitor.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	spsp (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, EDGE_VALUE_ITERATOR edgeWeights, std::deque< std::size_t > &path, T &distance, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH >
bool	spspEdges (const GRAPH &g, const std::size_t vs, const std::size_t vt, std::deque< std::size_t > &path, std::vector< std::ptrdiff_t > &parents)
	Search for a shortest path from one to another vertex in an unweighted graph using breadth-first-search.
template<class GRAPH >
bool	spspEdges (const GRAPH &, const std::size_t, const std::size_t, std::deque< std::size_t > &)
template<class GRAPH , class SUBGRAPH_MASK >
bool	spspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, std::deque< std::size_t > &path)
	Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.
template<class GRAPH , class SUBGRAPH_MASK >
bool	spspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, std::deque< std::size_t > &path,std::vector< std::ptrdiff_t > &parents)
	Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.
template<class GRAPH , class EDGE_VALUE_ITERATOR , class T >
void	spspEdges (const GRAPH &g, const std::size_t vs, const std::size_t vt, EDGE_VALUE_ITERATOR edgeWeights, std::deque< std::size_t > &path, T &distance)
	Search for a shortest path from one to another vertex in a graph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T >
void	spspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, EDGE_VALUE_ITERATOR edgeWeights, std::deque< std::size_t > &path, T &distance)
	Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class DISTANCE_ITERATOR >
void	ssspEdges (const GRAPH &g, const std::size_t vs, DISTANCE_ITERATOR distances)
	Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.
template<class GRAPH , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const std::size_t vs, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.
template<class GRAPH , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const std::size_t vs, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents, PARENT_ITERATOR parentsEdges)
	Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR >
void	ssspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, DISTANCE_ITERATOR distances)
	Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents, PARENT_ITERATOR parentsEdges)
	Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.
template<class GRAPH , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in a graph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents, PARENT_ITERATOR parentsEdges)
	Search for shortest paths from a given vertex to every other vertex in a graph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents)
	Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	ssspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents, PARENT_ITERATOR parentsEdges)
	Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR , class VISITOR >
void	ssspEdges (const GRAPH &, const SUBGRAPH_MASK &, const std::size_t, const EDGE_VALUE_ITERATOR, DISTANCE_ITERATOR, PARENT_ITERATOR, VISITOR &)
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	spspEdges (const GRAPH &, const SUBGRAPH_MASK &, const std::size_t, const std::size_t, EDGE_VALUE_ITERATOR, std::deque< std::size_t > &, T &, DISTANCE_ITERATOR, PARENT_ITERATOR)
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR , class VISITOR >
void	ssspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const EDGE_VALUE_ITERATOR edgeWeights, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents, PARENT_ITERATOR parentsEdges, VISITOR &visitor)
	Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm with a visitor.
template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T , class DISTANCE_ITERATOR , class PARENT_ITERATOR >
void	spspEdges (const GRAPH &g, const SUBGRAPH_MASK &mask, const std::size_t vs, const std::size_t vt, EDGE_VALUE_ITERATOR edgeWeights, std::deque< std::size_t > &path, T &distance, DISTANCE_ITERATOR distances, PARENT_ITERATOR parents, PARENT_ITERATOR parentsEdges)
	Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Detailed Description

Graphs and graph algorithms.

Enumeration Type Documentation

enum andres::graph::LiftingMetric

Definition at line 20 of file lifting.hxx.

Function Documentation

template<typename GRAPH , typename CALLBACK >

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &	callback
	)

inline

Definition at line 55 of file bfs.hxx.

template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &&	callback
	)

inline

Definition at line 67 of file bfs.hxx.

template<typename GRAPH , typename CALLBACK >

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &	callback,
		BreadthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 79 of file bfs.hxx.

template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &&	callback,
		BreadthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 91 of file bfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &	callback
	)

inline

Definition at line 103 of file bfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &&	callback
	)

inline

Definition at line 116 of file bfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &	callback,
		BreadthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 129 of file bfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::breadthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &&	callback,
		BreadthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 179 of file bfs.hxx.

template<typename GRAPH , typename CALLBACK >

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &	callback
	)

inline

Definition at line 50 of file dfs.hxx.

template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &&	callback
	)

inline

Definition at line 62 of file dfs.hxx.

template<typename GRAPH , typename CALLBACK >

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &	callback,
		DepthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 74 of file dfs.hxx.

template<typename GRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const std::size_t	start_vertex,
		CALLBACK &&	callback,
		DepthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 86 of file dfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &	callback
	)

inline

Definition at line 98 of file dfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &&	callback
	)

inline

Definition at line 111 of file dfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK >

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &	callback,
		DepthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 124 of file dfs.hxx.

template<typename GRAPH , typename SUBGRAPH , typename CALLBACK , typename = typename std::enable_if<!std::is_lvalue_reference<CALLBACK>::value>::type>

void andres::graph::depthFirstSearch	(	const GRAPH &	g,
		const SUBGRAPH &	subgraph_mask,
		const std::size_t	start_vertex,
		CALLBACK &&	callback,
		DepthFirstSearchData< std::size_t > &	data
	)

inline

Definition at line 168 of file dfs.hxx.

template<typename GRAPH , typename ARRAY >

void andres::graph::findBridges	(	const GRAPH &	graph,
		ARRAY &	is_bridge
	)

inline

Find, by Tarjan's algorithm, bridges (cut edges) in an undirected graph.

Tarjan, R. (1974). A note on finding the bridges of a graph. Information Processing Letters 2(6):160-161.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
is_bridge	Array storing 1 for each edge-index if it is a bridge, or 0 otherwise.

Definition at line 98 of file bridges.hxx.

template<typename GRAPH , typename ARRAY >

void andres::graph::findBridges	(	const GRAPH &	graph,
		ARRAY &	is_bridge,
		BridgesBuffers< GRAPH > &	buffer
	)

inline

Find, by Tarjan's algorithm, bridges (cut edges) in an undirected graph.

Tarjan, R. (1974). A note on finding the bridges of a graph. Information Processing Letters 2(6):160-161.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
is_bridge	Array storing 1 for each edge-index if it is a bridge, or 0 otherwise.
buffer	A pre-allocated buffer object.

Definition at line 120 of file bridges.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findBridges	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		ARRAY &	is_bridge
	)

inline

Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph.

Tarjan, R. (1974). A note on finding the bridges of a graph. Information Processing Letters 2(6):160-161.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
is_bridge	Array storing 1 for each edge-index if it is a bridge, or 0 otherwise.

Definition at line 142 of file bridges.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findBridges	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		ARRAY &	is_bridge,
		BridgesBuffers< GRAPH > &	buffer
	)

inline

Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph.

Tarjan, R. (1974). A note on finding the bridges of a graph. Information Processing Letters 2(6):160-161.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
is_bridge	Array storing 1 for each edge-index if it is a bridge, or 0 otherwise.
buffer	A pre-allocated buffer object.

Definition at line 166 of file bridges.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findBridges	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		std::size_t	starting_vertex,
		ARRAY &	is_bridge
	)

inline

Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph containing a vertex.

Tarjan, R. (1974). A note on finding the bridges of a graph. Information Processing Letters 2(6):160-161.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
starting_vertex	A vertex inside the subgraph.
is_bridge	Array storing 1 for each edge-index if it is a bridge, or 0 otherwise.

Definition at line 194 of file bridges.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findBridges	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		std::size_t	starting_vertex,
		ARRAY &	is_bridge,
		BridgesBuffers< GRAPH > &	buffer
	)

inline

Find, by Tarjan's algorithm, bridges (cut edges) in a subgraph of an undirected graph containing a vertex.

Tarjan, R. (1974). A note on finding the bridges of a graph. Information Processing Letters 2(6):160-161.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
starting_vertex	A vertex inside the subgraph.
is_bridge	Array storing 1 for each edge-index if it is a bridge, or 0 otherwise.
buffer	A pre-allocated buffer object.

Definition at line 220 of file bridges.hxx.

template<class GRAPH , class ITERATOR >

std::pair<bool, std::size_t> andres::graph::findChord	(	const GRAPH &	graph,
		ITERATOR	begin,
		ITERATOR	end,
		const bool	ignoreEdgeBetweenFirstAndLast = `false`
	)

inline

Search a path for a chord.

Parameters

graph	Graph.
begin	Iterator to the beginning of the sequence of nodes on the path.
end	Iterator to the end of the sequence of nodes on the path.
ignoreEdgeBetweenFirstAndLast	Flag.

Definition at line 22 of file paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class ITERATOR >

std::pair<bool, std::size_t> andres::graph::findChord	(	const GRAPH &	graph,
		const SUBGRAPH_MASK &	mask,
		ITERATOR	begin,
		ITERATOR	end,
		const bool	ignoreEdgeBetweenFirstAndLast = `false`
	)

inline

Search a path for a chord.

Parameters

graph	Graph.
mask	A subgraph mask such as DefaultSubgraphMask.
begin	Iterator to the beginning of the sequence of nodes on the path.
end	Iterator to the end of the sequence of nodes on the path.
ignoreEdgeBetweenFirstAndLast	Flag.

Definition at line 42 of file paths.hxx.

template<typename GRAPH , typename ARRAY >

void andres::graph::findCutVertices	(	const GRAPH &	graph,
		ARRAY &	is_cut_vertex
	)

inline

Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in an undirected graph.

Hopcroft J. and Tarjan R. (1973). Efficient algorithms for graph manipulation. Communications of the ACM 16(6):372-378.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
is_cut_vertex	Array storing 1 for each vertex-index if it is a cut vertex, or 0 otherwise.

Definition at line 98 of file cut-vertices.hxx.

template<typename GRAPH , typename ARRAY >

void andres::graph::findCutVertices	(	const GRAPH &	graph,
		ARRAY &	is_cut_vertex,
		CutVerticesBuffers< GRAPH > &	buffer
	)

inline

Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in an undirected graph.

Hopcroft J. and Tarjan R. (1973). Efficient algorithms for graph manipulation. Communications of the ACM 16(6):372-378.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
is_cut_vertex	Array storing 1 for each vertex-index if it is a cut vertex, or 0 otherwise.
buffer	A pre-allocated buffer object.

Definition at line 120 of file cut-vertices.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findCutVertices	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		ARRAY &	is_cut_vertex
	)

inline

Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph.

Hopcroft J. and Tarjan R. (1973). Efficient algorithms for graph manipulation. Communications of the ACM 16(6):372-378.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
is_cut_vertex	Array storing 1 for each vertex-index if it is a cut vertex, or 0 otherwise.

Definition at line 142 of file cut-vertices.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findCutVertices	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		ARRAY &	is_cut_vertex,
		CutVerticesBuffers< GRAPH > &	buffer
	)

inline

Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph.

Hopcroft J. and Tarjan R. (1973). Efficient algorithms for graph manipulation. Communications of the ACM 16(6):372-378.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
is_cut_vertex	Array storing 1 for each vertex-index if it is a cut vertex, or 0 otherwise.
buffer	A pre-allocated buffer object.

Definition at line 166 of file cut-vertices.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findCutVertices	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		std::size_t	starting_vertex,
		ARRAY &	is_cut_vertex
	)

inline

Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph containing a vertex.

Hopcroft J. and Tarjan R. (1973). Efficient algorithms for graph manipulation. Communications of the ACM 16(6):372-378.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
starting_vertex	A vertex inside the subgraph.
is_cut_vertex	Array storing 1 for each vertex-index if it is a cut vertex, or 0 otherwise.

Definition at line 194 of file cut-vertices.hxx.

template<typename GRAPH , typename SUBGRAPH , typename ARRAY >

void andres::graph::findCutVertices	(	const GRAPH &	graph,
		const SUBGRAPH &	subgraph_mask,
		std::size_t	starting_vertex,
		ARRAY &	is_cut_vertex,
		CutVerticesBuffers< GRAPH > &	buffer
	)

inline

Find, by Hopcroft-Tarjan algorithm, cut vertices (articulation points) in a subgraph of an undirected graph containing a vertex.

Hopcroft J. and Tarjan R. (1973). Efficient algorithms for graph manipulation. Communications of the ACM 16(6):372-378.

Runtime complexity O(|E| + |V|).

Parameters

graph	An undirected graph.
subgraph_mask	Mask defining the subgraph.
starting_vertex	A vertex inside the subgraph.
is_cut_vertex	Array storing 1 for each vertex-index if it is a cut vertex, or 0 otherwise.
buffer	A pre-allocated buffer object.

Definition at line 220 of file cut-vertices.hxx.

template<typename GRAPH , typename ECA , typename PRED , typename FUNC = Identity<typename ECA::value_type>>

ECA::value_type andres::graph::findMSTDynamicProgramming	(	const GRAPH &	graph,
		const ECA &	edge_weights,
		PRED &	predecessor,
		const FUNC &	f
	)

inline

Find, by dynamic programming, the minimum spanning forest of an undirected graph.

Runtime complexity O(|V|^2).

Parameters

graph	An undirected graph.
edge_weights	Edge weights.
predecessor	Vector storing, for each vertex, the index of the edge connecting this vertex to the MST, or graph.numberOfEdges(), for the root of the MST.
f	Functor transforming edge weights.

Definition at line 227 of file minimum-spanning-tree.hxx.

template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>

ECA::value_type andres::graph::findMSTDynamicProgramming	(	const GRAPH &	graph,
		const ECA &	edge_weights,
		const SUBGRAPH &	subgraph_mask,
		PRED &	predecessor,
		const FUNC &	f
	)

inline

Find, by Prim's algorithm, the minimum spanning forest of a subgraph of an undirected graph.

Runtime complexity O(|V|^2).

Parameters

graph	An undirected graph.
edge_weights	Edge weights.
subgraph_mask	Mask defining the subgraph.
predecessor	Vector storing, for each vertex, the index of the edge connecting this vertex to the MST, or graph.numberOfEdges(), for the root of the MST.
f	Functor transforming edge weights.

Definition at line 249 of file minimum-spanning-tree.hxx.

template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>

ECA::value_type andres::graph::findMSTDynamicProgramming	(	const GRAPH &	graph,
		const ECA &	edge_weights,
		const SUBGRAPH &	subgraph_mask,
		std::size_t	starting_vertex,
		PRED &	predecessor,
		const FUNC &	f
	)

inline

Find, by dynamic programming, the MST of the component of a subgraph of an undirected graph containing a (root) vertex.

Runtime complexity O(|V|^2).

Parameters

graph	An undirected graph.
edge_weights	Edge weights.
subgraph_mask	Mask defining the subgraph.
starting_vertex	Root vertex of the MST.
predecessor	Vector storing, for each vertex, the index of the edge connecting this vertex to the MST, or graph.numberOfEdges(), for the root of the MST.
f	Functor transforming edge weights.

Definition at line 282 of file minimum-spanning-tree.hxx.

template<typename GRAPH , typename ECA , typename PRED , typename FUNC = Identity<typename ECA::value_type>>

ECA::value_type andres::graph::findMSTPrim	(	const GRAPH &	graph,
		const ECA &	edge_weights,
		PRED &	predecessor,
		const FUNC &	f
	)

inline

Find, by Prim's algorithm, the minimum spanning forest of an undirected graph.

Robert C. Prim. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401.

Runtime complexity O(|E|log|V|).

Parameters

graph	An undirected graph.
edge_weights	Edge weights.
predecessor	Vector storing, for each vertex, the index of the edge connecting this vertex to the MST, or graph.numberOfEdges(), for the root of the MST.
f	Functor transforming edge weights.

Definition at line 89 of file minimum-spanning-tree.hxx.

template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>

ECA::value_type andres::graph::findMSTPrim	(	const GRAPH &	graph,
		const ECA &	edge_weights,
		const SUBGRAPH &	subgraph_mask,
		PRED &	predecessor,
		const FUNC &	f
	)

inline

Find, by Prim's algorithm, the minimum spanning forest of a subgraph of an undirected graph.

Robert C. Prim. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401.

Runtime complexity O(|E|log|V|).

Parameters

graph	An undirected graph.
edge_weights	Edge weights.
subgraph_mask	Mask defining the subgraph.
predecessor	Vector storing, for each vertex, the index of the edge connecting this vertex to the MST, or graph.numberOfEdges(), for the root of the MST.
f	Functor transforming edge weights.

Definition at line 114 of file minimum-spanning-tree.hxx.

template<typename GRAPH , typename ECA , typename SUBGRAPH , typename PRED , typename FUNC = Identity<typename ECA::value_type>>

ECA::value_type andres::graph::findMSTPrim	(	const GRAPH &	graph,
		const ECA &	edge_weights,
		const SUBGRAPH &	subgraph_mask,
		std::size_t	starting_vertex,
		PRED &	predecessor,
		const FUNC &	f
	)

inline

Find, by Prim's algorithm, the MST of the component of a subgraph of an undirected graph containing a (root) vertex.

Robert C. Prim. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401.

Runtime complexity O(|E|log|V|).

Parameters

graph	An undirected graph.
edge_weights	Edge weights.
subgraph_mask	Mask defining the subgraph.
starting_vertex	Root vertex of the MST.
predecessor	Vector storing, for each vertex, the index of the edge connecting this vertex to the MST, or graph.numberOfEdges(), for the root of the MST.
f	Functor transforming edge weights.

Definition at line 150 of file minimum-spanning-tree.hxx.

template<class GRAPH , class ITERATOR >

std::size_t andres::graph::labelComponents	(	const GRAPH &	graph,
		ITERATOR	labeling
	)

inline

Connected component labeling by breadth-first-search (labels start at 0).

Parameters

graph	Graph.
labeling	Random access iterator to a container that has as many entries as there are vertices in the graph; all entries need to be initialized as 0

Definition at line 54 of file components.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class ITERATOR >

std::size_t andres::graph::labelComponents	(	const GRAPH &	graph,
		const SUBGRAPH_MASK &	mask,
		ITERATOR	labeling
	)

Connected component labeling by breadth-first-search (labels start at 0).

Parameters

graph	Graph.
mask	A subgraph mask such as DefaultSubgraphMask.
labeling	Random access iterator to a container that has as many entries as there are vertices in the graph; all entries need to be initialized as 0

Definition at line 71 of file components.hxx.

template<class INPUT_GRAPH , class OUTPUT_GRAPH >

void andres::graph::lift	(	const INPUT_GRAPH &	inputGraph,
		OUTPUT_GRAPH &	outputGraph,
		const std::size_t	distanceUpperBound,
		const std::size_t	distanceLowerBound = `0`
	)

inline

Lift a graph.

Definition at line 25 of file lifting.hxx.

template<class INPUT_GRAPH_VISITOR , class OUTPUT_GRAPH >

void andres::graph::lift	(	const GridGraph< 2, INPUT_GRAPH_VISITOR > &	inputGraph,
		OUTPUT_GRAPH &	outputGraph,
		const std::size_t	distanceUpperBound,
		const std::size_t	distanceLowerBound = `0`,
		LiftingMetric	metric = `LiftingMetric::PathLength`
	)

inline

Lift a grid graph - a faster implementation using the grid structure.

Definition at line 85 of file lifting.hxx.

template<class GRAPH >

bool andres::graph::spsp	(	const GRAPH &	g,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path,
		std::vector< std::ptrdiff_t > &	parents
	)

inline

Search for a shortest path from one to another vertex in an unweighted graph using breadth-first-search.

This function works for both undirected and directed graphs. It carries out breadth-first searches from the source vertex vs and the target vertex vt, alternating between the two search trees, until these trees meet and thus, a shortest path from vs to vt has been found.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	The source vertex.
vt	The target vertex.
path	A double-ended queue to which the path is written.
parents	An optional external buffer.

Returns: true if a (shortest) path was found, false otherwise.

Definition at line 571 of file shortest-paths.hxx.

template<class GRAPH >

bool andres::graph::spsp	(	const GRAPH &	g,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path
	)

inline

Definition at line 583 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK >

bool andres::graph::spsp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path
	)

Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.

This function works for both undirected and directed graphs. It carries out breadth-first searches from the source vertex vs and the target vertex vt, alternating between the two search trees, until these trees meet and thus, a shortest path from vs to vt has been found.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	The source vertex.
vt	The target vertex.
path	A double-ended queue to which the path is written.

Returns: true if a (shortest) path was found, false otherwise.

Definition at line 609 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK >

bool andres::graph::spsp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path,
		std::vector< std::ptrdiff_t > &	parents
	)

Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.

This function works for both undirected and directed graphs. It carries out breadth-first searches from the source vertex vs and the target vertex vt, alternating between the two search trees, until these trees meet and thus, a shortest path from vs to vt has been found.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	The source vertex.
vt	The target vertex.
path	A double-ended queue to which the path is written.
parents	An optional external buffer.

Returns: true if a (shortest) path was found, false otherwise.

Definition at line 639 of file shortest-paths.hxx.

template<class GRAPH , class EDGE_VALUE_ITERATOR , class T >

void andres::graph::spsp	(	const GRAPH &	g,
		const std::size_t	vs,
		const std::size_t	vt,
		EDGE_VALUE_ITERATOR	edgeWeights,
		std::deque< std::size_t > &	path,
		T &	distance
	)

inline

Search for a shortest path from one to another vertex in a graph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
vt	Target vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
path	A double-ended queue to which the path is written.
distance	the distance to from the source to the target vertex (if there exists a path). if no path is found, path.size() == 0. the data type of this parameter is used to sum up edge weights.

Definition at line 727 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T >

void andres::graph::spsp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		EDGE_VALUE_ITERATOR	edgeWeights,
		std::deque< std::size_t > &	path,
		T &	distance
	)

inline

Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
vt	Target vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
path	A double-ended queue to which the path is written.
distance	the distance to from the source to the target vertex (if there exists a path). if no path is found, path.size() == 0. the data type of this parameter is used to sum up edge weights.

Definition at line 761 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::spsp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		EDGE_VALUE_ITERATOR	edgeWeights,
		std::deque< std::size_t > &	path,
		T &	distance,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
vt	Target vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
path	A double-ended queue to which the path is written.
distance	the distance to from the source to the target vertex (if there exists a path). if no path is found, path.size() == 0. the data type of this parameter is used to sum up edge weights.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices

Definition at line 1016 of file shortest-paths.hxx.

template<class GRAPH >

bool andres::graph::spspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path,
		std::vector< std::ptrdiff_t > &	parents
	)

inline

Search for a shortest path from one to another vertex in an unweighted graph using breadth-first-search.

This function works for both undirected and directed graphs. It carries out breadth-first searches from the source vertex vs and the target vertex vt, alternating between the two search trees, until these trees meet and thus, a shortest path from vs to vt has been found.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	The source vertex.
vt	The target vertex.
path	A double-ended queue to which the path (in edges) is written.
parents	An optional external buffer.

Returns: true if a (shortest) path was found, false otherwise.

Definition at line 1053 of file shortest-paths.hxx.

template<class GRAPH >

bool andres::graph::spspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path
	)

inline

Definition at line 1065 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK >

bool andres::graph::spspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path
	)

inline

Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.

This function works for both undirected and directed graphs. It carries out breadth-first searches from the source vertex vs and the target vertex vt, alternating between the two search trees, until these trees meet and thus, a shortest path from vs to vt has been found.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	The source vertex.
vt	The target vertex.
path	A double-ended queue to which the path (in edges) is written.

Returns: true if a (shortest) path was found, false otherwise.

Definition at line 1091 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK >

bool andres::graph::spspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		std::deque< std::size_t > &	path,
		std::vector< std::ptrdiff_t > &	parents
	)

Search for a shortest path from one to another vertex in an unweighted subgraph using breadth-first-search.

This function works for both undirected and directed graphs. It carries out breadth-first searches from the source vertex vs and the target vertex vt, alternating between the two search trees, until these trees meet and thus, a shortest path from vs to vt has been found.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	The source vertex.
vt	The target vertex.
path	A double-ended queue to which the path (in edges) is written.
parents	An optional external buffer.

Returns: true if a (shortest) path was found, false otherwise.

Definition at line 1119 of file shortest-paths.hxx.

template<class GRAPH , class EDGE_VALUE_ITERATOR , class T >

void andres::graph::spspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		const std::size_t	vt,
		EDGE_VALUE_ITERATOR	edgeWeights,
		std::deque< std::size_t > &	path,
		T &	distance
	)

inline

Search for a shortest path from one to another vertex in a graph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
vt	Target vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
path	A double-ended queue to which the path (in edges) is written.
distance	the distance to from the source to the target vertex (if there exists a path). if no path is found, path.size() == 0. the data type of this parameter is used to sum up edge weights.

Definition at line 1216 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T >

void andres::graph::spspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		EDGE_VALUE_ITERATOR	edgeWeights,
		std::deque< std::size_t > &	path,
		T &	distance
	)

inline

Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
vt	Target vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
path	A double-ended queue to which the path (in edges) is written.
distance	the distance to from the source to the target vertex (if there exists a path). if no path is found, path.size() == 0. the data type of this parameter is used to sum up edge weights.

Definition at line 1250 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::spspEdges	(	const GRAPH &	,
		const SUBGRAPH_MASK &	,
		const std::size_t	,
		const std::size_t	,
		EDGE_VALUE_ITERATOR	,
		std::deque< std::size_t > &	,
		T &	,
		DISTANCE_ITERATOR	,
		PARENT_ITERATOR
	)

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class T , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::spspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const std::size_t	vt,
		EDGE_VALUE_ITERATOR	edgeWeights,
		std::deque< std::size_t > &	path,
		T &	distance,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents,
		PARENT_ITERATOR	parentsEdges
	)

inline

Search for a shortest path from one to another vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
vt	Target vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
path	A double-ended queue to which the path (in edges) is written.
distance	the distance to from the source to the target vertex (if there exists a path). if no path is found, path.size() == 0. the data type of this parameter is used to sum up edge weights.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices
parentsEdges	Random access iterator pointing to the edge that led to each vertex in the shortest-paths tree.

Definition at line 1598 of file shortest-paths.hxx.

template<class GRAPH , class DISTANCE_ITERATOR >

void andres::graph::sssp	(	const GRAPH &	g,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
distances	Random access iterator pointing to distances

Definition at line 785 of file shortest-paths.hxx.

template<class GRAPH , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::sssp	(	const GRAPH &	g,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices

Definition at line 803 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR >

void andres::graph::sssp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
distances	Random access iterator pointing to distances

Definition at line 824 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::sssp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices

Definition at line 844 of file shortest-paths.hxx.

template<class GRAPH , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::sssp	(	const GRAPH &	g,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in a graph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices

Definition at line 865 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::sssp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances.
parents	Random access iterator pointing to parent vertices.

Definition at line 905 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR , class VISITOR >

void andres::graph::sssp	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents,
		VISITOR &	visitor
	)

Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm with a visitor.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances.
parents	Random access iterator pointing to parent vertices.
visitor	See DijkstraIdleVisitor.

Definition at line 939 of file shortest-paths.hxx.

template<class GRAPH , class DISTANCE_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.

Uses edges internally (although this doesn't affect the output).

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
distances	Random access iterator pointing to distances

Definition at line 1274 of file shortest-paths.hxx.

template<class GRAPH , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.

Uses edges internally (although this doesn't affect the output).

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices

Definition at line 1292 of file shortest-paths.hxx.

template<class GRAPH , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents,
		PARENT_ITERATOR	parentsEdges
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted graph using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices
parentsEdges	Random access iterator pointing to the edge that led to each vertex in the shortest-paths tree.

Definition at line 1314 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.

Uses edges internally (although this doesn't affect the output).

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
distances	Random access iterator pointing to distances

Definition at line 1335 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.

Uses edges internally (although this doesn't affect the output).

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices

Definition at line 1355 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents,
		PARENT_ITERATOR	parentsEdges
	)

inline

Search for shortest paths from a given vertex to every other vertex in an unweighted subgraph using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices
parentsEdges	Random access iterator pointing to the edge that led to each vertex in the shortest-paths tree.

Definition at line 1378 of file shortest-paths.hxx.

template<class GRAPH , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in a graph with non-negative edge weights using Dijkstra's algorithm.

Uses edges internally (although this doesn't affect the output).

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices

Definition at line 1400 of file shortest-paths.hxx.

template<class GRAPH , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents,
		PARENT_ITERATOR	parentsEdges
	)

inline

Search for shortest paths from a given vertex to every other vertex in a graph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances
parents	Random access iterator pointing to parent vertices
parentsEdges	Random access iterator pointing to the edge that led to each vertex in the shortest-paths tree.

Definition at line 1421 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents
	)

inline

Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Uses edges internally (although this doesn't affect the output).

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances.
parents	Random access iterator pointing to parent vertices.

Definition at line 1449 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents,
		PARENT_ITERATOR	parentsEdges
	)

inline

Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances.
parents	Random access iterator pointing to parent vertices.
parentsEdges	Random access iterator pointing to the edge that led to each vertex in the shortest-paths tree.

Definition at line 1481 of file shortest-paths.hxx.

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR , class VISITOR >

void andres::graph::ssspEdges	(	const GRAPH &	,
		const SUBGRAPH_MASK &	,
		const std::size_t	,
		const EDGE_VALUE_ITERATOR	,
		DISTANCE_ITERATOR	,
		PARENT_ITERATOR	,
		VISITOR &
	)

template<class GRAPH , class SUBGRAPH_MASK , class EDGE_VALUE_ITERATOR , class DISTANCE_ITERATOR , class PARENT_ITERATOR , class VISITOR >

void andres::graph::ssspEdges	(	const GRAPH &	g,
		const SUBGRAPH_MASK &	mask,
		const std::size_t	vs,
		const EDGE_VALUE_ITERATOR	edgeWeights,
		DISTANCE_ITERATOR	distances,
		PARENT_ITERATOR	parents,
		PARENT_ITERATOR	parentsEdges,
		VISITOR &	visitor
	)

Search for shortest paths from a given vertex to every other vertex in a subgraph with non-negative edge weights using Dijkstra's algorithm with a visitor.

Parameters

g	A graph class such as andres::Graph or andres::Digraph.
mask	A subgraph mask such as DefaultSubgraphMask.
vs	Source vertex.
edgeWeights	A random access iterator pointing to positive edge weights.
distances	Random access iterator pointing to distances.
parents	Random access iterator pointing to parent vertices.
parentsEdges	Random access iterator pointing to the edge that led to each vertex in the shortest-paths tree.
visitor	See DijkstraIdleVisitor.

Definition at line 1516 of file shortest-paths.hxx.

Namespaces

Classes

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

Function Documentation