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