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
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
13 #include <boost/graph/graph_traits.hpp>
14 #include <boost/random/uniform_int.hpp>
15 #include <boost/random/variate_generator.hpp>
17 #include <boost/pending/property.hpp>
18 #include <boost/graph/properties.hpp>
19 #include <boost/next_prior.hpp>
21 #include <boost/graph/adjacency_list.hpp>
22 #include <boost/graph/copy.hpp>
23 #include <boost/mpl/if.hpp>
24 #include <boost/type_traits/is_convertible.hpp>
30 // grab a random vertex from the graph's vertex set
31 template <class Graph
, class RandomNumGen
>
32 typename graph_traits
<Graph
>::vertex_descriptor
33 random_vertex(Graph
& g
, RandomNumGen
& gen
)
35 if (num_vertices(g
) > 1) {
36 #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
37 std::size_t n
= std::random( num_vertices(g
) );
39 uniform_int
<> distrib(0, num_vertices(g
)-1);
40 variate_generator
<RandomNumGen
&, uniform_int
<> > rand_gen(gen
, distrib
);
41 std::size_t n
= rand_gen();
43 typename graph_traits
<Graph
>::vertex_iterator
44 i
= vertices(g
).first
;
45 return *(boost::next(i
, n
));
47 return *vertices(g
).first
;
50 template <class Graph
, class RandomNumGen
>
51 typename graph_traits
<Graph
>::edge_descriptor
52 random_edge(Graph
& g
, RandomNumGen
& gen
) {
53 if (num_edges(g
) > 1) {
54 #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
55 typename graph_traits
<Graph
>::edges_size_type
56 n
= std::random( num_edges(g
) );
58 uniform_int
<> distrib(0, num_edges(g
)-1);
59 variate_generator
<RandomNumGen
&, uniform_int
<> > rand_gen(gen
, distrib
);
60 typename graph_traits
<Graph
>::edges_size_type
63 typename graph_traits
<Graph
>::edge_iterator
65 return *(boost::next(i
, n
));
67 return *edges(g
).first
;
71 class dummy_property_copier
{
73 template<class V1
, class V2
>
74 void operator()(const V1
&, const V2
&) const {}
78 template <typename MutableGraph
, class RandNumGen
>
79 void generate_random_graph1
81 typename graph_traits
<MutableGraph
>::vertices_size_type V
,
82 typename graph_traits
<MutableGraph
>::vertices_size_type E
,
84 bool allow_parallel
= true,
85 bool self_edges
= false)
87 typedef graph_traits
<MutableGraph
> Traits
;
88 typedef typename
Traits::vertices_size_type v_size_t
;
89 typedef typename
Traits::edges_size_type e_size_t
;
90 typedef typename
Traits::vertex_descriptor vertex_descriptor
;
92 // When parallel edges are not allowed, we create a new graph which
93 // does not allow parallel edges, construct it and copy back.
94 // This is not efficient if 'g' already disallow parallel edges,
95 // but that's task for later.
96 if (!allow_parallel
) {
98 typedef typename
boost::graph_traits
<MutableGraph
>::directed_category dir
;
99 typedef typename
mpl::if_
<is_convertible
<dir
, directed_tag
>,
100 directedS
, undirectedS
>::type select
;
101 adjacency_list
<setS
, vecS
, select
> g2
;
102 generate_random_graph1(g2
, V
, E
, gen
, true, self_edges
);
104 copy_graph(g2
, g
, vertex_copy(detail::dummy_property_copier()).
105 edge_copy(detail::dummy_property_copier()));
109 for (v_size_t i
= 0; i
< V
; ++i
)
112 for (e_size_t j
= 0; j
< E
; ++j
) {
113 vertex_descriptor a
= random_vertex(g
, gen
), b
;
115 b
= random_vertex(g
, gen
);
116 } while (self_edges
== false && a
== b
);
122 template <typename MutableGraph
, class RandNumGen
>
123 void generate_random_graph
125 typename graph_traits
<MutableGraph
>::vertices_size_type V
,
126 typename graph_traits
<MutableGraph
>::vertices_size_type E
,
128 bool allow_parallel
= true,
129 bool self_edges
= false)
131 generate_random_graph1(g
, V
, E
, gen
, allow_parallel
, self_edges
);
134 template <typename MutableGraph
, typename RandNumGen
,
135 typename VertexOutputIterator
, typename EdgeOutputIterator
>
136 void generate_random_graph
138 typename graph_traits
<MutableGraph
>::vertices_size_type V
,
139 typename graph_traits
<MutableGraph
>::vertices_size_type E
,
141 VertexOutputIterator vertex_out
,
142 EdgeOutputIterator edge_out
,
143 bool self_edges
= false)
145 typedef graph_traits
<MutableGraph
> Traits
;
146 typedef typename
Traits::vertices_size_type v_size_t
;
147 typedef typename
Traits::edges_size_type e_size_t
;
148 typedef typename
Traits::vertex_descriptor vertex_t
;
149 typedef typename
Traits::edge_descriptor edge_t
;
151 for (v_size_t i
= 0; i
< V
; ++i
)
152 *vertex_out
++ = add_vertex(g
);
154 for (e_size_t j
= 0; j
< E
; ++j
) {
155 vertex_t a
= random_vertex(g
, gen
), b
;
157 b
= random_vertex(g
, gen
);
158 } while (self_edges
== false && a
== b
);
159 edge_t e
; bool inserted
;
160 tie(e
, inserted
) = add_edge(a
, b
, g
);
162 *edge_out
++ = std::make_pair(source(e
, g
), target(e
, g
));
168 template<class Property
, class G
, class RandomGenerator
>
169 void randomize_property(G
& g
, RandomGenerator
& rg
,
170 Property
, vertex_property_tag
)
172 typename property_map
<G
, Property
>::type pm
= get(Property(), g
);
173 typename graph_traits
<G
>::vertex_iterator vi
, ve
;
174 for (tie(vi
, ve
) = vertices(g
); vi
!= ve
; ++vi
) {
179 template<class Property
, class G
, class RandomGenerator
>
180 void randomize_property(G
& g
, RandomGenerator
& rg
,
181 Property
, edge_property_tag
)
183 typename property_map
<G
, Property
>::type pm
= get(Property(), g
);
184 typename graph_traits
<G
>::edge_iterator ei
, ee
;
185 for (tie(ei
, ee
) = edges(g
); ei
!= ee
; ++ei
) {
191 template<class Property
, class G
, class RandomGenerator
>
192 void randomize_property(G
& g
, RandomGenerator
& rg
)
194 detail::randomize_property
195 (g
, rg
, Property(), typename property_kind
<Property
>::type());