1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
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 //=======================================================================
8 #include <boost/config.hpp>
9 #include <iostream>
10 #include <fstream>
11 #include <string>
12 #include <boost/tuple/tuple.hpp>
13 #include <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/visitors.hpp>
15 #include <boost/graph/breadth_first_search.hpp>
16 #include <map>
17 #include <boost/graph/adj_list_serialize.hpp>
18 #include <boost/archive/text_iarchive.hpp>
19
20 struct vertex_properties {
21 std::string name;
22
23 template<class Archive>
serializevertex_properties24 void serialize(Archive & ar, const unsigned int version) {
25 ar & name;
26 }
27 };
28
29 struct edge_properties {
30 std::string name;
31
32 template<class Archive>
serializeedge_properties33 void serialize(Archive & ar, const unsigned int version) {
34 ar & name;
35 }
36 };
37
38 using namespace boost;
39
40 typedef adjacency_list<vecS, vecS, undirectedS,
41 vertex_properties, edge_properties> Graph;
42 typedef graph_traits<Graph>::vertex_descriptor Vertex;
43 typedef graph_traits<Graph>::edge_descriptor Edge;
44
45 class bacon_number_recorder : public default_bfs_visitor
46 {
47 public:
bacon_number_recorder(int * dist)48 bacon_number_recorder(int* dist) : d(dist) { }
49
tree_edge(Edge e,const Graph & g) const50 void tree_edge(Edge e, const Graph& g) const {
51 Vertex u = source(e, g), v = target(e, g);
52 d[v] = d[u] + 1;
53 }
54 private:
55 int* d;
56 };
57
main()58 int main()
59 {
60 std::ifstream ifs("./kevin-bacon2.dat");
61 if (!ifs) {
62 std::cerr << "No ./kevin-bacon2.dat file" << std::endl;
63 return EXIT_FAILURE;
64 }
65 archive::text_iarchive ia(ifs);
66 Graph g;
67 ia >> g;
68
69 std::vector<int> bacon_number(num_vertices(g));
70
71 // Get the vertex for Kevin Bacon
72 Vertex src;
73 graph_traits<Graph>::vertex_iterator i, end;
74 for (boost::tie(i, end) = vertices(g); i != end; ++i)
75 if (g[*i].name == "Kevin Bacon")
76 src = *i;
77
78 // Set Kevin's number to zero
79 bacon_number[src] = 0;
80
81 // Perform a breadth first search to compute everyone' Bacon number.
82 breadth_first_search(g, src,
83 visitor(bacon_number_recorder(&bacon_number[0])));
84
85 for (boost::tie(i, end) = vertices(g); i != end; ++i)
86 std::cout << g[*i].name << " has a Bacon number of "
87 << bacon_number[*i] << std::endl;
88
89 return 0;
90 }
91