SSCA Generator (Input Iterator)
Generate graphs following the Scalable Synthetic Compact Applications (SSCA#2) benchmark model.
Defined in: <boost/graph/ssca_graph_generator.hpp>
Synopsis
template <typename RandomGenerator, typename Graph>
class ssca_iterator;
ssca_iterator();
ssca_iterator(RandomGenerator& gen, vertices_size_type totVertices, vertices_size_type maxCliqueSize, double probUnidirectional, int maxParallelEdges, double probIntercliqueEdges);The SSCA#2 benchmark generates graphs with a clustered structure: dense cliques connected by sparse inter-clique edges. This models certain real-world networks such as social graphs.
The generator first creates random cliques of varying sizes (up to
maxCliqueSize), assigning every vertex to exactly one clique. Within each
clique, edges between all pairs of vertices are created, with direction
controlled by probUnidirectional. After all cliques are formed,
inter-clique edges are added with geometrically decreasing probability.
Parameters
| Direction | Parameter | Description |
|---|---|---|
IN |
|
A random number generator. |
IN |
|
Total number of vertices. |
IN |
|
Maximum size of generated cliques. |
IN |
|
Probability that an intra-clique edge is unidirectional (one direction only). Otherwise both directions are created. |
IN |
|
Maximum number of parallel edges between two vertices (chosen uniformly in [1, maxParallelEdges]). |
IN |
|
Base probability of generating inter-clique edges. Halved for each doubling of distance. |
Example
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/ssca_graph_generator.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>
int main() {
using namespace boost;
using Graph = adjacency_list<>;
using SSCAGen = ssca_iterator<mt19937, Graph>;
mt19937 gen(42);
int max_clique_size = 3;
double prob_unidirectional = 0.5;
int max_parallel_edges = 1;
double prob_interclique = 0.1;
Graph g(SSCAGen(gen, 8, max_clique_size, prob_unidirectional, max_parallel_edges, prob_interclique), SSCAGen(), 8);
std::cout << num_vertices(g) << " vertices, " << num_edges(g) << " edges\n";
for (auto e : make_iterator_range(edges(g))) {
std::cout << " " << source(e, g) << " -> " << target(e, g) << "\n";
}
}8 vertices, 9 edges
0 -> 0
0 -> 7
1 -> 4
1 -> 3
3 -> 4
3 -> 1
4 -> 1
4 -> 3
6 -> 7