1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 //
11
12 #include <boost/config.hpp>
13 #include <iostream>
14 #include <vector>
15 #include <string>
16 #include <boost/graph/adjacency_list.hpp>
17 #include <boost/graph/depth_first_search.hpp>
18 #include <boost/graph/breadth_first_search.hpp>
19 #include <boost/property_map/property_map.hpp>
20 #include <boost/graph/graph_utility.hpp> // for boost::make_list
21
22
23 /*
24 Example of using a visitor with the depth first search
25 and breadth first search algorithm
26
27 Sacramento ---- Reno ---- Salt Lake City
28 |
29 San Francisco
30 |
31 San Jose ---- Fresno
32 |
33 Los Angeles ---- Las Vegas ---- Phoenix
34 |
35 San Diego
36
37
38 The visitor has three main functions:
39
40 discover_vertex(u,g) is invoked when the algorithm first arrives at the
41 vertex u. This will happen in the depth first or breadth first
42 order depending on which algorithm you use.
43
44 examine_edge(e,g) is invoked when the algorithm first checks an edge to see
45 whether it has already been there. Whether using BFS or DFS, all
46 the edges of vertex u are examined immediately after the call to
47 visit(u).
48
49 finish_vertex(u,g) is called when after all the vertices reachable from vertex
50 u have already been visited.
51
52 */
53
54 using namespace std;
55 using namespace boost;
56
57
58 struct city_arrival : public base_visitor<city_arrival>
59 {
city_arrivalcity_arrival60 city_arrival(string* n) : names(n) { }
61 typedef on_discover_vertex event_filter;
62 template <class Vertex, class Graph>
operator ()city_arrival63 inline void operator()(Vertex u, Graph&) {
64 cout << endl << "arriving at " << names[u] << endl
65 << " neighboring cities are: ";
66 }
67 string* names;
68 };
69
70 struct neighbor_cities : public base_visitor<neighbor_cities>
71 {
neighbor_citiesneighbor_cities72 neighbor_cities(string* n) : names(n) { }
73 typedef on_examine_edge event_filter;
74 template <class Edge, class Graph>
operator ()neighbor_cities75 inline void operator()(Edge e, Graph& g) {
76 cout << names[ target(e, g) ] << ", ";
77 }
78 string* names;
79 };
80
81 struct finish_city : public base_visitor<finish_city>
82 {
finish_cityfinish_city83 finish_city(string* n) : names(n) { }
84 typedef on_finish_vertex event_filter;
85 template <class Vertex, class Graph>
operator ()finish_city86 inline void operator()(Vertex u, Graph&) {
87 cout << endl << "finished with " << names[u] << endl;
88 }
89 string* names;
90 };
91
main(int,char * [])92 int main(int, char*[])
93 {
94
95 enum { SanJose, SanFran, LA, SanDiego, Fresno, LasVegas, Reno,
96 Sacramento, SaltLake, Phoenix, N };
97
98 string names[] = { "San Jose", "San Francisco", "Los Angeles", "San Diego",
99 "Fresno", "Las Vegas", "Reno", "Sacramento",
100 "Salt Lake City", "Phoenix" };
101
102 typedef std::pair<int,int> E;
103 E edge_array[] = { E(Sacramento, Reno), E(Sacramento, SanFran),
104 E(Reno, SaltLake),
105 E(SanFran, SanJose),
106 E(SanJose, Fresno), E(SanJose, LA),
107 E(LA, LasVegas), E(LA, SanDiego),
108 E(LasVegas, Phoenix) };
109
110 /* Create the graph type we want. */
111 typedef adjacency_list<vecS, vecS, undirectedS> Graph;
112 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
113 // VC++ has trouble with the edge iterator constructor
114 Graph G(N);
115 for (std::size_t j = 0; j < sizeof(edge_array)/sizeof(E); ++j)
116 add_edge(edge_array[j].first, edge_array[j].second, G);
117 #else
118 Graph G(edge_array, edge_array + sizeof(edge_array)/sizeof(E), N);
119 #endif
120
121 cout << "*** Depth First ***" << endl;
122 depth_first_search
123 (G,
124 visitor(make_dfs_visitor(boost::make_list(city_arrival(names),
125 neighbor_cities(names),
126 finish_city(names)))));
127 cout << endl;
128
129 /* Get the source vertex */
130 boost::graph_traits<Graph>::vertex_descriptor
131 s = vertex(SanJose,G);
132
133 cout << "*** Breadth First ***" << endl;
134 breadth_first_search
135 (G, s, visitor(make_bfs_visitor(boost::make_list(city_arrival(names),
136 neighbor_cities(names),
137 finish_city(names)))));
138
139 return 0;
140 }
141