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
22enum Direction {FORWARD = 1, BACKWARD = 2, BOTH = FORWARD | BACKWARD};
23
24namespace 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 &current; }
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

source code of boost/boost/graph/ssca_graph_generator.hpp