Graph Traversal

Methods to traverse a graph, for example to find the shortest path between two vertices.

Functions
template<typename Graph, typename OutputIterator, typename NamedParameters = parameters::Default_named_parameters>
OutputIterator	CGAL::dijkstra_shortest_path (const typename boost::graph_traits< Graph >::vertex_descriptor vs, const typename boost::graph_traits< Graph >::vertex_descriptor vt, const Graph &g, OutputIterator halfedge_sequence_oit, const NamedParameters &np=parameters::default_values())
	computes the shortest path between two vertices in a graph g, where the vertices must belong to the same connected component of g.

Function Documentation

dijkstra_shortest_path()

template<typename Graph, typename OutputIterator, typename NamedParameters = parameters::Default_named_parameters>

OutputIterator CGAL::dijkstra_shortest_path	(	const typename boost::graph_traits< Graph >::vertex_descriptor	vs,
		const typename boost::graph_traits< Graph >::vertex_descriptor	vt,
		const Graph &	g,
		OutputIterator	halfedge_sequence_oit,
		const NamedParameters &	np = parameters::default_values() )

#include <CGAL/boost/graph/dijkstra_shortest_path.h>

computes the shortest path between two vertices in a graph g, where the vertices must belong to the same connected component of g.

Template Parameters

Graph	a model of the concept HalfedgeListGraph
OutputIterator	an output iterator with value type boost::graph_traits<Graph>::halfedge_descriptor
NamedParameters	a sequence of Named Parameters

Parameters

vs	source vertex
vt	target vertex
g	the graph
halfedge_sequence_oit	the output iterator holding the output sequence of halfedges that form the shortest path from vs to vt on g
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

edge_weight_map a property map associating to each edge in the graph its weight or "length". The weights must all be non-negative. Type: a class model of ReadablePropertyMap with boost::graph_traits<PolygonMesh>::edge_descriptor as key type and a value type which as specified in the named parameter distance_mapof the function boost::graph::dijkstra_shortest_paths(), with any model of RingNumberType fulfilling the requirements. Default: get(boost::edge_weight, mesh)

vertex_index_map a property map associating to each vertex of g a unique index between 0 and num_vertices(g) - 1 Type: a class model of ReadablePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and std::size_t as value type Default: an automatically indexed internal map

Examples

BGL_surface_mesh/shortest_path.cpp.