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 > >
76 VProperty;
77 typedef int weight_t;
78 typedef property< edge_weight_t, weight_t > EProperty;
79
80 typedef adjacency_list< vecS, vecS, directedS, VProperty, EProperty > Graph;
81
82 template < class Tag >
83 struct endl_printer : public boost::base_visitor< endl_printer< Tag > >
84 {
85 typedef Tag event_filter;
endl_printerendl_printer86 endl_printer(std::ostream& os) : m_os(os) {}
operator ()endl_printer87 template < class T, class Graph > void operator()(T, Graph&)
88 {
89 m_os << std::endl;
90 }
91 std::ostream& m_os;
92 };
print_endl(std::ostream & os,Tag)93 template < class Tag > endl_printer< Tag > print_endl(std::ostream& os, Tag)
94 {
95 return endl_printer< Tag >(os);
96 }
97
98 template < class PA, class Tag >
99 struct edge_printer : public boost::base_visitor< edge_printer< PA, Tag > >
100 {
101 typedef Tag event_filter;
102
edge_printeredge_printer103 edge_printer(PA pa, std::ostream& os) : m_pa(pa), m_os(os) {}
104
operator ()edge_printer105 template < class T, class Graph > void operator()(T x, Graph& g)
106 {
107 m_os << "(" << get(m_pa, source(x, g)) << "," << get(m_pa, target(x, g))
108 << ") ";
109 }
110 PA m_pa;
111 std::ostream& m_os;
112 };
113 template < class PA, class Tag >
print_edge(PA pa,std::ostream & os,Tag)114 edge_printer< PA, Tag > print_edge(PA pa, std::ostream& os, Tag)
115 {
116 return edge_printer< PA, Tag >(pa, os);
117 }
118
119 template < class NewGraph, class Tag >
120 struct graph_copier
121 : public boost::base_visitor< graph_copier< NewGraph, Tag > >
122 {
123 typedef Tag event_filter;
124
graph_copiergraph_copier125 graph_copier(NewGraph& graph) : new_g(graph) {}
126
operator ()graph_copier127 template < class Edge, class Graph > void operator()(Edge e, Graph& g)
128 {
129 add_edge(source(e, g), target(e, g), new_g);
130 }
131
132 private:
133 NewGraph& new_g;
134 };
135 template < class NewGraph, class Tag >
copy_graph(NewGraph & g,Tag)136 inline graph_copier< NewGraph, Tag > copy_graph(NewGraph& g, Tag)
137 {
138 return graph_copier< NewGraph, Tag >(g);
139 }
140
print(Graph & G,Name name)141 template < class Graph, class Name > void print(Graph& G, Name name)
142 {
143 typename boost::graph_traits< Graph >::vertex_iterator ui, uiend;
144 for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui)
145 {
146 cout << name[*ui] << " --> ";
147 typename boost::graph_traits< Graph >::adjacency_iterator vi, viend;
148 for (boost::tie(vi, viend) = adjacent_vertices(*ui, G); vi != viend;
149 ++vi)
150 cout << name[*vi] << " ";
151 cout << endl;
152 }
153 }
154
main(int,char * [])155 int main(int, char*[])
156 {
157 // Name and ID numbers for the vertices
158 char name[] = "abcdefg";
159 enum
160 {
161 a,
162 b,
163 c,
164 d,
165 e,
166 f,
167 g,
168 N
169 };
170
171 Graph G(N);
172 boost::property_map< Graph, vertex_index_t >::type vertex_id
173 = get(vertex_index, G);
174
175 std::vector< weight_t > distance(N, (numeric_limits< weight_t >::max)());
176 typedef boost::graph_traits< Graph >::vertex_descriptor Vertex;
177 std::vector< Vertex > parent(N);
178
179 typedef std::pair< int, int > E;
180
181 E edges[] = { E(a, c), E(a, d), E(b, a), E(b, d), E(c, f), E(d, c), E(d, e),
182 E(d, f), E(e, b), E(e, g), E(f, e), E(f, g) };
183
184 int weight[] = { 3, 4, 6, 8, 12, 7, 0, 5, 10, 3, 1, 2 };
185
186 for (int i = 0; i < 12; ++i)
187 add_edge(edges[i].first, edges[i].second, weight[i], G);
188
189 print(G, name);
190
191 adjacency_list< listS, vecS, directedS,
192 property< vertex_color_t, default_color_type > >
193 G_copy(N);
194
195 cout << "Starting graph:" << endl;
196
197 std::ostream_iterator< int > cout_int(std::cout, " ");
198 std::ostream_iterator< char > cout_char(std::cout, " ");
199
200 boost::queue< Vertex > Q;
201 boost::breadth_first_search(G, vertex(a, G), Q,
202 make_bfs_visitor(boost::make_list(
203 write_property(make_iterator_property_map(name, vertex_id, name[0]),
204 cout_char, on_examine_vertex()),
205 write_property(make_iterator_property_map(
206 distance.begin(), vertex_id, distance[0]),
207 cout_int, on_examine_vertex()),
208 print_edge(make_iterator_property_map(name, vertex_id, name[0]),
209 std::cout, on_examine_edge()),
210 print_endl(std::cout, on_finish_vertex()))),
211 get(vertex_color, G));
212
213 std::cout << "about to call dijkstra's" << std::endl;
214
215 parent[vertex(a, G)] = vertex(a, G);
216 boost::dijkstra_shortest_paths(G, vertex(a, G),
217 distance_map(make_iterator_property_map(
218 distance.begin(), vertex_id, distance[0]))
219 .predecessor_map(make_iterator_property_map(
220 parent.begin(), vertex_id, parent[0]))
221 .visitor(
222 make_dijkstra_visitor(copy_graph(G_copy, on_examine_edge()))));
223
224 cout << endl;
225 cout << "Result:" << endl;
226 boost::breadth_first_search(G, vertex(a, G),
227 visitor(make_bfs_visitor(boost::make_list(
228 write_property(make_iterator_property_map(name, vertex_id, name[0]),
229 cout_char, on_examine_vertex()),
230 write_property(make_iterator_property_map(
231 distance.begin(), vertex_id, distance[0]),
232 cout_int, on_examine_vertex()),
233 print_edge(make_iterator_property_map(name, vertex_id, name[0]),
234 std::cout, on_examine_edge()),
235 print_endl(std::cout, on_finish_vertex())))));
236
237 return 0;
238 }
239