1 // Copyright 2004, 2005 The Trustees of Indiana University.
2 
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6 
7 //  Authors: Nick Edmonds
8 //           Andrew Lumsdaine
9 #ifndef BOOST_GRAPH_SSCA_GENERATOR_HPP
10 #define BOOST_GRAPH_SSCA_GENERATOR_HPP
11 
12 #include <iterator>
13 #include <utility>
14 #include <vector>
15 #include <queue>
16 #include <boost/config.hpp>
17 #include <boost/random/uniform_int.hpp>
18 #include <boost/graph/graph_traits.hpp>
19 #include <boost/type_traits/is_base_and_derived.hpp>
20 #include <boost/type_traits/is_same.hpp>
21 
22 enum Direction
23 {
24     FORWARD = 1,
25     BACKWARD = 2,
26     BOTH = FORWARD | BACKWARD
27 };
28 
29 namespace boost
30 {
31 
32 // This generator generates graphs according to the method specified
33 // in SSCA 1.1.  Current versions of SSCA use R-MAT graphs
34 
35 template < typename RandomGenerator, typename Graph > class ssca_iterator
36 {
37     typedef typename graph_traits< Graph >::directed_category directed_category;
38     typedef
39         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
40 
41 public:
42     typedef std::input_iterator_tag iterator_category;
43     typedef std::pair< vertices_size_type, vertices_size_type > value_type;
44     typedef const value_type& reference;
45     typedef const value_type* pointer;
46     typedef void difference_type;
47 
48     // No argument constructor, set to terminating condition
ssca_iterator()49     ssca_iterator() : gen(), verticesRemaining(0) {}
50 
51     // Initialize for edge generation
ssca_iterator(RandomGenerator & gen,vertices_size_type totVertices,vertices_size_type maxCliqueSize,double probUnidirectional,int maxParallelEdges,double probIntercliqueEdges)52     ssca_iterator(RandomGenerator& gen, vertices_size_type totVertices,
53         vertices_size_type maxCliqueSize, double probUnidirectional,
54         int maxParallelEdges, double probIntercliqueEdges)
55     : gen(&gen)
56     , totVertices(totVertices)
57     , maxCliqueSize(maxCliqueSize)
58     , probUnidirectional(probUnidirectional)
59     , maxParallelEdges(maxParallelEdges)
60     , probIntercliqueEdges(probIntercliqueEdges)
61     , currentClique(0)
62     , verticesRemaining(totVertices)
63     {
64         cliqueNum = std::vector< int >(totVertices, -1);
65         current = std::make_pair(0, 0);
66     }
67 
operator *() const68     reference operator*() const { return current; }
operator ->() const69     pointer operator->() const { return &current; }
70 
operator ++()71     ssca_iterator& operator++()
72     {
73         BOOST_USING_STD_MIN();
74         while (values.empty() && verticesRemaining > 0)
75         { // If there are no values left, generate a new clique
76             uniform_int< vertices_size_type > clique_size(1, maxCliqueSize);
77             uniform_int< vertices_size_type > rand_vertex(0, totVertices - 1);
78             uniform_int< int > num_parallel_edges(1, maxParallelEdges);
79             uniform_int< short > direction(0, 1);
80             uniform_01< RandomGenerator > prob(*gen);
81             std::vector< vertices_size_type > cliqueVertices;
82 
83             cliqueVertices.clear();
84             vertices_size_type size = min BOOST_PREVENT_MACRO_SUBSTITUTION(
85                 clique_size(*gen), verticesRemaining);
86             while (cliqueVertices.size() < size)
87             {
88                 vertices_size_type v = rand_vertex(*gen);
89                 if (cliqueNum[v] == -1)
90                 {
91                     cliqueNum[v] = currentClique;
92                     cliqueVertices.push_back(v);
93                     verticesRemaining--;
94                 }
95             } // Nick: This is inefficient when only a few vertices remain...
96               //       I should probably just select the remaining vertices
97               //       in order when only a certain fraction remain.
98 
99             typename std::vector< vertices_size_type >::iterator first, second;
100             for (first = cliqueVertices.begin(); first != cliqueVertices.end();
101                  ++first)
102                 for (second = first + 1; second != cliqueVertices.end();
103                      ++second)
104                 {
105                     Direction d;
106                     int edges;
107 
108                     d = prob() < probUnidirectional
109                         ? (direction(*gen) == 0 ? FORWARD : BACKWARD)
110                         : BOTH;
111 
112                     if (d & FORWARD)
113                     {
114                         edges = num_parallel_edges(*gen);
115                         for (int i = 0; i < edges; ++i)
116                             values.push(std::make_pair(*first, *second));
117                     }
118 
119                     if (d & BACKWARD)
120                     {
121                         edges = num_parallel_edges(*gen);
122                         for (int i = 0; i < edges; ++i)
123                             values.push(std::make_pair(*second, *first));
124                     }
125                 }
126 
127             if (verticesRemaining == 0)
128             {
129                 // Generate interclique edges
130                 for (vertices_size_type i = 0; i < totVertices; ++i)
131                 {
132                     double p = probIntercliqueEdges;
133                     for (vertices_size_type d = 2; d < totVertices / 2;
134                          d *= 2, p /= 2)
135                     {
136                         vertices_size_type j = (i + d) % totVertices;
137                         if (cliqueNum[j] != cliqueNum[i] && prob() < p)
138                         {
139                             int edges = num_parallel_edges(*gen);
140                             for (int i = 0; i < edges; ++i)
141                                 values.push(std::make_pair(i, j));
142                         }
143                     }
144                 }
145             }
146 
147             currentClique++;
148         }
149 
150         if (!values.empty())
151         { // If we're not done return a value
152             current = values.front();
153             values.pop();
154         }
155 
156         return *this;
157     }
158 
operator ++(int)159     ssca_iterator operator++(int)
160     {
161         ssca_iterator temp(*this);
162         ++(*this);
163         return temp;
164     }
165 
operator ==(const ssca_iterator & other) const166     bool operator==(const ssca_iterator& other) const
167     {
168         return verticesRemaining == other.verticesRemaining && values.empty()
169             && other.values.empty();
170     }
171 
operator !=(const ssca_iterator & other) const172     bool operator!=(const ssca_iterator& other) const
173     {
174         return !(*this == other);
175     }
176 
177 private:
178     // Parameters
179     RandomGenerator* gen;
180     vertices_size_type totVertices;
181     vertices_size_type maxCliqueSize;
182     double probUnidirectional;
183     int maxParallelEdges;
184     double probIntercliqueEdges;
185 
186     // Internal data structures
187     std::vector< int > cliqueNum;
188     std::queue< value_type > values;
189     int currentClique;
190     vertices_size_type verticesRemaining;
191     value_type current;
192 };
193 
194 } // end namespace boost
195 
196 #endif // BOOST_GRAPH_SSCA_GENERATOR_HPP
197