boost/graph/ssca_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_SSCA_GENERATOR_HPP
0010 #define BOOST_GRAPH_SSCA_GENERATOR_HPP
0011
0012 #include <iterator>
0013 #include <utility>
0014 #include <vector>
0015 #include <queue>
0016 #include <boost/config.hpp>
0017 #include <boost/random/uniform_int.hpp>
0018 #include <boost/graph/graph_traits.hpp>
0019 #include <boost/type_traits/is_base_and_derived.hpp>
0020 #include <boost/type_traits/is_same.hpp>
0021
0022 enum Direction
0023 {
0024     FORWARD = 1,
0025     BACKWARD = 2,
0026     BOTH = FORWARD | BACKWARD
0027 };
0028
0029 namespace boost
0030 {
0031
0032 // This generator generates graphs according to the method specified
0033 // in SSCA 1.1.  Current versions of SSCA use R-MAT graphs
0034
0035 template < typename RandomGenerator, typename Graph > class ssca_iterator
0036 {
0037     typedef typename graph_traits< Graph >::directed_category directed_category;
0038     typedef
0039         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
0040
0041 public:
0042     typedef std::input_iterator_tag iterator_category;
0043     typedef std::pair< vertices_size_type, vertices_size_type > value_type;
0044     typedef const value_type& reference;
0045     typedef const value_type* pointer;
0046     typedef void difference_type;
0047
0048     // No argument constructor, set to terminating condition
0049     ssca_iterator() : gen(), verticesRemaining(0) {}
0050
0051     // Initialize for edge generation
0052     ssca_iterator(RandomGenerator& gen, vertices_size_type totVertices,
0053         vertices_size_type maxCliqueSize, double probUnidirectional,
0054         int maxParallelEdges, double probIntercliqueEdges)
0055     : gen(&gen)
0056     , totVertices(totVertices)
0057     , maxCliqueSize(maxCliqueSize)
0058     , probUnidirectional(probUnidirectional)
0059     , maxParallelEdges(maxParallelEdges)
0060     , probIntercliqueEdges(probIntercliqueEdges)
0061     , currentClique(0)
0062     , verticesRemaining(totVertices)
0063     {
0064         cliqueNum = std::vector< int >(totVertices, -1);
0065         current = std::make_pair(0, 0);
0066     }
0067
0068     reference operator*() const { return current; }
0069     pointer operator->() const { return &current; }
0070
0071     ssca_iterator& operator++()
0072     {
0073         BOOST_USING_STD_MIN();
0074         while (values.empty() && verticesRemaining > 0)
0075         { // If there are no values left, generate a new clique
0076             uniform_int< vertices_size_type > clique_size(1, maxCliqueSize);
0077             uniform_int< vertices_size_type > rand_vertex(0, totVertices - 1);
0078             uniform_int< int > num_parallel_edges(1, maxParallelEdges);
0079             uniform_int< short > direction(0, 1);
0080             uniform_01< RandomGenerator > prob(*gen);
0081             std::vector< vertices_size_type > cliqueVertices;
0082
0083             cliqueVertices.clear();
0084             vertices_size_type size = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0085                 clique_size(*gen), verticesRemaining);
0086             while (cliqueVertices.size() < size)
0087             {
0088                 vertices_size_type v = rand_vertex(*gen);
0089                 if (cliqueNum[v] == -1)
0090                 {
0091                     cliqueNum[v] = currentClique;
0092                     cliqueVertices.push_back(v);
0093                     verticesRemaining--;
0094                 }
0095             } // Nick: This is inefficient when only a few vertices remain...
0096               //       I should probably just select the remaining vertices
0097               //       in order when only a certain fraction remain.
0098
0099             typename std::vector< vertices_size_type >::iterator first, second;
0100             for (first = cliqueVertices.begin(); first != cliqueVertices.end();
0101                  ++first)
0102                 for (second = first + 1; second != cliqueVertices.end();
0103                      ++second)
0104                 {
0105                     Direction d;
0106                     int edges;
0107
0108                     d = prob() < probUnidirectional
0109                         ? (direction(*gen) == 0 ? FORWARD : BACKWARD)
0110                         : BOTH;
0111
0112                     if (d & FORWARD)
0113                     {
0114                         edges = num_parallel_edges(*gen);
0115                         for (int i = 0; i < edges; ++i)
0116                             values.push(std::make_pair(*first, *second));
0117                     }
0118
0119                     if (d & BACKWARD)
0120                     {
0121                         edges = num_parallel_edges(*gen);
0122                         for (int i = 0; i < edges; ++i)
0123                             values.push(std::make_pair(*second, *first));
0124                     }
0125                 }
0126
0127             if (verticesRemaining == 0)
0128             {
0129                 // Generate interclique edges
0130                 for (vertices_size_type i = 0; i < totVertices; ++i)
0131                 {
0132                     double p = probIntercliqueEdges;
0133                     for (vertices_size_type d = 2; d < totVertices / 2;
0134                          d *= 2, p /= 2)
0135                     {
0136                         vertices_size_type j = (i + d) % totVertices;
0137                         if (cliqueNum[j] != cliqueNum[i] && prob() < p)
0138                         {
0139                             int edges = num_parallel_edges(*gen);
0140                             for (int i = 0; i < edges; ++i)
0141                                 values.push(std::make_pair(i, j));
0142                         }
0143                     }
0144                 }
0145             }
0146
0147             currentClique++;
0148         }
0149
0150         if (!values.empty())
0151         { // If we're not done return a value
0152             current = values.front();
0153             values.pop();
0154         }
0155
0156         return *this;
0157     }
0158
0159     ssca_iterator operator++(int)
0160     {
0161         ssca_iterator temp(*this);
0162         ++(*this);
0163         return temp;
0164     }
0165
0166     bool operator==(const ssca_iterator& other) const
0167     {
0168         return verticesRemaining == other.verticesRemaining && values.empty()
0169             && other.values.empty();
0170     }
0171
0172     bool operator!=(const ssca_iterator& other) const
0173     {
0174         return !(*this == other);
0175     }
0176
0177 private:
0178     // Parameters
0179     RandomGenerator* gen;
0180     vertices_size_type totVertices;
0181     vertices_size_type maxCliqueSize;
0182     double probUnidirectional;
0183     int maxParallelEdges;
0184     double probIntercliqueEdges;
0185
0186     // Internal data structures
0187     std::vector< int > cliqueNum;
0188     std::queue< value_type > values;
0189     int currentClique;
0190     vertices_size_type verticesRemaining;
0191     value_type current;
0192 };
0193
0194 } // end namespace boost
0195
0196 #endif // BOOST_GRAPH_SSCA_GENERATOR_HPP