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 ¤t; } 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