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