1//=======================================================================
2// Copyright 2002 Indiana University.
3// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4//
5// Distributed under the Boost Software License, Version 1.0. (See
6// accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//=======================================================================
9
10#ifndef BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP
11#define BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP
12
13#include <boost/graph/topological_sort.hpp>
14#include <boost/graph/dijkstra_shortest_paths.hpp>
15
16// single-source shortest paths for a Directed Acyclic Graph (DAG)
17
18namespace boost {
19
20 // Initalize distances and call depth first search
21 template <class VertexListGraph, class DijkstraVisitor,
22 class DistanceMap, class WeightMap, class ColorMap,
23 class PredecessorMap,
24 class Compare, class Combine,
25 class DistInf, class DistZero>
26 inline void
27 dag_shortest_paths
28 (const VertexListGraph& g,
29 typename graph_traits<VertexListGraph>::vertex_descriptor s,
30 DistanceMap distance, WeightMap weight, ColorMap color,
31 PredecessorMap pred,
32 DijkstraVisitor vis, Compare compare, Combine combine,
33 DistInf inf, DistZero zero)
34 {
35 typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
36 std::vector<Vertex> rev_topo_order;
37 rev_topo_order.reserve(num_vertices(g));
38
39 // Call 'depth_first_visit', not 'topological_sort', because we don't
40 // want to traverse the entire graph, only vertices reachable from 's',
41 // and 'topological_sort' will traverse everything. The logic below
42 // is the same as for 'topological_sort', only we call 'depth_first_visit'
43 // and 'topological_sort' calls 'depth_first_search'.
44 topo_sort_visitor<std::back_insert_iterator<std::vector<Vertex> > >
45 topo_visitor(std::back_inserter(rev_topo_order));
46 depth_first_visit(g, s, topo_visitor, color);
47
48 typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
49 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
50 put(distance, *ui, inf);
51 put(pred, *ui, *ui);
52 }
53
54 put(distance, s, zero);
55 vis.discover_vertex(s, g);
56 typename std::vector<Vertex>::reverse_iterator i;
57 for (i = rev_topo_order.rbegin(); i != rev_topo_order.rend(); ++i) {
58 Vertex u = *i;
59 vis.examine_vertex(u, g);
60 typename graph_traits<VertexListGraph>::out_edge_iterator e, e_end;
61 for (boost::tie(e, e_end) = out_edges(u, g); e != e_end; ++e) {
62 vis.discover_vertex(target(*e, g), g);
63 bool decreased = relax(*e, g, weight, pred, distance,
64 combine, compare);
65 if (decreased)
66 vis.edge_relaxed(*e, g);
67 else
68 vis.edge_not_relaxed(*e, g);
69 }
70 vis.finish_vertex(u, g);
71 }
72 }
73
74 namespace detail {
75
76 // Defaults are the same as Dijkstra's algorithm
77
78 // Handle Distance Compare, Combine, Inf and Zero defaults
79 template <class VertexListGraph, class DijkstraVisitor,
80 class DistanceMap, class WeightMap, class ColorMap,
81 class IndexMap, class Params>
82 inline void
83 dag_sp_dispatch2
84 (const VertexListGraph& g,
85 typename graph_traits<VertexListGraph>::vertex_descriptor s,
86 DistanceMap distance, WeightMap weight, ColorMap color, IndexMap /*id*/,
87 DijkstraVisitor vis, const Params& params)
88 {
89 typedef typename property_traits<DistanceMap>::value_type D;
90 dummy_property_map p_map;
91 D inf =
92 choose_param(get_param(params, distance_inf_t()),
93 (std::numeric_limits<D>::max)());
94 dag_shortest_paths
95 (g, s, distance, weight, color,
96 choose_param(get_param(params, vertex_predecessor), p_map),
97 vis,
98 choose_param(get_param(params, distance_compare_t()), std::less<D>()),
99 choose_param(get_param(params, distance_combine_t()), closed_plus<D>(inf)),
100 inf,
101 choose_param(get_param(params, distance_zero_t()),
102 D()));
103 }
104
105 // Handle DistanceMap and ColorMap defaults
106 template <class VertexListGraph, class DijkstraVisitor,
107 class DistanceMap, class WeightMap, class ColorMap,
108 class IndexMap, class Params>
109 inline void
110 dag_sp_dispatch1
111 (const VertexListGraph& g,
112 typename graph_traits<VertexListGraph>::vertex_descriptor s,
113 DistanceMap distance, WeightMap weight, ColorMap color, IndexMap id,
114 DijkstraVisitor vis, const Params& params)
115 {
116 typedef typename property_traits<WeightMap>::value_type T;
117 typename std::vector<T>::size_type n;
118 n = is_default_param(distance) ? num_vertices(g) : 1;
119 std::vector<T> distance_map(n);
120 n = is_default_param(color) ? num_vertices(g) : 1;
121 std::vector<default_color_type> color_map(n);
122
123 dag_sp_dispatch2
124 (g, s,
125 choose_param(distance,
126 make_iterator_property_map(distance_map.begin(), id,
127 distance_map[0])),
128 weight,
129 choose_param(color,
130 make_iterator_property_map(color_map.begin(), id,
131 color_map[0])),
132 id, vis, params);
133 }
134
135 } // namespace detail
136
137 template <class VertexListGraph, class Param, class Tag, class Rest>
138 inline void
139 dag_shortest_paths
140 (const VertexListGraph& g,
141 typename graph_traits<VertexListGraph>::vertex_descriptor s,
142 const bgl_named_params<Param,Tag,Rest>& params)
143 {
144 // assert that the graph is directed...
145 null_visitor null_vis;
146 detail::dag_sp_dispatch1
147 (g, s,
148 get_param(params, vertex_distance),
149 choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
150 get_param(params, vertex_color),
151 choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
152 choose_param(get_param(params, graph_visitor),
153 make_dijkstra_visitor(vis: null_vis)),
154 params);
155 }
156
157} // namespace boost
158
159#endif // BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP
160

source code of boost/boost/graph/dag_shortest_paths.hpp