epoc32/include/stdapis/boost/graph/random.hpp
branchSymbian3
changeset 4 837f303aceeb
parent 3 e1b950c65cb4
     1.1 --- a/epoc32/include/stdapis/boost/graph/random.hpp	Wed Mar 31 12:27:01 2010 +0100
     1.2 +++ b/epoc32/include/stdapis/boost/graph/random.hpp	Wed Mar 31 12:33:34 2010 +0100
     1.3 @@ -1,72 +1,205 @@
     1.4 -/* boost random.hpp header file
     1.5 - *
     1.6 - * Copyright Jens Maurer 2000-2001
     1.7 - * Distributed under the Boost Software License, Version 1.0. (See
     1.8 - * accompanying file LICENSE_1_0.txt or copy at
     1.9 - * http://www.boost.org/LICENSE_1_0.txt)
    1.10 - *
    1.11 - * See http://www.boost.org/libs/random for documentation.
    1.12 - *
    1.13 - * $Id: random.hpp,v 1.18 2004/07/27 03:43:27 dgregor Exp $
    1.14 - *
    1.15 - * Revision history
    1.16 - *  2000-02-18  portability fixes (thanks to Beman Dawes)
    1.17 - *  2000-02-21  shuffle_output, inversive_congruential_schrage,
    1.18 - *              generator_iterator, uniform_smallint
    1.19 - *  2000-02-23  generic modulus arithmetic helper, removed *_schrage classes,
    1.20 - *              implemented Streamable and EqualityComparable concepts for 
    1.21 - *              generators, added Bernoulli distribution and Box-Muller
    1.22 - *              transform
    1.23 - *  2000-03-01  cauchy, lognormal, triangle distributions; fixed 
    1.24 - *              uniform_smallint; renamed gaussian to normal distribution
    1.25 - *  2000-03-05  implemented iterator syntax for distribution functions
    1.26 - *  2000-04-21  removed some optimizations for better BCC/MSVC compatibility
    1.27 - *  2000-05-10  adapted to BCC and MSVC
    1.28 - *  2000-06-13  incorporated review results
    1.29 - *  2000-07-06  moved basic templates from namespace detail to random
    1.30 - *  2000-09-23  warning removals and int64 fixes (Ed Brey)
    1.31 - *  2000-09-24  added lagged_fibonacci generator (Matthias Troyer)
    1.32 - *  2001-02-18  moved to individual header files
    1.33 - */
    1.34 +//=======================================================================
    1.35 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
    1.36 +// Copyright (C) Vladimir Prus 2003
    1.37 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
    1.38 +//
    1.39 +// Distributed under the Boost Software License, Version 1.0. (See
    1.40 +// accompanying file LICENSE_1_0.txt or copy at
    1.41 +// http://www.boost.org/LICENSE_1_0.txt)
    1.42 +//=======================================================================
    1.43 +#ifndef BOOST_GRAPH_RANDOM_HPP
    1.44 +#define BOOST_GRAPH_RANDOM_HPP
    1.45  
    1.46 -#ifndef BOOST_RANDOM_HPP
    1.47 -#define BOOST_RANDOM_HPP
    1.48 +#include <boost/graph/graph_traits.hpp>
    1.49 +#include <boost/random/uniform_int.hpp>
    1.50 +#include <boost/random/variate_generator.hpp>
    1.51  
    1.52 -// generators
    1.53 -#include <boost/random/linear_congruential.hpp>
    1.54 -#include <boost/random/additive_combine.hpp>
    1.55 -#include <boost/random/inversive_congruential.hpp>
    1.56 -#include <boost/random/shuffle_output.hpp>
    1.57 -#include <boost/random/mersenne_twister.hpp>
    1.58 -#include <boost/random/lagged_fibonacci.hpp>
    1.59 -#include <boost/random/ranlux.hpp>
    1.60 -#include <boost/random/linear_feedback_shift.hpp>
    1.61 -#include <boost/random/xor_combine.hpp>
    1.62 +#include <boost/pending/property.hpp>
    1.63 +#include <boost/graph/properties.hpp>
    1.64 +
    1.65 +#include <boost/graph/adjacency_list.hpp>
    1.66 +#include <boost/graph/copy.hpp>
    1.67 +#include <boost/mpl/if.hpp>
    1.68 +#include <boost/type_traits/is_convertible.hpp>
    1.69 +
    1.70 +#include <iostream>
    1.71  
    1.72  namespace boost {
    1.73 -  typedef random::xor_combine<random::xor_combine<random::linear_feedback_shift<uint32_t, 32, 31, 13, 12, 0>, 0,
    1.74 -    random::linear_feedback_shift<uint32_t, 32, 29, 2, 4, 0>, 0, 0>, 0,
    1.75 -                      random::linear_feedback_shift<uint32_t, 32, 28, 3, 17, 0>, 0, 0> taus88;
    1.76 -} // namespace  boost
    1.77  
    1.78 -// misc
    1.79 -#include <boost/random/random_number_generator.hpp>
    1.80 +  // grab a random vertex from the graph's vertex set
    1.81 +  template <class Graph, class RandomNumGen>
    1.82 +  typename graph_traits<Graph>::vertex_descriptor
    1.83 +  random_vertex(Graph& g, RandomNumGen& gen)
    1.84 +  {
    1.85 +    if (num_vertices(g) > 1) {
    1.86 +    #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
    1.87 +      std::size_t n = std::random( num_vertices(g) );
    1.88 +    #else
    1.89 +      uniform_int<> distrib(0, num_vertices(g)-1);
    1.90 +      variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
    1.91 +      std::size_t n = rand_gen();
    1.92 +    #endif
    1.93 +      typename graph_traits<Graph>::vertex_iterator
    1.94 +        i = vertices(g).first;
    1.95 +      while (n-- > 0) ++i; // std::advance not VC++ portable
    1.96 +      return *i;
    1.97 +    } else
    1.98 +      return *vertices(g).first;
    1.99 +  }
   1.100  
   1.101 -// distributions
   1.102 -#include <boost/random/uniform_smallint.hpp>
   1.103 -#include <boost/random/uniform_int.hpp>
   1.104 -#include <boost/random/uniform_01.hpp>
   1.105 -#include <boost/random/uniform_real.hpp>
   1.106 -#include <boost/random/triangle_distribution.hpp>
   1.107 -#include <boost/random/bernoulli_distribution.hpp>
   1.108 -#include <boost/random/cauchy_distribution.hpp>
   1.109 -#include <boost/random/exponential_distribution.hpp>
   1.110 -#include <boost/random/geometric_distribution.hpp>
   1.111 -#include <boost/random/normal_distribution.hpp>
   1.112 -#include <boost/random/lognormal_distribution.hpp>
   1.113 -#include <boost/random/poisson_distribution.hpp>
   1.114 -#include <boost/random/gamma_distribution.hpp>
   1.115 -#include <boost/random/binomial_distribution.hpp>
   1.116 -#include <boost/random/uniform_on_sphere.hpp>
   1.117 +  template <class Graph, class RandomNumGen>
   1.118 +  typename graph_traits<Graph>::edge_descriptor
   1.119 +  random_edge(Graph& g, RandomNumGen& gen) {
   1.120 +    if (num_edges(g) > 1) {
   1.121 +    #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
   1.122 +      typename graph_traits<Graph>::edges_size_type
   1.123 +        n = std::random( num_edges(g) );
   1.124 +    #else
   1.125 +      uniform_int<> distrib(0, num_edges(g)-1);
   1.126 +      variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
   1.127 +      typename graph_traits<Graph>::edges_size_type
   1.128 +        n = rand_gen();
   1.129 +    #endif
   1.130 +      typename graph_traits<Graph>::edge_iterator
   1.131 +        i = edges(g).first;
   1.132 +      while (n-- > 0) ++i; // std::advance not VC++ portable
   1.133 +      return *i;
   1.134 +    } else
   1.135 +      return *edges(g).first;
   1.136 +  }
   1.137  
   1.138 -#endif // BOOST_RANDOM_HPP
   1.139 +  namespace detail {
   1.140 +    class dummy_property_copier {
   1.141 +    public:
   1.142 +      template<class V1, class V2>
   1.143 +      void operator()(const V1&, const V2&) const {}
   1.144 +    };
   1.145 +  }
   1.146 +
   1.147 +  template <typename MutableGraph, class RandNumGen>
   1.148 +  void generate_random_graph1
   1.149 +    (MutableGraph& g,
   1.150 +     typename graph_traits<MutableGraph>::vertices_size_type V,
   1.151 +     typename graph_traits<MutableGraph>::vertices_size_type E,
   1.152 +     RandNumGen& gen,
   1.153 +     bool allow_parallel = true,
   1.154 +     bool self_edges = false)
   1.155 +  {
   1.156 +    typedef graph_traits<MutableGraph> Traits;
   1.157 +    typedef typename Traits::vertices_size_type v_size_t;
   1.158 +    typedef typename Traits::edges_size_type e_size_t;
   1.159 +    typedef typename Traits::vertex_descriptor vertex_descriptor;
   1.160 +
   1.161 +    // When parallel edges are not allowed, we create a new graph which
   1.162 +    // does not allow parallel edges, construct it and copy back.
   1.163 +    // This is not efficient if 'g' already disallow parallel edges,
   1.164 +    // but that's task for later.
   1.165 +    if (!allow_parallel) {
   1.166 +
   1.167 +      typedef typename boost::graph_traits<MutableGraph>::directed_category dir;
   1.168 +      typedef typename mpl::if_<is_convertible<dir, directed_tag>,
   1.169 +          directedS, undirectedS>::type select;
   1.170 +      adjacency_list<setS, vecS, select> g2;
   1.171 +      generate_random_graph1(g2, V, E, gen, true, self_edges);
   1.172 +
   1.173 +      copy_graph(g2, g, vertex_copy(detail::dummy_property_copier()).
   1.174 +                        edge_copy(detail::dummy_property_copier()));
   1.175 +
   1.176 +    } else {
   1.177 +
   1.178 +      for (v_size_t i = 0; i < V; ++i)
   1.179 +        add_vertex(g);
   1.180 +
   1.181 +      for (e_size_t j = 0; j < E; ++j) {
   1.182 +        vertex_descriptor a = random_vertex(g, gen), b;
   1.183 +        do {
   1.184 +          b = random_vertex(g, gen);
   1.185 +        } while (self_edges == false && a == b);
   1.186 +        add_edge(a, b, g);
   1.187 +      }
   1.188 +    }
   1.189 +  }
   1.190 +
   1.191 +  template <typename MutableGraph, class RandNumGen>
   1.192 +  void generate_random_graph
   1.193 +    (MutableGraph& g,
   1.194 +     typename graph_traits<MutableGraph>::vertices_size_type V,
   1.195 +     typename graph_traits<MutableGraph>::vertices_size_type E,
   1.196 +     RandNumGen& gen,
   1.197 +     bool allow_parallel = true,
   1.198 +     bool self_edges = false)
   1.199 +  {
   1.200 +      generate_random_graph1(g, V, E, gen, allow_parallel, self_edges);
   1.201 +  }
   1.202 +
   1.203 +  template <typename MutableGraph, typename RandNumGen,
   1.204 +            typename VertexOutputIterator, typename EdgeOutputIterator>
   1.205 +  void generate_random_graph
   1.206 +    (MutableGraph& g,
   1.207 +     typename graph_traits<MutableGraph>::vertices_size_type V,
   1.208 +     typename graph_traits<MutableGraph>::vertices_size_type E,
   1.209 +     RandNumGen& gen,
   1.210 +     VertexOutputIterator vertex_out,
   1.211 +     EdgeOutputIterator edge_out,
   1.212 +     bool self_edges = false)
   1.213 +  {
   1.214 +    typedef graph_traits<MutableGraph> Traits;
   1.215 +    typedef typename Traits::vertices_size_type v_size_t;
   1.216 +    typedef typename Traits::edges_size_type e_size_t;
   1.217 +    typedef typename Traits::vertex_descriptor vertex_t;
   1.218 +    typedef typename Traits::edge_descriptor edge_t;
   1.219 +
   1.220 +    for (v_size_t i = 0; i < V; ++i)
   1.221 +      *vertex_out++ = add_vertex(g);
   1.222 +
   1.223 +    for (e_size_t j = 0; j < E; ++j) {
   1.224 +      vertex_t a = random_vertex(g, gen), b;
   1.225 +      do {
   1.226 +        b = random_vertex(g, gen);
   1.227 +      } while (self_edges == false && a == b);
   1.228 +      edge_t e; bool inserted;
   1.229 +      tie(e, inserted) = add_edge(a, b, g);
   1.230 +      if (inserted)
   1.231 +        *edge_out++ = std::make_pair(source(e, g), target(e, g));
   1.232 +    }
   1.233 +  }
   1.234 +
   1.235 +  namespace detail {
   1.236 +
   1.237 +    template<class Property, class G, class RandomGenerator>
   1.238 +    void randomize_property(G& g, RandomGenerator& rg,
   1.239 +                            Property, vertex_property_tag)
   1.240 +    {
   1.241 +      typename property_map<G, Property>::type pm = get(Property(), g);
   1.242 +      typename graph_traits<G>::vertex_iterator vi, ve;
   1.243 +      for (tie(vi, ve) = vertices(g); vi != ve; ++vi) {
   1.244 +        pm[*vi] = rg();
   1.245 +      }
   1.246 +    }
   1.247 +
   1.248 +    template<class Property, class G, class RandomGenerator>
   1.249 +    void randomize_property(G& g, RandomGenerator& rg,
   1.250 +                            Property, edge_property_tag)
   1.251 +    {
   1.252 +      typename property_map<G, Property>::type pm = get(Property(), g);
   1.253 +      typename graph_traits<G>::edge_iterator ei, ee;
   1.254 +      for (tie(ei, ee) = edges(g); ei != ee; ++ei) {
   1.255 +        pm[*ei] = rg();
   1.256 +      }
   1.257 +    }
   1.258 +  }
   1.259 +
   1.260 +  template<class Property, class G, class RandomGenerator>
   1.261 +  void randomize_property(G& g, RandomGenerator& rg)
   1.262 +  {
   1.263 +    detail::randomize_property
   1.264 +        (g, rg, Property(), typename property_kind<Property>::type());
   1.265 +  }
   1.266 +
   1.267 +
   1.268 +
   1.269 +  
   1.270 +}
   1.271 +
   1.272 +
   1.273 +#endif