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 Example of using a visitor with the depth first search
24 and breadth first search algorithm
25
26 Sacramento ---- Reno ---- Salt Lake City
27 |
28 San Francisco
29 |
30 San Jose ---- Fresno
31 |
32 Los Angeles ---- Las Vegas ---- Phoenix
33 |
34 San Diego
35
36
37 The visitor has three main functions:
38
39 discover_vertex(u,g) is invoked when the algorithm first arrives at the
40 vertex u. This will happen in the depth first or breadth first
41 order depending on which algorithm you use.
42
43 examine_edge(e,g) is invoked when the algorithm first checks an edge to see
44 whether it has already been there. Whether using BFS or DFS, all
45 the edges of vertex u are examined immediately after the call to
46 visit(u).
47
48 finish_vertex(u,g) is called when after all the vertices reachable from vertex
49 u have already been visited.
50
51 */
52
53 using namespace std;
54 using namespace boost;
55
56 struct city_arrival : public base_visitor< city_arrival >
57 {
city_arrivalcity_arrival58 city_arrival(string* n) : names(n) {}
59 typedef on_discover_vertex event_filter;
60 template < class Vertex, class Graph >
operator ()city_arrival61 inline void operator()(Vertex u, Graph&)
62 {
63 cout << endl
64 << "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 {
77 cout << names[target(e, g)] << ", ";
78 }
79 string* names;
80 };
81
82 struct finish_city : public base_visitor< finish_city >
83 {
finish_cityfinish_city84 finish_city(string* n) : names(n) {}
85 typedef on_finish_vertex event_filter;
86 template < class Vertex, class Graph >
operator ()finish_city87 inline void operator()(Vertex u, Graph&)
88 {
89 cout << endl << "finished with " << names[u] << endl;
90 }
91 string* names;
92 };
93
main(int,char * [])94 int main(int, char*[])
95 {
96
97 enum
98 {
99 SanJose,
100 SanFran,
101 LA,
102 SanDiego,
103 Fresno,
104 LasVegas,
105 Reno,
106 Sacramento,
107 SaltLake,
108 Phoenix,
109 N
110 };
111
112 string names[]
113 = { "San Jose", "San Francisco", "Los Angeles", "San Diego", "Fresno",
114 "Las Vegas", "Reno", "Sacramento", "Salt Lake City", "Phoenix" };
115
116 typedef std::pair< int, int > E;
117 E edge_array[]
118 = { E(Sacramento, Reno), E(Sacramento, SanFran), E(Reno, SaltLake),
119 E(SanFran, SanJose), E(SanJose, Fresno), E(SanJose, LA),
120 E(LA, LasVegas), E(LA, SanDiego), E(LasVegas, Phoenix) };
121
122 /* Create the graph type we want. */
123 typedef adjacency_list< vecS, vecS, undirectedS > Graph;
124 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
125 // VC++ has trouble with the edge iterator constructor
126 Graph G(N);
127 for (std::size_t j = 0; j < sizeof(edge_array) / sizeof(E); ++j)
128 add_edge(edge_array[j].first, edge_array[j].second, G);
129 #else
130 Graph G(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
131 #endif
132
133 cout << "*** Depth First ***" << endl;
134 depth_first_search(G,
135 visitor(make_dfs_visitor(boost::make_list(
136 city_arrival(names), neighbor_cities(names), finish_city(names)))));
137 cout << endl;
138
139 /* Get the source vertex */
140 boost::graph_traits< Graph >::vertex_descriptor s = vertex(SanJose, G);
141
142 cout << "*** Breadth First ***" << endl;
143 breadth_first_search(G, s,
144 visitor(make_bfs_visitor(boost::make_list(
145 city_arrival(names), neighbor_cities(names), finish_city(names)))));
146
147 return 0;
148 }
149