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 | #include <boost/config.hpp> |
11 | #include <boost/concept_archetype.hpp> |
12 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
13 | #include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp> |
14 | #include <boost/graph/graph_archetypes.hpp> |
15 | |
16 | typedef boost::default_constructible_archetype< |
17 | boost::sgi_assignable_archetype<> > |
18 | dist_value; |
19 | |
20 | // So generate_infinity works... |
21 | namespace std |
22 | { |
23 | template <> class numeric_limits< dist_value > |
24 | { |
25 | public: |
26 | static dist_value max BOOST_PREVENT_MACRO_SUBSTITUTION() |
27 | { |
28 | return boost::static_object< dist_value >::get(); |
29 | } |
30 | }; |
31 | } |
32 | |
33 | dist_value abs(const dist_value& x) { return x; } |
34 | std::size_t abs(std::size_t x) { return x; } |
35 | |
36 | int main() |
37 | { |
38 | using namespace boost; |
39 | typedef default_constructible_archetype< |
40 | sgi_assignable_archetype< equality_comparable_archetype<> > > |
41 | vertex_t; |
42 | { |
43 | typedef incidence_graph_archetype< vertex_t, directed_tag, |
44 | allow_parallel_edge_tag > |
45 | IncidenceGraph; |
46 | typedef vertex_list_graph_archetype< vertex_t, directed_tag, |
47 | allow_parallel_edge_tag, IncidenceGraph > |
48 | graph_t; |
49 | graph_t& g = static_object< graph_t >::get(); |
50 | vertex_t s; |
51 | typedef graph_traits< graph_t >::edge_descriptor edge_t; |
52 | readable_property_map_archetype< edge_t, std::size_t > weight; |
53 | readable_property_map_archetype< vertex_t, int > index; |
54 | read_write_property_map_archetype< vertex_t, std::size_t > distance; |
55 | dijkstra_shortest_paths(g, s, |
56 | params: vertex_index_map(p: index).weight_map(p: weight).distance_map(p: distance)); |
57 | |
58 | dijkstra_shortest_paths_no_color_map(graph: g, start_vertex: s, |
59 | params: vertex_index_map(p: index).weight_map(p: weight).distance_map(p: distance)); |
60 | } |
61 | { |
62 | typedef incidence_graph_archetype< vertex_t, directed_tag, |
63 | allow_parallel_edge_tag > |
64 | IncidenceGraph; |
65 | typedef vertex_list_graph_archetype< vertex_t, directed_tag, |
66 | allow_parallel_edge_tag, IncidenceGraph > |
67 | Graph; |
68 | vertex_t s; |
69 | typedef graph_traits< Graph >::edge_descriptor edge_t; |
70 | readable_property_map_archetype< edge_t, std::size_t > weight; |
71 | typedef property_graph_archetype< Graph, vertex_index_t, std::size_t > |
72 | graph_t; |
73 | graph_t& g = static_object< graph_t >::get(); |
74 | read_write_property_map_archetype< vertex_t, vertex_t > pred; |
75 | dijkstra_shortest_paths(g, s, params: predecessor_map(p: pred).weight_map(p: weight)); |
76 | |
77 | dijkstra_shortest_paths_no_color_map( |
78 | graph: g, start_vertex: s, params: predecessor_map(p: pred).weight_map(p: weight)); |
79 | } |
80 | { |
81 | typedef incidence_graph_archetype< vertex_t, directed_tag, |
82 | allow_parallel_edge_tag > |
83 | IncidenceGraph; |
84 | typedef vertex_list_graph_archetype< vertex_t, directed_tag, |
85 | allow_parallel_edge_tag, IncidenceGraph > |
86 | Graph; |
87 | vertex_t s; |
88 | typedef property_graph_archetype< Graph, edge_weight_t, std::size_t > |
89 | graph_t; |
90 | graph_t& g = static_object< graph_t >::get(); |
91 | read_write_property_map_archetype< vertex_t, vertex_t > pred; |
92 | readable_property_map_archetype< vertex_t, int > index; |
93 | dijkstra_shortest_paths( |
94 | g, s, params: predecessor_map(p: pred).vertex_index_map(p: index)); |
95 | |
96 | dijkstra_shortest_paths_no_color_map( |
97 | graph: g, start_vertex: s, params: predecessor_map(p: pred).vertex_index_map(p: index)); |
98 | } |
99 | { |
100 | typedef incidence_graph_archetype< vertex_t, directed_tag, |
101 | allow_parallel_edge_tag > |
102 | IncidenceGraph; |
103 | typedef vertex_list_graph_archetype< vertex_t, directed_tag, |
104 | allow_parallel_edge_tag, IncidenceGraph > |
105 | graph_t; |
106 | graph_t& g = static_object< graph_t >::get(); |
107 | vertex_t s; |
108 | typedef graph_traits< graph_t >::edge_descriptor edge_t; |
109 | readable_property_map_archetype< edge_t, dist_value > weight; |
110 | readable_property_map_archetype< vertex_t, int > index; |
111 | read_write_property_map_archetype< vertex_t, color_value_archetype > |
112 | color; |
113 | read_write_property_map_archetype< vertex_t, dist_value > distance; |
114 | typedef binary_function_archetype< dist_value, dist_value, dist_value > |
115 | Combine; |
116 | Combine combine = static_object< Combine >::get(); |
117 | typedef binary_predicate_archetype< dist_value, dist_value > Compare; |
118 | Compare compare = static_object< Compare >::get(); |
119 | dijkstra_visitor<> vis; |
120 | |
121 | dijkstra_shortest_paths(g, s, |
122 | params: color_map(p: color) |
123 | .vertex_index_map(p: index) |
124 | .weight_map(p: weight) |
125 | .distance_map(p: distance) |
126 | .distance_combine(p: combine) |
127 | .distance_compare(p: compare) |
128 | .visitor(p: vis)); |
129 | |
130 | dijkstra_shortest_paths_no_color_map(graph: g, start_vertex: s, |
131 | params: vertex_index_map(p: index) |
132 | .weight_map(p: weight) |
133 | .distance_map(p: distance) |
134 | .distance_combine(p: combine) |
135 | .distance_compare(p: compare) |
136 | .visitor(p: vis)); |
137 | } |
138 | return 0; |
139 | } |
140 | |