Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * fm.c
00005  *
00006  * This file contains code that implements the edge-based FM refinement
00007  *
00008  * Started 7/23/97
00009  * George
00010  *
00011  * $Id$
00012  */
00013 
00014 #include <metis.h>
00015 
00016 
00017 /*************************************************************************
00018 * This function performs an edge-based FM refinement
00019 **************************************************************************/
00020 void FM_2WayEdgeRefine(CtrlType *ctrl, GraphType *graph, int *tpwgts, int npasses)
00021 {
00022   int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, limit, tmp;
00023   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
00024   idxtype *moved, *swaps, *perm;
00025   PQueueType parts[2];
00026   int higain, oldgain, mincut, mindiff, origdiff, initcut, newcut, mincutorder, avgvwgt;
00027 
00028   nvtxs = graph->nvtxs;
00029   xadj = graph->xadj;
00030   vwgt = graph->vwgt;
00031   adjncy = graph->adjncy;
00032   adjwgt = graph->adjwgt;
00033   where = graph->where;
00034   id = graph->id;
00035   ed = graph->ed;
00036   pwgts = graph->pwgts;
00037   bndptr = graph->bndptr;
00038   bndind = graph->bndind;
00039 
00040   moved = idxwspacemalloc(ctrl, nvtxs);
00041   swaps = idxwspacemalloc(ctrl, nvtxs);
00042   perm = idxwspacemalloc(ctrl, nvtxs);
00043 
00044   limit = amin(amax(0.01*nvtxs, 15), 100);
00045   avgvwgt = amin((pwgts[0]+pwgts[1])/20, 2*(pwgts[0]+pwgts[1])/nvtxs);
00046 
00047   tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];
00048   PQueueInit(ctrl, &parts[0], nvtxs, tmp);
00049   PQueueInit(ctrl, &parts[1], nvtxs, tmp);
00050 
00051   IFSET(ctrl->dbglvl, DBG_REFINE, 
00052      printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d\n",
00053              pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00054 
00055   origdiff = abs(tpwgts[0]-pwgts[0]);
00056   idxset(nvtxs, -1, moved);
00057   for (pass=0; pass<npasses; pass++) { /* Do a number of passes */
00058     PQueueReset(&parts[0]);
00059     PQueueReset(&parts[1]);
00060 
00061     mincutorder = -1;
00062     newcut = mincut = initcut = graph->mincut;
00063     mindiff = abs(tpwgts[0]-pwgts[0]);
00064 
00065     ASSERT(ComputeCut(graph, where) == graph->mincut);
00066     ASSERT(CheckBnd(graph));
00067 
00068     /* Insert boundary nodes in the priority queues */
00069     nbnd = graph->nbnd;
00070     RandomPermute(nbnd, perm, 1);
00071     for (ii=0; ii<nbnd; ii++) {
00072       i = perm[ii];
00073       ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
00074       ASSERT(bndptr[bndind[i]] != -1);
00075       PQueueInsert(&parts[where[bndind[i]]], bndind[i], ed[bndind[i]]-id[bndind[i]]);
00076     }
00077 
00078     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00079       from = (tpwgts[0]-pwgts[0] < tpwgts[1]-pwgts[1] ? 0 : 1);
00080       to = (from+1)%2;
00081 
00082       if ((higain = PQueueGetMax(&parts[from])) == -1)
00083         break;
00084       ASSERT(bndptr[higain] != -1);
00085 
00086       newcut -= (ed[higain]-id[higain]);
00087       INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
00088 
00089       if ((newcut < mincut && abs(tpwgts[0]-pwgts[0]) <= origdiff+avgvwgt) || 
00090           (newcut == mincut && abs(tpwgts[0]-pwgts[0]) < mindiff)) {
00091         mincut = newcut;
00092         mindiff = abs(tpwgts[0]-pwgts[0]);
00093         mincutorder = nswaps;
00094       }
00095       else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
00096         newcut += (ed[higain]-id[higain]);
00097         INC_DEC(pwgts[from], pwgts[to], vwgt[higain]);
00098         break;
00099       }
00100 
00101       where[higain] = to;
00102       moved[higain] = nswaps;
00103       swaps[nswaps] = higain;
00104 
00105       IFSET(ctrl->dbglvl, DBG_MOVEINFO, 
00106         printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-id[higain], vwgt[higain], newcut, pwgts[0], pwgts[1]));
00107 
00108       /**************************************************************
00109       * Update the id[i]/ed[i] values of the affected nodes
00110       ***************************************************************/
00111       SWAP(id[higain], ed[higain], tmp);
00112       if (ed[higain] == 0 && xadj[higain] < xadj[higain+1]) 
00113         BNDDelete(nbnd, bndind,  bndptr, higain);
00114 
00115       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00116         k = adjncy[j];
00117         oldgain = ed[k]-id[k];
00118 
00119         kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00120         INC_DEC(id[k], ed[k], kwgt);
00121 
00122         /* Update its boundary information and queue position */
00123         if (bndptr[k] != -1) { /* If k was a boundary vertex */
00124           if (ed[k] == 0) { /* Not a boundary vertex any more */
00125             BNDDelete(nbnd, bndind, bndptr, k);
00126             if (moved[k] == -1)  /* Remove it if in the queues */
00127               PQueueDelete(&parts[where[k]], k, oldgain);
00128           }
00129           else { /* If it has not been moved, update its position in the queue */
00130             if (moved[k] == -1)
00131               PQueueUpdate(&parts[where[k]], k, oldgain, ed[k]-id[k]);
00132           }
00133         }
00134         else {
00135           if (ed[k] > 0) {  /* It will now become a boundary vertex */
00136             BNDInsert(nbnd, bndind, bndptr, k);
00137             if (moved[k] == -1) 
00138               PQueueInsert(&parts[where[k]], k, ed[k]-id[k]);
00139           }
00140         }
00141       }
00142 
00143     }
00144 
00145 
00146     /****************************************************************
00147     * Roll back computations
00148     *****************************************************************/
00149     for (i=0; i<nswaps; i++)
00150       moved[swaps[i]] = -1;  /* reset moved array */
00151     for (nswaps--; nswaps>mincutorder; nswaps--) {
00152       higain = swaps[nswaps];
00153 
00154       to = where[higain] = (where[higain]+1)%2;
00155       SWAP(id[higain], ed[higain], tmp);
00156       if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
00157         BNDDelete(nbnd, bndind,  bndptr, higain);
00158       else if (ed[higain] > 0 && bndptr[higain] == -1)
00159         BNDInsert(nbnd, bndind,  bndptr, higain);
00160 
00161       INC_DEC(pwgts[to], pwgts[(to+1)%2], vwgt[higain]);
00162       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00163         k = adjncy[j];
00164 
00165         kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00166         INC_DEC(id[k], ed[k], kwgt);
00167 
00168         if (bndptr[k] != -1 && ed[k] == 0)
00169           BNDDelete(nbnd, bndind, bndptr, k);
00170         if (bndptr[k] == -1 && ed[k] > 0)
00171           BNDInsert(nbnd, bndind, bndptr, k);
00172       }
00173     }
00174 
00175     IFSET(ctrl->dbglvl, DBG_REFINE, 
00176       printf("\tMinimum cut: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00177 
00178     graph->mincut = mincut;
00179     graph->nbnd = nbnd;
00180 
00181     if (mincutorder == -1 || mincut == initcut)
00182       break;
00183   }
00184 
00185   PQueueFree(ctrl, &parts[0]);
00186   PQueueFree(ctrl, &parts[1]);
00187 
00188   idxwspacefree(ctrl, nvtxs);
00189   idxwspacefree(ctrl, nvtxs);
00190   idxwspacefree(ctrl, nvtxs);
00191 
00192 }
00193 
00194
libs/ck-libs/parmetis/METISLib/fm.c
