1function comparisonData = compareAll(trials)
2    if (nargin < 1 || trials < 1)
3        trials = 5;
4    end
5
6    try
7        load('mongoose_data.mat');
8    catch fileNotFound
9        save('mongoose_data.mat');
10        comparisonData = {};
11        lastMatrixCompleted = 0;
12        j = 1;
13    end
14
15    index = ssget;
16    % Sort by nnz
17    nnzs = index.nnz;
18    [~,ids] = sortrows(nnzs');
19
20    for i = ids'
21        % Skip specific problematic matrices
22        if (i == 1772 || i == 2177 || i == 2249)
23            continue;
24        end
25
26        found = ID_present(comparisonData,i);
27        if (index.isReal(i) && ~found)
28            Prob = ssget(i);
29            A = Prob.A;
30
31            fprintf('Computing separator for %d: %s\n', i, Prob.name);
32
33            [~, n_cols] = size(A);
34
35            % If matrix is unsymmetric, form the augmented system
36            if (index.numerical_symmetry(i) < 1)
37                [m_rows, n_cols] = size(A);
38                A = [sparse(m_rows,m_rows) A; A' sparse(n_cols,n_cols)];
39            end
40
41            for use_weights = 0:1
42
43                % Sanitize the matrix (remove diagonal, make symmetric)
44                A = sanitize(A, ~use_weights);
45
46                % If the sanitization removed all vertices, skip this matrix
47                if nnz(A) < 2
48                    comparisonData(j).problem_id = Prob.id;
49                    j = j+1;
50                    continue;
51                end
52
53                % Run Mongoose with various options to partition the graph.
54                for guessCutType = 0:2
55
56                    for doCommunityMatching = 0:1
57
58                        for matchingStrategy = 3:-1:0
59                            % Community matching does not affect matching
60                            % strategies Random or HEM
61                            if (doCommunityMatching == 1 && (matchingStrategy == 0 || matchingStrategy == 1))
62                                continue;
63                            end
64
65                            % if highest degree > 10*sqrt(n), skip Random/HEM
66                            if (max(sum(sign(A))) > 10*sqrt(n_cols))
67                                if (matchingStrategy == 0 || matchingStrategy == 1)
68                                    continue;
69                                end
70                            end
71
72                            for coarsenLimit = [64, 256, 1024]
73                                comparisonData(j).mongoose = 1;
74                                comparisonData(j).problem_id = Prob.id;
75                                comparisonData(j).problem_name = Prob.name;
76                                comparisonData(j).problem_kind = Prob.kind;
77                                comparisonData(j).problem_nnz = nnz(A);
78                                comparisonData(j).problem_n = n_cols;
79                                comparisonData(j).useWeights = use_weights;
80                                comparisonData(j).guessCutType = guessCutType;
81                                comparisonData(j).doCommunityMatching = doCommunityMatching;
82                                comparisonData(j).matchingStrategy = matchingStrategy;
83                                comparisonData(j).coarsenLimit = coarsenLimit;
84
85                                fprintf('name = %s\n', Prob.name);
86                                fprintf('use_weights = %d\n', use_weights);
87                                fprintf('guessCutType = %d\n', guessCutType);
88                                fprintf('doCommunityMatching = %d\n', doCommunityMatching);
89                                fprintf('matchingStrategy = %d\n', matchingStrategy);
90                                fprintf('coarsenLimit = %d\n', coarsenLimit);
91
92                                for k = 1:trials
93                                    % Set up options struct for this run
94                                    O = edgecut_options();
95                                    O.randomSeed = 123456789;
96                                    O.guessCutType = guessCutType;
97                                    O.doCommunityMatching = doCommunityMatching;
98                                    O.matchingStrategy = matchingStrategy;
99                                    O.coarsenLimit = coarsenLimit;
100
101                                    tic;
102                                    partition = edgecut(A,O);
103                                    t = toc;
104
105                                    fprintf('Mongoose: %0.2f\n', t);
106                                    mongoose_times(j, k) = t;
107                                    part_A = find(partition);
108                                    part_B = find(1-partition);
109                                    perm = [part_A part_B];
110                                    p = length(part_A);
111                                    A_perm = A(perm, perm);
112                                    mongoose_cut_weight(j, k) = sum(sum(A_perm((p+1):n_cols, 1:p)));
113                                    mongoose_cut_size(j, k) = sum(sum(sign(A_perm((p+1):n_cols, 1:p))));
114                                    mongoose_imbalance(j, k) = abs(0.5-(length(part_A)/(length(part_A) + length(part_B))));
115                                    % If it took more than 30 minutes, only
116                                    % run once.
117                                    if (t > 1800)
118                                        break;
119                                    end
120                                end
121
122                                comparisonData(j).time = trimmean(mongoose_times(j, 1:k), 40);
123                                comparisonData(j).cutWeight = trimmean(mongoose_cut_weight(j, 1:k), 40);
124                                comparisonData(j).cutSize = trimmean(mongoose_cut_size(j, 1:k), 40);
125                                comparisonData(j).cutImbalance = trimmean(mongoose_imbalance(j, 1:k), 40);
126                                j = j+1;
127                            end
128                        end
129                    end
130                end
131
132                % Run METIS to partition the graph.
133                for k = 1:trials
134                    tic;
135                    [part_A,part_B] = metispart(A, 0, 123456789);
136                    t = toc;
137                    fprintf('METIS:    %0.2f\n', t);
138                    metis_times(j, k) = t;
139                    p = length(part_A);
140                    perm = [part_A part_B];
141                    A_perm = A(perm, perm);
142                    metis_cut_weight(j, k) = sum(sum(A_perm((p+1):n_cols, 1:p)));
143                    metis_cut_size(j, k) = sum(sum(sign(A_perm((p+1):n_cols, 1:p))));
144                    metis_imbalance(j, k) = abs(0.5-(length(part_A)/(length(part_A) + length(part_B))));
145                end
146                comparisonData(j).problem_id = Prob.id;
147                comparisonData(j).problem_name = Prob.name;
148                comparisonData(j).problem_kind = Prob.kind;
149                comparisonData(j).problem_nnz = nnz(A);
150                comparisonData(j).problem_n = n_cols;
151                comparisonData(j).useWeights = use_weights;
152                comparisonData(j).mongoose = 0;
153                comparisonData(j).time = trimmean(metis_times(j, 1:k), 40);
154                comparisonData(j).cutWeight = trimmean(metis_cut_weight(j, 1:k), 40);
155                comparisonData(j).cutSize = trimmean(metis_cut_size(j, 1:k), 40);
156                comparisonData(j).cutImbalance = trimmean(metis_imbalance(j, 1:k), 40);
157                j = j+1;
158            end
159        end
160        lastMatrixCompleted = i;
161        save('mongoose_data.mat');
162    end
163
164    % Write data to file for future comparisons
165    writetable(struct2table(comparisonData), 'mongoose_data.csv');
166end
167
168function found = ID_present(comparisonData, id)
169    found = 0;
170    for i = 1:length(comparisonData)
171        if (comparisonData(i).problem_id == id)
172            found = 1;
173            return;
174        end
175    end
176end
177
178