]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
7c673cae | 22 | /* |
f67539c2 | 23 | Example of using a visitor with the depth first search |
7c673cae FG |
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 | | | |
f67539c2 TL |
34 | San Diego |
35 | ||
7c673cae | 36 | |
f67539c2 | 37 | The visitor has three main functions: |
7c673cae | 38 | |
7c673cae FG |
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 | |
f67539c2 | 49 | u have already been visited. |
7c673cae FG |
50 | |
51 | */ | |
52 | ||
53 | using namespace std; | |
54 | using namespace boost; | |
55 | ||
f67539c2 | 56 | struct city_arrival : public base_visitor< city_arrival > |
7c673cae | 57 | { |
f67539c2 TL |
58 | city_arrival(string* n) : names(n) {} |
59 | typedef on_discover_vertex event_filter; | |
60 | template < class Vertex, class Graph > | |
61 | inline void operator()(Vertex u, Graph&) | |
62 | { | |
63 | cout << endl | |
64 | << "arriving at " << names[u] << endl | |
65 | << " neighboring cities are: "; | |
66 | } | |
67 | string* names; | |
7c673cae FG |
68 | }; |
69 | ||
f67539c2 | 70 | struct neighbor_cities : public base_visitor< neighbor_cities > |
7c673cae | 71 | { |
f67539c2 TL |
72 | neighbor_cities(string* n) : names(n) {} |
73 | typedef on_examine_edge event_filter; | |
74 | template < class Edge, class Graph > | |
75 | inline void operator()(Edge e, Graph& g) | |
76 | { | |
77 | cout << names[target(e, g)] << ", "; | |
78 | } | |
79 | string* names; | |
7c673cae FG |
80 | }; |
81 | ||
f67539c2 | 82 | struct finish_city : public base_visitor< finish_city > |
7c673cae | 83 | { |
f67539c2 TL |
84 | finish_city(string* n) : names(n) {} |
85 | typedef on_finish_vertex event_filter; | |
86 | template < class Vertex, class Graph > | |
87 | inline void operator()(Vertex u, Graph&) | |
88 | { | |
89 | cout << endl << "finished with " << names[u] << endl; | |
90 | } | |
91 | string* names; | |
7c673cae FG |
92 | }; |
93 | ||
f67539c2 | 94 | int main(int, char*[]) |
7c673cae FG |
95 | { |
96 | ||
f67539c2 TL |
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; | |
7c673cae | 124 | #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
f67539c2 TL |
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); | |
7c673cae | 129 | #else |
f67539c2 | 130 | Graph G(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N); |
7c673cae FG |
131 | #endif |
132 | ||
f67539c2 TL |
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; | |
7c673cae | 148 | } |