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