source: NonGTP/Boost/boost/graph/random.hpp @ 857

Revision 857, 6.5 KB checked in by igarcia, 19 years ago (diff)
Line 
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/variate_generator.hpp>
16
17#include <boost/pending/property.hpp>
18#include <boost/graph/properties.hpp>
19
20#include <boost/graph/adjacency_list.hpp>
21#include <boost/graph/copy.hpp>
22#include <boost/mpl/if.hpp>
23#include <boost/type_traits/is_convertible.hpp>
24
25#include <iostream>
26
27namespace boost {
28
29  // grab a random vertex from the graph's vertex set
30  template <class Graph, class RandomNumGen>
31  typename graph_traits<Graph>::vertex_descriptor
32  random_vertex(Graph& g, RandomNumGen& gen)
33  {
34    if (num_vertices(g) > 1) {
35      uniform_int<> distrib(0, num_vertices(g)-1);
36      variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
37      std::size_t n = rand_gen();
38      typename graph_traits<Graph>::vertex_iterator
39        i = vertices(g).first;
40      while (n-- > 0) ++i; // std::advance not VC++ portable
41      return *i;
42    } else
43      return *vertices(g).first;
44  }
45
46  template <class Graph, class RandomNumGen>
47  typename graph_traits<Graph>::edge_descriptor
48  random_edge(Graph& g, RandomNumGen& gen) {
49    if (num_edges(g) > 1) {
50      uniform_int<> distrib(0, num_edges(g)-1);
51      variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
52      typename graph_traits<Graph>::edges_size_type
53        n = rand_gen();
54      typename graph_traits<Graph>::edge_iterator
55        i = edges(g).first;
56      while (n-- > 0) ++i; // std::advance not VC++ portable
57      return *i;
58    } else
59      return *edges(g).first;
60  }
61
62  namespace detail {
63    class dummy_property_copier {
64    public:
65      template<class V1, class V2>
66      void operator()(const V1&, const V2&) const {}
67    };
68  }
69
70  template <typename MutableGraph, class RandNumGen>
71  void generate_random_graph1
72    (MutableGraph& g,
73     typename graph_traits<MutableGraph>::vertices_size_type V,
74     typename graph_traits<MutableGraph>::vertices_size_type E,
75     RandNumGen& gen,
76     bool allow_parallel = true,
77     bool self_edges = false)
78  {
79    typedef graph_traits<MutableGraph> Traits;
80    typedef typename Traits::vertices_size_type v_size_t;
81    typedef typename Traits::edges_size_type e_size_t;
82    typedef typename Traits::vertex_descriptor vertex_descriptor;
83
84    // When parallel edges are not allowed, we create a new graph which
85    // does not allow parallel edges, construct it and copy back.
86    // This is not efficient if 'g' already disallow parallel edges,
87    // but that's task for later.
88    if (!allow_parallel) {
89
90      typedef typename boost::graph_traits<MutableGraph>::directed_category dir;     
91      typedef typename mpl::if_<is_convertible<dir, directed_tag>,
92          directedS, undirectedS>::type select;
93      adjacency_list<setS, vecS, select> g2;
94      generate_random_graph1(g2, V, E, gen, true, self_edges);
95
96      copy_graph(g2, g, vertex_copy(detail::dummy_property_copier()).
97                        edge_copy(detail::dummy_property_copier()));
98
99    } else {
100
101      for (v_size_t i = 0; i < V; ++i)
102        add_vertex(g);
103     
104      for (e_size_t j = 0; j < E; ++j) {
105        vertex_descriptor a = random_vertex(g, gen), b;
106        do {
107          b = random_vertex(g, gen);
108        } while (self_edges == false && a == b);
109        add_edge(a, b, g);
110      }
111    }
112  }
113
114  template <typename MutableGraph, class RandNumGen>
115  void generate_random_graph
116    (MutableGraph& g,
117     typename graph_traits<MutableGraph>::vertices_size_type V,
118     typename graph_traits<MutableGraph>::vertices_size_type E,
119     RandNumGen& gen,
120     bool allow_parallel = true,
121     bool self_edges = false)
122  {
123      generate_random_graph1(g, V, E, gen, allow_parallel, self_edges);
124  }
125
126  template <typename MutableGraph, typename RandNumGen,
127            typename VertexOutputIterator, typename EdgeOutputIterator>
128  void generate_random_graph
129    (MutableGraph& g,
130     typename graph_traits<MutableGraph>::vertices_size_type V,
131     typename graph_traits<MutableGraph>::vertices_size_type E,
132     RandNumGen& gen,
133     VertexOutputIterator vertex_out,
134     EdgeOutputIterator edge_out,
135     bool self_edges = false)
136  {
137    typedef graph_traits<MutableGraph> Traits;
138    typedef typename Traits::vertices_size_type v_size_t;
139    typedef typename Traits::edges_size_type e_size_t;
140    typedef typename Traits::vertex_descriptor vertex_t;
141    typedef typename Traits::edge_descriptor edge_t;
142
143    for (v_size_t i = 0; i < V; ++i)
144      *vertex_out++ = add_vertex(g);
145
146    for (e_size_t j = 0; j < E; ++j) {
147      vertex_t a = random_vertex(g, gen), b;
148      do {
149        b = random_vertex(g, gen);
150      } while (self_edges == false && a == b);
151      edge_t e; bool inserted;
152      tie(e, inserted) = add_edge(a, b, g);
153      if (inserted)
154        *edge_out++ = std::make_pair(source(e, g), target(e, g));
155    }
156  }
157
158  namespace detail {
159
160    template<class Property, class G, class RandomGenerator>
161    void randomize_property(G& g, RandomGenerator& rg,
162                            Property, vertex_property_tag)
163    {
164      typename property_map<G, Property>::type pm = get(Property(), g);
165      typename graph_traits<G>::vertex_iterator vi, ve;
166      for (tie(vi, ve) = vertices(g); vi != ve; ++vi) {
167        pm[*vi] = rg();
168      }
169    }
170
171    template<class Property, class G, class RandomGenerator>
172    void randomize_property(G& g, RandomGenerator& rg,
173                            Property, edge_property_tag)
174    {
175      typename property_map<G, Property>::type pm = get(Property(), g);
176      typename graph_traits<G>::edge_iterator ei, ee;
177      for (tie(ei, ee) = edges(g); ei != ee; ++ei) {
178        pm[*ei] = rg();
179      }
180    }
181  }
182
183  template<class Property, class G, class RandomGenerator>
184  void randomize_property(G& g, RandomGenerator& rg)
185  {
186    detail::randomize_property
187        (g, rg, Property(), typename property_kind<Property>::type());
188  }
189
190
191
192 
193}
194
195
196#endif
Note: See TracBrowser for help on using the repository browser.