//======================================================================= | |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
//======================================================================= | |
// | |
// | |
// Revision History: | |
// 04 April 2001: Added named parameter variant. (Jeremy Siek) | |
// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock) | |
// | |
#ifndef BOOST_GRAPH_DIJKSTRA_HPP | |
#define BOOST_GRAPH_DIJKSTRA_HPP | |
#include <functional> | |
#include <boost/limits.hpp> | |
#include <boost/graph/named_function_params.hpp> | |
#include <boost/graph/breadth_first_search.hpp> | |
#include <boost/graph/relax.hpp> | |
#include <boost/pending/indirect_cmp.hpp> | |
#include <boost/graph/exception.hpp> | |
#include <boost/pending/relaxed_heap.hpp> | |
#include <boost/graph/overloading.hpp> | |
#include <boost/smart_ptr.hpp> | |
#include <boost/graph/detail/d_ary_heap.hpp> | |
#include <boost/graph/two_bit_color_map.hpp> | |
#include <boost/property_map/property_map.hpp> | |
#include <boost/property_map/vector_property_map.hpp> | |
#include <boost/type_traits.hpp> | |
#ifdef BOOST_GRAPH_DIJKSTRA_TESTING | |
# include <boost/pending/mutable_queue.hpp> | |
#endif // BOOST_GRAPH_DIJKSTRA_TESTING | |
namespace boost { | |
/** | |
* @brief Updates a particular value in a queue used by Dijkstra's | |
* algorithm. | |
* | |
* This routine is called by Dijkstra's algorithm after it has | |
* decreased the distance from the source vertex to the given @p | |
* vertex. By default, this routine will just call @c | |
* Q.update(vertex). However, other queues may provide more | |
* specialized versions of this routine. | |
* | |
* @param Q the queue that will be updated. | |
* @param vertex the vertex whose distance has been updated | |
* @param old_distance the previous distance to @p vertex | |
*/ | |
template<typename Buffer, typename Vertex, typename DistanceType> | |
inline void | |
dijkstra_queue_update(Buffer& Q, Vertex vertex, DistanceType old_distance) | |
{ | |
(void)old_distance; | |
Q.update(vertex); | |
} | |
#ifdef BOOST_GRAPH_DIJKSTRA_TESTING | |
// This is a misnomer now: it now just refers to the "default heap", which is | |
// currently d-ary (d=4) but can be changed by a #define. | |
static bool dijkstra_relaxed_heap = true; | |
#endif | |
template <class Visitor, class Graph> | |
struct DijkstraVisitorConcept { | |
void constraints() { | |
function_requires< CopyConstructibleConcept<Visitor> >(); | |
vis.initialize_vertex(u, g); | |
vis.discover_vertex(u, g); | |
vis.examine_vertex(u, g); | |
vis.examine_edge(e, g); | |
vis.edge_relaxed(e, g); | |
vis.edge_not_relaxed(e, g); | |
vis.finish_vertex(u, g); | |
} | |
Visitor vis; | |
Graph g; | |
typename graph_traits<Graph>::vertex_descriptor u; | |
typename graph_traits<Graph>::edge_descriptor e; | |
}; | |
template <class Visitors = null_visitor> | |
class dijkstra_visitor : public bfs_visitor<Visitors> { | |
public: | |
dijkstra_visitor() { } | |
dijkstra_visitor(Visitors vis) | |
: bfs_visitor<Visitors>(vis) { } | |
template <class Edge, class Graph> | |
void edge_relaxed(Edge e, Graph& g) { | |
invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); | |
} | |
template <class Edge, class Graph> | |
void edge_not_relaxed(Edge e, Graph& g) { | |
invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); | |
} | |
private: | |
template <class Edge, class Graph> | |
void tree_edge(Edge u, Graph& g) { } | |
}; | |
template <class Visitors> | |
dijkstra_visitor<Visitors> | |
make_dijkstra_visitor(Visitors vis) { | |
return dijkstra_visitor<Visitors>(vis); | |
} | |
typedef dijkstra_visitor<> default_dijkstra_visitor; | |
namespace detail { | |
template <class UniformCostVisitor, class UpdatableQueue, | |
class WeightMap, class PredecessorMap, class DistanceMap, | |
class BinaryFunction, class BinaryPredicate> | |
struct dijkstra_bfs_visitor | |
{ | |
typedef typename property_traits<DistanceMap>::value_type D; | |
dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q, | |
WeightMap w, PredecessorMap p, DistanceMap d, | |
BinaryFunction combine, BinaryPredicate compare, | |
D zero) | |
: m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d), | |
m_combine(combine), m_compare(compare), m_zero(zero) { } | |
template <class Edge, class Graph> | |
void tree_edge(Edge e, Graph& g) { | |
bool decreased = relax(e, g, m_weight, m_predecessor, m_distance, | |
m_combine, m_compare); | |
if (decreased) | |
m_vis.edge_relaxed(e, g); | |
else | |
m_vis.edge_not_relaxed(e, g); | |
} | |
template <class Edge, class Graph> | |
void gray_target(Edge e, Graph& g) { | |
D old_distance = get(m_distance, target(e, g)); | |
bool decreased = relax(e, g, m_weight, m_predecessor, m_distance, | |
m_combine, m_compare); | |
if (decreased) { | |
dijkstra_queue_update(m_Q, target(e, g), old_distance); | |
m_vis.edge_relaxed(e, g); | |
} else | |
m_vis.edge_not_relaxed(e, g); | |
} | |
template <class Vertex, class Graph> | |
void initialize_vertex(Vertex u, Graph& g) | |
{ m_vis.initialize_vertex(u, g); } | |
template <class Edge, class Graph> | |
void non_tree_edge(Edge, Graph&) { } | |
template <class Vertex, class Graph> | |
void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); } | |
template <class Vertex, class Graph> | |
void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); } | |
template <class Edge, class Graph> | |
void examine_edge(Edge e, Graph& g) { | |
if (m_compare(get(m_weight, e), m_zero)) | |
boost::throw_exception(negative_edge()); | |
m_vis.examine_edge(e, g); | |
} | |
template <class Edge, class Graph> | |
void black_target(Edge, Graph&) { } | |
template <class Vertex, class Graph> | |
void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); } | |
UniformCostVisitor m_vis; | |
UpdatableQueue& m_Q; | |
WeightMap m_weight; | |
PredecessorMap m_predecessor; | |
DistanceMap m_distance; | |
BinaryFunction m_combine; | |
BinaryPredicate m_compare; | |
D m_zero; | |
}; | |
} // namespace detail | |
namespace detail { | |
template <class Graph, class IndexMap, class Value, bool KnownNumVertices> | |
struct vertex_property_map_generator_helper {}; | |
template <class Graph, class IndexMap, class Value> | |
struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> { | |
typedef boost::iterator_property_map<Value*, IndexMap> type; | |
static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { | |
array_holder.reset(new Value[num_vertices(g)]); | |
std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value()); | |
return make_iterator_property_map(array_holder.get(), index); | |
} | |
}; | |
template <class Graph, class IndexMap, class Value> | |
struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> { | |
typedef boost::vector_property_map<Value, IndexMap> type; | |
static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { | |
return boost::make_vector_property_map<Value>(index); | |
} | |
}; | |
template <class Graph, class IndexMap, class Value> | |
struct vertex_property_map_generator { | |
typedef boost::is_base_and_derived< | |
boost::vertex_list_graph_tag, | |
typename boost::graph_traits<Graph>::traversal_category> | |
known_num_vertices; | |
typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper; | |
typedef typename helper::type type; | |
static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { | |
return helper::build(g, index, array_holder); | |
} | |
}; | |
} | |
namespace detail { | |
template <class Graph, class IndexMap, bool KnownNumVertices> | |
struct default_color_map_generator_helper {}; | |
template <class Graph, class IndexMap> | |
struct default_color_map_generator_helper<Graph, IndexMap, true> { | |
typedef boost::two_bit_color_map<IndexMap> type; | |
static type build(const Graph& g, const IndexMap& index) { | |
size_t nv = num_vertices(g); | |
return boost::two_bit_color_map<IndexMap>(nv, index); | |
} | |
}; | |
template <class Graph, class IndexMap> | |
struct default_color_map_generator_helper<Graph, IndexMap, false> { | |
typedef boost::vector_property_map<boost::two_bit_color_type, IndexMap> type; | |
static type build(const Graph& g, const IndexMap& index) { | |
return boost::make_vector_property_map<boost::two_bit_color_type>(index); | |
} | |
}; | |
template <class Graph, class IndexMap> | |
struct default_color_map_generator { | |
typedef boost::is_base_and_derived< | |
boost::vertex_list_graph_tag, | |
typename boost::graph_traits<Graph>::traversal_category> | |
known_num_vertices; | |
typedef default_color_map_generator_helper<Graph, IndexMap, known_num_vertices::value> helper; | |
typedef typename helper::type type; | |
static type build(const Graph& g, const IndexMap& index) { | |
return helper::build(g, index); | |
} | |
}; | |
} | |
// Call breadth first search with default color map. | |
template <class Graph, class DijkstraVisitor, | |
class PredecessorMap, class DistanceMap, | |
class WeightMap, class IndexMap, class Compare, class Combine, | |
class DistZero> | |
inline void | |
dijkstra_shortest_paths_no_init | |
(const Graph& g, | |
typename graph_traits<Graph>::vertex_descriptor s, | |
PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
IndexMap index_map, | |
Compare compare, Combine combine, DistZero zero, | |
DijkstraVisitor vis) | |
{ | |
typedef | |
detail::default_color_map_generator<Graph, IndexMap> | |
ColorMapHelper; | |
typedef typename ColorMapHelper::type ColorMap; | |
ColorMap color = | |
ColorMapHelper::build(g, index_map); | |
dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight, | |
index_map, compare, combine, zero, vis, | |
color); | |
} | |
// Call breadth first search | |
template <class Graph, class DijkstraVisitor, | |
class PredecessorMap, class DistanceMap, | |
class WeightMap, class IndexMap, class Compare, class Combine, | |
class DistZero, class ColorMap> | |
inline void | |
dijkstra_shortest_paths_no_init | |
(const Graph& g, | |
typename graph_traits<Graph>::vertex_descriptor s, | |
PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
IndexMap index_map, | |
Compare compare, Combine combine, DistZero zero, | |
DijkstraVisitor vis, ColorMap color) | |
{ | |
typedef indirect_cmp<DistanceMap, Compare> IndirectCmp; | |
IndirectCmp icmp(distance, compare); | |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
#ifdef BOOST_GRAPH_DIJKSTRA_TESTING | |
if (!dijkstra_relaxed_heap) { | |
typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap> | |
MutableQueue; | |
MutableQueue Q(num_vertices(g), icmp, index_map); | |
detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, | |
PredecessorMap, DistanceMap, Combine, Compare> | |
bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); | |
breadth_first_visit(g, s, Q, bfs_vis, color); | |
return; | |
} | |
#endif // BOOST_GRAPH_DIJKSTRA_TESTING | |
#ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP | |
typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue; | |
MutableQueue Q(num_vertices(g), icmp, index_map); | |
#else // Now the default: use a d-ary heap | |
boost::scoped_array<std::size_t> index_in_heap_map_holder; | |
typedef | |
detail::vertex_property_map_generator<Graph, IndexMap, std::size_t> | |
IndexInHeapMapHelper; | |
typedef typename IndexInHeapMapHelper::type IndexInHeapMap; | |
IndexInHeapMap index_in_heap = | |
IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder); | |
typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare> | |
MutableQueue; | |
MutableQueue Q(distance, index_in_heap, compare); | |
#endif // Relaxed heap | |
detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, | |
PredecessorMap, DistanceMap, Combine, Compare> | |
bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); | |
breadth_first_visit(g, s, Q, bfs_vis, color); | |
} | |
// Initialize distances and call breadth first search with default color map | |
template <class VertexListGraph, class DijkstraVisitor, | |
class PredecessorMap, class DistanceMap, | |
class WeightMap, class IndexMap, class Compare, class Combine, | |
class DistInf, class DistZero, typename T, typename Tag, | |
typename Base> | |
inline void | |
dijkstra_shortest_paths | |
(const VertexListGraph& g, | |
typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
IndexMap index_map, | |
Compare compare, Combine combine, DistInf inf, DistZero zero, | |
DijkstraVisitor vis, | |
const bgl_named_params<T, Tag, Base>& | |
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag)) | |
{ | |
boost::two_bit_color_map<IndexMap> color(num_vertices(g), index_map); | |
dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map, | |
compare, combine, inf, zero, vis, | |
color); | |
} | |
// Initialize distances and call breadth first search | |
template <class VertexListGraph, class DijkstraVisitor, | |
class PredecessorMap, class DistanceMap, | |
class WeightMap, class IndexMap, class Compare, class Combine, | |
class DistInf, class DistZero, class ColorMap> | |
inline void | |
dijkstra_shortest_paths | |
(const VertexListGraph& g, | |
typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
IndexMap index_map, | |
Compare compare, Combine combine, DistInf inf, DistZero zero, | |
DijkstraVisitor vis, ColorMap color) | |
{ | |
typedef typename property_traits<ColorMap>::value_type ColorValue; | |
typedef color_traits<ColorValue> Color; | |
typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; | |
for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { | |
vis.initialize_vertex(*ui, g); | |
put(distance, *ui, inf); | |
put(predecessor, *ui, *ui); | |
put(color, *ui, Color::white()); | |
} | |
put(distance, s, zero); | |
dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight, | |
index_map, compare, combine, zero, vis, color); | |
} | |
// Initialize distances and call breadth first search | |
template <class VertexListGraph, class DijkstraVisitor, | |
class PredecessorMap, class DistanceMap, | |
class WeightMap, class IndexMap, class Compare, class Combine, | |
class DistInf, class DistZero> | |
inline void | |
dijkstra_shortest_paths | |
(const VertexListGraph& g, | |
typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
IndexMap index_map, | |
Compare compare, Combine combine, DistInf inf, DistZero zero, | |
DijkstraVisitor vis) | |
{ | |
dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map, | |
compare, combine, inf, zero, vis, | |
no_named_parameters()); | |
} | |
namespace detail { | |
// Handle defaults for PredecessorMap and | |
// Distance Compare, Combine, Inf and Zero | |
template <class VertexListGraph, class DistanceMap, class WeightMap, | |
class IndexMap, class Params> | |
inline void | |
dijkstra_dispatch2 | |
(const VertexListGraph& g, | |
typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
DistanceMap distance, WeightMap weight, IndexMap index_map, | |
const Params& params) | |
{ | |
// Default for predecessor map | |
dummy_property_map p_map; | |
typedef typename property_traits<DistanceMap>::value_type D; | |
dijkstra_shortest_paths | |
(g, s, | |
choose_param(get_param(params, vertex_predecessor), p_map), | |
distance, weight, index_map, | |
choose_param(get_param(params, distance_compare_t()), | |
std::less<D>()), | |
choose_param(get_param(params, distance_combine_t()), | |
closed_plus<D>()), | |
choose_param(get_param(params, distance_inf_t()), | |
(std::numeric_limits<D>::max)()), | |
choose_param(get_param(params, distance_zero_t()), | |
D()), | |
choose_param(get_param(params, graph_visitor), | |
make_dijkstra_visitor(null_visitor())), | |
params); | |
} | |
template <class VertexListGraph, class DistanceMap, class WeightMap, | |
class IndexMap, class Params> | |
inline void | |
dijkstra_dispatch1 | |
(const VertexListGraph& g, | |
typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
DistanceMap distance, WeightMap weight, IndexMap index_map, | |
const Params& params) | |
{ | |
// Default for distance map | |
typedef typename property_traits<WeightMap>::value_type D; | |
typename std::vector<D>::size_type | |
n = is_default_param(distance) ? num_vertices(g) : 1; | |
std::vector<D> distance_map(n); | |
detail::dijkstra_dispatch2 | |
(g, s, choose_param(distance, make_iterator_property_map | |
(distance_map.begin(), index_map, | |
distance_map[0])), | |
weight, index_map, params); | |
} | |
} // namespace detail | |
// Named Parameter Variant | |
template <class VertexListGraph, class Param, class Tag, class Rest> | |
inline void | |
dijkstra_shortest_paths | |
(const VertexListGraph& g, | |
typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
const bgl_named_params<Param,Tag,Rest>& params) | |
{ | |
// Default for edge weight and vertex index map is to ask for them | |
// from the graph. Default for the visitor is null_visitor. | |
detail::dijkstra_dispatch1 | |
(g, s, | |
get_param(params, vertex_distance), | |
choose_const_pmap(get_param(params, edge_weight), g, edge_weight), | |
choose_const_pmap(get_param(params, vertex_index), g, vertex_index), | |
params); | |
} | |
} // namespace boost | |
#ifdef BOOST_GRAPH_USE_MPI | |
# include <boost/graph/distributed/dijkstra_shortest_paths.hpp> | |
#endif | |
#endif // BOOST_GRAPH_DIJKSTRA_HPP |