-
Notifications
You must be signed in to change notification settings - Fork 0
/
kronecker_generator.m
58 lines (48 loc) · 1.6 KB
/
kronecker_generator.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
function ijw = kronecker_generator (SCALE, edgefactor)
%% Generate an edgelist according to the Graph500 parameters. In this
%% sample, the edge list is returned in an array with three rows,
%% where StartVertex is first row, EndVertex is the second row, and
%% Weight is the third row. The vertex labels start at zero.
%%
%% Example, creating a sparse matrix for viewing:
%% ijw = kronecker_generator (10, 16);
%% G = sparse (ijw(1,:)+1, ijw(2,:)+1, ones (1, size (ijw, 2)));
%% spy (G);
%% The spy plot should appear fairly dense. Any locality
%% is removed by the final permutations.
%% Set number of vertices.
N = 2^SCALE;
%% Set number of edges.
M = edgefactor * N;
%% Set initiator probabilities.
[A, B, C] = deal (0.57, 0.19, 0.19);
%% Create index arrays.
ijw = ones (3, M);
%% Loop over each order of bit.
ab = A + B;
c_norm = C/(1 - (A + B));
a_norm = A/(A + B);
for ib = 1:SCALE,
%% Compare with probabilities and set bits of indices.
ii_bit = rand (1, M) > ab;
jj_bit = rand (1, M) > ( c_norm * ii_bit + a_norm * not (ii_bit) );
ijw(1:2,:) = ijw(1:2,:) + 2^(ib-1) * [ii_bit; jj_bit];
end
%% Generate weights
% ijw(3,:) = unifrnd(0, 1, M);
ijw(3,:) = unifrnd(0, 1, M, 1);
%% Permute vertex labels
p = randperm (N);
ijw(1:2,:) = p(ijw(1:2,:));
%% Permute the edge list
p = randperm (M);
ijw = ijw(:, p);
%% Adjust to zero-based labels.
ijw(1:2,:) = ijw(1:2,:) - 1;
%% Print graph to file
fileID = fopen(sprintf('graph_%d_%d.txt', edgefactor, SCALE),'w');
for i = 1:M
fprintf(fileID, '%d %d\n', ijw(1:2, i));
end
fclose(fileID);
end