Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 09:43:06 

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Copyright (C) Vladimir Prus 2003
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 #ifndef BOOST_GRAPH_RANDOM_HPP
0011 #define BOOST_GRAPH_RANDOM_HPP
0012 
0013 #include <boost/graph/graph_traits.hpp>
0014 #include <boost/random/uniform_int.hpp>
0015 #include <boost/random/uniform_real.hpp>
0016 #include <boost/random/variate_generator.hpp>
0017 
0018 #include <boost/pending/property.hpp>
0019 #include <boost/graph/properties.hpp>
0020 #include <boost/graph/iteration_macros.hpp>
0021 #include <boost/next_prior.hpp>
0022 
0023 #include <boost/graph/adjacency_list.hpp>
0024 #include <boost/graph/copy.hpp>
0025 #include <boost/mpl/if.hpp>
0026 #include <boost/type_traits/is_convertible.hpp>
0027 
0028 #include <iostream>
0029 #include <boost/assert.hpp>
0030 
0031 namespace boost
0032 {
0033 
0034 // grab a random vertex from the graph's vertex set
0035 template < class Graph, class RandomNumGen >
0036 typename graph_traits< Graph >::vertex_descriptor random_vertex(
0037     Graph& g, RandomNumGen& gen)
0038 {
0039     if (num_vertices(g) > 1)
0040     {
0041 #if BOOST_WORKAROUND(BOOST_BORLANDC, BOOST_TESTED_AT(0x581))
0042         std::size_t n = std::random(num_vertices(g));
0043 #else
0044         uniform_int<> distrib(0, num_vertices(g) - 1);
0045         variate_generator< RandomNumGen&, uniform_int<> > rand_gen(
0046             gen, distrib);
0047         std::size_t n = rand_gen();
0048 #endif
0049         typename graph_traits< Graph >::vertex_iterator i = vertices(g).first;
0050         return *(boost::next(i, n));
0051     }
0052     else
0053         return *vertices(g).first;
0054 }
0055 
0056 template < class Graph, class RandomNumGen >
0057 typename graph_traits< Graph >::edge_descriptor random_edge(
0058     Graph& g, RandomNumGen& gen)
0059 {
0060     if (num_edges(g) > 1)
0061     {
0062 #if BOOST_WORKAROUND(BOOST_BORLANDC, BOOST_TESTED_AT(0x581))
0063         typename graph_traits< Graph >::edges_size_type n
0064             = std::random(num_edges(g));
0065 #else
0066         uniform_int<> distrib(0, num_edges(g) - 1);
0067         variate_generator< RandomNumGen&, uniform_int<> > rand_gen(
0068             gen, distrib);
0069         typename graph_traits< Graph >::edges_size_type n = rand_gen();
0070 #endif
0071         typename graph_traits< Graph >::edge_iterator i = edges(g).first;
0072         return *(boost::next(i, n));
0073     }
0074     else
0075         return *edges(g).first;
0076 }
0077 
0078 template < typename Graph, typename RandomNumGen >
0079 typename graph_traits< Graph >::edge_descriptor random_out_edge(Graph& g,
0080     typename graph_traits< Graph >::vertex_descriptor src, RandomNumGen& gen)
0081 {
0082     typedef typename graph_traits< Graph >::degree_size_type degree_size_type;
0083     typedef boost::uniform_int< degree_size_type > ui_type;
0084     ui_type ui(0, out_degree(src, g) - 1);
0085     boost::variate_generator< RandomNumGen&, ui_type > variate(gen, ui);
0086     typename graph_traits< Graph >::out_edge_iterator it
0087         = out_edges(src, g).first;
0088     std::advance(it, variate());
0089     return *it;
0090 }
0091 
0092 template < typename Graph, typename WeightMap, typename RandomNumGen >
0093 typename graph_traits< Graph >::edge_descriptor weighted_random_out_edge(
0094     Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
0095     WeightMap weight, RandomNumGen& gen)
0096 {
0097     typedef typename property_traits< WeightMap >::value_type weight_type;
0098     weight_type weight_sum(0);
0099     BGL_FORALL_OUTEDGES_T(src, e, g, Graph) { weight_sum += get(weight, e); }
0100     typedef boost::uniform_real<> ur_type;
0101     ur_type ur(0, weight_sum);
0102     boost::variate_generator< RandomNumGen&, ur_type > variate(gen, ur);
0103     weight_type chosen_weight = variate();
0104     BGL_FORALL_OUTEDGES_T(src, e, g, Graph)
0105     {
0106         weight_type w = get(weight, e);
0107         if (chosen_weight < w)
0108         {
0109             return e;
0110         }
0111         else
0112         {
0113             chosen_weight -= w;
0114         }
0115     }
0116     BOOST_ASSERT(false); // Should not get here
0117     return typename graph_traits< Graph >::edge_descriptor();
0118 }
0119 
0120 namespace detail
0121 {
0122     class dummy_property_copier
0123     {
0124     public:
0125         template < class V1, class V2 >
0126         void operator()(const V1&, const V2&) const
0127         {
0128         }
0129     };
0130 }
0131 
0132 template < typename MutableGraph, class RandNumGen >
0133 void generate_random_graph1(MutableGraph& g,
0134     typename graph_traits< MutableGraph >::vertices_size_type V,
0135     typename graph_traits< MutableGraph >::vertices_size_type E,
0136     RandNumGen& gen, bool allow_parallel = true, bool self_edges = false)
0137 {
0138     typedef graph_traits< MutableGraph > Traits;
0139     typedef typename Traits::edge_descriptor edge_t;
0140     typedef typename Traits::vertices_size_type v_size_t;
0141     typedef typename Traits::edges_size_type e_size_t;
0142     typedef typename Traits::vertex_descriptor vertex_descriptor;
0143 
0144     // When parallel edges are not allowed, we create a new graph which
0145     // does not allow parallel edges, construct it and copy back.
0146     // This is not efficient if 'g' already disallow parallel edges,
0147     // but that's task for later.
0148     if (!allow_parallel)
0149     {
0150 
0151         typedef
0152             typename boost::graph_traits< MutableGraph >::directed_category dir;
0153         typedef typename mpl::if_< is_convertible< dir, directed_tag >,
0154             directedS, undirectedS >::type select;
0155         adjacency_list< setS, vecS, select > g2;
0156         generate_random_graph1(g2, V, E, gen, true, self_edges);
0157 
0158         copy_graph(g2, g,
0159             vertex_copy(detail::dummy_property_copier())
0160                 .edge_copy(detail::dummy_property_copier()));
0161     }
0162     else
0163     {
0164 
0165         for (v_size_t i = 0; i < V; ++i)
0166             add_vertex(g);
0167 
0168         e_size_t not_inserted_counter
0169             = 0; /* Number of edge insertion failures */
0170         e_size_t num_vertices_squared = num_vertices(g) * num_vertices(g);
0171         for (e_size_t j = 0; j < E; /* Increment in body */)
0172         {
0173             vertex_descriptor a = random_vertex(g, gen), b;
0174             do
0175             {
0176                 b = random_vertex(g, gen);
0177             } while (self_edges == false && a == b);
0178             edge_t e;
0179             bool inserted;
0180             boost::tie(e, inserted) = add_edge(a, b, g);
0181             if (inserted)
0182             {
0183                 ++j;
0184             }
0185             else
0186             {
0187                 ++not_inserted_counter;
0188             }
0189             if (not_inserted_counter >= num_vertices_squared)
0190             {
0191                 return; /* Rather than looping forever on complete graph */
0192             }
0193         }
0194     }
0195 }
0196 
0197 template < typename MutableGraph, class RandNumGen >
0198 void generate_random_graph(MutableGraph& g,
0199     typename graph_traits< MutableGraph >::vertices_size_type V,
0200     typename graph_traits< MutableGraph >::vertices_size_type E,
0201     RandNumGen& gen, bool allow_parallel = true, bool self_edges = false)
0202 {
0203     generate_random_graph1(g, V, E, gen, allow_parallel, self_edges);
0204 }
0205 
0206 template < typename MutableGraph, typename RandNumGen,
0207     typename VertexOutputIterator, typename EdgeOutputIterator >
0208 void generate_random_graph(MutableGraph& g,
0209     typename graph_traits< MutableGraph >::vertices_size_type V,
0210     typename graph_traits< MutableGraph >::vertices_size_type E,
0211     RandNumGen& gen, VertexOutputIterator vertex_out,
0212     EdgeOutputIterator edge_out, bool self_edges = false)
0213 {
0214     typedef graph_traits< MutableGraph > Traits;
0215     typedef typename Traits::vertices_size_type v_size_t;
0216     typedef typename Traits::edges_size_type e_size_t;
0217     typedef typename Traits::vertex_descriptor vertex_t;
0218     typedef typename Traits::edge_descriptor edge_t;
0219 
0220     for (v_size_t i = 0; i < V; ++i)
0221         *vertex_out++ = add_vertex(g);
0222 
0223     e_size_t not_inserted_counter = 0; /* Number of edge insertion failures */
0224     e_size_t num_vertices_squared = num_vertices(g) * num_vertices(g);
0225     for (e_size_t j = 0; j < E; /* Increment in body */)
0226     {
0227         vertex_t a = random_vertex(g, gen), b;
0228         do
0229         {
0230             b = random_vertex(g, gen);
0231         } while (self_edges == false && a == b);
0232         edge_t e;
0233         bool inserted;
0234         boost::tie(e, inserted) = add_edge(a, b, g);
0235         if (inserted)
0236         {
0237             *edge_out++ = std::make_pair(source(e, g), target(e, g));
0238             ++j;
0239         }
0240         else
0241         {
0242             ++not_inserted_counter;
0243         }
0244         if (not_inserted_counter >= num_vertices_squared)
0245         {
0246             return; /* Rather than looping forever on complete graph */
0247         }
0248     }
0249 }
0250 
0251 namespace detail
0252 {
0253 
0254     template < class Property, class G, class RandomGenerator >
0255     void randomize_property(
0256         G& g, RandomGenerator& rg, Property, vertex_property_tag)
0257     {
0258         typename property_map< G, Property >::type pm = get(Property(), g);
0259         typename graph_traits< G >::vertex_iterator vi, ve;
0260         for (boost::tie(vi, ve) = vertices(g); vi != ve; ++vi)
0261         {
0262             pm[*vi] = rg();
0263         }
0264     }
0265 
0266     template < class Property, class G, class RandomGenerator >
0267     void randomize_property(
0268         G& g, RandomGenerator& rg, Property, edge_property_tag)
0269     {
0270         typename property_map< G, Property >::type pm = get(Property(), g);
0271         typename graph_traits< G >::edge_iterator ei, ee;
0272         for (boost::tie(ei, ee) = edges(g); ei != ee; ++ei)
0273         {
0274             pm[*ei] = rg();
0275         }
0276     }
0277 }
0278 
0279 template < class Property, class G, class RandomGenerator >
0280 void randomize_property(G& g, RandomGenerator& rg)
0281 {
0282     detail::randomize_property(
0283         g, rg, Property(), typename property_kind< Property >::type());
0284 }
0285 
0286 }
0287 
0288 #include <boost/graph/iteration_macros_undef.hpp>
0289 
0290 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!