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:
BOOST_PREVENT_MACRO_SUBSTITUTION()26 static dist_value max BOOST_PREVENT_MACRO_SUBSTITUTION()
27 {
28 return boost::static_object< dist_value >::get();
29 }
30 };
31 }
32
abs(const dist_value & x)33 dist_value abs(const dist_value& x) { return x; }
abs(std::size_t x)34 std::size_t abs(std::size_t x) { return x; }
35
main()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 vertex_index_map(index).weight_map(weight).distance_map(distance));
57
58 dijkstra_shortest_paths_no_color_map(g, s,
59 vertex_index_map(index).weight_map(weight).distance_map(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, predecessor_map(pred).weight_map(weight));
76
77 dijkstra_shortest_paths_no_color_map(
78 g, s, predecessor_map(pred).weight_map(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, predecessor_map(pred).vertex_index_map(index));
95
96 dijkstra_shortest_paths_no_color_map(
97 g, s, predecessor_map(pred).vertex_index_map(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 color_map(color)
123 .vertex_index_map(index)
124 .weight_map(weight)
125 .distance_map(distance)
126 .distance_combine(combine)
127 .distance_compare(compare)
128 .visitor(vis));
129
130 dijkstra_shortest_paths_no_color_map(g, s,
131 vertex_index_map(index)
132 .weight_map(weight)
133 .distance_map(distance)
134 .distance_combine(combine)
135 .distance_compare(compare)
136 .visitor(vis));
137 }
138 return 0;
139 }
140