Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * separator.c
00005  *
00006  * This file contains code for separator extraction
00007  *
00008  * Started 8/1/97
00009  * George
00010  *
00011  * $Id$
00012  *
00013  */
00014 
00015 #include <metis.h>
00016 
00017 /*************************************************************************
00018 * This function takes a bisection and constructs a minimum weight vertex 
00019 * separator out of it. It uses the node-based separator refinement for it.
00020 **************************************************************************/
00021 void ConstructSeparator(CtrlType *ctrl, GraphType *graph, floattype ubfactor)
00022 {
00023   int i, j, k, nvtxs, nbnd;
00024   idxtype *xadj, *where, *bndind;
00025 
00026   nvtxs = graph->nvtxs;
00027   xadj = graph->xadj;
00028   nbnd = graph->nbnd;
00029   bndind = graph->bndind;
00030 
00031   where = idxcopy(nvtxs, graph->where, idxwspacemalloc(ctrl, nvtxs));
00032 
00033   /* Put the nodes in the boundary into the separator */
00034   for (i=0; i<nbnd; i++) {
00035     j = bndind[i];
00036     if (xadj[j+1]-xadj[j] > 0)  /* Ignore islands */
00037       where[j] = 2;
00038   }
00039 
00040   GKfree(&graph->rdata, LTERM);
00041   Allocate2WayNodePartitionMemory(ctrl, graph);
00042   idxcopy(nvtxs, where, graph->where);
00043   idxwspacefree(ctrl, nvtxs);
00044 
00045   ASSERT(IsSeparable(graph));
00046 
00047   Compute2WayNodePartitionParams(ctrl, graph);
00048 
00049   ASSERT(CheckNodePartitionParams(graph));
00050 
00051   FM_2WayNodeRefine(ctrl, graph, ubfactor, 8); 
00052 
00053   ASSERT(IsSeparable(graph));
00054 }
00055 
00056 
00057 
00058 /*************************************************************************
00059 * This function takes a bisection and constructs a minimum weight vertex 
00060 * separator out of it. It uses an unweighted minimum-cover algorithm
00061 * followed by node-based separator refinement.
00062 **************************************************************************/
00063 void ConstructMinCoverSeparator0(CtrlType *ctrl, GraphType *graph, floattype ubfactor)
00064 {
00065   int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
00066   idxtype *xadj, *adjncy, *bxadj, *badjncy;
00067   idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
00068 
00069 
00070   nvtxs = graph->nvtxs;
00071   xadj = graph->xadj;
00072   adjncy = graph->adjncy;
00073 
00074   nbnd = graph->nbnd;
00075   bndind = graph->bndind;
00076   bndptr = graph->bndptr;
00077   where = graph->where;
00078 
00079   vmap = idxwspacemalloc(ctrl, nvtxs);
00080   ivmap = idxwspacemalloc(ctrl, nbnd);
00081   cover = idxwspacemalloc(ctrl, nbnd);
00082 
00083   if (nbnd > 0) {
00084     /* Go through the boundary and determine the sizes of the bipartite graph */
00085     bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
00086     for (i=0; i<nbnd; i++) {
00087       j = bndind[i];
00088       k = where[j];
00089       if (xadj[j+1]-xadj[j] > 0) {
00090         bnvtxs[k]++;
00091         bnedges[k] += xadj[j+1]-xadj[j];
00092       }
00093     }
00094 
00095     bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
00096     bnvtxs[1] = bnvtxs[0];
00097     bnvtxs[0] = 0;
00098 
00099     bxadj = idxmalloc(bnvtxs[2]+1, "ConstructMinCoverSeparator: bxadj");
00100     badjncy = idxmalloc(bnedges[0]+bnedges[1]+1, "ConstructMinCoverSeparator: badjncy");
00101 
00102     /* Construct the ivmap and vmap */
00103     ASSERT(idxset(nvtxs, -1, vmap) == vmap);
00104     for (i=0; i<nbnd; i++) {
00105       j = bndind[i];
00106       k = where[j];
00107       if (xadj[j+1]-xadj[j] > 0) {
00108         vmap[j] = bnvtxs[k];
00109         ivmap[bnvtxs[k]++] = j;
00110       }
00111     }
00112 
00113     /* OK, go through and put the vertices of each part starting from 0 */
00114     bnvtxs[1] = bnvtxs[0];
00115     bnvtxs[0] = 0;
00116     bxadj[0] = l = 0;
00117     for (k=0; k<2; k++) {
00118       for (ii=0; ii<nbnd; ii++) {
00119         i = bndind[ii];
00120         if (where[i] == k && xadj[i] < xadj[i+1]) {
00121           for (j=xadj[i]; j<xadj[i+1]; j++) {
00122             jj = adjncy[j];
00123             if (where[jj] != k) {
00124               ASSERT(bndptr[jj] != -1); 
00125               ASSERTP(vmap[jj] != -1, ("%d %d %d\n", jj, vmap[jj], graph->bndptr[jj]));
00126               badjncy[l++] = vmap[jj];
00127             }
00128           }
00129           bxadj[++bnvtxs[k]] = l;
00130         }
00131       }
00132     }
00133 
00134     ASSERT(l <= bnedges[0]+bnedges[1]);
00135 
00136     MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
00137 
00138     IFSET(ctrl->dbglvl, DBG_SEPINFO,
00139       printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
00140 
00141     for (i=0; i<csize; i++) {
00142       j = ivmap[cover[i]];
00143       where[j] = 2;
00144     }
00145 
00146     GKfree(&bxadj, &badjncy, LTERM);
00147 
00148     for (i=0; i<nbnd; i++)
00149       bndptr[bndind[i]] = -1;
00150     for (nbnd=i=0; i<nvtxs; i++) {
00151       if (where[i] == 2) {
00152         bndind[nbnd] = i;
00153         bndptr[i] = nbnd++;
00154       }
00155     }
00156   }
00157   else {
00158     IFSET(ctrl->dbglvl, DBG_SEPINFO,
00159       printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, 0, 0, 0));
00160   }
00161 
00162   idxwspacefree(ctrl, nvtxs);
00163   idxwspacefree(ctrl, graph->nbnd);
00164   idxwspacefree(ctrl, graph->nbnd);
00165   graph->nbnd = nbnd;
00166 
00167 
00168   ASSERT(IsSeparable(graph));
00169 }
00170 
00171 
00172 
00173 /*************************************************************************
00174 * This function takes a bisection and constructs a minimum weight vertex 
00175 * separator out of it. It uses an unweighted minimum-cover algorithm
00176 * followed by node-based separator refinement.
00177 **************************************************************************/
00178 void ConstructMinCoverSeparator(CtrlType *ctrl, GraphType *graph, floattype ubfactor)
00179 {
00180   int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
00181   idxtype *xadj, *adjncy, *bxadj, *badjncy;
00182   idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
00183 
00184 
00185   nvtxs = graph->nvtxs;
00186   xadj = graph->xadj;
00187   adjncy = graph->adjncy;
00188 
00189   nbnd = graph->nbnd;
00190   bndind = graph->bndind;
00191   bndptr = graph->bndptr;
00192   where = graph->where;
00193 
00194   vmap = idxwspacemalloc(ctrl, nvtxs);
00195   ivmap = idxwspacemalloc(ctrl, nbnd);
00196   cover = idxwspacemalloc(ctrl, nbnd);
00197 
00198   if (nbnd > 0) {
00199     /* Go through the boundary and determine the sizes of the bipartite graph */
00200     bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
00201     for (i=0; i<nbnd; i++) {
00202       j = bndind[i];
00203       k = where[j];
00204       if (xadj[j+1]-xadj[j] > 0) {
00205         bnvtxs[k]++;
00206         bnedges[k] += xadj[j+1]-xadj[j];
00207       }
00208     }
00209 
00210     bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
00211     bnvtxs[1] = bnvtxs[0];
00212     bnvtxs[0] = 0;
00213 
00214     bxadj = idxmalloc(bnvtxs[2]+1, "ConstructMinCoverSeparator: bxadj");
00215     badjncy = idxmalloc(bnedges[0]+bnedges[1]+1, "ConstructMinCoverSeparator: badjncy");
00216 
00217     /* Construct the ivmap and vmap */
00218     ASSERT(idxset(nvtxs, -1, vmap) == vmap);
00219     for (i=0; i<nbnd; i++) {
00220       j = bndind[i];
00221       k = where[j];
00222       if (xadj[j+1]-xadj[j] > 0) {
00223         vmap[j] = bnvtxs[k];
00224         ivmap[bnvtxs[k]++] = j;
00225       }
00226     }
00227 
00228     /* OK, go through and put the vertices of each part starting from 0 */
00229     bnvtxs[1] = bnvtxs[0];
00230     bnvtxs[0] = 0;
00231     bxadj[0] = l = 0;
00232     for (k=0; k<2; k++) {
00233       for (ii=0; ii<nbnd; ii++) {
00234         i = bndind[ii];
00235         if (where[i] == k && xadj[i] < xadj[i+1]) {
00236           for (j=xadj[i]; j<xadj[i+1]; j++) {
00237             jj = adjncy[j];
00238             if (where[jj] != k) {
00239               ASSERT(bndptr[jj] != -1); 
00240               ASSERTP(vmap[jj] != -1, ("%d %d %d\n", jj, vmap[jj], graph->bndptr[jj]));
00241               badjncy[l++] = vmap[jj];
00242             }
00243           }
00244           bxadj[++bnvtxs[k]] = l;
00245         }
00246       }
00247     }
00248 
00249     ASSERT(l <= bnedges[0]+bnedges[1]);
00250 
00251     MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
00252 
00253     IFSET(ctrl->dbglvl, DBG_SEPINFO,
00254       printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
00255 
00256     for (i=0; i<csize; i++) {
00257       j = ivmap[cover[i]];
00258       where[j] = 2;
00259     }
00260 
00261     GKfree(&bxadj, &badjncy, LTERM);
00262   }
00263   else {
00264     IFSET(ctrl->dbglvl, DBG_SEPINFO,
00265       printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, 0, 0, 0));
00266   }
00267 
00268   /* Prepare to refine the vertex separator */
00269   idxcopy(nvtxs, graph->where, vmap);
00270   GKfree(&graph->rdata, LTERM);
00271 
00272   Allocate2WayNodePartitionMemory(ctrl, graph);
00273   idxcopy(nvtxs, vmap, graph->where);
00274   idxwspacefree(ctrl, nvtxs+2*graph->nbnd);
00275 
00276   Compute2WayNodePartitionParams(ctrl, graph);
00277 
00278   ASSERT(CheckNodePartitionParams(graph));
00279 
00280   FM_2WayNodeRefine_OneSided(ctrl, graph, ubfactor, 6); 
00281 
00282   ASSERT(IsSeparable(graph));
00283 }
00284
libs/ck-libs/parmetis/METISLib/separator.c
