Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * graph.c
00005  *
00006  * This file contains functions that deal with setting up the graphs
00007  * for METIS.
00008  *
00009  * Started 7/25/97
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 /*************************************************************************
00019 * This function sets up the graph from the user input
00020 **************************************************************************/
00021 void SetUpGraph(GraphType *graph, int OpType, int nvtxs, int ncon,
00022        idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int wgtflag)
00023 {
00024   int i, j, k, sum, gsize;
00025   floattype *nvwgt;
00026   idxtype tvwgt[MAXNCON];
00027 
00028   if (OpType == OP_KMETIS && ncon == 1 && (wgtflag&2) == 0 && (wgtflag&1) == 0) {
00029     SetUpGraphKway(graph, nvtxs, xadj, adjncy);
00030     return;
00031   }
00032 
00033   InitGraph(graph);
00034 
00035   graph->nvtxs = nvtxs;
00036   graph->nedges = xadj[nvtxs];
00037   graph->ncon = ncon;
00038   graph->xadj = xadj;
00039   graph->adjncy = adjncy;
00040 
00041   if (ncon == 1) { /* We are in the non mC mode */
00042     gsize = 0; 
00043     if ((wgtflag&2) == 0)
00044       gsize += nvtxs;
00045     if ((wgtflag&1) == 0)
00046       gsize += graph->nedges;
00047 
00048     gsize += 2*nvtxs;
00049 
00050     graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
00051 
00052     /* Create the vertex/edge weight vectors if they are not supplied */
00053     gsize = 0;
00054     if ((wgtflag&2) == 0) {
00055       vwgt = graph->vwgt = idxset(nvtxs, 1, graph->gdata);
00056       gsize += nvtxs;
00057     }
00058     else
00059       graph->vwgt = vwgt;
00060 
00061     if ((wgtflag&1) == 0) {
00062       adjwgt = graph->adjwgt = idxset(graph->nedges, 1, graph->gdata+gsize);
00063       gsize += graph->nedges;
00064     }
00065     else
00066       graph->adjwgt = adjwgt;
00067 
00068 
00069     /* Compute the initial values of the adjwgtsum */
00070     graph->adjwgtsum = graph->gdata + gsize;
00071     gsize += nvtxs;
00072 
00073     for (i=0; i<nvtxs; i++) {
00074       sum = 0;
00075       for (j=xadj[i]; j<xadj[i+1]; j++)
00076         sum += adjwgt[j];
00077       graph->adjwgtsum[i] = sum;
00078     }
00079 
00080     graph->cmap = graph->gdata + gsize;
00081     gsize += nvtxs;
00082 
00083   }
00084   else {  /* Set up the graph in MOC mode */
00085     gsize = 0; 
00086     if ((wgtflag&1) == 0)
00087       gsize += graph->nedges;
00088 
00089     gsize += 2*nvtxs;
00090 
00091     graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
00092     gsize = 0;
00093 
00094     for (i=0; i<ncon; i++) 
00095       tvwgt[i] = idxsum_strd(nvtxs, vwgt+i, ncon);
00096     
00097     nvwgt = graph->nvwgt = fmalloc(ncon*nvtxs, "SetUpGraph: nvwgt");
00098 
00099     for (i=0; i<nvtxs; i++) {
00100       for (j=0; j<ncon; j++) 
00101         nvwgt[i*ncon+j] = (1.0*vwgt[i*ncon+j])/(1.0*tvwgt[j]);
00102     }
00103 
00104 
00105     /* Create the edge weight vectors if they are not supplied */
00106     if ((wgtflag&1) == 0) {
00107       adjwgt = graph->adjwgt = idxset(graph->nedges, 1, graph->gdata+gsize);
00108       gsize += graph->nedges;
00109     }
00110     else
00111       graph->adjwgt = adjwgt;
00112 
00113     /* Compute the initial values of the adjwgtsum */
00114     graph->adjwgtsum = graph->gdata + gsize;
00115     gsize += nvtxs;
00116 
00117     for (i=0; i<nvtxs; i++) {
00118       sum = 0;
00119       for (j=xadj[i]; j<xadj[i+1]; j++)
00120         sum += adjwgt[j];
00121       graph->adjwgtsum[i] = sum;
00122     }
00123 
00124     graph->cmap = graph->gdata + gsize;
00125     gsize += nvtxs;
00126 
00127   }
00128 
00129   if (OpType != OP_KMETIS && OpType != OP_KVMETIS) {
00130     graph->label = idxmalloc(nvtxs, "SetUpGraph: label");
00131 
00132     for (i=0; i<nvtxs; i++)
00133       graph->label[i] = i;
00134   }
00135 
00136 }
00137 
00138 
00139 /*************************************************************************
00140 * This function sets up the graph from the user input
00141 **************************************************************************/
00142 void SetUpGraphKway(GraphType *graph, int nvtxs, idxtype *xadj, idxtype *adjncy)
00143 {
00144   int i;
00145 
00146   InitGraph(graph);
00147 
00148   graph->nvtxs = nvtxs;
00149   graph->nedges = xadj[nvtxs];
00150   graph->ncon = 1;
00151   graph->xadj = xadj;
00152   graph->vwgt = NULL;
00153   graph->adjncy = adjncy;
00154   graph->adjwgt = NULL;
00155 
00156   graph->gdata = idxmalloc(2*nvtxs, "SetUpGraph: gdata");
00157   graph->adjwgtsum = graph->gdata;
00158   graph->cmap = graph->gdata + nvtxs;
00159 
00160   /* Compute the initial values of the adjwgtsum */
00161   for (i=0; i<nvtxs; i++) 
00162     graph->adjwgtsum[i] = xadj[i+1]-xadj[i];
00163 
00164 }
00165 
00166 
00167 
00168 /*************************************************************************
00169 * This function sets up the graph from the user input
00170 **************************************************************************/
00171 void SetUpGraph2(GraphType *graph, int nvtxs, int ncon, idxtype *xadj, 
00172        idxtype *adjncy, floattype *nvwgt, idxtype *adjwgt)
00173 {
00174   int i, j, sum;
00175 
00176   InitGraph(graph);
00177 
00178   graph->nvtxs = nvtxs;
00179   graph->nedges = xadj[nvtxs];
00180   graph->ncon = ncon;
00181   graph->xadj = xadj;
00182   graph->adjncy = adjncy;
00183   graph->adjwgt = adjwgt;
00184 
00185   graph->nvwgt = fmalloc(nvtxs*ncon, "SetUpGraph2: graph->nvwgt");
00186   scopy(nvtxs*ncon, nvwgt, graph->nvwgt);
00187 
00188   graph->gdata = idxmalloc(2*nvtxs, "SetUpGraph: gdata");
00189 
00190   /* Compute the initial values of the adjwgtsum */
00191   graph->adjwgtsum = graph->gdata;
00192   for (i=0; i<nvtxs; i++) {
00193     sum = 0;
00194     for (j=xadj[i]; j<xadj[i+1]; j++)
00195       sum += adjwgt[j];
00196     graph->adjwgtsum[i] = sum;
00197   }
00198 
00199   graph->cmap = graph->gdata+nvtxs;
00200 
00201   graph->label = idxmalloc(nvtxs, "SetUpGraph: label");
00202   for (i=0; i<nvtxs; i++)
00203     graph->label[i] = i;
00204 
00205 }
00206 
00207 
00208 /*************************************************************************
00209 * This function sets up the graph from the user input
00210 **************************************************************************/
00211 void VolSetUpGraph(GraphType *graph, int OpType, int nvtxs, int ncon, idxtype *xadj, 
00212                    idxtype *adjncy, idxtype *vwgt, idxtype *vsize, int wgtflag)
00213 {
00214   int i, j, k, sum, gsize;
00215   idxtype *adjwgt;
00216   floattype *nvwgt;
00217   idxtype tvwgt[MAXNCON];
00218 
00219   InitGraph(graph);
00220 
00221   graph->nvtxs = nvtxs;
00222   graph->nedges = xadj[nvtxs];
00223   graph->ncon = ncon;
00224   graph->xadj = xadj;
00225   graph->adjncy = adjncy;
00226 
00227   if (ncon == 1) { /* We are in the non mC mode */
00228     gsize = graph->nedges;  /* This is for the edge weights */
00229     if ((wgtflag&2) == 0)
00230       gsize += nvtxs; /* vwgts */
00231     if ((wgtflag&1) == 0)
00232       gsize += nvtxs; /* vsize */
00233 
00234     gsize += 2*nvtxs;
00235 
00236     graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
00237 
00238     /* Create the vertex/edge weight vectors if they are not supplied */
00239     gsize = 0;
00240     if ((wgtflag&2) == 0) {
00241       vwgt = graph->vwgt = idxset(nvtxs, 1, graph->gdata);
00242       gsize += nvtxs;
00243     }
00244     else
00245       graph->vwgt = vwgt;
00246 
00247     if ((wgtflag&1) == 0) {
00248       vsize = graph->vsize = idxset(nvtxs, 1, graph->gdata);
00249       gsize += nvtxs;
00250     }
00251     else
00252       graph->vsize = vsize;
00253 
00254     /* Allocate memory for edge weights and initialize them to the sum of the vsize */
00255     adjwgt = graph->adjwgt = graph->gdata+gsize;
00256     gsize += graph->nedges;
00257 
00258     for (i=0; i<nvtxs; i++) {
00259       for (j=xadj[i]; j<xadj[i+1]; j++)
00260         adjwgt[j] = 1+vsize[i]+vsize[adjncy[j]];
00261     }
00262 
00263 
00264     /* Compute the initial values of the adjwgtsum */
00265     graph->adjwgtsum = graph->gdata + gsize;
00266     gsize += nvtxs;
00267 
00268     for (i=0; i<nvtxs; i++) {
00269       sum = 0;
00270       for (j=xadj[i]; j<xadj[i+1]; j++)
00271         sum += adjwgt[j];
00272       graph->adjwgtsum[i] = sum;
00273     }
00274 
00275     graph->cmap = graph->gdata + gsize;
00276     gsize += nvtxs;
00277 
00278   }
00279   else {  /* Set up the graph in MOC mode */
00280     gsize = graph->nedges; 
00281     if ((wgtflag&1) == 0)
00282       gsize += nvtxs;
00283 
00284     gsize += 2*nvtxs;
00285 
00286     graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
00287     gsize = 0;
00288 
00289     /* Create the normalized vertex weights along each constrain */
00290     if ((wgtflag&2) == 0) 
00291       vwgt = idxsmalloc(nvtxs, 1, "SetUpGraph: vwgt");
00292 
00293     for (i=0; i<ncon; i++) 
00294       tvwgt[i] = idxsum_strd(nvtxs, vwgt+i, ncon);
00295     
00296     nvwgt = graph->nvwgt = fmalloc(ncon*nvtxs, "SetUpGraph: nvwgt");
00297 
00298     for (i=0; i<nvtxs; i++) {
00299       for (j=0; j<ncon; j++) 
00300         nvwgt[i*ncon+j] = (1.0*vwgt[i*ncon+j])/(1.0*tvwgt[j]);
00301     }
00302     if ((wgtflag&2) == 0) 
00303       free(vwgt);
00304 
00305 
00306     /* Create the vsize vector if it is not supplied */
00307     if ((wgtflag&1) == 0) {
00308       vsize = graph->vsize = idxset(nvtxs, 1, graph->gdata);
00309       gsize += nvtxs;
00310     }
00311     else
00312       graph->vsize = vsize;
00313 
00314     /* Allocate memory for edge weights and initialize them to the sum of the vsize */
00315     adjwgt = graph->adjwgt = graph->gdata+gsize;
00316     gsize += graph->nedges;
00317 
00318     for (i=0; i<nvtxs; i++) {
00319       for (j=xadj[i]; j<xadj[i+1]; j++)
00320         adjwgt[j] = 1+vsize[i]+vsize[adjncy[j]];
00321     }
00322 
00323     /* Compute the initial values of the adjwgtsum */
00324     graph->adjwgtsum = graph->gdata + gsize;
00325     gsize += nvtxs;
00326 
00327     for (i=0; i<nvtxs; i++) {
00328       sum = 0;
00329       for (j=xadj[i]; j<xadj[i+1]; j++)
00330         sum += adjwgt[j];
00331       graph->adjwgtsum[i] = sum;
00332     }
00333 
00334     graph->cmap = graph->gdata + gsize;
00335     gsize += nvtxs;
00336 
00337   }
00338 
00339   if (OpType != OP_KVMETIS) {
00340     graph->label = idxmalloc(nvtxs, "SetUpGraph: label");
00341 
00342     for (i=0; i<nvtxs; i++)
00343       graph->label[i] = i;
00344   }
00345 
00346 }
00347 
00348 
00349 /*************************************************************************
00350 * This function randomly permutes the adjacency lists of a graph
00351 **************************************************************************/
00352 void RandomizeGraph(GraphType *graph)
00353 {
00354   int i, j, k, l, tmp, nvtxs;
00355   idxtype *xadj, *adjncy, *adjwgt;
00356 
00357   nvtxs = graph->nvtxs;
00358   xadj = graph->xadj;
00359   adjncy = graph->adjncy;
00360   adjwgt = graph->adjwgt;
00361 
00362   for (i=0; i<nvtxs; i++) {
00363     l = xadj[i+1]-xadj[i];
00364     for (j=xadj[i]; j<xadj[i+1]; j++) {
00365       k = xadj[i] + RandomInRange(l);
00366       SWAP(adjncy[j], adjncy[k], tmp);
00367       SWAP(adjwgt[j], adjwgt[k], tmp);
00368     }
00369   }
00370 }
00371 
00372 
00373 /*************************************************************************
00374 * This function checks whether or not partition pid is contigous
00375 **************************************************************************/
00376 int IsConnectedSubdomain(CtrlType *ctrl, GraphType *graph, int pid, int report)
00377 {
00378   int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
00379   idxtype *xadj, *adjncy, *where, *touched, *queue;
00380   idxtype *cptr;
00381 
00382   nvtxs = graph->nvtxs;
00383   xadj = graph->xadj;
00384   adjncy = graph->adjncy;
00385   where = graph->where;
00386 
00387   touched = idxsmalloc(nvtxs, 0, "IsConnected: touched");
00388   queue   = idxmalloc(nvtxs, "IsConnected: queue");
00389   cptr    = idxmalloc(nvtxs+1, "IsConnected: cptr");
00390 
00391   nleft = 0;
00392   for (i=0; i<nvtxs; i++) {
00393     if (where[i] == pid) 
00394       nleft++;
00395   }
00396 
00397   for (i=0; i<nvtxs; i++) {
00398     if (where[i] == pid) 
00399       break;
00400   }
00401 
00402   touched[i] = 1;
00403   queue[0] = i;
00404   first = 0; last = 1;
00405 
00406   cptr[0] = 0;  /* This actually points to queue */
00407   ncmps = 0;
00408   while (first != nleft) {
00409     if (first == last) { /* Find another starting vertex */
00410       cptr[++ncmps] = first;
00411       for (i=0; i<nvtxs; i++) {
00412         if (where[i] == pid && !touched[i])
00413           break;
00414       }
00415       queue[last++] = i;
00416       touched[i] = 1;
00417     }
00418 
00419     i = queue[first++];
00420     for (j=xadj[i]; j<xadj[i+1]; j++) {
00421       k = adjncy[j];
00422       if (where[k] == pid && !touched[k]) {
00423         queue[last++] = k;
00424         touched[k] = 1;
00425       }
00426     }
00427   }
00428   cptr[++ncmps] = first;
00429 
00430   if (ncmps > 1 && report) {
00431     printf("The graph has %d connected components in partition %d:\t", ncmps, pid);
00432     for (i=0; i<ncmps; i++) {
00433       wgt = 0;
00434       for (j=cptr[i]; j<cptr[i+1]; j++)
00435         wgt += graph->vwgt[queue[j]];
00436       printf("[%5d %5d] ", cptr[i+1]-cptr[i], wgt);
00437       /*
00438       if (cptr[i+1]-cptr[i] == 1)
00439         printf("[%d %d] ", queue[cptr[i]], xadj[queue[cptr[i]]+1]-xadj[queue[cptr[i]]]);
00440       */
00441     }
00442     printf("\n");
00443   }
00444 
00445   GKfree(&touched, &queue, &cptr, LTERM);
00446 
00447   return (ncmps == 1 ? 1 : 0);
00448 }
00449 
00450 
00451 /*************************************************************************
00452 * This function checks whether a graph is contigous or not
00453 **************************************************************************/
00454 int IsConnected(CtrlType *ctrl, GraphType *graph, int report)
00455 {
00456   int i, j, k, nvtxs, first, last;
00457   idxtype *xadj, *adjncy, *touched, *queue;
00458 
00459   nvtxs = graph->nvtxs;
00460   xadj = graph->xadj;
00461   adjncy = graph->adjncy;
00462 
00463   touched = idxsmalloc(nvtxs, 0, "IsConnected: touched");
00464   queue = idxmalloc(nvtxs, "IsConnected: queue");
00465 
00466   touched[0] = 1;
00467   queue[0] = 0;
00468   first = 0; last = 1;
00469 
00470   while (first < last) {
00471     i = queue[first++];
00472     for (j=xadj[i]; j<xadj[i+1]; j++) {
00473       k = adjncy[j];
00474       if (!touched[k]) {
00475         queue[last++] = k;
00476         touched[k] = 1;
00477       }
00478     }
00479   }
00480 
00481   if (first != nvtxs && report)
00482     printf("The graph is not connected. It has %d disconnected vertices!\n", nvtxs-first);
00483 
00484   return (first == nvtxs ? 1 : 0);
00485 }
00486 
00487 
00488 /*************************************************************************
00489 * This function checks whether or not partition pid is contigous
00490 **************************************************************************/
00491 int IsConnected2(GraphType *graph, int report)
00492 {
00493   int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
00494   idxtype *xadj, *adjncy, *where, *touched, *queue;
00495   idxtype *cptr;
00496 
00497   nvtxs = graph->nvtxs;
00498   xadj = graph->xadj;
00499   adjncy = graph->adjncy;
00500   where = graph->where;
00501 
00502   touched = idxsmalloc(nvtxs, 0, "IsConnected: touched");
00503   queue   = idxmalloc(nvtxs, "IsConnected: queue");
00504   cptr    = idxmalloc(nvtxs+1, "IsConnected: cptr");
00505 
00506   nleft = nvtxs;
00507   touched[0] = 1;
00508   queue[0] = 0;
00509   first = 0; last = 1;
00510 
00511   cptr[0] = 0;  /* This actually points to queue */
00512   ncmps = 0;
00513   while (first != nleft) {
00514     if (first == last) { /* Find another starting vertex */
00515       cptr[++ncmps] = first;
00516       for (i=0; i<nvtxs; i++) {
00517         if (!touched[i])
00518           break;
00519       }
00520       queue[last++] = i;
00521       touched[i] = 1;
00522     }
00523 
00524     i = queue[first++];
00525     for (j=xadj[i]; j<xadj[i+1]; j++) {
00526       k = adjncy[j];
00527       if (!touched[k]) {
00528         queue[last++] = k;
00529         touched[k] = 1;
00530       }
00531     }
00532   }
00533   cptr[++ncmps] = first;
00534 
00535   if (ncmps > 1 && report) {
00536     printf("%d connected components:\t", ncmps);
00537     for (i=0; i<ncmps; i++) {
00538       if (cptr[i+1]-cptr[i] > 200)
00539         printf("[%5d] ", cptr[i+1]-cptr[i]);
00540     }
00541     printf("\n");
00542   }
00543 
00544   GKfree(&touched, &queue, &cptr, LTERM);
00545 
00546   return (ncmps == 1 ? 1 : 0);
00547 }
00548 
00549 
00550 /*************************************************************************
00551 * This function returns the number of connected components in cptr,cind
00552 * The separator of the graph is used to split it and then find its components.
00553 **************************************************************************/
00554 int FindComponents(CtrlType *ctrl, GraphType *graph, idxtype *cptr, idxtype *cind)
00555 {
00556   int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
00557   idxtype *xadj, *adjncy, *where, *touched, *queue;
00558 
00559   nvtxs = graph->nvtxs;
00560   xadj = graph->xadj;
00561   adjncy = graph->adjncy;
00562   where = graph->where;
00563 
00564   touched = idxsmalloc(nvtxs, 0, "IsConnected: queue");
00565 
00566   for (i=0; i<graph->nbnd; i++)
00567     touched[graph->bndind[i]] = 1;
00568 
00569   queue = cind;
00570 
00571   nleft = 0;
00572   for (i=0; i<nvtxs; i++) {
00573     if (where[i] != 2) 
00574       nleft++;
00575   }
00576 
00577   for (i=0; i<nvtxs; i++) {
00578     if (where[i] != 2)
00579       break;
00580   }
00581 
00582   touched[i] = 1;
00583   queue[0] = i;
00584   first = 0; last = 1;
00585 
00586   cptr[0] = 0;  /* This actually points to queue */
00587   ncmps = 0;
00588   while (first != nleft) {
00589     if (first == last) { /* Find another starting vertex */
00590       cptr[++ncmps] = first;
00591       for (i=0; i<nvtxs; i++) {
00592         if (!touched[i])
00593           break;
00594       }
00595       queue[last++] = i;
00596       touched[i] = 1;
00597     }
00598 
00599     i = queue[first++];
00600     for (j=xadj[i]; j<xadj[i+1]; j++) {
00601       k = adjncy[j];
00602       if (!touched[k]) {
00603         queue[last++] = k;
00604         touched[k] = 1;
00605       }
00606     }
00607   }
00608   cptr[++ncmps] = first;
00609 
00610   free(touched);
00611 
00612   return ncmps;
00613 }
00614 
00615 
00616
libs/ck-libs/parmetis/METISLib/graph.c
