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
9 /*
10 IMPORTANT:
11 ~~~~~~~~~~
12
13 This example appears to be broken and crashes at runtime, see
14 https://github.com/boostorg/graph/issues/148
15
16 */
17
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
31 struct vertex_properties
32 {
33 std::string name;
34
35 template < class Archive >
serializevertex_properties36 void serialize(Archive& ar, const unsigned int version)
37 {
38 ar& name;
39 }
40 };
41
42 struct edge_properties
43 {
44 std::string name;
45
46 template < class Archive >
serializeedge_properties47 void serialize(Archive& ar, const unsigned int version)
48 {
49 ar& name;
50 }
51 };
52
53 using namespace boost;
54
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;
60
61 class bacon_number_recorder : public default_bfs_visitor
62 {
63 public:
bacon_number_recorder(int * dist)64 bacon_number_recorder(int* dist) : d(dist) {}
65
tree_edge(Edge e,const Graph & g) const66 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 }
71
72 private:
73 int* d;
74 };
75
main(int argc,const char ** argv)76 int main(int argc, const char** argv)
77 {
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;
109 }
110