ceph/src/boost/libs/graph/example/girth.cpp

   1 //=======================================================================
   2 // Copyright 2002 Indiana University.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 /*
  11   Adapted from the GIRTH program of the Stanford GraphBase.
  12
  13   Sample output:
  14
  15   This program explores the girth and diameter of Ramanujan graphs.
  16   The bipartite graphs have q^3-q vertices, and the non-bipartite
  17   graphs have half that number. Each vertex has degree p+1.
  18   Both p and q should be odd prime numbers;
  19     or you can try p = 2 with q = 17 or 43.
  20
  21   Choose a branching factor, p: 2
  22   Ok, now choose the cube root of graph size, q: 17
  23   Starting at any given vertex, there are
  24   3 vertices at distance 1,
  25   6 vertices at distance 2,
  26   12 vertices at distance 3,
  27   24 vertices at distance 4,
  28   46 vertices at distance 5,
  29   90 vertices at distance 6,
  30   169 vertices at distance 7,
  31   290 vertices at distance 8,
  32   497 vertices at distance 9,
  33   634 vertices at distance 10,
  34   521 vertices at distance 11,
  35   138 vertices at distance 12,
  36   13 vertices at distance 13,
  37   3 vertices at distance 14,
  38   1 vertices at distance 15.
  39   So the diameter is 15, and the girth is 9.
  40
  41  */
  42
  43 #include <boost/config.hpp>
  44 #include <vector>
  45 #include <list>
  46 #include <iostream>
  47 #include <boost/limits.hpp>
  48 #include <boost/graph/stanford_graph.hpp>
  49 #include <boost/graph/breadth_first_search.hpp>
  50 #include <boost/graph/graph_utility.hpp>
  51
  52 typedef boost::graph_traits<Graph*> Traits;
  53 typedef Traits::vertex_descriptor vertex_descriptor;
  54 typedef Traits::edge_descriptor edge_descriptor;
  55 typedef Traits::vertex_iterator vertex_iterator;
  56
  57 std::vector<std::size_t> distance_list;
  58
  59 typedef boost::v_property<long> dist_t;
  60 boost::property_map<Graph*, dist_t>::type d_map;
  61
  62 typedef boost::u_property<vertex_descriptor> pred_t;
  63 boost::property_map<Graph*, pred_t>::type p_map;
  64
  65 typedef boost::w_property<long> color_t;
  66 boost::property_map<Graph*, color_t>::type c_map;
  67
  68 class diameter_and_girth_visitor : public boost::bfs_visitor<>
  69 {
  70 public:
  71   diameter_and_girth_visitor(std::size_t& k_, std::size_t& girth_)
  72     : k(k_), girth(girth_) { }
  73
  74   void tree_edge(edge_descriptor e, Graph* g) {
  75     vertex_descriptor u = source(e, g), v = target(e, g);
  76     k = d_map[u] + 1;
  77     d_map[v] = k;
  78     ++distance_list[k];
  79     p_map[v] = u;
  80   }
  81   void non_tree_edge(edge_descriptor e, Graph* g) {
  82     vertex_descriptor u = source(e, g), v = target(e, g);
  83     k = d_map[u] + 1;
  84     if (d_map[v] + k < girth && v != p_map[u])
  85       girth = d_map[v]+ k;
  86   }
  87 private:
  88   std::size_t& k;
  89   std::size_t& girth;
  90 };
  91
  92
  93 int
  94 main()
  95 {
  96   std::cout <<
  97     "This program explores the girth and diameter of Ramanujan graphs."
  98             << std::endl;
  99   std::cout <<
 100     "The bipartite graphs have q^3-q vertices, and the non-bipartite"
 101             << std::endl;
 102   std::cout <<
 103     "graphs have half that number. Each vertex has degree p+1."
 104             << std::endl;
 105   std::cout << "Both p and q should be odd prime numbers;" << std::endl;
 106   std::cout << "  or you can try p = 2 with q = 17 or 43." << std::endl;
 107
 108   while (1) {
 109
 110     std::cout << std::endl
 111               << "Choose a branching factor, p: ";
 112     long p = 0, q = 0;
 113     std::cin >> p;
 114     if (p == 0)
 115       break;
 116     std::cout << "Ok, now choose the cube root of graph size, q: ";
 117     std::cin >> q;
 118     if (q == 0)
 119       break;
 120
 121     Graph* g;
 122     g = raman(p, q, 0L, 0L);
 123     if (g == 0) {
 124       std::cerr << " Sorry, I couldn't make that graph (error code "
 125         << panic_code << ")" << std::endl;
 126       continue;
 127     }
 128     distance_list.clear();
 129     distance_list.resize(boost::num_vertices(g), 0);
 130
 131     // obtain property maps
 132     d_map = get(dist_t(), g);
 133     p_map = get(pred_t(), g);
 134     c_map = get(color_t(), g);
 135
 136     vertex_iterator i, end;
 137     for (boost::tie(i, end) = boost::vertices(g); i != end; ++i)
 138       d_map[*i] = 0;
 139
 140     std::size_t k = 0;
 141     std::size_t girth = (std::numeric_limits<std::size_t>::max)();
 142     diameter_and_girth_visitor vis(k, girth);
 143
 144     vertex_descriptor s = *boost::vertices(g).first;
 145
 146     boost::breadth_first_search(g, s, visitor(vis).color_map(c_map));
 147
 148     std::cout << "Starting at any given vertex, there are" << std::endl;
 149
 150     for (long d = 1; distance_list[d] != 0; ++d)
 151       std::cout << distance_list[d] << " vertices at distance " << d
 152                 << (distance_list[d+1] != 0 ? "," : ".") << std::endl;
 153
 154     std::cout << "So the diameter is " << k - 1
 155               << ", and the girth is " << girth
 156               << "." << std::endl;
 157   } // end while
 158
 159   return 0;
 160 }