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