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_SSCA_GENERATOR_HPP
Chris@16: #define BOOST_GRAPH_SSCA_GENERATOR_HPP
Chris@16: 
Chris@16: #include <iterator>
Chris@16: #include <utility>
Chris@16: #include <vector>
Chris@16: #include <queue>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/random/uniform_int.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/type_traits/is_base_and_derived.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: 
Chris@16: enum Direction {FORWARD = 1, BACKWARD = 2, BOTH = FORWARD | BACKWARD};
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   // This generator generates graphs according to the method specified
Chris@16:   // in SSCA 1.1.  Current versions of SSCA use R-MAT graphs
Chris@16: 
Chris@16:   template<typename RandomGenerator, typename Graph>
Chris@16:   class ssca_iterator
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type 
Chris@16:       vertices_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:     ssca_iterator()
Chris@16:       : gen(), verticesRemaining(0) { }
Chris@16: 
Chris@16:     // Initialize for edge generation
Chris@16:     ssca_iterator(RandomGenerator& gen, vertices_size_type totVertices, 
Chris@16:                   vertices_size_type maxCliqueSize, double probUnidirectional, 
Chris@16:                   int maxParallelEdges, double probIntercliqueEdges) 
Chris@16:       : gen(&gen), totVertices(totVertices), maxCliqueSize(maxCliqueSize), 
Chris@16:         probUnidirectional(probUnidirectional), maxParallelEdges(maxParallelEdges),
Chris@16:         probIntercliqueEdges(probIntercliqueEdges), currentClique(0), 
Chris@16:         verticesRemaining(totVertices)
Chris@16:     { 
Chris@16:       cliqueNum = std::vector<int>(totVertices, -1);
Chris@16:       current = std::make_pair(0,0);
Chris@16:     }
Chris@16: 
Chris@16:     reference operator*() const { return current; }
Chris@16:     pointer operator->() const { return &current; }
Chris@16:     
Chris@16:     ssca_iterator& operator++()
Chris@16:     {
Chris@16:       BOOST_USING_STD_MIN();
Chris@16:       while (values.empty() && verticesRemaining > 0) { // If there are no values left, generate a new clique
Chris@16:         uniform_int<vertices_size_type> clique_size(1, maxCliqueSize);
Chris@16:         uniform_int<vertices_size_type> rand_vertex(0, totVertices-1);
Chris@16:         uniform_int<int> num_parallel_edges(1, maxParallelEdges);
Chris@16:         uniform_int<short> direction(0,1);
Chris@16:         uniform_01<RandomGenerator> prob(*gen);
Chris@16:         std::vector<vertices_size_type> cliqueVertices;
Chris@16: 
Chris@16:         cliqueVertices.clear();
Chris@16:         vertices_size_type size = min BOOST_PREVENT_MACRO_SUBSTITUTION (clique_size(*gen), verticesRemaining);
Chris@16:         while (cliqueVertices.size() < size) {
Chris@16:           vertices_size_type v = rand_vertex(*gen);
Chris@16:           if (cliqueNum[v] == -1) {
Chris@16:             cliqueNum[v] = currentClique;
Chris@16:             cliqueVertices.push_back(v);
Chris@16:             verticesRemaining--;
Chris@16:           }
Chris@16:         }  // Nick: This is inefficient when only a few vertices remain...
Chris@16:            //       I should probably just select the remaining vertices 
Chris@16:            //       in order when only a certain fraction remain.
Chris@16: 
Chris@16:         typename std::vector<vertices_size_type>::iterator first, second;
Chris@16:         for (first = cliqueVertices.begin(); first != cliqueVertices.end(); ++first)
Chris@16:           for (second = first+1; second != cliqueVertices.end(); ++second) {
Chris@16:             Direction d;
Chris@16:             int edges;
Chris@16: 
Chris@16:             d = prob() < probUnidirectional ? (direction(*gen) == 0 ? FORWARD : BACKWARD) : BOTH;
Chris@16: 
Chris@16:             if (d & FORWARD) {
Chris@16:               edges = num_parallel_edges(*gen);
Chris@16:               for (int i = 0; i < edges; ++i)
Chris@16:                 values.push(std::make_pair(*first, *second));
Chris@16:             }
Chris@16:               
Chris@16:             if (d & BACKWARD) {
Chris@16:               edges = num_parallel_edges(*gen);
Chris@16:               for (int i = 0; i < edges; ++i)
Chris@16:                 values.push(std::make_pair(*second, *first));
Chris@16:             }
Chris@16:           }
Chris@16: 
Chris@16:         if (verticesRemaining == 0) {
Chris@16:           // Generate interclique edges
Chris@16:           for (vertices_size_type i = 0; i < totVertices; ++i) {
Chris@16:             double p = probIntercliqueEdges;
Chris@16:             for (vertices_size_type d = 2; d < totVertices/2; d *= 2, p/= 2) {
Chris@16:               vertices_size_type j = (i+d) % totVertices;
Chris@16:               if (cliqueNum[j] != cliqueNum[i] && prob() < p) {
Chris@16:                 int edges = num_parallel_edges(*gen);
Chris@16:                 for (int i = 0; i < edges; ++i)
Chris@16:                   values.push(std::make_pair(i, j));
Chris@16:               }
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         currentClique++;
Chris@16:       } 
Chris@16: 
Chris@16:       if (!values.empty()) { // If we're not done return a value
Chris@16:         current = values.front();
Chris@16:         values.pop();
Chris@16:       }
Chris@16: 
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     ssca_iterator operator++(int)
Chris@16:     {
Chris@16:       ssca_iterator temp(*this);
Chris@16:       ++(*this);
Chris@16:       return temp;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const ssca_iterator& other) const
Chris@16:     {
Chris@16:       return verticesRemaining == other.verticesRemaining && values.empty() && other.values.empty();
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(const ssca_iterator& other) const
Chris@16:     { return !(*this == other); }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     // Parameters
Chris@16:     RandomGenerator* gen;
Chris@16:     vertices_size_type totVertices;
Chris@16:     vertices_size_type maxCliqueSize;
Chris@16:     double probUnidirectional;
Chris@16:     int maxParallelEdges;
Chris@16:     double probIntercliqueEdges;
Chris@16: 
Chris@16:     // Internal data structures
Chris@16:     std::vector<int> cliqueNum;
Chris@16:     std::queue<value_type> values;
Chris@16:     int currentClique;
Chris@16:     vertices_size_type verticesRemaining;
Chris@16:     value_type current;
Chris@16:   };
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_SSCA_GENERATOR_HPP