]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
18 | namespace boost |
19 | { | |
20 | ||
21 | // Initalize distances and call depth first search | |
22 | template < class VertexListGraph, class DijkstraVisitor, class DistanceMap, | |
23 | class WeightMap, class ColorMap, class PredecessorMap, class Compare, | |
24 | class Combine, class DistInf, class DistZero > | |
25 | inline void dag_shortest_paths(const VertexListGraph& g, | |
26 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
27 | DistanceMap distance, WeightMap weight, ColorMap color, PredecessorMap pred, | |
28 | DijkstraVisitor vis, Compare compare, Combine combine, DistInf inf, | |
29 | DistZero zero) | |
30 | { | |
31 | typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex; | |
32 | std::vector< Vertex > rev_topo_order; | |
7c673cae FG |
33 | rev_topo_order.reserve(num_vertices(g)); |
34 | ||
35 | // Call 'depth_first_visit', not 'topological_sort', because we don't | |
36 | // want to traverse the entire graph, only vertices reachable from 's', | |
37 | // and 'topological_sort' will traverse everything. The logic below | |
38 | // is the same as for 'topological_sort', only we call 'depth_first_visit' | |
39 | // and 'topological_sort' calls 'depth_first_search'. | |
f67539c2 | 40 | topo_sort_visitor< std::back_insert_iterator< std::vector< Vertex > > > |
7c673cae FG |
41 | topo_visitor(std::back_inserter(rev_topo_order)); |
42 | depth_first_visit(g, s, topo_visitor, color); | |
43 | ||
f67539c2 TL |
44 | typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end; |
45 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) | |
46 | { | |
47 | put(distance, *ui, inf); | |
48 | put(pred, *ui, *ui); | |
7c673cae FG |
49 | } |
50 | ||
51 | put(distance, s, zero); | |
52 | vis.discover_vertex(s, g); | |
f67539c2 TL |
53 | typename std::vector< Vertex >::reverse_iterator i; |
54 | for (i = rev_topo_order.rbegin(); i != rev_topo_order.rend(); ++i) | |
55 | { | |
56 | Vertex u = *i; | |
57 | vis.examine_vertex(u, g); | |
58 | typename graph_traits< VertexListGraph >::out_edge_iterator e, e_end; | |
59 | for (boost::tie(e, e_end) = out_edges(u, g); e != e_end; ++e) | |
60 | { | |
61 | vis.discover_vertex(target(*e, g), g); | |
62 | bool decreased | |
63 | = relax(*e, g, weight, pred, distance, combine, compare); | |
64 | if (decreased) | |
65 | vis.edge_relaxed(*e, g); | |
66 | else | |
67 | vis.edge_not_relaxed(*e, g); | |
68 | } | |
69 | vis.finish_vertex(u, g); | |
7c673cae | 70 | } |
f67539c2 | 71 | } |
7c673cae | 72 | |
f67539c2 TL |
73 | namespace detail |
74 | { | |
7c673cae FG |
75 | |
76 | // Defaults are the same as Dijkstra's algorithm | |
77 | ||
78 | // Handle Distance Compare, Combine, Inf and Zero defaults | |
f67539c2 TL |
79 | template < class VertexListGraph, class DijkstraVisitor, class DistanceMap, |
80 | class WeightMap, class ColorMap, class IndexMap, class Params > | |
81 | inline void dag_sp_dispatch2(const VertexListGraph& g, | |
82 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
83 | DistanceMap distance, WeightMap weight, ColorMap color, IndexMap /*id*/, | |
84 | DijkstraVisitor vis, const Params& params) | |
7c673cae | 85 | { |
f67539c2 TL |
86 | typedef typename property_traits< DistanceMap >::value_type D; |
87 | dummy_property_map p_map; | |
88 | D inf = choose_param(get_param(params, distance_inf_t()), | |
89 | (std::numeric_limits< D >::max)()); | |
90 | dag_shortest_paths(g, s, distance, weight, color, | |
91 | choose_param(get_param(params, vertex_predecessor), p_map), vis, | |
92 | choose_param( | |
93 | get_param(params, distance_compare_t()), std::less< D >()), | |
94 | choose_param( | |
95 | get_param(params, distance_combine_t()), closed_plus< D >(inf)), | |
96 | inf, choose_param(get_param(params, distance_zero_t()), D())); | |
7c673cae FG |
97 | } |
98 | ||
99 | // Handle DistanceMap and ColorMap defaults | |
f67539c2 TL |
100 | template < class VertexListGraph, class DijkstraVisitor, class DistanceMap, |
101 | class WeightMap, class ColorMap, class IndexMap, class Params > | |
102 | inline void dag_sp_dispatch1(const VertexListGraph& g, | |
103 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
104 | DistanceMap distance, WeightMap weight, ColorMap color, IndexMap id, | |
105 | DijkstraVisitor vis, const Params& params) | |
7c673cae | 106 | { |
f67539c2 TL |
107 | typedef typename property_traits< WeightMap >::value_type T; |
108 | typename std::vector< T >::size_type n; | |
109 | n = is_default_param(distance) ? num_vertices(g) : 1; | |
110 | std::vector< T > distance_map(n); | |
111 | n = is_default_param(color) ? num_vertices(g) : 1; | |
112 | std::vector< default_color_type > color_map(n); | |
113 | ||
114 | dag_sp_dispatch2(g, s, | |
115 | choose_param(distance, | |
116 | make_iterator_property_map( | |
117 | distance_map.begin(), id, distance_map[0])), | |
118 | weight, | |
119 | choose_param(color, | |
120 | make_iterator_property_map( | |
121 | color_map.begin(), id, color_map[0])), | |
122 | id, vis, params); | |
7c673cae | 123 | } |
f67539c2 TL |
124 | |
125 | } // namespace detail | |
126 | ||
127 | template < class VertexListGraph, class Param, class Tag, class Rest > | |
128 | inline void dag_shortest_paths(const VertexListGraph& g, | |
129 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
130 | const bgl_named_params< Param, Tag, Rest >& params) | |
131 | { | |
7c673cae FG |
132 | // assert that the graph is directed... |
133 | null_visitor null_vis; | |
f67539c2 TL |
134 | detail::dag_sp_dispatch1(g, s, get_param(params, vertex_distance), |
135 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), | |
136 | get_param(params, vertex_color), | |
137 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), | |
138 | choose_param( | |
139 | get_param(params, graph_visitor), make_dijkstra_visitor(null_vis)), | |
140 | params); | |
141 | } | |
142 | ||
7c673cae FG |
143 | } // namespace boost |
144 | ||
145 | #endif // BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP |