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/tokenizer.hpp>
13 #include <boost/tuple/tuple.hpp>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/visitors.hpp>
16 #include <boost/graph/breadth_first_search.hpp>
17 #include <map>
18
19 using namespace boost;
20
21 template <typename DistanceMap>
22 class bacon_number_recorder : public default_bfs_visitor
23 {
24 public:
bacon_number_recorder(DistanceMap dist)25 bacon_number_recorder(DistanceMap dist) : d(dist) { }
26
27 template <typename Edge, typename Graph>
tree_edge(Edge e,const Graph & g) const28 void tree_edge(Edge e, const Graph& g) const
29 {
30 typename graph_traits<Graph>::vertex_descriptor
31 u = source(e, g), v = target(e, g);
32 d[v] = d[u] + 1;
33 }
34 private:
35 DistanceMap d;
36 };
37
38 // Convenience function
39 template < typename DistanceMap >
40 bacon_number_recorder<DistanceMap>
record_bacon_number(DistanceMap d)41 record_bacon_number(DistanceMap d)
42 {
43 return bacon_number_recorder < DistanceMap > (d);
44 }
45
46
47 int
main(int argc,const char ** argv)48 main(int argc, const char** argv)
49 {
50 std::ifstream datafile(argc >= 2 ? argv[1] : "./kevin-bacon.dat");
51 if (!datafile) {
52 std::cerr << "No ./kevin-bacon.dat file" << std::endl;
53 return EXIT_FAILURE;
54 }
55
56 typedef adjacency_list < vecS, vecS, undirectedS, property < vertex_name_t,
57 std::string >, property < edge_name_t, std::string > > Graph;
58 Graph g;
59
60 typedef property_map < Graph, vertex_name_t >::type actor_name_map_t;
61 actor_name_map_t actor_name = get(vertex_name, g);
62 typedef property_map < Graph, edge_name_t >::type movie_name_map_t;
63 movie_name_map_t connecting_movie = get(edge_name, g);
64
65 typedef graph_traits < Graph >::vertex_descriptor Vertex;
66 typedef std::map < std::string, Vertex > NameVertexMap;
67 NameVertexMap actors;
68
69 for (std::string line; std::getline(datafile, line);) {
70 char_delimiters_separator < char >sep(false, "", ";");
71 tokenizer <> line_toks(line, sep);
72 tokenizer <>::iterator i = line_toks.begin();
73 std::string actors_name = *i++;
74 NameVertexMap::iterator pos;
75 bool inserted;
76 Vertex u, v;
77 boost::tie(pos, inserted) = actors.insert(std::make_pair(actors_name, Vertex()));
78 if (inserted) {
79 u = add_vertex(g);
80 actor_name[u] = actors_name;
81 pos->second = u;
82 } else
83 u = pos->second;
84
85 std::string movie_name = *i++;
86
87 boost::tie(pos, inserted) = actors.insert(std::make_pair(*i, Vertex()));
88 if (inserted) {
89 v = add_vertex(g);
90 actor_name[v] = *i;
91 pos->second = v;
92 } else
93 v = pos->second;
94
95 graph_traits < Graph >::edge_descriptor e;
96 boost::tie(e, inserted) = add_edge(u, v, g);
97 if (inserted)
98 connecting_movie[e] = movie_name;
99
100 }
101
102 std::vector < int >bacon_number(num_vertices(g));
103
104 Vertex src = actors["Kevin Bacon"];
105 bacon_number[src] = 0;
106
107 breadth_first_search(g, src,
108 visitor(record_bacon_number(&bacon_number[0])));
109
110 graph_traits < Graph >::vertex_iterator i, end;
111 for (boost::tie(i, end) = vertices(g); i != end; ++i) {
112 std::cout << actor_name[*i] << " has a Bacon number of "
113 << bacon_number[*i] << std::endl;
114 }
115
116 return 0;
117 }
118