1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/graph/random.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,205 @@
1.4 +//=======================================================================
1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.6 +// Copyright (C) Vladimir Prus 2003
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +#ifndef BOOST_GRAPH_RANDOM_HPP
1.14 +#define BOOST_GRAPH_RANDOM_HPP
1.15 +
1.16 +#include <boost/graph/graph_traits.hpp>
1.17 +#include <boost/random/uniform_int.hpp>
1.18 +#include <boost/random/variate_generator.hpp>
1.19 +
1.20 +#include <boost/pending/property.hpp>
1.21 +#include <boost/graph/properties.hpp>
1.22 +
1.23 +#include <boost/graph/adjacency_list.hpp>
1.24 +#include <boost/graph/copy.hpp>
1.25 +#include <boost/mpl/if.hpp>
1.26 +#include <boost/type_traits/is_convertible.hpp>
1.27 +
1.28 +#include <iostream>
1.29 +
1.30 +namespace boost {
1.31 +
1.32 + // grab a random vertex from the graph's vertex set
1.33 + template <class Graph, class RandomNumGen>
1.34 + typename graph_traits<Graph>::vertex_descriptor
1.35 + random_vertex(Graph& g, RandomNumGen& gen)
1.36 + {
1.37 + if (num_vertices(g) > 1) {
1.38 + #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
1.39 + std::size_t n = std::random( num_vertices(g) );
1.40 + #else
1.41 + uniform_int<> distrib(0, num_vertices(g)-1);
1.42 + variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
1.43 + std::size_t n = rand_gen();
1.44 + #endif
1.45 + typename graph_traits<Graph>::vertex_iterator
1.46 + i = vertices(g).first;
1.47 + while (n-- > 0) ++i; // std::advance not VC++ portable
1.48 + return *i;
1.49 + } else
1.50 + return *vertices(g).first;
1.51 + }
1.52 +
1.53 + template <class Graph, class RandomNumGen>
1.54 + typename graph_traits<Graph>::edge_descriptor
1.55 + random_edge(Graph& g, RandomNumGen& gen) {
1.56 + if (num_edges(g) > 1) {
1.57 + #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
1.58 + typename graph_traits<Graph>::edges_size_type
1.59 + n = std::random( num_edges(g) );
1.60 + #else
1.61 + uniform_int<> distrib(0, num_edges(g)-1);
1.62 + variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
1.63 + typename graph_traits<Graph>::edges_size_type
1.64 + n = rand_gen();
1.65 + #endif
1.66 + typename graph_traits<Graph>::edge_iterator
1.67 + i = edges(g).first;
1.68 + while (n-- > 0) ++i; // std::advance not VC++ portable
1.69 + return *i;
1.70 + } else
1.71 + return *edges(g).first;
1.72 + }
1.73 +
1.74 + namespace detail {
1.75 + class dummy_property_copier {
1.76 + public:
1.77 + template<class V1, class V2>
1.78 + void operator()(const V1&, const V2&) const {}
1.79 + };
1.80 + }
1.81 +
1.82 + template <typename MutableGraph, class RandNumGen>
1.83 + void generate_random_graph1
1.84 + (MutableGraph& g,
1.85 + typename graph_traits<MutableGraph>::vertices_size_type V,
1.86 + typename graph_traits<MutableGraph>::vertices_size_type E,
1.87 + RandNumGen& gen,
1.88 + bool allow_parallel = true,
1.89 + bool self_edges = false)
1.90 + {
1.91 + typedef graph_traits<MutableGraph> Traits;
1.92 + typedef typename Traits::vertices_size_type v_size_t;
1.93 + typedef typename Traits::edges_size_type e_size_t;
1.94 + typedef typename Traits::vertex_descriptor vertex_descriptor;
1.95 +
1.96 + // When parallel edges are not allowed, we create a new graph which
1.97 + // does not allow parallel edges, construct it and copy back.
1.98 + // This is not efficient if 'g' already disallow parallel edges,
1.99 + // but that's task for later.
1.100 + if (!allow_parallel) {
1.101 +
1.102 + typedef typename boost::graph_traits<MutableGraph>::directed_category dir;
1.103 + typedef typename mpl::if_<is_convertible<dir, directed_tag>,
1.104 + directedS, undirectedS>::type select;
1.105 + adjacency_list<setS, vecS, select> g2;
1.106 + generate_random_graph1(g2, V, E, gen, true, self_edges);
1.107 +
1.108 + copy_graph(g2, g, vertex_copy(detail::dummy_property_copier()).
1.109 + edge_copy(detail::dummy_property_copier()));
1.110 +
1.111 + } else {
1.112 +
1.113 + for (v_size_t i = 0; i < V; ++i)
1.114 + add_vertex(g);
1.115 +
1.116 + for (e_size_t j = 0; j < E; ++j) {
1.117 + vertex_descriptor a = random_vertex(g, gen), b;
1.118 + do {
1.119 + b = random_vertex(g, gen);
1.120 + } while (self_edges == false && a == b);
1.121 + add_edge(a, b, g);
1.122 + }
1.123 + }
1.124 + }
1.125 +
1.126 + template <typename MutableGraph, class RandNumGen>
1.127 + void generate_random_graph
1.128 + (MutableGraph& g,
1.129 + typename graph_traits<MutableGraph>::vertices_size_type V,
1.130 + typename graph_traits<MutableGraph>::vertices_size_type E,
1.131 + RandNumGen& gen,
1.132 + bool allow_parallel = true,
1.133 + bool self_edges = false)
1.134 + {
1.135 + generate_random_graph1(g, V, E, gen, allow_parallel, self_edges);
1.136 + }
1.137 +
1.138 + template <typename MutableGraph, typename RandNumGen,
1.139 + typename VertexOutputIterator, typename EdgeOutputIterator>
1.140 + void generate_random_graph
1.141 + (MutableGraph& g,
1.142 + typename graph_traits<MutableGraph>::vertices_size_type V,
1.143 + typename graph_traits<MutableGraph>::vertices_size_type E,
1.144 + RandNumGen& gen,
1.145 + VertexOutputIterator vertex_out,
1.146 + EdgeOutputIterator edge_out,
1.147 + bool self_edges = false)
1.148 + {
1.149 + typedef graph_traits<MutableGraph> Traits;
1.150 + typedef typename Traits::vertices_size_type v_size_t;
1.151 + typedef typename Traits::edges_size_type e_size_t;
1.152 + typedef typename Traits::vertex_descriptor vertex_t;
1.153 + typedef typename Traits::edge_descriptor edge_t;
1.154 +
1.155 + for (v_size_t i = 0; i < V; ++i)
1.156 + *vertex_out++ = add_vertex(g);
1.157 +
1.158 + for (e_size_t j = 0; j < E; ++j) {
1.159 + vertex_t a = random_vertex(g, gen), b;
1.160 + do {
1.161 + b = random_vertex(g, gen);
1.162 + } while (self_edges == false && a == b);
1.163 + edge_t e; bool inserted;
1.164 + tie(e, inserted) = add_edge(a, b, g);
1.165 + if (inserted)
1.166 + *edge_out++ = std::make_pair(source(e, g), target(e, g));
1.167 + }
1.168 + }
1.169 +
1.170 + namespace detail {
1.171 +
1.172 + template<class Property, class G, class RandomGenerator>
1.173 + void randomize_property(G& g, RandomGenerator& rg,
1.174 + Property, vertex_property_tag)
1.175 + {
1.176 + typename property_map<G, Property>::type pm = get(Property(), g);
1.177 + typename graph_traits<G>::vertex_iterator vi, ve;
1.178 + for (tie(vi, ve) = vertices(g); vi != ve; ++vi) {
1.179 + pm[*vi] = rg();
1.180 + }
1.181 + }
1.182 +
1.183 + template<class Property, class G, class RandomGenerator>
1.184 + void randomize_property(G& g, RandomGenerator& rg,
1.185 + Property, edge_property_tag)
1.186 + {
1.187 + typename property_map<G, Property>::type pm = get(Property(), g);
1.188 + typename graph_traits<G>::edge_iterator ei, ee;
1.189 + for (tie(ei, ee) = edges(g); ei != ee; ++ei) {
1.190 + pm[*ei] = rg();
1.191 + }
1.192 + }
1.193 + }
1.194 +
1.195 + template<class Property, class G, class RandomGenerator>
1.196 + void randomize_property(G& g, RandomGenerator& rg)
1.197 + {
1.198 + detail::randomize_property
1.199 + (g, rg, Property(), typename property_kind<Property>::type());
1.200 + }
1.201 +
1.202 +
1.203 +
1.204 +
1.205 +}
1.206 +
1.207 +
1.208 +#endif