ceph/src/boost/libs/graph/example/kevin-bacon2.cpp

   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 /*
  11    IMPORTANT:
  12    ~~~~~~~~~~
  13
  14    This example appears to be broken and crashes at runtime, see 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   std::string name;
  33
  34   template<class Archive>
  35   void serialize(Archive & ar, const unsigned int version) {
  36     ar & name;
  37   }
  38 };
  39
  40 struct edge_properties {
  41   std::string name;
  42
  43   template<class Archive>
  44   void serialize(Archive & ar, const unsigned int version) {
  45     ar & name;
  46   }
  47 };
  48
  49 using namespace boost;
  50
  51 typedef adjacency_list<vecS, vecS, undirectedS,
  52                vertex_properties, edge_properties> Graph;
  53 typedef graph_traits<Graph>::vertex_descriptor Vertex;
  54 typedef graph_traits<Graph>::edge_descriptor Edge;
  55
  56 class bacon_number_recorder : public default_bfs_visitor
  57 {
  58 public:
  59   bacon_number_recorder(int* dist) : d(dist) { }
  60
  61   void tree_edge(Edge e, const Graph& g) const {
  62     Vertex u = source(e, g), v = target(e, g);
  63     d[v] = d[u] + 1;
  64   }
  65 private:
  66   int* d;
  67 };
  68
  69 int main(int argc, const char** argv)
  70 {
  71   std::ifstream ifs(argc >= 2 ? argv[1] : "./kevin-bacon2.dat");
  72   if (!ifs) {
  73     std::cerr << "No ./kevin-bacon2.dat file" << std::endl;
  74     return EXIT_FAILURE;
  75   }
  76   archive::text_iarchive ia(ifs);
  77   Graph g;
  78   ia >> g;
  79
  80   std::vector<int> bacon_number(num_vertices(g));
  81
  82   // Get the vertex for Kevin Bacon
  83   Vertex src;
  84   graph_traits<Graph>::vertex_iterator i, end;
  85   for (boost::tie(i, end) = vertices(g); i != end; ++i)
  86     if (g[*i].name == "Kevin Bacon")
  87       src = *i;
  88
  89   // Set Kevin's number to zero
  90   bacon_number[src] = 0;
  91
  92   // Perform a breadth first search to compute everyone' Bacon number.
  93   breadth_first_search(g, src,
  94                        visitor(bacon_number_recorder(&bacon_number[0])));
  95
  96   for (boost::tie(i, end) = vertices(g); i != end; ++i)
  97     std::cout << g[*i].name << " has a Bacon number of "
  98           << bacon_number[*i] << std::endl;
  99
 100   return 0;
 101 }