ceph/src/boost/libs/graph/include/boost/graph/random.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Copyright (C) Vladimir Prus 2003
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 #ifndef BOOST_GRAPH_RANDOM_HPP
  11 #define BOOST_GRAPH_RANDOM_HPP
  12
  13 #include <boost/graph/graph_traits.hpp>
  14 #include <boost/random/uniform_int.hpp>
  15 #include <boost/random/uniform_real.hpp>
  16 #include <boost/random/variate_generator.hpp>
  17
  18 #include <boost/pending/property.hpp>
  19 #include <boost/graph/properties.hpp>
  20 #include <boost/graph/iteration_macros.hpp>
  21 #include <boost/next_prior.hpp>
  22
  23 #include <boost/graph/adjacency_list.hpp>
  24 #include <boost/graph/copy.hpp>
  25 #include <boost/mpl/if.hpp>
  26 #include <boost/type_traits/is_convertible.hpp>
  27
  28 #include <iostream>
  29 #include <boost/assert.hpp>
  30
  31 namespace boost {
  32
  33   // grab a random vertex from the graph's vertex set
  34   template <class Graph, class RandomNumGen>
  35   typename graph_traits<Graph>::vertex_descriptor
  36   random_vertex(Graph& g, RandomNumGen& gen)
  37   {
  38     if (num_vertices(g) > 1) {
  39     #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
  40       std::size_t n = std::random( num_vertices(g) );
  41     #else
  42       uniform_int<> distrib(0, num_vertices(g)-1);
  43       variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
  44       std::size_t n = rand_gen();
  45     #endif
  46       typename graph_traits<Graph>::vertex_iterator
  47         i = vertices(g).first;
  48       return *(boost::next(i, n));
  49     } else
  50       return *vertices(g).first;
  51   }
  52
  53   template <class Graph, class RandomNumGen>
  54   typename graph_traits<Graph>::edge_descriptor
  55   random_edge(Graph& g, RandomNumGen& gen) {
  56     if (num_edges(g) > 1) {
  57     #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
  58       typename graph_traits<Graph>::edges_size_type
  59         n = std::random( num_edges(g) );
  60     #else
  61       uniform_int<> distrib(0, num_edges(g)-1);
  62       variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
  63       typename graph_traits<Graph>::edges_size_type
  64         n = rand_gen();
  65     #endif
  66       typename graph_traits<Graph>::edge_iterator
  67         i = edges(g).first;
  68       return *(boost::next(i, n));
  69     } else
  70       return *edges(g).first;
  71   }
  72
  73   template <typename Graph, typename RandomNumGen>
  74   typename graph_traits<Graph>::edge_descriptor
  75   random_out_edge(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, RandomNumGen& gen) {
  76     typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
  77     typedef boost::uniform_int<degree_size_type> ui_type;
  78     ui_type ui(0, out_degree(src, g) - 1);
  79     boost::variate_generator<RandomNumGen&, ui_type>
  80       variate(gen, ui);
  81     typename graph_traits<Graph>::out_edge_iterator it = out_edges(src, g).first;
  82     std::advance(it, variate());
  83     return *it;
  84   }
  85
  86   template <typename Graph, typename WeightMap, typename RandomNumGen>
  87   typename graph_traits<Graph>::edge_descriptor
  88   weighted_random_out_edge(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, WeightMap weight, RandomNumGen& gen) {
  89     typedef typename property_traits<WeightMap>::value_type weight_type;
  90     weight_type weight_sum(0);
  91     BGL_FORALL_OUTEDGES_T(src, e, g, Graph) {weight_sum += get(weight, e);}
  92     typedef boost::uniform_real<> ur_type;
  93     ur_type ur(0, weight_sum);
  94     boost::variate_generator<RandomNumGen&, ur_type>
  95       variate(gen, ur);
  96     weight_type chosen_weight = variate();
  97     BGL_FORALL_OUTEDGES_T(src, e, g, Graph) {
  98       weight_type w = get(weight, e);
  99       if (chosen_weight < w) {
 100         return e;
 101       } else {
 102         chosen_weight -= w;
 103       }
 104     }
 105     BOOST_ASSERT (false); // Should not get here
 106     return typename graph_traits<Graph>::edge_descriptor();
 107   }
 108
 109   namespace detail {
 110     class dummy_property_copier {
 111     public:
 112       template<class V1, class V2>
 113       void operator()(const V1&, const V2&) const {}
 114     };
 115   }
 116
 117   template <typename MutableGraph, class RandNumGen>
 118   void generate_random_graph1
 119     (MutableGraph& g,
 120      typename graph_traits<MutableGraph>::vertices_size_type V,
 121      typename graph_traits<MutableGraph>::vertices_size_type E,
 122      RandNumGen& gen,
 123      bool allow_parallel = true,
 124      bool self_edges = false)
 125   {
 126     typedef graph_traits<MutableGraph> Traits;
 127     typedef typename Traits::edge_descriptor edge_t;
 128     typedef typename Traits::vertices_size_type v_size_t;
 129     typedef typename Traits::edges_size_type e_size_t;
 130     typedef typename Traits::vertex_descriptor vertex_descriptor;
 131
 132     // When parallel edges are not allowed, we create a new graph which
 133     // does not allow parallel edges, construct it and copy back.
 134     // This is not efficient if 'g' already disallow parallel edges,
 135     // but that's task for later.
 136     if (!allow_parallel) {
 137
 138       typedef typename boost::graph_traits<MutableGraph>::directed_category dir;
 139       typedef typename mpl::if_<is_convertible<dir, directed_tag>,
 140           directedS, undirectedS>::type select;
 141       adjacency_list<setS, vecS, select> g2;
 142       generate_random_graph1(g2, V, E, gen, true, self_edges);
 143
 144       copy_graph(g2, g, vertex_copy(detail::dummy_property_copier()).
 145                         edge_copy(detail::dummy_property_copier()));
 146
 147     } else {
 148
 149       for (v_size_t i = 0; i < V; ++i)
 150         add_vertex(g);
 151
 152       e_size_t not_inserted_counter = 0; /* Number of edge insertion failures */
 153       e_size_t num_vertices_squared = num_vertices(g) * num_vertices(g);
 154       for (e_size_t j = 0; j < E; /* Increment in body */) {
 155         vertex_descriptor a = random_vertex(g, gen), b;
 156         do {
 157           b = random_vertex(g, gen);
 158         } while (self_edges == false && a == b);
 159         edge_t e; bool inserted;
 160         boost::tie(e, inserted) = add_edge(a, b, g);
 161         if (inserted) {
 162           ++j;
 163         } else {
 164           ++not_inserted_counter;
 165         }
 166         if (not_inserted_counter >= num_vertices_squared) {
 167           return; /* Rather than looping forever on complete graph */
 168         }
 169       }
 170     }
 171   }
 172
 173   template <typename MutableGraph, class RandNumGen>
 174   void generate_random_graph
 175     (MutableGraph& g,
 176      typename graph_traits<MutableGraph>::vertices_size_type V,
 177      typename graph_traits<MutableGraph>::vertices_size_type E,
 178      RandNumGen& gen,
 179      bool allow_parallel = true,
 180      bool self_edges = false)
 181   {
 182       generate_random_graph1(g, V, E, gen, allow_parallel, self_edges);
 183   }
 184
 185   template <typename MutableGraph, typename RandNumGen,
 186             typename VertexOutputIterator, typename EdgeOutputIterator>
 187   void generate_random_graph
 188     (MutableGraph& g,
 189      typename graph_traits<MutableGraph>::vertices_size_type V,
 190      typename graph_traits<MutableGraph>::vertices_size_type E,
 191      RandNumGen& gen,
 192      VertexOutputIterator vertex_out,
 193      EdgeOutputIterator edge_out,
 194      bool self_edges = false)
 195   {
 196     typedef graph_traits<MutableGraph> Traits;
 197     typedef typename Traits::vertices_size_type v_size_t;
 198     typedef typename Traits::edges_size_type e_size_t;
 199     typedef typename Traits::vertex_descriptor vertex_t;
 200     typedef typename Traits::edge_descriptor edge_t;
 201
 202     for (v_size_t i = 0; i < V; ++i)
 203       *vertex_out++ = add_vertex(g);
 204
 205     e_size_t not_inserted_counter = 0; /* Number of edge insertion failures */
 206     e_size_t num_vertices_squared = num_vertices(g) * num_vertices(g);
 207     for (e_size_t j = 0; j < E; /* Increment in body */) {
 208       vertex_t a = random_vertex(g, gen), b;
 209       do {
 210         b = random_vertex(g, gen);
 211       } while (self_edges == false && a == b);
 212       edge_t e; bool inserted;
 213       boost::tie(e, inserted) = add_edge(a, b, g);
 214       if (inserted) {
 215         *edge_out++ = std::make_pair(source(e, g), target(e, g));
 216         ++j;
 217       } else {
 218         ++not_inserted_counter;
 219       }
 220       if (not_inserted_counter >= num_vertices_squared) {
 221         return; /* Rather than looping forever on complete graph */
 222       }
 223     }
 224   }
 225
 226   namespace detail {
 227
 228     template<class Property, class G, class RandomGenerator>
 229     void randomize_property(G& g, RandomGenerator& rg,
 230                             Property, vertex_property_tag)
 231     {
 232       typename property_map<G, Property>::type pm = get(Property(), g);
 233       typename graph_traits<G>::vertex_iterator vi, ve;
 234       for (boost::tie(vi, ve) = vertices(g); vi != ve; ++vi) {
 235         pm[*vi] = rg();
 236       }
 237     }
 238
 239     template<class Property, class G, class RandomGenerator>
 240     void randomize_property(G& g, RandomGenerator& rg,
 241                             Property, edge_property_tag)
 242     {
 243       typename property_map<G, Property>::type pm = get(Property(), g);
 244       typename graph_traits<G>::edge_iterator ei, ee;
 245       for (boost::tie(ei, ee) = edges(g); ei != ee; ++ei) {
 246         pm[*ei] = rg();
 247       }
 248     }
 249   }
 250
 251   template<class Property, class G, class RandomGenerator>
 252   void randomize_property(G& g, RandomGenerator& rg)
 253   {
 254     detail::randomize_property
 255         (g, rg, Property(), typename property_kind<Property>::type());
 256   }
 257
 258
 259
 260
 261 }
 262
 263 #include <boost/graph/iteration_macros_undef.hpp>
 264
 265 #endif