-
Notifications
You must be signed in to change notification settings - Fork 5
/
naive_enumerate_cliques_and_write_to_file.m
136 lines (105 loc) · 5.02 KB
/
naive_enumerate_cliques_and_write_to_file.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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
function [ maxFiltration ] = naive_enumerate_cliques_and_write_to_file( ...
symMatrix, maxCliqueSize, maxDensity, filePrefix )
% ----------------------------------------------------------------
% NAIVE ENUMERATE CLIQUES AND WRITE TO FILE
% written by Chad Giusti, 11/2014
%
% Given a symmetric matrix, naively list all cliques of size under
% the specified limit, along with the filtration level at which that
% clique is complete.
%
% INPUTS:
% symMatrix: the symmetric matrix whose order complex
% we are working with
% maxCliqueSize: maximum size of clique to enumerate
% maxDensity: maximum edge density -- stopping condition
% filePrefix: file prefix for output file
%
% ----------------------------------------------------------------
matrixSize = size(symMatrix, 1);
maxFiltration = ceil(nchoosek(matrixSize,2) * maxDensity);
% ----------------------------------------------------------------
% Put matrix in order canonical form and set entries which lie
% beyond the density threhold to Inf
% ----------------------------------------------------------------
orderCanonicalForm = zeros(matrixSize);
orderedElements = sort(unique(symMatrix(:)), 'descend');
for i=1:matrixSize
for j=i+1:matrixSize
orderCanonicalForm(i,j) = ...
find(orderedElements == symMatrix(i,j), 1, 'first');
if orderCanonicalForm(i,j) > maxFiltration
orderCanonicalForm(i,j) = Inf;
end
end
end
orderCanonicalForm = orderCanonicalForm + orderCanonicalForm';
% ----------------------------------------------------------------
% Create simplex output file and list vertices
% ----------------------------------------------------------------
cliqueFid = fopen(sprintf('%s_simplices.txt',filePrefix), 'w');
fprintf(cliqueFid, '1\n');
for i=1:matrixSize
fprintf(cliqueFid, '%i ', [0 i 1]);
fprintf(cliqueFid, '\n');
end
% ----------------------------------------------------------------
% In order of increasing simplex size, list all simplices that
% appear in the order complex (before the given max density)
% and print them to the file
% ----------------------------------------------------------------
for simplexSize = 2:min(maxCliqueSize, matrixSize)
index = 1:simplexSize;
final = (matrixSize-simplexSize+1):matrixSize;
complete = false;
while ~complete
% ----------------------------------------------------------------
% Starting with the clique 1..simplexSize, take minors of the
% order normal form and find the filtration when they appear.
% ----------------------------------------------------------------
thisMinor = orderCanonicalForm(index,index);
thisFilt = max(max(thisMinor));
if (thisFilt < Inf)
% ------------------------------------------------------------
% If no Inf appears, print this clique and the filtration in
% which is arisees to the file.
% ------------------------------------------------------------
fprintf(cliqueFid, '%i ', [simplexSize-1 index thisFilt]);
fprintf(cliqueFid, '\n');
incIndex = find(index < final, 1, 'last');
else
% ------------------------------------------------------------
% If an Inf appears, skip all minors that would include that
% same entry, since those cliques all appear after the density
% threshold
% ------------------------------------------------------------
[infrow, infcol] = find(thisMinor == Inf, 1, 'last');
incIndex = min(max(infrow, infcol),...
find(index < final, 1, 'last'));
end
% ----------------------------------------------------------------
% Increment the minor indices and see if the process is complete
% ----------------------------------------------------------------
index(incIndex:end) = ...
(index(incIndex)+1):(index(incIndex)+simplexSize-incIndex+1);
if (index(1) > matrixSize - simplexSize)
% ------------------------------------------------------------
% We've reached the final possible clique. See if we need
% to output it and then exit the loop.
% ------------------------------------------------------------
thisMinor = orderCanonicalForm(index,index);
thisFilt = max(max(thisMinor));
if (thisFilt < Inf)
% ------------------------------------------------------------
% If no Inf appears, print this clique and the filtration in
% which is arises to the file.
% ------------------------------------------------------------
fprintf(cliqueFid, '%i ', [simplexSize-1 index thisFilt]);
fprintf(cliqueFid, '\n');
end
complete = true;
end
end
end
fclose(cliqueFid);
end