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
16typedef boost::default_constructible_archetype<
17 boost::sgi_assignable_archetype<> >
18 dist_value;
19
20// So generate_infinity works...
21namespace std
22{
23template <> class numeric_limits< dist_value >
24{
25public:
26 static dist_value max BOOST_PREVENT_MACRO_SUBSTITUTION()
27 {
28 return boost::static_object< dist_value >::get();
29 }
30};
31}
32
33dist_value abs(const dist_value& x) { return x; }
34std::size_t abs(std::size_t x) { return x; }
35
36int 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

source code of boost/libs/graph/test/dijkstra_cc.cpp