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 {FORWARD = 1, BACKWARD = 2, BOTH = FORWARD | BACKWARD}; |
23 | |
24 | namespace boost { |
25 | |
26 | // This generator generates graphs according to the method specified |
27 | // in SSCA 1.1. Current versions of SSCA use R-MAT graphs |
28 | |
29 | template<typename RandomGenerator, typename Graph> |
30 | class ssca_iterator |
31 | { |
32 | typedef typename graph_traits<Graph>::directed_category directed_category; |
33 | typedef typename graph_traits<Graph>::vertices_size_type |
34 | vertices_size_type; |
35 | |
36 | public: |
37 | typedef std::input_iterator_tag iterator_category; |
38 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; |
39 | typedef const value_type& reference; |
40 | typedef const value_type* pointer; |
41 | typedef void difference_type; |
42 | |
43 | // No argument constructor, set to terminating condition |
44 | ssca_iterator() |
45 | : gen(), verticesRemaining(0) { } |
46 | |
47 | // Initialize for edge generation |
48 | ssca_iterator(RandomGenerator& gen, vertices_size_type totVertices, |
49 | vertices_size_type maxCliqueSize, double probUnidirectional, |
50 | int maxParallelEdges, double probIntercliqueEdges) |
51 | : gen(&gen), totVertices(totVertices), maxCliqueSize(maxCliqueSize), |
52 | probUnidirectional(probUnidirectional), maxParallelEdges(maxParallelEdges), |
53 | probIntercliqueEdges(probIntercliqueEdges), currentClique(0), |
54 | verticesRemaining(totVertices) |
55 | { |
56 | cliqueNum = std::vector<int>(totVertices, -1); |
57 | current = std::make_pair(x: 0,y: 0); |
58 | } |
59 | |
60 | reference operator*() const { return current; } |
61 | pointer operator->() const { return ¤t; } |
62 | |
63 | ssca_iterator& operator++() |
64 | { |
65 | BOOST_USING_STD_MIN(); |
66 | while (values.empty() && verticesRemaining > 0) { // If there are no values left, generate a new clique |
67 | uniform_int<vertices_size_type> clique_size(1, maxCliqueSize); |
68 | uniform_int<vertices_size_type> rand_vertex(0, totVertices-1); |
69 | uniform_int<int> num_parallel_edges(1, maxParallelEdges); |
70 | uniform_int<short> direction(0,1); |
71 | uniform_01<RandomGenerator> prob(*gen); |
72 | std::vector<vertices_size_type> cliqueVertices; |
73 | |
74 | cliqueVertices.clear(); |
75 | vertices_size_type size = min BOOST_PREVENT_MACRO_SUBSTITUTION (clique_size(*gen), verticesRemaining); |
76 | while (cliqueVertices.size() < size) { |
77 | vertices_size_type v = rand_vertex(*gen); |
78 | if (cliqueNum[v] == -1) { |
79 | cliqueNum[v] = currentClique; |
80 | cliqueVertices.push_back(v); |
81 | verticesRemaining--; |
82 | } |
83 | } // Nick: This is inefficient when only a few vertices remain... |
84 | // I should probably just select the remaining vertices |
85 | // in order when only a certain fraction remain. |
86 | |
87 | typename std::vector<vertices_size_type>::iterator first, second; |
88 | for (first = cliqueVertices.begin(); first != cliqueVertices.end(); ++first) |
89 | for (second = first+1; second != cliqueVertices.end(); ++second) { |
90 | Direction d; |
91 | int edges; |
92 | |
93 | d = prob() < probUnidirectional ? (direction(*gen) == 0 ? FORWARD : BACKWARD) : BOTH; |
94 | |
95 | if (d & FORWARD) { |
96 | edges = num_parallel_edges(*gen); |
97 | for (int i = 0; i < edges; ++i) |
98 | values.push(std::make_pair(*first, *second)); |
99 | } |
100 | |
101 | if (d & BACKWARD) { |
102 | edges = num_parallel_edges(*gen); |
103 | for (int i = 0; i < edges; ++i) |
104 | values.push(std::make_pair(*second, *first)); |
105 | } |
106 | } |
107 | |
108 | if (verticesRemaining == 0) { |
109 | // Generate interclique edges |
110 | for (vertices_size_type i = 0; i < totVertices; ++i) { |
111 | double p = probIntercliqueEdges; |
112 | for (vertices_size_type d = 2; d < totVertices/2; d *= 2, p/= 2) { |
113 | vertices_size_type j = (i+d) % totVertices; |
114 | if (cliqueNum[j] != cliqueNum[i] && prob() < p) { |
115 | int edges = num_parallel_edges(*gen); |
116 | for (int i = 0; i < edges; ++i) |
117 | values.push(std::make_pair(i, j)); |
118 | } |
119 | } |
120 | } |
121 | } |
122 | |
123 | currentClique++; |
124 | } |
125 | |
126 | if (!values.empty()) { // If we're not done return a value |
127 | current = values.front(); |
128 | values.pop(); |
129 | } |
130 | |
131 | return *this; |
132 | } |
133 | |
134 | ssca_iterator operator++(int) |
135 | { |
136 | ssca_iterator temp(*this); |
137 | ++(*this); |
138 | return temp; |
139 | } |
140 | |
141 | bool operator==(const ssca_iterator& other) const |
142 | { |
143 | return verticesRemaining == other.verticesRemaining && values.empty() && other.values.empty(); |
144 | } |
145 | |
146 | bool operator!=(const ssca_iterator& other) const |
147 | { return !(*this == other); } |
148 | |
149 | private: |
150 | |
151 | // Parameters |
152 | RandomGenerator* gen; |
153 | vertices_size_type totVertices; |
154 | vertices_size_type maxCliqueSize; |
155 | double probUnidirectional; |
156 | int maxParallelEdges; |
157 | double probIntercliqueEdges; |
158 | |
159 | // Internal data structures |
160 | std::vector<int> cliqueNum; |
161 | std::queue<value_type> values; |
162 | int currentClique; |
163 | vertices_size_type verticesRemaining; |
164 | value_type current; |
165 | }; |
166 | |
167 | } // end namespace boost |
168 | |
169 | #endif // BOOST_GRAPH_SSCA_GENERATOR_HPP |
170 | |