1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
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 #include <boost/config.hpp>
10 #include <iostream>
11 #include <iterator>
12 #include <vector>
13 #include <list>
14 // Use boost::queue instead of std::queue because std::queue doesn't
15 // model Buffer; it has to top() function. -Jeremy
16 #include <boost/pending/queue.hpp>
17
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/graph/visitors.hpp>
20 #include <boost/graph/breadth_first_search.hpp>
21 #include <boost/graph/dijkstra_shortest_paths.hpp>
22 #include <boost/graph/graph_utility.hpp>
23
24 using namespace std;
25 using namespace boost;
26 /*
27 This example does a best-first-search (using dijkstra's) and
28 simultaneously makes a copy of the graph (assuming the graph is
29 connected).
30
31 Example Graph: (p. 90 "Data Structures and Network Algorithms", Tarjan)
32
33 g
34 3+ +2
35 / 1 \
36 e+----f
37 |+0 5++
38 | \ / |
39 10| d |12
40 |8++\7|
41 +/ | +|
42 b 4| c
43 \ | +
44 6+|/3
45 a
46
47 Sample Output:
48 a --> c d
49 b --> a d
50 c --> f
51 d --> c e f
52 e --> b g
53 f --> e g
54 g -->
55 Starting graph:
56 a(32767); c d
57 c(32767); f
58 d(32767); c e f
59 f(32767); e g
60 e(32767); b g
61 g(32767);
62 b(32767); a d
63 Result:
64 a(0); d c
65 d(4); f e c
66 c(3); f
67 f(9); g e
68 e(4); g b
69 g(7);
70 b(14); d a
71
72 */
73
74 typedef property<vertex_color_t, default_color_type,
75 property<vertex_distance_t,int> > VProperty;
76 typedef int weight_t;
77 typedef property<edge_weight_t,weight_t> EProperty;
78
79 typedef adjacency_list<vecS, vecS, directedS, VProperty, EProperty > Graph;
80
81
82
83 template <class Tag>
84 struct endl_printer
85 : public boost::base_visitor< endl_printer<Tag> >
86 {
87 typedef Tag event_filter;
endl_printerendl_printer88 endl_printer(std::ostream& os) : m_os(os) { }
89 template <class T, class Graph>
operator ()endl_printer90 void operator()(T, Graph&) { m_os << std::endl; }
91 std::ostream& m_os;
92 };
93 template <class Tag>
print_endl(std::ostream & os,Tag)94 endl_printer<Tag> print_endl(std::ostream& os, Tag) {
95 return endl_printer<Tag>(os);
96 }
97
98 template <class PA, class Tag>
99 struct edge_printer
100 : public boost::base_visitor< edge_printer<PA, Tag> >
101 {
102 typedef Tag event_filter;
103
edge_printeredge_printer104 edge_printer(PA pa, std::ostream& os) : m_pa(pa), m_os(os) { }
105
106 template <class T, class Graph>
operator ()edge_printer107 void operator()(T x, Graph& g) {
108 m_os << "(" << get(m_pa, source(x, g)) << ","
109 << get(m_pa, target(x, g)) << ") ";
110 }
111 PA m_pa;
112 std::ostream& m_os;
113 };
114 template <class PA, class Tag>
115 edge_printer<PA, Tag>
print_edge(PA pa,std::ostream & os,Tag)116 print_edge(PA pa, std::ostream& os, Tag) {
117 return edge_printer<PA, Tag>(pa, os);
118 }
119
120
121 template <class NewGraph, class Tag>
122 struct graph_copier
123 : public boost::base_visitor<graph_copier<NewGraph, Tag> >
124 {
125 typedef Tag event_filter;
126
graph_copiergraph_copier127 graph_copier(NewGraph& graph) : new_g(graph) { }
128
129 template <class Edge, class Graph>
operator ()graph_copier130 void operator()(Edge e, Graph& g) {
131 add_edge(source(e, g), target(e, g), new_g);
132 }
133 private:
134 NewGraph& new_g;
135 };
136 template <class NewGraph, class Tag>
137 inline graph_copier<NewGraph, Tag>
copy_graph(NewGraph & g,Tag)138 copy_graph(NewGraph& g, Tag) {
139 return graph_copier<NewGraph, Tag>(g);
140 }
141
142 template <class Graph, class Name>
print(Graph & G,Name name)143 void print(Graph& G, Name name)
144 {
145 typename boost::graph_traits<Graph>::vertex_iterator ui, uiend;
146 for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui) {
147 cout << name[*ui] << " --> ";
148 typename boost::graph_traits<Graph>::adjacency_iterator vi, viend;
149 for(boost::tie(vi, viend) = adjacent_vertices(*ui, G); vi != viend; ++vi)
150 cout << name[*vi] << " ";
151 cout << endl;
152 }
153
154 }
155
156
157 int
main(int,char * [])158 main(int , char* [])
159 {
160 // Name and ID numbers for the vertices
161 char name[] = "abcdefg";
162 enum { a, b, c, d, e, f, g, N};
163
164 Graph G(N);
165 boost::property_map<Graph, vertex_index_t>::type
166 vertex_id = get(vertex_index, G);
167
168 std::vector<weight_t> distance(N, (numeric_limits<weight_t>::max)());
169 typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
170 std::vector<Vertex> parent(N);
171
172 typedef std::pair<int,int> E;
173
174 E edges[] = { E(a,c), E(a,d),
175 E(b,a), E(b,d),
176 E(c,f),
177 E(d,c), E(d,e), E(d,f),
178 E(e,b), E(e,g),
179 E(f,e), E(f,g) };
180
181 int weight[] = { 3, 4,
182 6, 8,
183 12,
184 7, 0, 5,
185 10, 3,
186 1, 2 };
187
188 for (int i = 0; i < 12; ++i)
189 add_edge(edges[i].first, edges[i].second, weight[i], G);
190
191 print(G, name);
192
193 adjacency_list<listS, vecS, directedS,
194 property<vertex_color_t, default_color_type> > G_copy(N);
195
196 cout << "Starting graph:" << endl;
197
198 std::ostream_iterator<int> cout_int(std::cout, " ");
199 std::ostream_iterator<char> cout_char(std::cout, " ");
200
201 boost::queue<Vertex> Q;
202 boost::breadth_first_search
203 (G, vertex(a, G), Q,
204 make_bfs_visitor(
205 boost::make_list
206 (write_property(make_iterator_property_map(name, vertex_id,
207 name[0]),
208 cout_char, on_examine_vertex()),
209 write_property(make_iterator_property_map(distance.begin(),
210 vertex_id,
211 distance[0]),
212 cout_int, on_examine_vertex()),
213 print_edge(make_iterator_property_map(name, vertex_id,
214 name[0]),
215 std::cout, on_examine_edge()),
216 print_endl(std::cout, on_finish_vertex()))),
217 get(vertex_color, G));
218
219 std::cout << "about to call dijkstra's" << std::endl;
220
221 parent[vertex(a, G)] = vertex(a, G);
222 boost::dijkstra_shortest_paths
223 (G, vertex(a, G),
224 distance_map(make_iterator_property_map(distance.begin(), vertex_id,
225 distance[0])).
226 predecessor_map(make_iterator_property_map(parent.begin(), vertex_id,
227 parent[0])).
228 visitor(make_dijkstra_visitor(copy_graph(G_copy, on_examine_edge()))));
229
230 cout << endl;
231 cout << "Result:" << endl;
232 boost::breadth_first_search
233 (G, vertex(a, G),
234 visitor(make_bfs_visitor(
235 boost::make_list
236 (write_property(make_iterator_property_map(name, vertex_id,
237 name[0]),
238 cout_char, on_examine_vertex()),
239 write_property(make_iterator_property_map(distance.begin(),
240 vertex_id,
241 distance[0]),
242 cout_int, on_examine_vertex()),
243 print_edge(make_iterator_property_map(name, vertex_id,
244 name[0]),
245 std::cout, on_examine_edge()),
246 print_endl(std::cout, on_finish_vertex())))));
247
248 return 0;
249 }
250