00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #include "metislib.h"
00015
00016
00017
00021
00022 int rvecle(idx_t n, real_t *x, real_t *y)
00023 {
00024 for (n--; n>=0; n--) {
00025 if (x[n] > y[n])
00026 return 0;
00027 }
00028
00029 return 1;
00030 }
00031
00032
00033
00037
00038 int rvecge(idx_t n, real_t *x, real_t *y)
00039 {
00040 for (n--; n>=0; n--) {
00041 if (x[n] < y[n])
00042 return 0;
00043 }
00044
00045 return 1;
00046 }
00047
00048
00049
00053
00054 int rvecsumle(idx_t n, real_t *x1, real_t *x2, real_t *y)
00055 {
00056 for (n--; n>=0; n--) {
00057 if (x1[n]+x2[n] > y[n])
00058 return 0;
00059 }
00060
00061 return 1;
00062 }
00063
00064
00065
00067
00068 real_t rvecmaxdiff(idx_t n, real_t *x, real_t *y)
00069 {
00070 real_t max;
00071
00072 max = x[0]-y[0];
00073
00074 for (n--; n>0; n--) {
00075 if (max < x[n]-y[n])
00076 max = x[n]-y[n];
00077 }
00078
00079 return max;
00080 }
00081
00082
00083
00085
00086 int ivecle(idx_t n, idx_t *x, idx_t *z)
00087 {
00088 for (n--; n>=0; n--) {
00089 if (x[n] > z[n])
00090 return 0;
00091 }
00092
00093 return 1;
00094 }
00095
00096
00097
00099
00100 int ivecge(idx_t n, idx_t *x, idx_t *z)
00101 {
00102 for (n--; n>=0; n--) {
00103 if (x[n] < z[n])
00104 return 0;
00105 }
00106
00107 return 1;
00108 }
00109
00110
00111
00113
00114 int ivecaxpylez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
00115 {
00116 for (n--; n>=0; n--) {
00117 if (a*x[n]+y[n] > z[n])
00118 return 0;
00119 }
00120
00121 return 1;
00122 }
00123
00124
00125
00127
00128 int ivecaxpygez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
00129 {
00130 for (n--; n>=0; n--) {
00131 if (a*x[n]+y[n] < z[n])
00132 return 0;
00133 }
00134
00135 return 1;
00136 }
00137
00138
00139
00142
00143 int BetterVBalance(idx_t ncon, real_t *invtvwgt, idx_t *v_vwgt, idx_t *u1_vwgt,
00144 idx_t *u2_vwgt)
00145 {
00146 idx_t i;
00147 real_t sum1=0.0, sum2=0.0, diff1=0.0, diff2=0.0;
00148
00149 for (i=0; i<ncon; i++) {
00150 sum1 += (v_vwgt[i]+u1_vwgt[i])*invtvwgt[i];
00151 sum2 += (v_vwgt[i]+u2_vwgt[i])*invtvwgt[i];
00152 }
00153 sum1 = sum1/ncon;
00154 sum2 = sum2/ncon;
00155
00156 for (i=0; i<ncon; i++) {
00157 diff1 += rabs(sum1 - (v_vwgt[i]+u1_vwgt[i])*invtvwgt[i]);
00158 diff2 += rabs(sum2 - (v_vwgt[i]+u2_vwgt[i])*invtvwgt[i]);
00159 }
00160
00161 return (diff1 - diff2 >= 0);
00162 }
00163
00164
00165
00168
00169 int BetterBalance2Way(idx_t n, real_t *x, real_t *y)
00170 {
00171 real_t nrm1=0.0, nrm2=0.0;
00172
00173 for (--n; n>=0; n--) {
00174 if (x[n] > 0) nrm1 += x[n]*x[n];
00175 if (y[n] > 0) nrm2 += y[n]*y[n];
00176 }
00177 return nrm2 < nrm1;
00178 }
00179
00180
00181
00188
00189 int BetterBalanceKWay(idx_t ncon, idx_t *vwgt, real_t *ubvec,
00190 idx_t a1, idx_t *pt1, real_t *bm1,
00191 idx_t a2, idx_t *pt2, real_t *bm2)
00192 {
00193 idx_t i;
00194 real_t tmp, nrm1=0.0, nrm2=0.0, max1=0.0, max2=0.0;
00195
00196 for (i=0; i<ncon; i++) {
00197 tmp = bm1[i]*(pt1[i]+a1*vwgt[i]) - ubvec[i];
00198
00199 nrm1 += tmp*tmp;
00200 max1 = (tmp > max1 ? tmp : max1);
00201
00202 tmp = bm2[i]*(pt2[i]+a2*vwgt[i]) - ubvec[i];
00203
00204 nrm2 += tmp*tmp;
00205 max2 = (tmp > max2 ? tmp : max2);
00206
00207
00208
00209
00210
00211 }
00212
00213
00214 if (max2 < max1)
00215 return 1;
00216
00217 if (max2 == max1 && nrm2 < nrm1)
00218 return 1;
00219
00220 return 0;
00221 }
00222
00223
00224
00227
00228 real_t ComputeLoadImbalance(graph_t *graph, idx_t nparts, real_t *pijbm)
00229 {
00230 idx_t i, j, ncon, *pwgts;
00231 real_t max, cur;
00232
00233 ncon = graph->ncon;
00234 pwgts = graph->pwgts;
00235
00236 max = 1.0;
00237 for (i=0; i<ncon; i++) {
00238 for (j=0; j<nparts; j++) {
00239 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i];
00240 if (cur > max)
00241 max = cur;
00242 }
00243 }
00244
00245 return max;
00246 }
00247
00248
00249
00255
00256 real_t ComputeLoadImbalanceDiff(graph_t *graph, idx_t nparts, real_t *pijbm,
00257 real_t *ubvec)
00258 {
00259 idx_t i, j, ncon, *pwgts;
00260 real_t max, cur;
00261
00262 ncon = graph->ncon;
00263 pwgts = graph->pwgts;
00264
00265 max = -1.0;
00266 for (i=0; i<ncon; i++) {
00267 for (j=0; j<nparts; j++) {
00268 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i] - ubvec[i];
00269 if (cur > max)
00270 max = cur;
00271 }
00272 }
00273
00274 return max;
00275 }
00276
00277
00278
00283
00284 real_t ComputeLoadImbalanceDiffVec(graph_t *graph, idx_t nparts, real_t *pijbm,
00285 real_t *ubfactors, real_t *diffvec)
00286 {
00287 idx_t i, j, ncon, *pwgts;
00288 real_t cur, max;
00289
00290 ncon = graph->ncon;
00291 pwgts = graph->pwgts;
00292
00293 for (max=-1.0, i=0; i<ncon; i++) {
00294 diffvec[i] = pwgts[i]*pijbm[i] - ubfactors[i];
00295 for (j=1; j<nparts; j++) {
00296 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i] - ubfactors[i];
00297 if (cur > diffvec[i])
00298 diffvec[i] = cur;
00299 }
00300 if (max < diffvec[i])
00301 max = diffvec[i];
00302 }
00303
00304 return max;
00305 }
00306
00307
00308
00310
00311 void ComputeLoadImbalanceVec(graph_t *graph, idx_t nparts, real_t *pijbm,
00312 real_t *lbvec)
00313 {
00314 idx_t i, j, ncon, *pwgts;
00315 real_t cur;
00316
00317 ncon = graph->ncon;
00318 pwgts = graph->pwgts;
00319
00320 for (i=0; i<ncon; i++) {
00321 lbvec[i] = pwgts[i]*pijbm[i];
00322 for (j=1; j<nparts; j++) {
00323 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i];
00324 if (cur > lbvec[i])
00325 lbvec[i] = cur;
00326 }
00327 }
00328 }
00329
00330
1.5.5