]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(0,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 |