Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * ccgraph.c
00005  *
00006  * This file contains the functions that create the coarse graph
00007  *
00008  * Started 8/11/97
00009  * George
00010  *
00011  * $Id$
00012  *
00013  */
00014 
00015 #include <metis.h>
00016 
00017 
00018 
00019 /*************************************************************************
00020 * This function creates the coarser graph
00021 **************************************************************************/
00022 void CreateCoarseGraph(CtrlType *ctrl, GraphType *graph, int cnvtxs, idxtype *match, idxtype *perm)
00023 {
00024   int i, j, jj, k, kk, l, m, istart, iend, nvtxs, nedges, ncon, cnedges, v, u, mask, dovsize;
00025   idxtype *xadj, *vwgt, *vsize, *adjncy, *adjwgt, *adjwgtsum, *auxadj;
00026   idxtype *cmap, *htable;
00027   idxtype *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt, *cadjwgtsum;
00028   floattype *nvwgt, *cnvwgt;
00029   GraphType *cgraph;
00030 
00031   dovsize = (ctrl->optype == OP_KVMETIS ? 1 : 0);
00032 
00033   mask = HTLENGTH;
00034   if (cnvtxs < 8*mask || graph->nedges/graph->nvtxs > 15) { 
00035     CreateCoarseGraphNoMask(ctrl, graph, cnvtxs, match, perm);
00036     return;
00037   }
00038 
00039   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
00040 
00041   nvtxs = graph->nvtxs;
00042   ncon = graph->ncon;
00043   xadj = graph->xadj;
00044   vwgt = graph->vwgt;
00045   vsize = graph->vsize;
00046   nvwgt = graph->nvwgt;
00047   adjncy = graph->adjncy;
00048   adjwgt = graph->adjwgt;
00049   adjwgtsum = graph->adjwgtsum;
00050   cmap = graph->cmap;
00051 
00052   /* Initialize the coarser graph */
00053   cgraph = SetUpCoarseGraph(graph, cnvtxs, dovsize);
00054   cxadj = cgraph->xadj;
00055   cvwgt = cgraph->vwgt;
00056   cvsize = cgraph->vsize;
00057   cnvwgt = cgraph->nvwgt;
00058   cadjwgtsum = cgraph->adjwgtsum;
00059   cadjncy = cgraph->adjncy;
00060   cadjwgt = cgraph->adjwgt;
00061 
00062 
00063   iend = xadj[nvtxs];
00064   auxadj = ctrl->wspace.auxcore; 
00065   memcpy(auxadj, adjncy, iend*sizeof(idxtype)); 
00066   for (i=0; i<iend; i++)
00067     auxadj[i] = cmap[auxadj[i]];
00068 
00069   htable = idxset(mask+1, -1, idxwspacemalloc(ctrl, mask+1)); 
00070 
00071   cxadj[0] = cnvtxs = cnedges = 0;
00072   for (i=0; i<nvtxs; i++) {
00073     v = perm[i];
00074     if (cmap[v] != cnvtxs) 
00075       continue;
00076 
00077     u = match[v];
00078     if (ncon == 1)
00079       cvwgt[cnvtxs] = vwgt[v];
00080     else
00081       scopy(ncon, nvwgt+v*ncon, cnvwgt+cnvtxs*ncon);
00082 
00083     if (dovsize)
00084       cvsize[cnvtxs] = vsize[v];
00085 
00086     cadjwgtsum[cnvtxs] = adjwgtsum[v];
00087     nedges = 0;
00088 
00089     istart = xadj[v];
00090     iend = xadj[v+1];
00091     for (j=istart; j<iend; j++) {
00092       k = auxadj[j];
00093       kk = k&mask;
00094       if ((m = htable[kk]) == -1) {
00095         cadjncy[nedges] = k;
00096         cadjwgt[nedges] = adjwgt[j];
00097         htable[kk] = nedges++;
00098       }
00099       else if (cadjncy[m] == k) {
00100         cadjwgt[m] += adjwgt[j];
00101       }
00102       else {
00103         for (jj=0; jj<nedges; jj++) {
00104           if (cadjncy[jj] == k) {
00105             cadjwgt[jj] += adjwgt[j];
00106             break;
00107           }
00108         }
00109         if (jj == nedges) {
00110           cadjncy[nedges] = k;
00111           cadjwgt[nedges++] = adjwgt[j];
00112         }
00113       }
00114     }
00115 
00116     if (v != u) { 
00117       if (ncon == 1)
00118         cvwgt[cnvtxs] += vwgt[u];
00119       else
00120         saxpy(ncon, 1.0, nvwgt+u*ncon, 1, cnvwgt+cnvtxs*ncon, 1);
00121 
00122       if (dovsize)
00123         cvsize[cnvtxs] += vsize[u];
00124 
00125       cadjwgtsum[cnvtxs] += adjwgtsum[u];
00126 
00127       istart = xadj[u];
00128       iend = xadj[u+1];
00129       for (j=istart; j<iend; j++) {
00130         k = auxadj[j];
00131         kk = k&mask;
00132         if ((m = htable[kk]) == -1) {
00133           cadjncy[nedges] = k;
00134           cadjwgt[nedges] = adjwgt[j];
00135           htable[kk] = nedges++;
00136         }
00137         else if (cadjncy[m] == k) {
00138           cadjwgt[m] += adjwgt[j];
00139         }
00140         else {
00141           for (jj=0; jj<nedges; jj++) {
00142             if (cadjncy[jj] == k) {
00143               cadjwgt[jj] += adjwgt[j];
00144               break;
00145             }
00146           }
00147           if (jj == nedges) {
00148             cadjncy[nedges] = k;
00149             cadjwgt[nedges++] = adjwgt[j];
00150           }
00151         }
00152       }
00153 
00154       /* Remove the contracted adjacency weight */
00155       jj = htable[cnvtxs&mask];
00156       if (jj >= 0 && cadjncy[jj] != cnvtxs) {
00157         for (jj=0; jj<nedges; jj++) {
00158           if (cadjncy[jj] == cnvtxs) 
00159             break;
00160         }
00161       }
00162       if (jj >= 0 && cadjncy[jj] == cnvtxs) { /* This 2nd check is needed for non-adjacent matchings */
00163         cadjwgtsum[cnvtxs] -= cadjwgt[jj];
00164         cadjncy[jj] = cadjncy[--nedges];
00165         cadjwgt[jj] = cadjwgt[nedges];
00166       }
00167     }
00168 
00169     ASSERTP(cadjwgtsum[cnvtxs] == idxsum(nedges, cadjwgt), ("%d %d %d %d %d\n", cnvtxs, cadjwgtsum[cnvtxs], idxsum(nedges, cadjwgt), adjwgtsum[u], adjwgtsum[v]));
00170 
00171     for (j=0; j<nedges; j++)
00172       htable[cadjncy[j]&mask] = -1;  /* Zero out the htable */
00173     htable[cnvtxs&mask] = -1;
00174 
00175     cnedges += nedges;
00176     cxadj[++cnvtxs] = cnedges;
00177     cadjncy += nedges;
00178     cadjwgt += nedges;
00179   }
00180 
00181   cgraph->nedges = cnedges;
00182 
00183   ReAdjustMemory(graph, cgraph, dovsize);
00184 
00185   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
00186 
00187   idxwspacefree(ctrl, mask+1);
00188 
00189 }
00190 
00191 
00192 /*************************************************************************
00193 * This function creates the coarser graph
00194 **************************************************************************/
00195 void CreateCoarseGraphNoMask(CtrlType *ctrl, GraphType *graph, int cnvtxs, idxtype *match, idxtype *perm)
00196 {
00197   int i, j, k, m, istart, iend, nvtxs, nedges, ncon, cnedges, v, u, dovsize;
00198   idxtype *xadj, *vwgt, *vsize, *adjncy, *adjwgt, *adjwgtsum, *auxadj;
00199   idxtype *cmap, *htable;
00200   idxtype *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt, *cadjwgtsum;
00201   floattype *nvwgt, *cnvwgt;
00202   GraphType *cgraph;
00203 
00204   dovsize = (ctrl->optype == OP_KVMETIS ? 1 : 0);
00205 
00206   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
00207 
00208   nvtxs = graph->nvtxs;
00209   ncon = graph->ncon;
00210   xadj = graph->xadj;
00211   vwgt = graph->vwgt;
00212   vsize = graph->vsize;
00213   nvwgt = graph->nvwgt;
00214   adjncy = graph->adjncy;
00215   adjwgt = graph->adjwgt;
00216   adjwgtsum = graph->adjwgtsum;
00217   cmap = graph->cmap;
00218 
00219 
00220   /* Initialize the coarser graph */
00221   cgraph = SetUpCoarseGraph(graph, cnvtxs, dovsize);
00222   cxadj = cgraph->xadj;
00223   cvwgt = cgraph->vwgt;
00224   cvsize = cgraph->vsize;
00225   cnvwgt = cgraph->nvwgt;
00226   cadjwgtsum = cgraph->adjwgtsum;
00227   cadjncy = cgraph->adjncy;
00228   cadjwgt = cgraph->adjwgt;
00229 
00230 
00231   htable = idxset(cnvtxs, -1, idxwspacemalloc(ctrl, cnvtxs));
00232 
00233   iend = xadj[nvtxs];
00234   auxadj = ctrl->wspace.auxcore; 
00235   memcpy(auxadj, adjncy, iend*sizeof(idxtype)); 
00236   for (i=0; i<iend; i++)
00237     auxadj[i] = cmap[auxadj[i]];
00238 
00239   cxadj[0] = cnvtxs = cnedges = 0;
00240   for (i=0; i<nvtxs; i++) {
00241     v = perm[i];
00242     if (cmap[v] != cnvtxs) 
00243       continue;
00244 
00245     u = match[v];
00246     if (ncon == 1)
00247       cvwgt[cnvtxs] = vwgt[v];
00248     else
00249       scopy(ncon, nvwgt+v*ncon, cnvwgt+cnvtxs*ncon);
00250 
00251     if (dovsize)
00252       cvsize[cnvtxs] = vsize[v];
00253 
00254     cadjwgtsum[cnvtxs] = adjwgtsum[v];
00255     nedges = 0;
00256 
00257     istart = xadj[v];
00258     iend = xadj[v+1];
00259     for (j=istart; j<iend; j++) {
00260       k = auxadj[j];
00261       if ((m = htable[k]) == -1) {
00262         cadjncy[nedges] = k;
00263         cadjwgt[nedges] = adjwgt[j];
00264         htable[k] = nedges++;
00265       }
00266       else {
00267         cadjwgt[m] += adjwgt[j];
00268       }
00269     }
00270 
00271     if (v != u) { 
00272       if (ncon == 1)
00273         cvwgt[cnvtxs] += vwgt[u];
00274       else
00275         saxpy(ncon, 1.0, nvwgt+u*ncon, 1, cnvwgt+cnvtxs*ncon, 1);
00276 
00277       if (dovsize)
00278         cvsize[cnvtxs] += vsize[u];
00279 
00280       cadjwgtsum[cnvtxs] += adjwgtsum[u];
00281 
00282       istart = xadj[u];
00283       iend = xadj[u+1];
00284       for (j=istart; j<iend; j++) {
00285         k = auxadj[j];
00286         if ((m = htable[k]) == -1) {
00287           cadjncy[nedges] = k;
00288           cadjwgt[nedges] = adjwgt[j];
00289           htable[k] = nedges++;
00290         }
00291         else {
00292           cadjwgt[m] += adjwgt[j];
00293         }
00294       }
00295 
00296       /* Remove the contracted adjacency weight */
00297       if ((j = htable[cnvtxs]) != -1) {
00298         ASSERT(cadjncy[j] == cnvtxs);
00299         cadjwgtsum[cnvtxs] -= cadjwgt[j];
00300         cadjncy[j] = cadjncy[--nedges];
00301         cadjwgt[j] = cadjwgt[nedges];
00302         htable[cnvtxs] = -1;
00303       }
00304     }
00305 
00306     ASSERTP(cadjwgtsum[cnvtxs] == idxsum(nedges, cadjwgt), ("%d %d\n", cadjwgtsum[cnvtxs], idxsum(nedges, cadjwgt)));
00307 
00308     for (j=0; j<nedges; j++)
00309       htable[cadjncy[j]] = -1;  /* Zero out the htable */
00310 
00311     cnedges += nedges;
00312     cxadj[++cnvtxs] = cnedges;
00313     cadjncy += nedges;
00314     cadjwgt += nedges;
00315   }
00316 
00317   cgraph->nedges = cnedges;
00318 
00319   ReAdjustMemory(graph, cgraph, dovsize);
00320 
00321   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
00322 
00323   idxwspacefree(ctrl, cnvtxs);
00324 }
00325 
00326 
00327 /*************************************************************************
00328 * This function creates the coarser graph
00329 **************************************************************************/
00330 void CreateCoarseGraph_NVW(CtrlType *ctrl, GraphType *graph, int cnvtxs, idxtype *match, idxtype *perm)
00331 {
00332   int i, j, jj, k, kk, l, m, istart, iend, nvtxs, nedges, ncon, cnedges, v, u, mask;
00333   idxtype *xadj, *adjncy, *adjwgtsum, *auxadj;
00334   idxtype *cmap, *htable;
00335   idxtype *cxadj, *cvwgt, *cadjncy, *cadjwgt, *cadjwgtsum;
00336   floattype *nvwgt, *cnvwgt;
00337   GraphType *cgraph;
00338 
00339 
00340   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
00341 
00342   nvtxs = graph->nvtxs;
00343   ncon = graph->ncon;
00344   xadj = graph->xadj;
00345   nvwgt = graph->nvwgt;
00346   adjncy = graph->adjncy;
00347   adjwgtsum = graph->adjwgtsum;
00348   cmap = graph->cmap;
00349 
00350   /* Initialize the coarser graph */
00351   cgraph = SetUpCoarseGraph(graph, cnvtxs, 0);
00352   cxadj = cgraph->xadj;
00353   cvwgt = cgraph->vwgt;
00354   cnvwgt = cgraph->nvwgt;
00355   cadjwgtsum = cgraph->adjwgtsum;
00356   cadjncy = cgraph->adjncy;
00357   cadjwgt = cgraph->adjwgt;
00358 
00359 
00360   iend = xadj[nvtxs];
00361   auxadj = ctrl->wspace.auxcore; 
00362   memcpy(auxadj, adjncy, iend*sizeof(idxtype)); 
00363   for (i=0; i<iend; i++)
00364     auxadj[i] = cmap[auxadj[i]];
00365 
00366   mask = HTLENGTH;
00367   htable = idxset(mask+1, -1, idxwspacemalloc(ctrl, mask+1)); 
00368 
00369   cxadj[0] = cnvtxs = cnedges = 0;
00370   for (i=0; i<nvtxs; i++) {
00371     v = perm[i];
00372     if (cmap[v] != cnvtxs) 
00373       continue;
00374 
00375     u = match[v];
00376     cvwgt[cnvtxs] = 1;
00377     cadjwgtsum[cnvtxs] = adjwgtsum[v];
00378     nedges = 0;
00379 
00380     istart = xadj[v];
00381     iend = xadj[v+1];
00382     for (j=istart; j<iend; j++) {
00383       k = auxadj[j];
00384       kk = k&mask;
00385       if ((m = htable[kk]) == -1) {
00386         cadjncy[nedges] = k;
00387         cadjwgt[nedges] = 1;
00388         htable[kk] = nedges++;
00389       }
00390       else if (cadjncy[m] == k) {
00391         cadjwgt[m]++;
00392       }
00393       else {
00394         for (jj=0; jj<nedges; jj++) {
00395           if (cadjncy[jj] == k) {
00396             cadjwgt[jj]++;
00397             break;
00398           }
00399         }
00400         if (jj == nedges) {
00401           cadjncy[nedges] = k;
00402           cadjwgt[nedges++] = 1;
00403         }
00404       }
00405     }
00406 
00407     if (v != u) { 
00408       cvwgt[cnvtxs]++;
00409       cadjwgtsum[cnvtxs] += adjwgtsum[u];
00410 
00411       istart = xadj[u];
00412       iend = xadj[u+1];
00413       for (j=istart; j<iend; j++) {
00414         k = auxadj[j];
00415         kk = k&mask;
00416         if ((m = htable[kk]) == -1) {
00417           cadjncy[nedges] = k;
00418           cadjwgt[nedges] = 1;
00419           htable[kk] = nedges++;
00420         }
00421         else if (cadjncy[m] == k) {
00422           cadjwgt[m]++;
00423         }
00424         else {
00425           for (jj=0; jj<nedges; jj++) {
00426             if (cadjncy[jj] == k) {
00427               cadjwgt[jj]++;
00428               break;
00429             }
00430           }
00431           if (jj == nedges) {
00432             cadjncy[nedges] = k;
00433             cadjwgt[nedges++] = 1;
00434           }
00435         }
00436       }
00437 
00438       /* Remove the contracted adjacency weight */
00439       jj = htable[cnvtxs&mask];
00440       if (jj >= 0 && cadjncy[jj] != cnvtxs) {
00441         for (jj=0; jj<nedges; jj++) {
00442           if (cadjncy[jj] == cnvtxs) 
00443             break;
00444         }
00445       }
00446       if (jj >= 0 && cadjncy[jj] == cnvtxs) { /* This 2nd check is needed for non-adjacent matchings */
00447         cadjwgtsum[cnvtxs] -= cadjwgt[jj];
00448         cadjncy[jj] = cadjncy[--nedges];
00449         cadjwgt[jj] = cadjwgt[nedges];
00450       }
00451     }
00452 
00453     ASSERTP(cadjwgtsum[cnvtxs] == idxsum(nedges, cadjwgt), ("%d %d %d %d %d\n", cnvtxs, cadjwgtsum[cnvtxs], idxsum(nedges, cadjwgt), adjwgtsum[u], adjwgtsum[v]));
00454 
00455     for (j=0; j<nedges; j++)
00456       htable[cadjncy[j]&mask] = -1;  /* Zero out the htable */
00457     htable[cnvtxs&mask] = -1;
00458 
00459     cnedges += nedges;
00460     cxadj[++cnvtxs] = cnedges;
00461     cadjncy += nedges;
00462     cadjwgt += nedges;
00463   }
00464 
00465   cgraph->nedges = cnedges;
00466 
00467   ReAdjustMemory(graph, cgraph, 0);
00468 
00469   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
00470 
00471   idxwspacefree(ctrl, mask+1);
00472 
00473 }
00474 
00475 
00476 /*************************************************************************
00477 * Setup the various arrays for the coarse graph
00478 **************************************************************************/
00479 GraphType *SetUpCoarseGraph(GraphType *graph, int cnvtxs, int dovsize)
00480 {
00481   GraphType *cgraph;
00482 
00483   cgraph = CreateGraph();
00484   cgraph->nvtxs = cnvtxs;
00485   cgraph->ncon = graph->ncon;
00486 
00487   cgraph->finer = graph;
00488   graph->coarser = cgraph;
00489 
00490 
00491   /* Allocate memory for the coarser graph */
00492   if (graph->ncon == 1) {
00493     if (dovsize) {
00494       cgraph->gdata = idxmalloc(5*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
00495       cgraph->xadj              = cgraph->gdata;
00496       cgraph->vwgt              = cgraph->gdata + cnvtxs+1;
00497       cgraph->vsize             = cgraph->gdata + 2*cnvtxs+1;
00498       cgraph->adjwgtsum         = cgraph->gdata + 3*cnvtxs+1;
00499       cgraph->cmap              = cgraph->gdata + 4*cnvtxs+1;
00500       cgraph->adjncy            = cgraph->gdata + 5*cnvtxs+1;
00501       cgraph->adjwgt            = cgraph->gdata + 5*cnvtxs+1 + graph->nedges;
00502     }
00503     else {
00504       cgraph->gdata = idxmalloc(4*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
00505       cgraph->xadj              = cgraph->gdata;
00506       cgraph->vwgt              = cgraph->gdata + cnvtxs+1;
00507       cgraph->adjwgtsum         = cgraph->gdata + 2*cnvtxs+1;
00508       cgraph->cmap              = cgraph->gdata + 3*cnvtxs+1;
00509       cgraph->adjncy            = cgraph->gdata + 4*cnvtxs+1;
00510       cgraph->adjwgt            = cgraph->gdata + 4*cnvtxs+1 + graph->nedges;
00511     }
00512   }
00513   else {
00514     if (dovsize) {
00515       cgraph->gdata = idxmalloc(4*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
00516       cgraph->xadj              = cgraph->gdata;
00517       cgraph->vsize             = cgraph->gdata + cnvtxs+1;
00518       cgraph->adjwgtsum         = cgraph->gdata + 2*cnvtxs+1;
00519       cgraph->cmap              = cgraph->gdata + 3*cnvtxs+1;
00520       cgraph->adjncy            = cgraph->gdata + 4*cnvtxs+1;
00521       cgraph->adjwgt            = cgraph->gdata + 4*cnvtxs+1 + graph->nedges;
00522     }
00523     else {
00524       cgraph->gdata = idxmalloc(3*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
00525       cgraph->xadj              = cgraph->gdata;
00526       cgraph->adjwgtsum         = cgraph->gdata + cnvtxs+1;
00527       cgraph->cmap              = cgraph->gdata + 2*cnvtxs+1;
00528       cgraph->adjncy            = cgraph->gdata + 3*cnvtxs+1;
00529       cgraph->adjwgt            = cgraph->gdata + 3*cnvtxs+1 + graph->nedges;
00530     }
00531 
00532     cgraph->nvwgt       = fmalloc(graph->ncon*cnvtxs, "SetUpCoarseGraph: nvwgt");
00533   }
00534 
00535   return cgraph;
00536 }
00537 
00538 
00539 /*************************************************************************
00540 * This function re-adjusts the amount of memory that was allocated if
00541 * it will lead to significant savings
00542 **************************************************************************/
00543 void ReAdjustMemory(GraphType *graph, GraphType *cgraph, int dovsize) 
00544 {
00545 
00546   if (cgraph->nedges > 100000 && graph->nedges < 0.7*graph->nedges) {
00547     idxcopy(cgraph->nedges, cgraph->adjwgt, cgraph->adjncy+cgraph->nedges);
00548 
00549     if (graph->ncon == 1) {
00550       if (dovsize) {
00551         cgraph->gdata = realloc(cgraph->gdata, (5*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
00552 
00553         /* Do this, in case everything was copied into new space */
00554         cgraph->xadj            = cgraph->gdata;
00555         cgraph->vwgt            = cgraph->gdata + cgraph->nvtxs+1;
00556         cgraph->vsize           = cgraph->gdata + 2*cgraph->nvtxs+1;
00557         cgraph->adjwgtsum       = cgraph->gdata + 3*cgraph->nvtxs+1;
00558         cgraph->cmap            = cgraph->gdata + 4*cgraph->nvtxs+1;
00559         cgraph->adjncy          = cgraph->gdata + 5*cgraph->nvtxs+1;
00560         cgraph->adjwgt          = cgraph->gdata + 5*cgraph->nvtxs+1 + cgraph->nedges;
00561       }
00562       else {
00563         cgraph->gdata = realloc(cgraph->gdata, (4*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
00564 
00565         /* Do this, in case everything was copied into new space */
00566         cgraph->xadj    = cgraph->gdata;
00567         cgraph->vwgt    = cgraph->gdata + cgraph->nvtxs+1;
00568         cgraph->adjwgtsum       = cgraph->gdata + 2*cgraph->nvtxs+1;
00569         cgraph->cmap    = cgraph->gdata + 3*cgraph->nvtxs+1;
00570         cgraph->adjncy  = cgraph->gdata + 4*cgraph->nvtxs+1;
00571         cgraph->adjwgt  = cgraph->gdata + 4*cgraph->nvtxs+1 + cgraph->nedges;
00572       }
00573     }
00574     else {
00575       if (dovsize) {
00576         cgraph->gdata = realloc(cgraph->gdata, (4*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
00577 
00578         /* Do this, in case everything was copied into new space */
00579         cgraph->xadj            = cgraph->gdata;
00580         cgraph->vsize           = cgraph->gdata + cgraph->nvtxs+1;
00581         cgraph->adjwgtsum       = cgraph->gdata + 2*cgraph->nvtxs+1;
00582         cgraph->cmap            = cgraph->gdata + 3*cgraph->nvtxs+1;
00583         cgraph->adjncy          = cgraph->gdata + 4*cgraph->nvtxs+1;
00584         cgraph->adjwgt          = cgraph->gdata + 4*cgraph->nvtxs+1 + cgraph->nedges;
00585       }
00586       else {
00587         cgraph->gdata = realloc(cgraph->gdata, (3*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
00588 
00589         /* Do this, in case everything was copied into new space */
00590         cgraph->xadj            = cgraph->gdata;
00591         cgraph->adjwgtsum       = cgraph->gdata + cgraph->nvtxs+1;
00592         cgraph->cmap            = cgraph->gdata + 2*cgraph->nvtxs+1;
00593         cgraph->adjncy          = cgraph->gdata + 3*cgraph->nvtxs+1;
00594         cgraph->adjwgt          = cgraph->gdata + 3*cgraph->nvtxs+1 + cgraph->nedges;
00595       }
00596     }
00597   }
00598 
00599 }
libs/ck-libs/parmetis/METISLib/ccgraph.c
