1 //=======================================================================
2 // Copyright 2002 Indiana University.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
10 #ifndef BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP
11 #define BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP
13 #include <boost/graph/topological_sort.hpp>
14 #include <boost/graph/dijkstra_shortest_paths.hpp>
16 // single-source shortest paths for a Directed Acyclic Graph (DAG)
20 // Initalize distances and call depth first search
21 template <class VertexListGraph
, class DijkstraVisitor
,
22 class DistanceMap
, class WeightMap
, class ColorMap
,
24 class Compare
, class Combine
,
25 class DistInf
, class DistZero
>
28 (const VertexListGraph
& g
,
29 typename graph_traits
<VertexListGraph
>::vertex_descriptor s
,
30 DistanceMap distance
, WeightMap weight
, ColorMap color
,
32 DijkstraVisitor vis
, Compare compare
, Combine combine
,
33 DistInf inf
, DistZero zero
)
35 typedef typename graph_traits
<VertexListGraph
>::vertex_descriptor Vertex
;
36 std::vector
<Vertex
> rev_topo_order
;
37 rev_topo_order
.reserve(num_vertices(g
));
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
);
48 typename graph_traits
<VertexListGraph
>::vertex_iterator ui
, ui_end
;
49 for (tie(ui
, ui_end
) = vertices(g
); ui
!= ui_end
; ++ui
) {
50 put(distance
, *ui
, inf
);
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
) {
59 vis
.examine_vertex(u
, g
);
60 typename graph_traits
<VertexListGraph
>::out_edge_iterator e
, e_end
;
61 for (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
,
66 vis
.edge_relaxed(*e
, g
);
68 vis
.edge_not_relaxed(*e
, g
);
70 vis
.finish_vertex(u
, g
);
76 // Defaults are the same as Dijkstra's algorithm
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
>
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
)
89 typedef typename property_traits
<DistanceMap
>::value_type D
;
90 dummy_property_map p_map
;
92 (g
, s
, distance
, weight
, color
,
93 choose_param(get_param(params
, vertex_predecessor
), p_map
),
95 choose_param(get_param(params
, distance_compare_t()), std::less
<D
>()),
96 choose_param(get_param(params
, distance_combine_t()), closed_plus
<D
>()),
97 choose_param(get_param(params
, distance_inf_t()),
98 (std::numeric_limits
<D
>::max
)()),
99 choose_param(get_param(params
, distance_zero_t()),
103 // Handle DistanceMap and ColorMap defaults
104 template <class VertexListGraph
, class DijkstraVisitor
,
105 class DistanceMap
, class WeightMap
, class ColorMap
,
106 class IndexMap
, class Params
>
109 (const VertexListGraph
& g
,
110 typename graph_traits
<VertexListGraph
>::vertex_descriptor s
,
111 DistanceMap distance
, WeightMap weight
, ColorMap color
, IndexMap id
,
112 DijkstraVisitor vis
, const Params
& params
)
114 typedef typename property_traits
<WeightMap
>::value_type T
;
115 typename
std::vector
<T
>::size_type n
;
116 n
= is_default_param(distance
) ? num_vertices(g
) : 1;
117 std::vector
<T
> distance_map(n
);
118 n
= is_default_param(color
) ? num_vertices(g
) : 1;
119 std::vector
<default_color_type
> color_map(n
);
123 choose_param(distance
,
124 make_iterator_property_map(distance_map
.begin(), id
,
128 make_iterator_property_map(color_map
.begin(), id
,
133 } // namespace detail
135 template <class VertexListGraph
, class Param
, class Tag
, class Rest
>
138 (const VertexListGraph
& g
,
139 typename graph_traits
<VertexListGraph
>::vertex_descriptor s
,
140 const bgl_named_params
<Param
,Tag
,Rest
>& params
)
142 // assert that the graph is directed...
143 null_visitor null_vis
;
144 detail::dag_sp_dispatch1
146 get_param(params
, vertex_distance
),
147 choose_const_pmap(get_param(params
, edge_weight
), g
, edge_weight
),
148 get_param(params
, vertex_color
),
149 choose_const_pmap(get_param(params
, vertex_index
), g
, vertex_index
),
150 choose_param(get_param(params
, graph_visitor
),
151 make_dijkstra_visitor(null_vis
)),
157 #endif // BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP