Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * match.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 Match_RM(CtrlType *ctrl, GraphType *graph)
00023 {
00024   int i, ii, j, nvtxs, cnvtxs, maxidx;
00025   idxtype *xadj, *vwgt, *adjncy, *adjwgt;
00026   idxtype *match, *cmap, *perm;
00027 
00028   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00029 
00030   nvtxs = graph->nvtxs;
00031   xadj = graph->xadj;
00032   vwgt = graph->vwgt;
00033   adjncy = graph->adjncy;
00034   adjwgt = graph->adjwgt;
00035 
00036   cmap = graph->cmap;
00037   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00038 
00039   perm = idxwspacemalloc(ctrl, nvtxs);
00040   RandomPermute(nvtxs, perm, 1);
00041 
00042   cnvtxs = 0;
00043   for (ii=0; ii<nvtxs; ii++) {
00044     i = perm[ii];
00045 
00046     if (match[i] == UNMATCHED) {  /* Unmatched */
00047       maxidx = i;
00048 
00049       /* Find a random matching, subject to maxvwgt constraints */
00050       for (j=xadj[i]; j<xadj[i+1]; j++) {
00051         if (match[adjncy[j]] == UNMATCHED && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
00052           maxidx = adjncy[j];
00053           break;
00054         }
00055       }
00056 
00057       cmap[i] = cmap[maxidx] = cnvtxs++;
00058       match[i] = maxidx;
00059       match[maxidx] = i;
00060     }
00061   }
00062 
00063   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00064 
00065   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00066 
00067   idxwspacefree(ctrl, nvtxs);
00068   idxwspacefree(ctrl, nvtxs);
00069 }
00070 
00071 
00072 /*************************************************************************
00073 * This function finds a matching using the HEM heuristic
00074 **************************************************************************/
00075 void Match_RM_NVW(CtrlType *ctrl, GraphType *graph)
00076 {
00077   int i, ii, j, nvtxs, cnvtxs, maxidx;
00078   idxtype *xadj, *adjncy;
00079   idxtype *match, *cmap, *perm;
00080 
00081   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00082 
00083   nvtxs = graph->nvtxs;
00084   xadj = graph->xadj;
00085   adjncy = graph->adjncy;
00086 
00087   cmap = graph->cmap;
00088   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00089 
00090   perm = idxwspacemalloc(ctrl, nvtxs);
00091   RandomPermute(nvtxs, perm, 1);
00092 
00093   cnvtxs = 0;
00094   for (ii=0; ii<nvtxs; ii++) {
00095     i = perm[ii];
00096 
00097     if (match[i] == UNMATCHED) {  /* Unmatched */
00098       maxidx = i;
00099 
00100       /* Find a random matching, subject to maxvwgt constraints */
00101       for (j=xadj[i]; j<xadj[i+1]; j++) {
00102         if (match[adjncy[j]] == UNMATCHED) {
00103           maxidx = adjncy[j];
00104           break;
00105         }
00106       }
00107 
00108       cmap[i] = cmap[maxidx] = cnvtxs++;
00109       match[i] = maxidx;
00110       match[maxidx] = i;
00111     }
00112   }
00113 
00114   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00115 
00116   CreateCoarseGraph_NVW(ctrl, graph, cnvtxs, match, perm);
00117 
00118   idxwspacefree(ctrl, nvtxs);
00119   idxwspacefree(ctrl, nvtxs);
00120 }
00121 
00122 
00123 
00124 /*************************************************************************
00125 * This function finds a matching using the HEM heuristic
00126 **************************************************************************/
00127 void Match_HEM(CtrlType *ctrl, GraphType *graph)
00128 {
00129   int i, ii, j, k, nvtxs, cnvtxs, maxidx, maxwgt;
00130   idxtype *xadj, *vwgt, *adjncy, *adjwgt;
00131   idxtype *match, *cmap, *perm;
00132 
00133   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00134 
00135   nvtxs = graph->nvtxs;
00136   xadj = graph->xadj;
00137   vwgt = graph->vwgt;
00138   adjncy = graph->adjncy;
00139   adjwgt = graph->adjwgt;
00140 
00141   cmap = graph->cmap;
00142   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00143 
00144   perm = idxwspacemalloc(ctrl, nvtxs);
00145   RandomPermute(nvtxs, perm, 1);
00146 
00147   cnvtxs = 0;
00148   for (ii=0; ii<nvtxs; ii++) {
00149     i = perm[ii];
00150 
00151     if (match[i] == UNMATCHED) {  /* Unmatched */
00152       maxidx = i;
00153       maxwgt = 0;
00154 
00155       /* Find a heavy-edge matching, subject to maxvwgt constraints */
00156       for (j=xadj[i]; j<xadj[i+1]; j++) {
00157         k = adjncy[j];
00158         if (match[k] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[k] <= ctrl->maxvwgt) {
00159           maxwgt = adjwgt[j];
00160           maxidx = adjncy[j];
00161         }
00162       }
00163 
00164       cmap[i] = cmap[maxidx] = cnvtxs++;
00165       match[i] = maxidx;
00166       match[maxidx] = i;
00167     }
00168   }
00169 
00170   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00171 
00172   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00173 
00174   idxwspacefree(ctrl, nvtxs);
00175   idxwspacefree(ctrl, nvtxs);
00176 }
00177 
00178 
00179 
00180 /*************************************************************************
00181 * This function finds a matching using the HEM heuristic
00182 **************************************************************************/
00183 void Match_SHEM(CtrlType *ctrl, GraphType *graph)
00184 {
00185   int i, ii, j, k, nvtxs, cnvtxs, maxidx, maxwgt, avgdegree;
00186   idxtype *xadj, *vwgt, *adjncy, *adjwgt;
00187   idxtype *match, *cmap, *degrees, *perm, *tperm;
00188 
00189   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00190 
00191   nvtxs = graph->nvtxs;
00192   xadj = graph->xadj;
00193   vwgt = graph->vwgt;
00194   adjncy = graph->adjncy;
00195   adjwgt = graph->adjwgt;
00196 
00197   cmap = graph->cmap;
00198   match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
00199 
00200   perm = idxwspacemalloc(ctrl, nvtxs);
00201   tperm = idxwspacemalloc(ctrl, nvtxs);
00202   degrees = idxwspacemalloc(ctrl, nvtxs);
00203 
00204   RandomPermute(nvtxs, tperm, 1);
00205   avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
00206   for (i=0; i<nvtxs; i++) 
00207     degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
00208   BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);
00209 
00210   cnvtxs = 0;
00211 
00212   /* Take care any islands. Islands are matched with non-islands due to coarsening */
00213   for (ii=0; ii<nvtxs; ii++) {
00214     i = perm[ii];
00215 
00216     if (match[i] == UNMATCHED) {  /* Unmatched */
00217       if (xadj[i] < xadj[i+1])
00218         break;
00219 
00220       maxidx = i;
00221       for (j=nvtxs-1; j>ii; j--) {
00222         k = perm[j];
00223         if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
00224           maxidx = k;
00225           break;
00226         }
00227       }
00228 
00229       cmap[i] = cmap[maxidx] = cnvtxs++;
00230       match[i] = maxidx;
00231       match[maxidx] = i;
00232     }
00233   }
00234 
00235   /* Continue with normal matching */
00236   for (; ii<nvtxs; ii++) {
00237     i = perm[ii];
00238 
00239     if (match[i] == UNMATCHED) {  /* Unmatched */
00240       maxidx = i;
00241       maxwgt = 0;
00242 
00243       /* Find a heavy-edge matching, subject to maxvwgt constraints */
00244       for (j=xadj[i]; j<xadj[i+1]; j++) {
00245         if (match[adjncy[j]] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
00246           maxwgt = adjwgt[j];
00247           maxidx = adjncy[j];
00248         }
00249       }
00250 
00251       cmap[i] = cmap[maxidx] = cnvtxs++;
00252       match[i] = maxidx;
00253       match[maxidx] = i;
00254     }
00255   }
00256 
00257   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00258 
00259   idxwspacefree(ctrl, nvtxs);  /* degrees */
00260   idxwspacefree(ctrl, nvtxs);  /* tperm */
00261 
00262   CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
00263 
00264   idxwspacefree(ctrl, nvtxs);
00265   idxwspacefree(ctrl, nvtxs);
00266 }
00267
libs/ck-libs/parmetis/METISLib/match.c
