1function comparisonData = compare(trials, percent_to_keep, plot_outliers, use_weights)
2    if (nargin < 1 || trials < 1)
3        trials = 5;
4    end
5    if (nargin < 2 || percent_to_keep <= 0)
6        percent_to_keep = 60;
7    end
8    if (nargin < 3)
9        plot_outliers = 0;
10    end
11    if (nargin < 4)
12        use_weights = 0;
13    end
14
15    index = ssget;
16    j = 1;
17
18    comparisonData = struct('avg_mongoose_times', [], ...
19                            'avg_metis_times', [], ...
20                            'rel_mongoose_times',  [], ...
21                            'avg_mongoose_imbalance', [], ...
22                            'avg_metis_imbalance', [], ...
23                            'avg_mongoose_cut_weight', [], ...
24                            'avg_mongoose_cut_size', [], ...
25                            'avg_metis_cut_weight', [], ...
26                            'avg_metis_cut_size', [], ...
27                            'rel_mongoose_cut_size', [], ...
28                            'problem_id', [], ...
29                            'problem_name', [], ...
30                            'problem_kind', [], ...
31                            'problem_nnz', [], ...
32                            'problem_n', []);
33    for i = 1:length(index.nrows)
34        if (index.isReal(i))
35
36            % For comparing graph performance
37            % if (~index.isGraph(i))
38            %     continue;
39            % end
40            % use_weights = 1;
41
42            Prob = ssget(i);
43            A = Prob.A;
44
45            % If matrix is unsymmetric, form the augmented system
46            if (index.numerical_symmetry(i) < 1)
47                [m_rows, n_cols] = size(A);
48                A = [sparse(m_rows,m_rows) A; A' sparse(n_cols,n_cols)];
49            end
50
51            % Make matrix binary - matrix values are not necessarily edge weights
52            %A = sign(abs(A));
53            A = abs(A); % Edit for graph comparison
54
55            % Sanitize the matrix (remove diagonal, make symmetric)
56            A = sanitize(A, ~use_weights);
57
58            % If the sanitization removed all vertices, skip this matrix
59            if nnz(A) < 2
60                continue
61            end
62
63            fprintf('Computing separator for %d: %s\n', i, Prob.name);
64
65            [~, n_cols] = size(A);
66            comparisonData(j).problem_id = Prob.id;
67            comparisonData(j).problem_name = Prob.name;
68            comparisonData(j).problem_kind = Prob.kind;
69            comparisonData(j).problem_nnz = nnz(A);
70            comparisonData(j).problem_n = n_cols;
71
72            % Run Mongoose with default options to partition the graph.
73            O = edgecut_options();
74            O.randomSeed = 123456789;
75            for k = 1:trials
76                tic;
77                partition = edgecut(A,O);
78                t = toc;
79                fprintf('Mongoose: %0.2f\n', t);
80                mongoose_times(j,k) = t;
81                part_A = find(partition);
82                part_B = find(1-partition);
83                perm = [part_A part_B];
84                p = length(part_A);
85                A_perm = A(perm, perm);
86                mongoose_cut_weight(j,k) = sum(sum(A_perm((p+1):n_cols, 1:p)));
87                mongoose_cut_size(j,k) = sum(sum(sign(A_perm((p+1):n_cols, 1:p))));
88                mongoose_imbalance(j,k) = abs(0.5-(length(part_A)/(length(part_A) + length(part_B))));
89            end
90
91            % Run METIS to partition the graph.
92            for k = 1:trials
93                tic;
94                [part_A,part_B] = metispart(A, 0, 123456789);
95                t = toc;
96                fprintf('METIS:    %0.2f\n', t);
97                metis_times(j,k) = t;
98                p = length(part_A);
99                perm = [part_A part_B];
100                A_perm = A(perm, perm);
101                metis_cut_weight(j,k) = sum(sum(A_perm((p+1):n_cols, 1:p)));
102                metis_cut_size(j,k) = sum(sum(sign(A_perm((p+1):n_cols, 1:p))));
103                metis_imbalance(j,k) = abs(0.5-(length(part_A)/(length(part_A) + length(part_B))));
104            end
105            j = j + 1;
106        end
107    end
108
109    n = length(mongoose_times);
110
111    for i = 1:n
112        % Compute trimmed means - trim lowest and highest 20%
113        comparisonData(i).avg_mongoose_times = trimmean(mongoose_times(i,:), 100-percent_to_keep);
114        comparisonData(i).avg_mongoose_cut_weight = trimmean(mongoose_cut_weight(i,:), 100-percent_to_keep);
115        comparisonData(i).avg_mongoose_cut_size = trimmean(mongoose_cut_size(i,:), 100-percent_to_keep);
116        comparisonData(i).avg_mongoose_imbalance = trimmean(mongoose_imbalance(i,:), 100-percent_to_keep);
117
118        comparisonData(i).avg_metis_times = trimmean(metis_times(i,:), 100-percent_to_keep);
119        comparisonData(i).avg_metis_cut_weight = trimmean(metis_cut_weight(i,:), 100-percent_to_keep);
120        comparisonData(i).avg_metis_cut_size = trimmean(metis_cut_size(i,:), 100-percent_to_keep);
121        comparisonData(i).avg_metis_imbalance = trimmean(metis_imbalance(i,:), 100-percent_to_keep);
122
123        % Compute times relative to METIS
124        comparisonData(i).rel_mongoose_times = (comparisonData(i).avg_mongoose_times / comparisonData(i).avg_metis_times);
125
126        % Compute cut weight relative to METIS
127        comparisonData(i).rel_mongoose_cut_weight = (comparisonData(i).avg_mongoose_cut_weight / comparisonData(i).avg_metis_cut_weight);
128
129        % Compute cut size relative to METIS
130        comparisonData(i).rel_mongoose_cut_size = (comparisonData(i).avg_mongoose_cut_size / comparisonData(i).avg_metis_cut_size);
131
132        % Check for outliers
133        prob_id = comparisonData(i).problem_id;
134        outlier = 0;
135
136        if (comparisonData(i).rel_mongoose_times > 2)
137            disp(['Outlier! Mongoose time significantly worse. ID: ', num2str(prob_id)]);
138            outlier = 1;
139            comparisonData(i).outlier.time = 1;
140        end
141        if (comparisonData(i).rel_mongoose_times < 0.5)
142            disp(['Outlier! METIS time significantly worse. ID: ', num2str(prob_id)]);
143            outlier = 1;
144            comparisonData(i).outlier.time = -1;
145        end
146
147        if (comparisonData(i).rel_mongoose_cut_size > 2)
148            disp(['Outlier! Mongoose cut size significantly worse. ID: ', num2str(prob_id)]);
149            outlier = 1;
150            comparisonData(i).outlier.cut_size = 1;
151        end
152        if (comparisonData(i).rel_mongoose_cut_size < 0.5)
153            disp(['Outlier! METIS cut size significantly worse. ID: ', num2str(prob_id)]);
154            outlier = 1;
155            comparisonData(i).outlier.cut_size = -1;
156        end
157
158        if (comparisonData(i).avg_mongoose_imbalance > 2*comparisonData(i).avg_metis_imbalance)
159            disp(['Outlier! Mongoose imbalance significantly worse. ID: ', num2str(prob_id)]);
160            comparisonData(i).outlier.imbalance = 1;
161            outlier = 1;
162        end
163        if (comparisonData(i).avg_metis_imbalance > 2*comparisonData(i).avg_mongoose_imbalance)
164            disp(['Outlier! METIS imbalance significantly worse. ID: ', num2str(prob_id)]);
165            comparisonData(i).outlier.imbalance = -1;
166            outlier = 1;
167        end
168
169        if (outlier && plot_outliers)
170            plotGraphs(prob_id);
171        end
172    end
173
174    % Sort metrics
175    sorted_rel_mongoose_times = sort([comparisonData.rel_mongoose_times]);
176    sorted_rel_mongoose_cut_weight = sort([comparisonData.rel_mongoose_cut_weight]);
177    sorted_rel_mongoose_cut_size = sort([comparisonData.rel_mongoose_cut_size]);
178    sorted_avg_mongoose_imbalance = sort([comparisonData.avg_mongoose_imbalance]);
179    sorted_avg_metis_imbalance = sort([comparisonData.avg_metis_imbalance]);
180
181    % Get the Git commit hash for labeling purposes
182    [error, commit] = system('git rev-parse --short HEAD');
183    git_found = ~error;
184    commit = strtrim(commit);
185
186    %%%%% Plot performance profiles %%%%%
187
188    % Plot timing profiles
189    figure;
190    semilogy(1:n, sorted_rel_mongoose_times, 'Color', 'b');
191    hold on;
192    semilogy(1:n, ones(1,n), 'Color','r');
193    axis([1 n min(sorted_rel_mongoose_times) max(sorted_rel_mongoose_times)]);
194    xlabel('Matrix');
195    ylabel('Wall Time Relative to METIS');
196    hold off;
197
198    plt = Plot();
199    plt.LineStyle = {'-', '--'};
200    plt.Legend = {'Mongoose', 'METIS'};
201    plt.LegendLoc = 'SouthEast';
202    plt.BoxDim = [6, 5];
203
204    filename = ['Timing' date];
205    if(git_found)
206        title(['Timing Profile - Commit ' commit]);
207        filename = ['Timing-' commit];
208    end
209
210    plt.export([filename '.png']);
211
212    % Plot separator weight profiles
213    figure;
214    semilogy(1:n, sorted_rel_mongoose_cut_weight, 'Color', 'b');
215    hold on;
216    semilogy(1:n, ones(1,n), 'Color','r');
217    axis([1 n min(sorted_rel_mongoose_cut_weight) max(sorted_rel_mongoose_cut_weight)]);
218    xlabel('Matrix');
219    ylabel('Cut Weight Relative to METIS');
220    hold off;
221
222    plt = Plot();
223    plt.LineStyle = {'-', '--'};
224    plt.Legend = {'Mongoose', 'METIS'};
225    plt.LegendLoc = 'SouthEast';
226    plt.BoxDim = [6, 5];
227
228    filename = ['SeparatorWeight' date];
229    if(git_found)
230        title(['Separator Weight Profile - Commit ' commit]);
231        filename = ['SeparatorWeight-' commit];
232    end
233    plt.export([filename '.png']);
234
235    % Plot separator size profiles
236    figure;
237    semilogy(1:n, sorted_rel_mongoose_cut_size, 'Color', 'b');
238    hold on;
239    semilogy(1:n, ones(1,n), 'Color','r');
240    axis([1 n min(sorted_rel_mongoose_cut_size) max(sorted_rel_mongoose_cut_size)]);
241    xlabel('Matrix');
242    ylabel('Cut Size Relative to METIS');
243    hold off;
244
245    plt = Plot();
246    plt.LineStyle = {'-', '--'};
247    plt.Legend = {'Mongoose', 'METIS'};
248    plt.LegendLoc = 'SouthEast';
249    plt.BoxDim = [6, 5];
250
251    filename = ['SeparatorSize' date];
252    if(git_found)
253        title(['Separator Size Profile - Commit ' commit]);
254        filename = ['SeparatorSize-' commit];
255    end
256    plt.export([filename '.png']);
257
258    % Plot imbalance profiles
259    figure;
260    plot(1:n, sorted_avg_mongoose_imbalance, 'Color', 'b');
261    hold on;
262    plot(1:n, sorted_avg_metis_imbalance, 'Color','r');
263    axis([1 n 0 max([sorted_avg_metis_imbalance sorted_avg_mongoose_imbalance])]);
264    xlabel('Matrix');
265    ylabel('Imbalance');
266    hold off;
267
268    plt = Plot();
269    plt.LineStyle = {'-', '--'};
270    plt.Legend = {'Mongoose', 'METIS'};
271    plt.LegendLoc = 'NorthWest';
272    plt.BoxDim = [6, 5];
273
274    filename = ['Imbalance' date];
275    if(git_found)
276        title(['Imbalance Profile - Commit ' commit]);
277        filename = ['Imbalance-' commit];
278    end
279
280    plt.export([filename '.png']);
281
282    %% Plot only big matrices to compare
283
284
285
286    %% Write data to file for future comparisons
287    if(git_found)
288        writetable(struct2table(comparisonData), [commit '.txt']);
289    end
290end
291
292function plotGraphs(prob_id)
293    index = ssget;
294    Prob = ssget(prob_id);
295    A = Prob.A;
296    if (index.numerical_symmetry(prob_id) < 1)
297        [m_rows, n_cols] = size(A);
298        A = [sparse(m_rows,m_rows) A; A' sparse(n_cols,n_cols)];
299    end
300    A = mongoose_sanitizeMatrix(A);
301
302    % Compute partitioning using Mongoose
303    partition = mongoose_computeEdgeSeparator(A);
304%     part_A = find(partition);
305%     part_B = find(1-partition);
306%     perm = [part_A part_B];
307%     p = length(partition);
308%     A_perm = A(perm, perm);
309%     subplot(1,2,1);
310%     hold on;
311%     spy(A);
312%     subplot(1,2,2);
313%     spy(A_perm);
314%     hold off;
315    mongoose_separator_plot(A, partition, 1-partition, ['mongoose_' num2str(prob_id)]);
316
317    % Compute partitioning using METIS
318    [perm, ~] = metispart(A, 0, 123456789);
319    [m, ~] = size(A);
320    partition = zeros(m,1);
321    for j = 1:m
322        partition(j,1) = sum(sign(find(j == perm)));
323    end
324    mongoose_separator_plot(A, partition, 1-partition, ['metis_' num2str(prob_id)]);
325end
326
327function plotMatrix(prob_id)
328    index = ssget;
329    Prob = ssget(prob_id);
330    A = Prob.A;
331    if (index.numerical_symmetry(prob_id) < 1)
332        [m_rows, n_cols] = size(A);
333        A = [sparse(m_rows,m_rows) A; A' sparse(n_cols,n_cols)];
334    end
335    A = mongoose_sanitizeMatrix(A);
336
337    % Compute partitioning using Mongoose
338    partition = mongoose_computeEdgeSeparator(A);
339    part_A = find(partition);
340    part_B = find(1-partition);
341    perm = [part_A part_B];
342    A_perm = A(perm, perm);
343    subplot(1,2,1);
344    hold on;
345    spy(A);
346    subplot(1,2,2);
347    spy(A_perm);
348    hold off;
349end
350