Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r54769 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-07-07 09:02:33


Author: asutton
Date: 2009-07-07 09:02:32 EDT (Tue, 07 Jul 2009)
New Revision: 54769
URL: http://svn.boost.org/trac/boost/changeset/54769

Log:
Changed the default probability to the sorted_erdos_renyi_generator to 0.5
in order to avoid assertion.
Fixed a couple of warnings in rmat and small_world generators.

Text files modified:
   trunk/boost/graph/erdos_renyi_generator.hpp | 49 +++++++-------
   trunk/boost/graph/rmat_graph_generator.hpp | 127 ++++++++++++++++++++-------------------
   trunk/boost/graph/small_world_generator.hpp | 22 +++---
   3 files changed, 100 insertions(+), 98 deletions(-)

Modified: trunk/boost/graph/erdos_renyi_generator.hpp
==============================================================================
--- trunk/boost/graph/erdos_renyi_generator.hpp (original)
+++ trunk/boost/graph/erdos_renyi_generator.hpp 2009-07-07 09:02:32 EDT (Tue, 07 Jul 2009)
@@ -44,28 +44,28 @@
     typedef void difference_type;
 
     erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
- erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
+ erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                          double fraction = 0.0, bool allow_self_loops = false)
       : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
         allow_self_loops(allow_self_loops)
- {
+ {
       if (is_undirected) edges = edges / 2;
- next();
+ next();
     }
 
- erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
+ erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                          edges_size_type m, bool allow_self_loops = false)
       : gen(&gen), n(n), edges(m),
         allow_self_loops(allow_self_loops)
- {
- next();
+ {
+ next();
     }
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
+
     erdos_renyi_iterator& operator++()
- {
+ {
       --edges;
       next();
       return *this;
@@ -122,29 +122,30 @@
     typedef void difference_type;
 
     sorted_erdos_renyi_iterator()
- : gen(), rand_vertex(0.5), n(0), allow_self_loops(false),
- src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0) {}
- sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
- double prob = 0.0,
- bool allow_self_loops = false)
- : gen(),
- // The "1.0 - prob" in the next line is to work around a Boost.Random
- // (and TR1) bug in the specification of geometric_distribution. It
- // should be replaced by "prob" when the issue is fixed.
- rand_vertex(1.0 - prob),
- n(n), allow_self_loops(allow_self_loops), src(0), tgt(0), prob(prob)
- {
+ : gen(), rand_vertex(0.5), n(0), allow_self_loops(false)
+ , src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0)
+ { }
+
+ // NOTE: The default probability has been changed to be the same as that
+ // used by the geometic distribution. It was previously 0.0, which would
+ // cause an assertion.
+ sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
+ double prob = 0.5,
+ bool loops = false)
+ : gen(), rand_vertex(prob), n(n), allow_self_loops(loops), src(0)
+ , tgt(0), prob(prob)
+ {
       this->gen.reset(new uniform_01<RandomGenerator>(gen));
 
       if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
- next();
+ next();
     }
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
+
     sorted_erdos_renyi_iterator& operator++()
- {
+ {
       next();
       return *this;
     }
@@ -194,7 +195,7 @@
         if (src + src_increment >= n) {
           src = n;
         } else {
- tgt -= (src + allow_self_loops) * src_increment +
+ tgt -= (src + allow_self_loops) * src_increment +
                  src_increment * (src_increment - 1) / 2;
           src += src_increment;
         }

Modified: trunk/boost/graph/rmat_graph_generator.hpp
==============================================================================
--- trunk/boost/graph/rmat_graph_generator.hpp (original)
+++ trunk/boost/graph/rmat_graph_generator.hpp 2009-07-07 09:02:32 EDT (Tue, 07 Jul 2009)
@@ -47,7 +47,7 @@
   { }
 
   template <typename T>
- bool operator()(const T& x, const T& y)
+ bool operator()(const T& x, const T& y)
   { return distrib(x) == id || distrib(y) == id; }
 
 private:
@@ -58,16 +58,16 @@
 template <typename RandomGenerator, typename T>
 void
 generate_permutation_vector(RandomGenerator& gen, std::vector<T>& vertexPermutation, T n)
-{
+{
   using boost::uniform_int;
 
   vertexPermutation.resize(n);
-
+
   // Generate permutation map of vertex numbers
   uniform_int<T> rand_vertex(0, n-1);
   for (T i = 0; i < n; ++i)
     vertexPermutation[i] = i;
-
+
   // Can't use std::random_shuffle unless we create another (synchronized) PRNG
   for (T i = 0; i < n; ++i)
     std::swap(vertexPermutation[i], vertexPermutation[rand_vertex(gen)]);
@@ -75,14 +75,14 @@
 
 template <typename RandomGenerator, typename T>
 std::pair<T,T>
-generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
+generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
               unsigned int SCALE, double a, double b, double c, double d)
 {
   T u = 0, v = 0;
   T step = n/2;
   for (unsigned int j = 0; j < SCALE; ++j) {
     double p = (*prob)();
-
+
     if (p < a)
       ;
     else if (p >= a && p < a + b)
@@ -93,18 +93,18 @@
       u += step;
       v += step;
     }
-
+
     step /= 2;
 
     // 0.2 and 0.9 are hardcoded in the reference SSCA implementation.
     // The maximum change in any given value should be less than 10%
- a *= 0.9 + 0.2 * (*prob)();
- b *= 0.9 + 0.2 * (*prob)();
- c *= 0.9 + 0.2 * (*prob)();
- d *= 0.9 + 0.2 * (*prob)();
-
+ a *= 0.9 + 0.2 * (*prob)();
+ b *= 0.9 + 0.2 * (*prob)();
+ c *= 0.9 + 0.2 * (*prob)();
+ d *= 0.9 + 0.2 * (*prob)();
+
     double S = a + b + c + d;
-
+
     a /= S; b /= S; c /= S;
     // d /= S;
     // Ensure all values add up to 1, regardless of floating point errors
@@ -119,8 +119,8 @@
   /*
     Chakrabarti's R-MAT scale free generator.
 
- For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
- unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
+ For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
+ unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
     generator may be unable to generate sufficient unique edges
 
     To get a true scale free distribution {a, b, c, d : a > b, a > c, a > d}
@@ -145,19 +145,19 @@
       : gen(), edge(0) { }
 
     // Initialize for edge generation
- rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
                   double d, bool permute_vertices = true)
- : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
- permute_vertices(permute_vertices),
+ : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
+ permute_vertices(permute_vertices),
         SCALE(int_log2(n))
-
+
     {
       this->gen.reset(new uniform_01<RandomGenerator>(gen));
 
       assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
 
- if (permute_vertices)
+ if (permute_vertices)
         generate_permutation_vector(gen, vertexPermutation, n);
 
       // TODO: Generate the entire adjacency matrix then "Clip and flip" if undirected graph
@@ -167,9 +167,9 @@
       tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
 
       if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
+ current = std::make_pair(vertexPermutation[u],
                                  vertexPermutation[v]);
- else
+ else
         current = std::make_pair(u, v);
 
       --edge;
@@ -177,16 +177,16 @@
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
+
     rmat_iterator& operator++()
     {
       vertices_size_type u, v;
       tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
 
       if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
+ current = std::make_pair(vertexPermutation[u],
                                  vertexPermutation[v]);
- else
+ else
         current = std::make_pair(u, v);
 
       --edge;
@@ -223,15 +223,15 @@
     std::vector<vertices_size_type> vertexPermutation;
     value_type current;
   };
-
+
   // Sorted version for CSR
   template <typename T>
   struct sort_pair {
     bool operator() (const std::pair<T,T>& x, const std::pair<T,T>& y)
- {
+ {
       if (x.first == y.first)
         return x.second > y.second;
- else
+ else
         return x.first > y.first;
     }
   };
@@ -257,25 +257,25 @@
     { }
 
     // Initialize for edge generation
- sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
                          double d, bool permute_vertices = true,
                          EdgePredicate ep = keep_all_edges())
       : gen(), permute_vertices(permute_vertices),
         values(sort_pair<vertices_size_type>()), done(false)
-
+
     {
       assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
 
       this->gen.reset(new uniform_01<RandomGenerator>(gen));
 
       std::vector<vertices_size_type> vertexPermutation;
- if (permute_vertices)
+ if (permute_vertices)
         generate_permutation_vector(gen, vertexPermutation, n);
-
+
       // TODO: "Clip and flip" if undirected graph
       int SCALE = int_log2(n);
-
+
       for (edges_size_type i = 0; i < m; ++i) {
 
         vertices_size_type u, v;
@@ -297,7 +297,7 @@
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
+
     sorted_rmat_iterator& operator++()
     {
       if (!values.empty()) {
@@ -359,23 +359,23 @@
     { }
 
     // Initialize for edge generation
- unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
                          double d, bool permute_vertices = true,
                          EdgePredicate ep = keep_all_edges())
       : gen(), done(false)
-
+
     {
       assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
 
       this->gen.reset(new uniform_01<RandomGenerator>(gen));
 
       std::vector<vertices_size_type> vertexPermutation;
- if (permute_vertices)
+ if (permute_vertices)
         generate_permutation_vector(gen, vertexPermutation, n);
 
       int SCALE = int_log2(n);
-
+
       std::map<value_type, bool> edge_map;
 
       edges_size_type edges = 0;
@@ -383,14 +383,14 @@
         vertices_size_type u, v;
         tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
 
- // Lowest vertex number always comes first
+ // Lowest vertex number always comes first
         // (this means we don't have to worry about i->j and j->i being in the edge list)
         if (u > v && is_same<directed_category, undirected_tag>::value)
           std::swap(u, v);
 
         if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
           edge_map[std::make_pair(u, v)] = true;
-
+
           if (permute_vertices) {
             if (ep(vertexPermutation[u], vertexPermutation[v]))
               values.push_back(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
@@ -404,20 +404,20 @@
       } while (edges < m);
       // NGE - Asking for more than n^2 edges will result in an infinite loop here
       // Asking for a value too close to n^2 edges may as well
-
+
       current = values.back();
       values.pop_back();
     }
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
+
     unique_rmat_iterator& operator++()
     {
       if (!values.empty()) {
         current = values.back();
         values.pop_back();
- } else
+ } else
         done = true;
 
       return *this;
@@ -470,30 +470,30 @@
       : gen(), values(sort_pair<vertices_size_type>()), done(true) { }
 
     // Initialize for edge generation
- sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool bidirectional = false,
+ sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
+ double d, bool bidirectional = false,
                                 bool permute_vertices = true,
                                 EdgePredicate ep = keep_all_edges())
- : gen(), bidirectional(bidirectional),
+ : gen(), bidirectional(bidirectional),
         values(sort_pair<vertices_size_type>()), done(false)
-
+
     {
       assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
 
       this->gen.reset(new uniform_01<RandomGenerator>(gen));
-
+
       std::vector<vertices_size_type> vertexPermutation;
       if (permute_vertices)
         generate_permutation_vector(gen, vertexPermutation, n);
 
       int SCALE = int_log2(n);
-
+
       std::map<value_type, bool> edge_map;
-
+
       edges_size_type edges = 0;
       do {
-
+
         vertices_size_type u, v;
         tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
 
@@ -501,8 +501,8 @@
           if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
             edge_map[std::make_pair(u, v)] = true;
             edge_map[std::make_pair(v, u)] = true;
-
- if (ep(u, v))
+
+ if (ep(u, v)) {
               if (permute_vertices) {
                 values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
                 values.push(std::make_pair(vertexPermutation[v], vertexPermutation[u]));
@@ -510,15 +510,16 @@
                 values.push(std::make_pair(u, v));
                 values.push(std::make_pair(v, u));
               }
+ }
 
             ++edges;
           }
         } else {
- // Lowest vertex number always comes first
+ // Lowest vertex number always comes first
           // (this means we don't have to worry about i->j and j->i being in the edge list)
           if (u > v && is_same<directed_category, undirected_tag>::value)
             std::swap(u, v);
-
+
           if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
             edge_map[std::make_pair(u, v)] = true;
 
@@ -533,7 +534,7 @@
             ++edges;
           }
         }
-
+
       } while (edges < m);
       // NGE - Asking for more than n^2 edges will result in an infinite loop here
       // Asking for a value too close to n^2 edges may as well
@@ -544,13 +545,13 @@
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
+
     sorted_unique_rmat_iterator& operator++()
     {
       if (!values.empty()) {
         current = values.top();
         values.pop();
- } else
+ } else
         done = true;
 
       return *this;
@@ -578,7 +579,7 @@
     bool bidirectional;
 
     // Internal data structures
- std::priority_queue<value_type, std::vector<value_type>,
+ std::priority_queue<value_type, std::vector<value_type>,
                         sort_pair<vertices_size_type> > values;
     value_type current;
     bool done;

Modified: trunk/boost/graph/small_world_generator.hpp
==============================================================================
--- trunk/boost/graph/small_world_generator.hpp (original)
+++ trunk/boost/graph/small_world_generator.hpp 2009-07-07 09:02:32 EDT (Tue, 07 Jul 2009)
@@ -20,7 +20,7 @@
   template<typename RandomGenerator, typename Graph>
   class small_world_iterator
   {
- typedef typename graph_traits<Graph>::vertices_size_type
+ typedef typename graph_traits<Graph>::vertices_size_type
       vertices_size_type;
 
   public:
@@ -31,20 +31,20 @@
     typedef void difference_type;
 
     small_world_iterator() : gen(0) {}
- small_world_iterator(RandomGenerator& gen, vertices_size_type n,
- vertices_size_type k, double prob = 0.0,
- bool allow_self_loops = false)
- : gen(&gen), n(n), k(k), prob(prob), source(0),
- target(allow_self_loops? 0 : 1),
- allow_self_loops(allow_self_loops),
+ small_world_iterator(RandomGenerator& gen, vertices_size_type n,
+ vertices_size_type k, double prob = 0.0,
+ bool allow_self_loops = false)
+ : gen(&gen), n(n), k(k), prob(prob), source(0),
+ target(allow_self_loops? 0 : 1),
+ allow_self_loops(allow_self_loops),
         current(0, allow_self_loops? 0 : 1)
     { }
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
+
     small_world_iterator& operator++()
- {
+ {
       target = (target + 1) % n;
       if (target == (source + k/2 + 1) % n) {
         ++source;
@@ -62,8 +62,8 @@
         vertices_size_type upper = (source + k/2) % n;
         do {
           current.second = rand_vertex_gen(*gen);
- } while (current.second >= lower && current.second <= upper
- || (upper < lower
+ } while ((current.second >= lower && current.second <= upper)
+ || (upper < lower
                      && (current.second >= lower || current.second <= upper)));
       } else {
         current.second = target;


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk