Chris@16: // Copyright 2004, 2005 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Nick Edmonds
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP
Chris@16: #define BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/graph/parallel/algorithm.hpp>
Chris@16: #include <boost/graph/parallel/process_group.hpp>
Chris@16: #include <math.h>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   // Memory-scalable (amount of memory required will scale down
Chris@16:   // linearly as the number of processes increases) generator, which
Chris@16:   // requires an MPI process group.  Run-time is slightly worse than
Chris@16:   // the unique rmat generator.  Edge list generated is sorted and
Chris@16:   // unique.
Chris@16:   template<typename ProcessGroup, typename Distribution, 
Chris@16:            typename RandomGenerator, typename Graph>
Chris@16:   class scalable_rmat_iterator
Chris@16:   {
Chris@16:       typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:       typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:       typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:   public:
Chris@16:       typedef std::input_iterator_tag iterator_category;
Chris@16:       typedef std::pair<vertices_size_type, vertices_size_type> value_type;
Chris@16:       typedef const value_type& reference;
Chris@16:       typedef const value_type* pointer;
Chris@16:       typedef void difference_type;
Chris@16: 
Chris@16:       // No argument constructor, set to terminating condition
Chris@16:       scalable_rmat_iterator()
Chris@16:         : gen(), done(true)
Chris@16:       { }
Chris@16: 
Chris@16:       // Initialize for edge generation
Chris@16:       scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
Chris@16:                              RandomGenerator& gen, vertices_size_type n, 
Chris@16:                              edges_size_type m, double a, double b, double c, 
Chris@16:                              double d, bool permute_vertices = true)
Chris@16:           : gen(), done(false)
Chris@16:       {
Chris@16:           BOOST_ASSERT(a + b + c + d == 1);
Chris@16:           int id = process_id(pg);
Chris@16: 
Chris@16:           this->gen.reset(new uniform_01<RandomGenerator>(gen));
Chris@16: 
Chris@16:           std::vector<vertices_size_type> vertexPermutation;
Chris@16:           if (permute_vertices) 
Chris@16:               generate_permutation_vector(gen, vertexPermutation, n);
Chris@16: 
Chris@16:           int SCALE = int(floor(log(double(n))/log(2.)));
Chris@16:           boost::uniform_01<RandomGenerator> prob(gen);
Chris@16:       
Chris@16:           std::map<value_type, bool> edge_map;
Chris@16: 
Chris@16:           edges_size_type generated = 0, local_edges = 0;
Chris@16:           do {
Chris@16:               edges_size_type tossed = 0;
Chris@16:               do {
Chris@16:                   vertices_size_type u, v;
Chris@16:                   boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
Chris@16: 
Chris@16:                   if (permute_vertices) {
Chris@16:                       u = vertexPermutation[u];
Chris@16:                       v = vertexPermutation[v];
Chris@16:                   }
Chris@16: 
Chris@16:                   // Lowest vertex number always comes first (this
Chris@16:                   // means we don't have to worry about i->j and j->i
Chris@16:                   // being in the edge list)
Chris@16:                   if (u > v && is_same<directed_category, undirected_tag>::value)
Chris@16:                       std::swap(u, v);
Chris@16: 
Chris@16:                   if (distrib(u) == id || distrib(v) == id) {
Chris@16:                       if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
Chris@16:                           edge_map[std::make_pair(u, v)] = true;
Chris@16:                           local_edges++;
Chris@16:                       } else {
Chris@16:                           tossed++;
Chris@16: 
Chris@16:                           // special case - if both u and v are on same
Chris@16:                           // proc, ++ twice, since we divide by two (to
Chris@16:                           // cover the two process case)
Chris@16:                           if (distrib(u) == id && distrib(v) == id)
Chris@16:                               tossed++;
Chris@16:                       }
Chris@16:                   }
Chris@16:                   generated++;
Chris@16: 
Chris@16:               } while (generated < m);
Chris@16:               tossed = all_reduce(pg, tossed, boost::parallel::sum<vertices_size_type>());
Chris@16:               generated -= (tossed / 2);
Chris@16:           } while (generated < m);
Chris@16:           // NGE - Asking for more than n^2 edges will result in an infinite loop here
Chris@16:           //       Asking for a value too close to n^2 edges may as well
Chris@16: 
Chris@16:           values.reserve(local_edges);
Chris@16:           typename std::map<value_type, bool>::reverse_iterator em_end = edge_map.rend();
Chris@16:           for (typename std::map<value_type, bool>::reverse_iterator em_i = edge_map.rbegin();
Chris@16:                em_i != em_end ;
Chris@16:                ++em_i) {
Chris@16:               values.push_back(em_i->first);
Chris@16:           }
Chris@16: 
Chris@16:           current = values.back();
Chris@16:           values.pop_back();
Chris@16:       }
Chris@16: 
Chris@16:       reference operator*() const { return current; }
Chris@16:       pointer operator->() const { return &current; }
Chris@16:     
Chris@16:       scalable_rmat_iterator& operator++()
Chris@16:       {
Chris@16:           if (!values.empty()) {
Chris@16:               current = values.back();
Chris@16:               values.pop_back();
Chris@16:           } else 
Chris@16:               done = true;
Chris@16: 
Chris@16:           return *this;
Chris@16:       }
Chris@16: 
Chris@16:       scalable_rmat_iterator operator++(int)
Chris@16:       {
Chris@16:           scalable_rmat_iterator temp(*this);
Chris@16:           ++(*this);
Chris@16:           return temp;
Chris@16:       }
Chris@16: 
Chris@16:       bool operator==(const scalable_rmat_iterator& other) const
Chris@16:       {
Chris@16:           return values.empty() && other.values.empty() && done && other.done;
Chris@16:       }
Chris@16: 
Chris@16:       bool operator!=(const scalable_rmat_iterator& other) const
Chris@16:       { return !(*this == other); }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:       // Parameters
Chris@16:       shared_ptr<uniform_01<RandomGenerator> > gen;
Chris@16: 
Chris@16:       // Internal data structures
Chris@16:       std::vector<value_type> values;
Chris@16:       value_type              current;
Chris@16:       bool                    done;
Chris@16:   };
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP