epoc32/include/stdapis/boost/graph/random.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
parent 3 e1b950c65cb4
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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 
    27 namespace 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     #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581))
    36       std::size_t n = std::random( num_vertices(g) );
    37     #else
    38       uniform_int<> distrib(0, num_vertices(g)-1);
    39       variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
    40       std::size_t n = rand_gen();
    41     #endif
    42       typename graph_traits<Graph>::vertex_iterator
    43         i = vertices(g).first;
    44       while (n-- > 0) ++i; // std::advance not VC++ portable
    45       return *i;
    46     } else
    47       return *vertices(g).first;
    48   }
    49 
    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) );
    57     #else
    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
    61         n = rand_gen();
    62     #endif
    63       typename graph_traits<Graph>::edge_iterator
    64         i = edges(g).first;
    65       while (n-- > 0) ++i; // std::advance not VC++ portable
    66       return *i;
    67     } else
    68       return *edges(g).first;
    69   }
    70 
    71   namespace detail {
    72     class dummy_property_copier {
    73     public:
    74       template<class V1, class V2>
    75       void operator()(const V1&, const V2&) const {}
    76     };
    77   }
    78 
    79   template <typename MutableGraph, class RandNumGen>
    80   void generate_random_graph1
    81     (MutableGraph& g,
    82      typename graph_traits<MutableGraph>::vertices_size_type V,
    83      typename graph_traits<MutableGraph>::vertices_size_type E,
    84      RandNumGen& gen,
    85      bool allow_parallel = true,
    86      bool self_edges = false)
    87   {
    88     typedef graph_traits<MutableGraph> Traits;
    89     typedef typename Traits::vertices_size_type v_size_t;
    90     typedef typename Traits::edges_size_type e_size_t;
    91     typedef typename Traits::vertex_descriptor vertex_descriptor;
    92 
    93     // When parallel edges are not allowed, we create a new graph which
    94     // does not allow parallel edges, construct it and copy back.
    95     // This is not efficient if 'g' already disallow parallel edges,
    96     // but that's task for later.
    97     if (!allow_parallel) {
    98 
    99       typedef typename boost::graph_traits<MutableGraph>::directed_category dir;
   100       typedef typename mpl::if_<is_convertible<dir, directed_tag>,
   101           directedS, undirectedS>::type select;
   102       adjacency_list<setS, vecS, select> g2;
   103       generate_random_graph1(g2, V, E, gen, true, self_edges);
   104 
   105       copy_graph(g2, g, vertex_copy(detail::dummy_property_copier()).
   106                         edge_copy(detail::dummy_property_copier()));
   107 
   108     } else {
   109 
   110       for (v_size_t i = 0; i < V; ++i)
   111         add_vertex(g);
   112 
   113       for (e_size_t j = 0; j < E; ++j) {
   114         vertex_descriptor a = random_vertex(g, gen), b;
   115         do {
   116           b = random_vertex(g, gen);
   117         } while (self_edges == false && a == b);
   118         add_edge(a, b, g);
   119       }
   120     }
   121   }
   122 
   123   template <typename MutableGraph, class RandNumGen>
   124   void generate_random_graph
   125     (MutableGraph& g,
   126      typename graph_traits<MutableGraph>::vertices_size_type V,
   127      typename graph_traits<MutableGraph>::vertices_size_type E,
   128      RandNumGen& gen,
   129      bool allow_parallel = true,
   130      bool self_edges = false)
   131   {
   132       generate_random_graph1(g, V, E, gen, allow_parallel, self_edges);
   133   }
   134 
   135   template <typename MutableGraph, typename RandNumGen,
   136             typename VertexOutputIterator, typename EdgeOutputIterator>
   137   void generate_random_graph
   138     (MutableGraph& g,
   139      typename graph_traits<MutableGraph>::vertices_size_type V,
   140      typename graph_traits<MutableGraph>::vertices_size_type E,
   141      RandNumGen& gen,
   142      VertexOutputIterator vertex_out,
   143      EdgeOutputIterator edge_out,
   144      bool self_edges = false)
   145   {
   146     typedef graph_traits<MutableGraph> Traits;
   147     typedef typename Traits::vertices_size_type v_size_t;
   148     typedef typename Traits::edges_size_type e_size_t;
   149     typedef typename Traits::vertex_descriptor vertex_t;
   150     typedef typename Traits::edge_descriptor edge_t;
   151 
   152     for (v_size_t i = 0; i < V; ++i)
   153       *vertex_out++ = add_vertex(g);
   154 
   155     for (e_size_t j = 0; j < E; ++j) {
   156       vertex_t a = random_vertex(g, gen), b;
   157       do {
   158         b = random_vertex(g, gen);
   159       } while (self_edges == false && a == b);
   160       edge_t e; bool inserted;
   161       tie(e, inserted) = add_edge(a, b, g);
   162       if (inserted)
   163         *edge_out++ = std::make_pair(source(e, g), target(e, g));
   164     }
   165   }
   166 
   167   namespace detail {
   168 
   169     template<class Property, class G, class RandomGenerator>
   170     void randomize_property(G& g, RandomGenerator& rg,
   171                             Property, vertex_property_tag)
   172     {
   173       typename property_map<G, Property>::type pm = get(Property(), g);
   174       typename graph_traits<G>::vertex_iterator vi, ve;
   175       for (tie(vi, ve) = vertices(g); vi != ve; ++vi) {
   176         pm[*vi] = rg();
   177       }
   178     }
   179 
   180     template<class Property, class G, class RandomGenerator>
   181     void randomize_property(G& g, RandomGenerator& rg,
   182                             Property, edge_property_tag)
   183     {
   184       typename property_map<G, Property>::type pm = get(Property(), g);
   185       typename graph_traits<G>::edge_iterator ei, ee;
   186       for (tie(ei, ee) = edges(g); ei != ee; ++ei) {
   187         pm[*ei] = rg();
   188       }
   189     }
   190   }
   191 
   192   template<class Property, class G, class RandomGenerator>
   193   void randomize_property(G& g, RandomGenerator& rg)
   194   {
   195     detail::randomize_property
   196         (g, rg, Property(), typename property_kind<Property>::type());
   197   }
   198 
   199 
   200 
   201   
   202 }
   203 
   204 
   205 #endif