Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * mmatch.c
00005  *
00006  * This file contains the code that computes matchings and creates the next
00007  * level coarse graph.
00008  *
00009  * Started 7/23/97
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 
00019 /*************************************************************************
00020 * This function finds a matching using the HEM heuristic
00021 **************************************************************************/
00022 void MCMatch_RM(CtrlType *ctrl, GraphType *graph)
00023 {
00024   int i, ii, j, k, nvtxs, ncon, cnvtxs, maxidx;
00025   idxtype *xadj, *adjncy, *adjwgt;
00026   idxtype *match, *cmap, *perm;
00027   floattype *nvwgt;
00028 
00029   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00030 
00031   nvtxs = graph->nvtxs;
00032   ncon = graph->ncon;
00033   xadj = graph->xadj;
00034   nvwgt = graph->nvwgt;
00035   adjncy = graph->adjncy;
00036   adjwgt = graph->adjwgt;
00037 
00038   cmap = graph->cmap;
00039   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00040 
00041   perm = idxwspacemalloc(ctrl, nvtxs);
00042   RandomPermute(nvtxs, perm, 1);
00043 
00044   cnvtxs = 0;
00045   for (ii=0; ii<nvtxs; ii++) {
00046     i = perm[ii];
00047 
00048     if (match[i] == UNMATCHED) {  /* Unmatched */
00049       maxidx = i;
00050 
00051       /* Find a random matching, subject to maxvwgt constraints */
00052       for (j=xadj[i]; j<xadj[i+1]; j++) {
00053         k = adjncy[j];
00054         if (match[k] == UNMATCHED && AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
00055           maxidx = k;
00056           break;
00057         }
00058       }
00059 
00060       cmap[i] = cmap[maxidx] = cnvtxs++;
00061       match[i] = maxidx;
00062       match[maxidx] = i;
00063     }
00064   }
00065 
00066   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00067 
00068   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00069 
00070   idxwspacefree(ctrl, nvtxs);
00071   idxwspacefree(ctrl, nvtxs);
00072 }
00073 
00074 
00075 
00076 /*************************************************************************
00077 * This function finds a matching using the HEM heuristic
00078 **************************************************************************/
00079 void MCMatch_HEM(CtrlType *ctrl, GraphType *graph)
00080 {
00081   int i, ii, j, k, l, nvtxs, cnvtxs, ncon, maxidx, maxwgt;
00082   idxtype *xadj, *adjncy, *adjwgt;
00083   idxtype *match, *cmap, *perm;
00084   floattype *nvwgt;
00085 
00086   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00087 
00088   nvtxs = graph->nvtxs;
00089   ncon = graph->ncon;
00090   xadj = graph->xadj;
00091   nvwgt = graph->nvwgt;
00092   adjncy = graph->adjncy;
00093   adjwgt = graph->adjwgt;
00094 
00095   cmap = graph->cmap;
00096   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00097 
00098   perm = idxwspacemalloc(ctrl, nvtxs);
00099   RandomPermute(nvtxs, perm, 1);
00100 
00101   cnvtxs = 0;
00102   for (ii=0; ii<nvtxs; ii++) {
00103     i = perm[ii];
00104 
00105     if (match[i] == UNMATCHED) {  /* Unmatched */
00106       maxidx = i;
00107       maxwgt = 0;
00108 
00109       /* Find a heavy-edge matching, subject to maxvwgt constraints */
00110       for (j=xadj[i]; j<xadj[i+1]; j++) {
00111         k = adjncy[j];
00112         if (match[k] == UNMATCHED && maxwgt <= adjwgt[j] &&
00113                AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
00114           maxwgt = adjwgt[j];
00115           maxidx = adjncy[j];
00116         }
00117       }
00118 
00119       cmap[i] = cmap[maxidx] = cnvtxs++;
00120       match[i] = maxidx;
00121       match[maxidx] = i;
00122     }
00123   }
00124 
00125   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00126 
00127   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00128 
00129   idxwspacefree(ctrl, nvtxs);
00130   idxwspacefree(ctrl, nvtxs);
00131 }
00132 
00133 
00134 
00135 /*************************************************************************
00136 * This function finds a matching using the HEM heuristic
00137 **************************************************************************/
00138 void MCMatch_SHEM(CtrlType *ctrl, GraphType *graph)
00139 {
00140   int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
00141   idxtype *xadj, *adjncy, *adjwgt;
00142   idxtype *match, *cmap, *degrees, *perm, *tperm;
00143   floattype *nvwgt;
00144 
00145   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00146 
00147   nvtxs = graph->nvtxs;
00148   ncon = graph->ncon;
00149   xadj = graph->xadj;
00150   nvwgt = graph->nvwgt;
00151   adjncy = graph->adjncy;
00152   adjwgt = graph->adjwgt;
00153 
00154   cmap = graph->cmap;
00155   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00156 
00157   perm = idxwspacemalloc(ctrl, nvtxs);
00158   tperm = idxwspacemalloc(ctrl, nvtxs);
00159   degrees = idxwspacemalloc(ctrl, nvtxs);
00160 
00161   RandomPermute(nvtxs, tperm, 1);
00162   avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
00163   for (i=0; i<nvtxs; i++) 
00164     degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
00165   BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);
00166 
00167   cnvtxs = 0;
00168 
00169   /* Take care any islands. Islands are matched with non-islands due to coarsening */
00170   for (ii=0; ii<nvtxs; ii++) {
00171     i = perm[ii];
00172 
00173     if (match[i] == UNMATCHED) {  /* Unmatched */
00174       if (xadj[i] < xadj[i+1])
00175         break;
00176 
00177       maxidx = i;
00178       for (j=nvtxs-1; j>ii; j--) {
00179         k = perm[j];
00180         if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
00181           maxidx = k;
00182           break;
00183         }
00184       }
00185 
00186       cmap[i] = cmap[maxidx] = cnvtxs++;
00187       match[i] = maxidx;
00188       match[maxidx] = i;
00189     }
00190   }
00191 
00192   /* Continue with normal matching */
00193   for (; ii<nvtxs; ii++) {
00194     i = perm[ii];
00195 
00196     if (match[i] == UNMATCHED) {  /* Unmatched */
00197       maxidx = i;
00198       maxwgt = 0;
00199 
00200       /* Find a heavy-edge matching, subject to maxvwgt constraints */
00201       for (j=xadj[i]; j<xadj[i+1]; j++) {
00202         k = adjncy[j];
00203         if (match[k] == UNMATCHED && maxwgt <= adjwgt[j] &&
00204                AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
00205           maxwgt = adjwgt[j];
00206           maxidx = adjncy[j];
00207         }
00208       }
00209 
00210       cmap[i] = cmap[maxidx] = cnvtxs++;
00211       match[i] = maxidx;
00212       match[maxidx] = i;
00213     }
00214   }
00215 
00216   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00217 
00218   idxwspacefree(ctrl, nvtxs);  /* degrees */
00219   idxwspacefree(ctrl, nvtxs);  /* tperm */
00220 
00221   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00222 
00223   idxwspacefree(ctrl, nvtxs);
00224   idxwspacefree(ctrl, nvtxs);
00225 }
00226 
00227 
00228 
00229 /*************************************************************************
00230 * This function finds a matching using the HEM heuristic
00231 **************************************************************************/
00232 void MCMatch_SHEBM(CtrlType *ctrl, GraphType *graph, int norm)
00233 {
00234   int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
00235   idxtype *xadj, *adjncy, *adjwgt;
00236   idxtype *match, *cmap, *degrees, *perm, *tperm;
00237   floattype *nvwgt;
00238 
00239   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00240 
00241   nvtxs = graph->nvtxs;
00242   ncon = graph->ncon;
00243   xadj = graph->xadj;
00244   nvwgt = graph->nvwgt;
00245   adjncy = graph->adjncy;
00246   adjwgt = graph->adjwgt;
00247 
00248   cmap = graph->cmap;
00249   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00250 
00251   perm = idxwspacemalloc(ctrl, nvtxs);
00252   tperm = idxwspacemalloc(ctrl, nvtxs);
00253   degrees = idxwspacemalloc(ctrl, nvtxs);
00254 
00255   RandomPermute(nvtxs, tperm, 1);
00256   avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
00257   for (i=0; i<nvtxs; i++) 
00258     degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
00259   BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);
00260 
00261   cnvtxs = 0;
00262 
00263   /* Take care any islands. Islands are matched with non-islands due to coarsening */
00264   for (ii=0; ii<nvtxs; ii++) {
00265     i = perm[ii];
00266 
00267     if (match[i] == UNMATCHED) {  /* Unmatched */
00268       if (xadj[i] < xadj[i+1])
00269         break;
00270 
00271       maxidx = i;
00272       for (j=nvtxs-1; j>ii; j--) {
00273         k = perm[j];
00274         if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
00275           maxidx = k;
00276           break;
00277         }
00278       }
00279 
00280       cmap[i] = cmap[maxidx] = cnvtxs++;
00281       match[i] = maxidx;
00282       match[maxidx] = i;
00283     }
00284   }
00285 
00286   /* Continue with normal matching */
00287   for (; ii<nvtxs; ii++) {
00288     i = perm[ii];
00289 
00290     if (match[i] == UNMATCHED) {  /* Unmatched */
00291       maxidx = i;
00292       maxwgt = -1;
00293 
00294       /* Find a heavy-edge matching, subject to maxvwgt constraints */
00295       for (j=xadj[i]; j<xadj[i+1]; j++) {
00296         k = adjncy[j];
00297 
00298         if (match[k] == UNMATCHED && 
00299             AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt) &&
00300             (maxwgt < adjwgt[j] || 
00301               (maxwgt == adjwgt[j] && 
00302                BetterVBalance(ncon, norm, nvwgt+i*ncon, nvwgt+maxidx*ncon, nvwgt+k*ncon) >= 0
00303               )
00304             )
00305            ) {
00306           maxwgt = adjwgt[j];
00307           maxidx = k;
00308         }
00309       }
00310 
00311       cmap[i] = cmap[maxidx] = cnvtxs++;
00312       match[i] = maxidx;
00313       match[maxidx] = i;
00314     }
00315   }
00316 
00317   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00318 
00319   idxwspacefree(ctrl, nvtxs);  /* degrees */
00320   idxwspacefree(ctrl, nvtxs);  /* tperm */
00321 
00322   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00323 
00324   idxwspacefree(ctrl, nvtxs);
00325   idxwspacefree(ctrl, nvtxs);
00326 }
00327 
00328 
00329 
00330 /*************************************************************************
00331 * This function finds a matching using the HEM heuristic
00332 **************************************************************************/
00333 void MCMatch_SBHEM(CtrlType *ctrl, GraphType *graph, int norm)
00334 {
00335   int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
00336   idxtype *xadj, *adjncy, *adjwgt;
00337   idxtype *match, *cmap, *degrees, *perm, *tperm;
00338   floattype *nvwgt, vbal;
00339 
00340   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00341 
00342   nvtxs = graph->nvtxs;
00343   ncon = graph->ncon;
00344   xadj = graph->xadj;
00345   nvwgt = graph->nvwgt;
00346   adjncy = graph->adjncy;
00347   adjwgt = graph->adjwgt;
00348 
00349   cmap = graph->cmap;
00350   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00351 
00352   perm = idxwspacemalloc(ctrl, nvtxs);
00353   tperm = idxwspacemalloc(ctrl, nvtxs);
00354   degrees = idxwspacemalloc(ctrl, nvtxs);
00355 
00356   RandomPermute(nvtxs, tperm, 1);
00357   avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
00358   for (i=0; i<nvtxs; i++) 
00359     degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
00360   BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);
00361 
00362   cnvtxs = 0;
00363 
00364   /* Take care any islands. Islands are matched with non-islands due to coarsening */
00365   for (ii=0; ii<nvtxs; ii++) {
00366     i = perm[ii];
00367 
00368     if (match[i] == UNMATCHED) {  /* Unmatched */
00369       if (xadj[i] < xadj[i+1])
00370         break;
00371 
00372       maxidx = i;
00373       for (j=nvtxs-1; j>ii; j--) {
00374         k = perm[j];
00375         if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
00376           maxidx = k;
00377           break;
00378         }
00379       }
00380 
00381       cmap[i] = cmap[maxidx] = cnvtxs++;
00382       match[i] = maxidx;
00383       match[maxidx] = i;
00384     }
00385   }
00386 
00387   /* Continue with normal matching */
00388   for (; ii<nvtxs; ii++) {
00389     i = perm[ii];
00390 
00391     if (match[i] == UNMATCHED) {  /* Unmatched */
00392       maxidx = i;
00393       maxwgt = -1;
00394       vbal = 0.0;
00395 
00396       /* Find a heavy-edge matching, subject to maxvwgt constraints */
00397       for (j=xadj[i]; j<xadj[i+1]; j++) {
00398         k = adjncy[j];
00399         if (match[k] == UNMATCHED && AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
00400           if (maxidx != i)
00401             vbal = BetterVBalance(ncon, norm, nvwgt+i*ncon, nvwgt+maxidx*ncon, nvwgt+k*ncon);
00402 
00403           if (vbal > 0 || (vbal > -.01 && maxwgt < adjwgt[j])) {
00404             maxwgt = adjwgt[j];
00405             maxidx = k;
00406           }
00407         }
00408       }
00409 
00410       cmap[i] = cmap[maxidx] = cnvtxs++;
00411       match[i] = maxidx;
00412       match[maxidx] = i;
00413     }
00414   }
00415 
00416   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00417 
00418   idxwspacefree(ctrl, nvtxs);  /* degrees */
00419   idxwspacefree(ctrl, nvtxs);  /* tperm */
00420 
00421   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00422 
00423   idxwspacefree(ctrl, nvtxs);
00424   idxwspacefree(ctrl, nvtxs);
00425 }
00426 
00427 
00428 
00429 
00430 
00431 /*************************************************************************
00432 * This function checks if v+u2 provides a better balance in the weight 
00433 * vector that v+u1
00434 **************************************************************************/
00435 floattype BetterVBalance(int ncon, int norm, floattype *vwgt, floattype *u1wgt, floattype *u2wgt)
00436 {
00437   int i;
00438   floattype sum1, sum2, max1, max2, min1, min2, diff1, diff2;
00439 
00440   if (norm == -1) {
00441     max1 = min1 = vwgt[0]+u1wgt[0];
00442     max2 = min2 = vwgt[0]+u2wgt[0];
00443     sum1 = vwgt[0]+u1wgt[0];
00444     sum2 = vwgt[0]+u2wgt[0];
00445 
00446     for (i=1; i<ncon; i++) {
00447       if (max1 < vwgt[i]+u1wgt[i])
00448         max1 = vwgt[i]+u1wgt[i];
00449       if (min1 > vwgt[i]+u1wgt[i])
00450         min1 = vwgt[i]+u1wgt[i];
00451 
00452       if (max2 < vwgt[i]+u2wgt[i])
00453         max2 = vwgt[i]+u2wgt[i];
00454       if (min2 > vwgt[i]+u2wgt[i])
00455         min2 = vwgt[i]+u2wgt[i];
00456 
00457       sum1 += vwgt[i]+u1wgt[i];
00458       sum2 += vwgt[i]+u2wgt[i];
00459     }
00460 
00461     return ((max1-min1)/sum1) - ((max2-min2)/sum2);
00462   }
00463   else if (norm == 1) {
00464     sum1 = sum2 = 0.0;
00465     for (i=0; i<ncon; i++) {
00466       sum1 += vwgt[i]+u1wgt[i];
00467       sum2 += vwgt[i]+u2wgt[i];
00468     }
00469     sum1 = sum1/(1.0*ncon);
00470     sum2 = sum2/(1.0*ncon);
00471 
00472     diff1 = diff2 = 0.0;
00473     for (i=0; i<ncon; i++) {
00474       diff1 += fabs(sum1 - (vwgt[i]+u1wgt[i]));
00475       diff2 += fabs(sum2 - (vwgt[i]+u2wgt[i]));
00476     }
00477 
00478     return diff1 - diff2;
00479   }
00480   else {
00481     errexit("Unknown norm: %d\n", norm);
00482   }
00483   return 0.0;
00484 }
00485 
00486 
00487 /*************************************************************************
00488 * This function checks if the vertex weights of two vertices are below 
00489 * a given set of values
00490 **************************************************************************/
00491 int AreAllVwgtsBelowFast(int ncon, floattype *vwgt1, floattype *vwgt2, floattype limit)
00492 {
00493   int i;
00494 
00495   for (i=0; i<ncon; i++)
00496     if (vwgt1[i] + vwgt2[i] > limit)
00497       return 0;
00498 
00499   return 1;
00500 }
00501
libs/ck-libs/parmetis/METISLib/mmatch.c
