]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | //======================================================================= |
f67539c2 | 2 | // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, |
7c673cae FG |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See | |
5 | // accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | //======================================================================= | |
92f5a8d4 | 8 | |
92f5a8d4 TL |
9 | /* |
10 | IMPORTANT: | |
11 | ~~~~~~~~~~ | |
12 | ||
f67539c2 TL |
13 | This example appears to be broken and crashes at runtime, see |
14 | https://github.com/boostorg/graph/issues/148 | |
92f5a8d4 TL |
15 | |
16 | */ | |
17 | ||
7c673cae FG |
18 | #include <boost/config.hpp> |
19 | #include <iostream> | |
20 | #include <fstream> | |
21 | #include <string> | |
22 | #include <boost/tuple/tuple.hpp> | |
23 | #include <boost/graph/adjacency_list.hpp> | |
24 | #include <boost/graph/visitors.hpp> | |
25 | #include <boost/graph/breadth_first_search.hpp> | |
26 | #include <map> | |
27 | #include <boost/graph/adj_list_serialize.hpp> | |
28 | #include <boost/archive/text_iarchive.hpp> | |
29 | #include <boost/serialization/string.hpp> | |
30 | ||
f67539c2 TL |
31 | struct vertex_properties |
32 | { | |
33 | std::string name; | |
7c673cae | 34 | |
f67539c2 TL |
35 | template < class Archive > |
36 | void serialize(Archive& ar, const unsigned int version) | |
37 | { | |
38 | ar& name; | |
39 | } | |
7c673cae FG |
40 | }; |
41 | ||
f67539c2 TL |
42 | struct edge_properties |
43 | { | |
44 | std::string name; | |
7c673cae | 45 | |
f67539c2 TL |
46 | template < class Archive > |
47 | void serialize(Archive& ar, const unsigned int version) | |
48 | { | |
49 | ar& name; | |
50 | } | |
7c673cae FG |
51 | }; |
52 | ||
53 | using namespace boost; | |
54 | ||
f67539c2 TL |
55 | typedef adjacency_list< vecS, vecS, undirectedS, vertex_properties, |
56 | edge_properties > | |
57 | Graph; | |
58 | typedef graph_traits< Graph >::vertex_descriptor Vertex; | |
59 | typedef graph_traits< Graph >::edge_descriptor Edge; | |
7c673cae FG |
60 | |
61 | class bacon_number_recorder : public default_bfs_visitor | |
62 | { | |
63 | public: | |
f67539c2 TL |
64 | bacon_number_recorder(int* dist) : d(dist) {} |
65 | ||
66 | void tree_edge(Edge e, const Graph& g) const | |
67 | { | |
68 | Vertex u = source(e, g), v = target(e, g); | |
69 | d[v] = d[u] + 1; | |
70 | } | |
7c673cae | 71 | |
7c673cae | 72 | private: |
f67539c2 | 73 | int* d; |
7c673cae FG |
74 | }; |
75 | ||
92f5a8d4 | 76 | int main(int argc, const char** argv) |
7c673cae | 77 | { |
f67539c2 TL |
78 | std::ifstream ifs(argc >= 2 ? argv[1] : "./kevin-bacon2.dat"); |
79 | if (!ifs) | |
80 | { | |
81 | std::cerr << "No ./kevin-bacon2.dat file" << std::endl; | |
82 | return EXIT_FAILURE; | |
83 | } | |
84 | archive::text_iarchive ia(ifs); | |
85 | Graph g; | |
86 | ia >> g; | |
87 | ||
88 | std::vector< int > bacon_number(num_vertices(g)); | |
89 | ||
90 | // Get the vertex for Kevin Bacon | |
91 | Vertex src; | |
92 | graph_traits< Graph >::vertex_iterator i, end; | |
93 | for (boost::tie(i, end) = vertices(g); i != end; ++i) | |
94 | if (g[*i].name == "Kevin Bacon") | |
95 | src = *i; | |
96 | ||
97 | // Set Kevin's number to zero | |
98 | bacon_number[src] = 0; | |
99 | ||
100 | // Perform a breadth first search to compute everyone' Bacon number. | |
101 | breadth_first_search( | |
102 | g, src, visitor(bacon_number_recorder(&bacon_number[0]))); | |
103 | ||
104 | for (boost::tie(i, end) = vertices(g); i != end; ++i) | |
105 | std::cout << g[*i].name << " has a Bacon number of " << bacon_number[*i] | |
106 | << std::endl; | |
107 | ||
108 | return 0; | |
7c673cae | 109 | } |