graph/distributed/rmat_graph_generator.hpp

0001 // Copyright 2004, 2005 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Nick Edmonds
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP
0010 #define BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP
0011
0012 #ifndef BOOST_GRAPH_USE_MPI
0013 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0014 #endif
0015
0016 #include <boost/assert.hpp>
0017 #include <boost/graph/parallel/algorithm.hpp>
0018 #include <boost/graph/parallel/process_group.hpp>
0019 #include <math.h>
0020
0021 namespace boost {
0022
0023   // Memory-scalable (amount of memory required will scale down
0024   // linearly as the number of processes increases) generator, which
0025   // requires an MPI process group.  Run-time is slightly worse than
0026   // the unique rmat generator.  Edge list generated is sorted and
0027   // unique.
0028   template<typename ProcessGroup, typename Distribution,
0029            typename RandomGenerator, typename Graph>
0030   class scalable_rmat_iterator
0031   {
0032       typedef typename graph_traits<Graph>::directed_category directed_category;
0033       typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
0034       typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
0035
0036   public:
0037       typedef std::input_iterator_tag iterator_category;
0038       typedef std::pair<vertices_size_type, vertices_size_type> value_type;
0039       typedef const value_type& reference;
0040       typedef const value_type* pointer;
0041       typedef void difference_type;
0042
0043       // No argument constructor, set to terminating condition
0044       scalable_rmat_iterator()
0045         : gen(), done(true)
0046       { }
0047
0048       // Initialize for edge generation
0049       scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
0050                              RandomGenerator& gen, vertices_size_type n,
0051                              edges_size_type m, double a, double b, double c,
0052                              double d, bool permute_vertices = true)
0053           : gen(), done(false)
0054       {
0055           BOOST_ASSERT(a + b + c + d == 1);
0056           int id = process_id(pg);
0057
0058           this->gen.reset(new uniform_01<RandomGenerator>(gen));
0059
0060           std::vector<vertices_size_type> vertexPermutation;
0061           if (permute_vertices)
0062               generate_permutation_vector(gen, vertexPermutation, n);
0063
0064           int SCALE = int(floor(log(double(n))/log(2.)));
0065           boost::uniform_01<RandomGenerator> prob(gen);
0066
0067           std::map<value_type, bool> edge_map;
0068
0069           edges_size_type generated = 0, local_edges = 0;
0070           do {
0071               edges_size_type tossed = 0;
0072               do {
0073                   vertices_size_type u, v;
0074                   boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
0075
0076                   if (permute_vertices) {
0077                       u = vertexPermutation[u];
0078                       v = vertexPermutation[v];
0079                   }
0080
0081                   // Lowest vertex number always comes first (this
0082                   // means we don't have to worry about i->j and j->i
0083                   // being in the edge list)
0084                   if (u > v && is_same<directed_category, undirected_tag>::value)
0085                       std::swap(u, v);
0086
0087                   if (distrib(u) == id || distrib(v) == id) {
0088                       if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
0089                           edge_map[std::make_pair(u, v)] = true;
0090                           local_edges++;
0091                       } else {
0092                           tossed++;
0093
0094                           // special case - if both u and v are on same
0095                           // proc, ++ twice, since we divide by two (to
0096                           // cover the two process case)
0097                           if (distrib(u) == id && distrib(v) == id)
0098                               tossed++;
0099                       }
0100                   }
0101                   generated++;
0102
0103               } while (generated < m);
0104               tossed = all_reduce(pg, tossed, boost::parallel::sum<vertices_size_type>());
0105               generated -= (tossed / 2);
0106           } while (generated < m);
0107           // NGE - Asking for more than n^2 edges will result in an infinite loop here
0108           //       Asking for a value too close to n^2 edges may as well
0109
0110           values.reserve(local_edges);
0111           typename std::map<value_type, bool>::reverse_iterator em_end = edge_map.rend();
0112           for (typename std::map<value_type, bool>::reverse_iterator em_i = edge_map.rbegin();
0113                em_i != em_end ;
0114                ++em_i) {
0115               values.push_back(em_i->first);
0116           }
0117
0118           current = values.back();
0119           values.pop_back();
0120       }
0121
0122       reference operator*() const { return current; }
0123       pointer operator->() const { return &current; }
0124
0125       scalable_rmat_iterator& operator++()
0126       {
0127           if (!values.empty()) {
0128               current = values.back();
0129               values.pop_back();
0130           } else
0131               done = true;
0132
0133           return *this;
0134       }
0135
0136       scalable_rmat_iterator operator++(int)
0137       {
0138           scalable_rmat_iterator temp(*this);
0139           ++(*this);
0140           return temp;
0141       }
0142
0143       bool operator==(const scalable_rmat_iterator& other) const
0144       {
0145           return values.empty() && other.values.empty() && done && other.done;
0146       }
0147
0148       bool operator!=(const scalable_rmat_iterator& other) const
0149       { return !(*this == other); }
0150
0151   private:
0152
0153       // Parameters
0154       shared_ptr<uniform_01<RandomGenerator> > gen;
0155
0156       // Internal data structures
0157       std::vector<value_type> values;
0158       value_type              current;
0159       bool                    done;
0160   };
0161
0162 } // end namespace boost
0163
0164 #endif // BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP