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