Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * mesh.c
00005  *
00006  * This file contains routines for converting 3D and 4D finite element
00007  * meshes into dual or nodal graphs
00008  *
00009  * Started 8/18/97
00010  * George
00011  *
00012  * $Id: mesh.c 13804 2013-03-04 23:49:08Z karypis $
00013  *
00014  */
00015 
00016 #include "metislib.h"
00017 
00018 
00019 /*****************************************************************************/
00043 /*****************************************************************************/
00044 int METIS_MeshToDual(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, 
00045           idx_t *ncommon, idx_t *numflag,  idx_t **r_xadj, idx_t **r_adjncy)
00046 {
00047   int sigrval=0, renumber=0;
00048 
00049   /* set up malloc cleaning code and signal catchers */
00050   if (!gk_malloc_init()) 
00051     return METIS_ERROR_MEMORY;
00052 
00053   gk_sigtrap();
00054 
00055   if ((sigrval = gk_sigcatch()) != 0) 
00056     goto SIGTHROW;
00057 
00058 
00059   /* renumber the mesh */
00060   if (*numflag == 1) {
00061     ChangeMesh2CNumbering(*ne, eptr, eind);
00062     renumber = 1;
00063   }
00064 
00065   /* create dual graph */
00066   *r_xadj = *r_adjncy = NULL;
00067   CreateGraphDual(*ne, *nn, eptr, eind, *ncommon, r_xadj, r_adjncy);
00068 
00069 
00070 SIGTHROW:
00071   if (renumber)
00072     ChangeMesh2FNumbering(*ne, eptr, eind, *ne, *r_xadj, *r_adjncy);
00073 
00074   gk_siguntrap();
00075   gk_malloc_cleanup(0);
00076 
00077   if (sigrval != 0) {
00078     if (*r_xadj != NULL)
00079       free(*r_xadj);
00080     if (*r_adjncy != NULL)
00081       free(*r_adjncy);
00082     *r_xadj = *r_adjncy = NULL;
00083   }
00084 
00085   return metis_rcode(sigrval);
00086 }
00087 
00088 
00089 /*****************************************************************************/
00113 /*****************************************************************************/
00114 int METIS_MeshToNodal(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, 
00115           idx_t *numflag,  idx_t **r_xadj, idx_t **r_adjncy)
00116 {
00117   int sigrval=0, renumber=0;
00118 
00119   /* set up malloc cleaning code and signal catchers */
00120   if (!gk_malloc_init()) 
00121     return METIS_ERROR_MEMORY;
00122 
00123   gk_sigtrap();
00124 
00125   if ((sigrval = gk_sigcatch()) != 0) 
00126     goto SIGTHROW;
00127 
00128 
00129   /* renumber the mesh */
00130   if (*numflag == 1) {
00131     ChangeMesh2CNumbering(*ne, eptr, eind);
00132     renumber = 1;
00133   }
00134 
00135   /* create nodal graph */
00136   *r_xadj = *r_adjncy = NULL;
00137   CreateGraphNodal(*ne, *nn, eptr, eind, r_xadj, r_adjncy);
00138 
00139 
00140 SIGTHROW:
00141   if (renumber)
00142     ChangeMesh2FNumbering(*ne, eptr, eind, *nn, *r_xadj, *r_adjncy);
00143 
00144   gk_siguntrap();
00145   gk_malloc_cleanup(0);
00146 
00147   if (sigrval != 0) {
00148     if (*r_xadj != NULL)
00149       free(*r_xadj);
00150     if (*r_adjncy != NULL)
00151       free(*r_adjncy);
00152     *r_xadj = *r_adjncy = NULL;
00153   }
00154 
00155   return metis_rcode(sigrval);
00156 }
00157 
00158 
00159 /*****************************************************************************/
00161 /*****************************************************************************/
00162 void CreateGraphDual(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t ncommon, 
00163           idx_t **r_xadj, idx_t **r_adjncy)
00164 {
00165   idx_t i, j, nnbrs;
00166   idx_t *nptr, *nind;
00167   idx_t *xadj, *adjncy;
00168   idx_t *marker, *nbrs;
00169 
00170   if (ncommon < 1) {
00171     printf("  Increased ncommon to 1, as it was initially %"PRIDX"\n", ncommon);
00172     ncommon = 1;
00173   }
00174 
00175   /* construct the node-element list first */
00176   nptr = ismalloc(nn+1, 0, "CreateGraphDual: nptr");
00177   nind = imalloc(eptr[ne], "CreateGraphDual: nind");
00178 
00179   for (i=0; i<ne; i++) {
00180     for (j=eptr[i]; j<eptr[i+1]; j++)
00181       nptr[eind[j]]++;
00182   }
00183   MAKECSR(i, nn, nptr);
00184 
00185   for (i=0; i<ne; i++) {
00186     for (j=eptr[i]; j<eptr[i+1]; j++)
00187       nind[nptr[eind[j]]++] = i;
00188   }
00189   SHIFTCSR(i, nn, nptr);
00190 
00191 
00192   /* Allocate memory for xadj, since you know its size.
00193      These are done using standard malloc as they are returned
00194      to the calling function */
00195   if ((xadj = (idx_t *)malloc((ne+1)*sizeof(idx_t))) == NULL) 
00196     gk_errexit(SIGMEM, "***Failed to allocate memory for xadj.\n");
00197   *r_xadj = xadj;
00198   iset(ne+1, 0, xadj);
00199 
00200   /* allocate memory for working arrays used by FindCommonElements */
00201   marker = ismalloc(ne, 0, "CreateGraphDual: marker");
00202   nbrs   = imalloc(ne, "CreateGraphDual: nbrs");
00203 
00204   for (i=0; i<ne; i++) {
00205     xadj[i] = FindCommonElements(i, eptr[i+1]-eptr[i], eind+eptr[i], nptr, 
00206                   nind, eptr, ncommon, marker, nbrs);
00207   }
00208   MAKECSR(i, ne, xadj);
00209 
00210   /* Allocate memory for adjncy, since you now know its size.
00211      These are done using standard malloc as they are returned
00212      to the calling function */
00213   if ((adjncy = (idx_t *)malloc(xadj[ne]*sizeof(idx_t))) == NULL) {
00214     free(xadj);
00215     *r_xadj = NULL;
00216     gk_errexit(SIGMEM, "***Failed to allocate memory for adjncy.\n");
00217   }
00218   *r_adjncy = adjncy;
00219 
00220   for (i=0; i<ne; i++) {
00221     nnbrs = FindCommonElements(i, eptr[i+1]-eptr[i], eind+eptr[i], nptr, 
00222                 nind, eptr, ncommon, marker, nbrs);
00223     for (j=0; j<nnbrs; j++)
00224       adjncy[xadj[i]++] = nbrs[j];
00225   }
00226   SHIFTCSR(i, ne, xadj);
00227   
00228   gk_free((void **)&nptr, &nind, &marker, &nbrs, LTERM);
00229 }
00230 
00231 
00232 /*****************************************************************************/
00236 /*****************************************************************************/
00237 idx_t FindCommonElements(idx_t qid, idx_t elen, idx_t *eind, idx_t *nptr, 
00238           idx_t *nind, idx_t *eptr, idx_t ncommon, idx_t *marker, idx_t *nbrs)
00239 {
00240   idx_t i, ii, j, jj, k, l, overlap;
00241 
00242   /* find all elements that share at least one node with qid */
00243   for (k=0, i=0; i<elen; i++) {
00244     j = eind[i];
00245     for (ii=nptr[j]; ii<nptr[j+1]; ii++) {
00246       jj = nind[ii];
00247 
00248       if (marker[jj] == 0) 
00249         nbrs[k++] = jj;
00250       marker[jj]++;
00251     }
00252   }
00253 
00254   /* put qid into the neighbor list (in case it is not there) so that it
00255      will be removed in the next step */
00256   if (marker[qid] == 0)
00257     nbrs[k++] = qid;
00258   marker[qid] = 0;
00259 
00260   /* compact the list to contain only those with at least ncommon nodes */
00261   for (j=0, i=0; i<k; i++) {
00262     overlap = marker[l = nbrs[i]];
00263     if (overlap >= ncommon || 
00264         overlap >= elen-1 || 
00265         overlap >= eptr[l+1]-eptr[l]-1)
00266       nbrs[j++] = l;
00267     marker[l] = 0;
00268   }
00269 
00270   return j;
00271 }
00272 
00273 
00274 /*****************************************************************************/
00276 /*****************************************************************************/
00277 void CreateGraphNodal(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, 
00278           idx_t **r_xadj, idx_t **r_adjncy)
00279 {
00280   idx_t i, j, nnbrs;
00281   idx_t *nptr, *nind;
00282   idx_t *xadj, *adjncy;
00283   idx_t *marker, *nbrs;
00284 
00285 
00286   /* construct the node-element list first */
00287   nptr = ismalloc(nn+1, 0, "CreateGraphNodal: nptr");
00288   nind = imalloc(eptr[ne], "CreateGraphNodal: nind");
00289 
00290   for (i=0; i<ne; i++) {
00291     for (j=eptr[i]; j<eptr[i+1]; j++)
00292       nptr[eind[j]]++;
00293   }
00294   MAKECSR(i, nn, nptr);
00295 
00296   for (i=0; i<ne; i++) {
00297     for (j=eptr[i]; j<eptr[i+1]; j++)
00298       nind[nptr[eind[j]]++] = i;
00299   }
00300   SHIFTCSR(i, nn, nptr);
00301 
00302 
00303   /* Allocate memory for xadj, since you know its size.
00304      These are done using standard malloc as they are returned
00305      to the calling function */
00306   if ((xadj = (idx_t *)malloc((nn+1)*sizeof(idx_t))) == NULL)
00307     gk_errexit(SIGMEM, "***Failed to allocate memory for xadj.\n");
00308   *r_xadj = xadj;
00309   iset(nn+1, 0, xadj);
00310 
00311   /* allocate memory for working arrays used by FindCommonElements */
00312   marker = ismalloc(nn, 0, "CreateGraphNodal: marker");
00313   nbrs   = imalloc(nn, "CreateGraphNodal: nbrs");
00314 
00315   for (i=0; i<nn; i++) {
00316     xadj[i] = FindCommonNodes(i, nptr[i+1]-nptr[i], nind+nptr[i], eptr, 
00317                   eind, marker, nbrs);
00318   }
00319   MAKECSR(i, nn, xadj);
00320 
00321   /* Allocate memory for adjncy, since you now know its size.
00322      These are done using standard malloc as they are returned
00323      to the calling function */
00324   if ((adjncy = (idx_t *)malloc(xadj[nn]*sizeof(idx_t))) == NULL) {
00325     free(xadj);
00326     *r_xadj = NULL;
00327     gk_errexit(SIGMEM, "***Failed to allocate memory for adjncy.\n");
00328   }
00329   *r_adjncy = adjncy;
00330 
00331   for (i=0; i<nn; i++) {
00332     nnbrs = FindCommonNodes(i, nptr[i+1]-nptr[i], nind+nptr[i], eptr, 
00333                 eind, marker, nbrs);
00334     for (j=0; j<nnbrs; j++)
00335       adjncy[xadj[i]++] = nbrs[j];
00336   }
00337   SHIFTCSR(i, nn, xadj);
00338   
00339   gk_free((void **)&nptr, &nind, &marker, &nbrs, LTERM);
00340 }
00341 
00342 
00343 /*****************************************************************************/
00347 /*****************************************************************************/
00348 idx_t FindCommonNodes(idx_t qid, idx_t nelmnts, idx_t *elmntids, idx_t *eptr, 
00349           idx_t *eind, idx_t *marker, idx_t *nbrs)
00350 {
00351   idx_t i, ii, j, jj, k;
00352 
00353   /* find all nodes that share at least one element with qid */
00354   marker[qid] = 1;  /* this is to prevent self-loops */
00355   for (k=0, i=0; i<nelmnts; i++) {
00356     j = elmntids[i];
00357     for (ii=eptr[j]; ii<eptr[j+1]; ii++) {
00358       jj = eind[ii];
00359       if (marker[jj] == 0) {
00360         nbrs[k++] = jj;
00361         marker[jj] = 1;
00362       }
00363     }
00364   }
00365 
00366   /* reset the marker */
00367   marker[qid] = 0;
00368   for (i=0; i<k; i++) {
00369     marker[nbrs[i]] = 0;
00370   }
00371 
00372   return k;
00373 }
00374 
00375 
00376 
00377 /*************************************************************************/
00379 /*************************************************************************/
00380 mesh_t *CreateMesh(void)
00381 {
00382   mesh_t *mesh;
00383 
00384   mesh = (mesh_t *)gk_malloc(sizeof(mesh_t), "CreateMesh: mesh");
00385 
00386   InitMesh(mesh);
00387 
00388   return mesh;
00389 }
00390 
00391 
00392 /*************************************************************************/
00394 /*************************************************************************/
00395 void InitMesh(mesh_t *mesh) 
00396 {
00397   memset((void *)mesh, 0, sizeof(mesh_t));
00398 }
00399 
00400 
00401 /*************************************************************************/
00403 /*************************************************************************/
00404 void FreeMesh(mesh_t **r_mesh) 
00405 {
00406   mesh_t *mesh = *r_mesh;
00407   
00408   gk_free((void **)&mesh->eptr, &mesh->eind, &mesh->ewgt, &mesh, LTERM);
00409 
00410   *r_mesh = NULL;
00411 }
00412
libs/ck-libs/metis/libmetis/mesh.c
