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
31namespace 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 }
107
108 namespace detail {
109 class dummy_property_copier {
110 public:
111 template<class V1, class V2>
112 void operator()(const V1&, const V2&) const {}
113 };
114 }
115
116 template <typename MutableGraph, class RandNumGen>
117 void generate_random_graph1
118 (MutableGraph& g,
119 typename graph_traits<MutableGraph>::vertices_size_type V,
120 typename graph_traits<MutableGraph>::vertices_size_type E,
121 RandNumGen& gen,
122 bool allow_parallel = true,
123 bool self_edges = false)
124 {
125 typedef graph_traits<MutableGraph> Traits;
126 typedef typename Traits::edge_descriptor edge_t;
127 typedef typename Traits::vertices_size_type v_size_t;
128 typedef typename Traits::edges_size_type e_size_t;
129 typedef typename Traits::vertex_descriptor vertex_descriptor;
130
131 // When parallel edges are not allowed, we create a new graph which
132 // does not allow parallel edges, construct it and copy back.
133 // This is not efficient if 'g' already disallow parallel edges,
134 // but that's task for later.
135 if (!allow_parallel) {
136
137 typedef typename boost::graph_traits<MutableGraph>::directed_category dir;
138 typedef typename mpl::if_<is_convertible<dir, directed_tag>,
139 directedS, undirectedS>::type select;
140 adjacency_list<setS, vecS, select> g2;
141 generate_random_graph1(g2, V, E, gen, true, self_edges);
142
143 copy_graph(g2, g, vertex_copy(p: detail::dummy_property_copier()).
144 edge_copy(p: detail::dummy_property_copier()));
145
146 } else {
147
148 for (v_size_t i = 0; i < V; ++i)
149 add_vertex(g);
150
151 e_size_t not_inserted_counter = 0; /* Number of edge insertion failures */
152 e_size_t num_vertices_squared = num_vertices(g) * num_vertices(g);
153 for (e_size_t j = 0; j < E; /* Increment in body */) {
154 vertex_descriptor a = random_vertex(g, gen), b;
155 do {
156 b = random_vertex(g, gen);
157 } while (self_edges == false && a == b);
158 edge_t e; bool inserted;
159 boost::tie(e, inserted) = add_edge(a, b, g);
160 if (inserted) {
161 ++j;
162 } else {
163 ++not_inserted_counter;
164 }
165 if (not_inserted_counter >= num_vertices_squared) {
166 return; /* Rather than looping forever on complete graph */
167 }
168 }
169 }
170 }
171
172 template <typename MutableGraph, class RandNumGen>
173 void generate_random_graph
174 (MutableGraph& g,
175 typename graph_traits<MutableGraph>::vertices_size_type V,
176 typename graph_traits<MutableGraph>::vertices_size_type E,
177 RandNumGen& gen,
178 bool allow_parallel = true,
179 bool self_edges = false)
180 {
181 generate_random_graph1(g, V, E, gen, allow_parallel, self_edges);
182 }
183
184 template <typename MutableGraph, typename RandNumGen,
185 typename VertexOutputIterator, typename EdgeOutputIterator>
186 void generate_random_graph
187 (MutableGraph& g,
188 typename graph_traits<MutableGraph>::vertices_size_type V,
189 typename graph_traits<MutableGraph>::vertices_size_type E,
190 RandNumGen& gen,
191 VertexOutputIterator vertex_out,
192 EdgeOutputIterator edge_out,
193 bool self_edges = false)
194 {
195 typedef graph_traits<MutableGraph> Traits;
196 typedef typename Traits::vertices_size_type v_size_t;
197 typedef typename Traits::edges_size_type e_size_t;
198 typedef typename Traits::vertex_descriptor vertex_t;
199 typedef typename Traits::edge_descriptor edge_t;
200
201 for (v_size_t i = 0; i < V; ++i)
202 *vertex_out++ = add_vertex(g);
203
204 e_size_t not_inserted_counter = 0; /* Number of edge insertion failures */
205 e_size_t num_vertices_squared = num_vertices(g) * num_vertices(g);
206 for (e_size_t j = 0; j < E; /* Increment in body */) {
207 vertex_t a = random_vertex(g, gen), b;
208 do {
209 b = random_vertex(g, gen);
210 } while (self_edges == false && a == b);
211 edge_t e; bool inserted;
212 boost::tie(e, inserted) = add_edge(a, b, g);
213 if (inserted) {
214 *edge_out++ = std::make_pair(source(e, g), target(e, g));
215 ++j;
216 } else {
217 ++not_inserted_counter;
218 }
219 if (not_inserted_counter >= num_vertices_squared) {
220 return; /* Rather than looping forever on complete graph */
221 }
222 }
223 }
224
225 namespace detail {
226
227 template<class Property, class G, class RandomGenerator>
228 void randomize_property(G& g, RandomGenerator& rg,
229 Property, vertex_property_tag)
230 {
231 typename property_map<G, Property>::type pm = get(Property(), g);
232 typename graph_traits<G>::vertex_iterator vi, ve;
233 for (boost::tie(vi, ve) = vertices(g); vi != ve; ++vi) {
234 pm[*vi] = rg();
235 }
236 }
237
238 template<class Property, class G, class RandomGenerator>
239 void randomize_property(G& g, RandomGenerator& rg,
240 Property, edge_property_tag)
241 {
242 typename property_map<G, Property>::type pm = get(Property(), g);
243 typename graph_traits<G>::edge_iterator ei, ee;
244 for (boost::tie(ei, ee) = edges(g); ei != ee; ++ei) {
245 pm[*ei] = rg();
246 }
247 }
248 }
249
250 template<class Property, class G, class RandomGenerator>
251 void randomize_property(G& g, RandomGenerator& rg)
252 {
253 detail::randomize_property
254 (g, rg, Property(), typename property_kind<Property>::type());
255 }
256
257
258
259
260}
261
262#include <boost/graph/iteration_macros_undef.hpp>
263
264#endif
265

source code of boost/boost/graph/random.hpp