Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * debug.c
00005  *
00006  * This file contains code that performs self debuging
00007  *
00008  * Started 7/24/97
00009  * George
00010  *
00011  */
00012 
00013 #include "metislib.h"
00014 
00015 
00016 
00017 /*************************************************************************/
00020 /*************************************************************************/
00021 idx_t ComputeCut(graph_t *graph, idx_t *where)
00022 {
00023   idx_t i, j, cut;
00024 
00025   if (graph->adjwgt == NULL) {
00026     for (cut=0, i=0; i<graph->nvtxs; i++) {
00027       for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
00028         if (where[i] != where[graph->adjncy[j]])
00029           cut++;
00030     }
00031   }
00032   else {
00033     for (cut=0, i=0; i<graph->nvtxs; i++) {
00034       for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
00035         if (where[i] != where[graph->adjncy[j]])
00036           cut += graph->adjwgt[j];
00037     }
00038   }
00039 
00040   return cut/2;
00041 }
00042 
00043 
00044 /*************************************************************************/
00047 /*************************************************************************/
00048 idx_t ComputeVolume(graph_t *graph, idx_t *where)
00049 {
00050   idx_t i, j, k, me, nvtxs, nparts, totalv;
00051   idx_t *xadj, *adjncy, *vsize, *marker;
00052 
00053 
00054   nvtxs  = graph->nvtxs;
00055   xadj   = graph->xadj;
00056   adjncy = graph->adjncy;
00057   vsize  = graph->vsize;
00058 
00059   nparts = where[iargmax(nvtxs, where)]+1;
00060   marker = ismalloc(nparts, -1, "ComputeVolume: marker");
00061 
00062   totalv = 0;
00063 
00064   for (i=0; i<nvtxs; i++) {
00065     marker[where[i]] = i;
00066     for (j=xadj[i]; j<xadj[i+1]; j++) {
00067       k = where[adjncy[j]];
00068       if (marker[k] != i) {
00069         marker[k] = i;
00070         totalv += (vsize ? vsize[i] : 1);
00071       }
00072     }
00073   }
00074 
00075   gk_free((void **)&marker, LTERM);
00076 
00077   return totalv;
00078 }
00079 
00080 
00081 /*************************************************************************/
00084 /*************************************************************************/
00085 idx_t ComputeMaxCut(graph_t *graph, idx_t nparts, idx_t *where)
00086 {
00087   idx_t i, j, maxcut;
00088   idx_t *cuts;
00089 
00090   cuts = ismalloc(nparts, 0, "ComputeMaxCut: cuts");
00091 
00092   if (graph->adjwgt == NULL) {
00093     for (i=0; i<graph->nvtxs; i++) {
00094       for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
00095         if (where[i] != where[graph->adjncy[j]]) 
00096           cuts[where[i]]++;
00097     }
00098   }
00099   else {
00100     for (i=0; i<graph->nvtxs; i++) {
00101       for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
00102         if (where[i] != where[graph->adjncy[j]])
00103           cuts[where[i]] += graph->adjwgt[j];
00104     }
00105   }
00106 
00107   maxcut = cuts[iargmax(nparts, cuts)];
00108 
00109   printf("%zu => %"PRIDX"\n", iargmax(nparts, cuts), maxcut);
00110 
00111   gk_free((void **)&cuts, LTERM);
00112 
00113   return maxcut;
00114 }
00115 
00116 
00117 /*************************************************************************/
00120 /*************************************************************************/
00121 idx_t CheckBnd(graph_t *graph) 
00122 {
00123   idx_t i, j, nvtxs, nbnd;
00124   idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
00125 
00126   nvtxs = graph->nvtxs;
00127   xadj = graph->xadj;
00128   adjncy = graph->adjncy;
00129   where = graph->where;
00130   bndptr = graph->bndptr;
00131   bndind = graph->bndind;
00132 
00133   for (nbnd=0, i=0; i<nvtxs; i++) {
00134     if (xadj[i+1]-xadj[i] == 0)
00135       nbnd++;   /* Islands are considered to be boundary vertices */
00136 
00137     for (j=xadj[i]; j<xadj[i+1]; j++) {
00138       if (where[i] != where[adjncy[j]]) {
00139         nbnd++;
00140         ASSERT(bndptr[i] != -1);
00141         ASSERT(bndind[bndptr[i]] == i);
00142         break;
00143       }
00144     }
00145   }
00146 
00147   ASSERTP(nbnd == graph->nbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, graph->nbnd));
00148 
00149   return 1;
00150 }
00151 
00152 
00153 
00154 /*************************************************************************/
00157 /*************************************************************************/
00158 idx_t CheckBnd2(graph_t *graph) 
00159 {
00160   idx_t i, j, nvtxs, nbnd, id, ed;
00161   idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
00162 
00163   nvtxs  = graph->nvtxs;
00164   xadj   = graph->xadj;
00165   adjncy = graph->adjncy;
00166   where  = graph->where;
00167   bndptr = graph->bndptr;
00168   bndind = graph->bndind;
00169 
00170   for (nbnd=0, i=0; i<nvtxs; i++) {
00171     id = ed = 0;
00172     for (j=xadj[i]; j<xadj[i+1]; j++) {
00173       if (where[i] != where[adjncy[j]]) 
00174         ed += graph->adjwgt[j];
00175       else
00176         id += graph->adjwgt[j];
00177     }
00178     if (ed - id >= 0 && xadj[i] < xadj[i+1]) {
00179       nbnd++;
00180       ASSERTP(bndptr[i] != -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", i, id, ed));
00181       ASSERT(bndind[bndptr[i]] == i);
00182     }
00183   }
00184 
00185   ASSERTP(nbnd == graph->nbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, graph->nbnd));
00186 
00187   return 1;
00188 }
00189 
00190 
00191 /*************************************************************************/
00194 /*************************************************************************/
00195 idx_t CheckNodeBnd(graph_t *graph, idx_t onbnd) 
00196 {
00197   idx_t i, j, nvtxs, nbnd;
00198   idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
00199 
00200   nvtxs = graph->nvtxs;
00201   xadj = graph->xadj;
00202   adjncy = graph->adjncy;
00203   where = graph->where;
00204   bndptr = graph->bndptr;
00205   bndind = graph->bndind;
00206 
00207   for (nbnd=0, i=0; i<nvtxs; i++) {
00208     if (where[i] == 2) 
00209       nbnd++;   
00210   }
00211 
00212   ASSERTP(nbnd == onbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, onbnd));
00213 
00214   for (i=0; i<nvtxs; i++) {
00215     if (where[i] != 2) {
00216       ASSERTP(bndptr[i] == -1, ("%"PRIDX" %"PRIDX"\n", i, bndptr[i]));
00217     }
00218     else {
00219       ASSERTP(bndptr[i] != -1, ("%"PRIDX" %"PRIDX"\n", i, bndptr[i]));
00220     }
00221   }
00222 
00223   return 1;
00224 }
00225 
00226 
00227 
00228 /*************************************************************************/
00231 /*************************************************************************/
00232 idx_t CheckRInfo(ctrl_t *ctrl, ckrinfo_t *rinfo)
00233 {
00234   idx_t i, j;
00235   cnbr_t *nbrs;
00236 
00237   nbrs = ctrl->cnbrpool + rinfo->inbr;
00238 
00239   for (i=0; i<rinfo->nnbrs; i++) {
00240     for (j=i+1; j<rinfo->nnbrs; j++)
00241       ASSERTP(nbrs[i].pid != nbrs[j].pid, 
00242           ("%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n", 
00243            i, j, nbrs[i].pid, nbrs[j].pid));
00244   }
00245 
00246   return 1;
00247 }
00248 
00249 
00250 
00251 /*************************************************************************/
00254 /*************************************************************************/
00255 idx_t CheckNodePartitionParams(graph_t *graph)
00256 {
00257   idx_t i, j, k, l, nvtxs, me, other;
00258   idx_t *xadj, *adjncy, *adjwgt, *vwgt, *where;
00259   idx_t edegrees[2], pwgts[3];
00260 
00261   nvtxs  = graph->nvtxs;
00262   xadj   = graph->xadj;
00263   vwgt   = graph->vwgt;
00264   adjncy = graph->adjncy;
00265   adjwgt = graph->adjwgt;
00266   where  = graph->where;
00267 
00268   /*------------------------------------------------------------
00269   / Compute now the separator external degrees
00270   /------------------------------------------------------------*/
00271   pwgts[0] = pwgts[1] = pwgts[2] = 0;
00272   for (i=0; i<nvtxs; i++) {
00273     me = where[i];
00274     pwgts[me] += vwgt[i];
00275 
00276     if (me == 2) { /* If it is on the separator do some computations */
00277       edegrees[0] = edegrees[1] = 0;
00278 
00279       for (j=xadj[i]; j<xadj[i+1]; j++) {
00280         other = where[adjncy[j]];
00281         if (other != 2)
00282           edegrees[other] += vwgt[adjncy[j]];
00283       }
00284       if (edegrees[0] != graph->nrinfo[i].edegrees[0] || 
00285           edegrees[1] != graph->nrinfo[i].edegrees[1]) {
00286         printf("Something wrong with edegrees: %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n", 
00287             i, edegrees[0], edegrees[1], 
00288             graph->nrinfo[i].edegrees[0], graph->nrinfo[i].edegrees[1]);
00289         return 0;
00290       }
00291     }
00292   }
00293 
00294   if (pwgts[0] != graph->pwgts[0] || 
00295       pwgts[1] != graph->pwgts[1] || 
00296       pwgts[2] != graph->pwgts[2]) {
00297     printf("Something wrong with part-weights: %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n", pwgts[0], pwgts[1], pwgts[2], graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]);
00298     return 0;
00299   }
00300 
00301   return 1;
00302 }
00303 
00304 
00305 /*************************************************************************/
00308 /*************************************************************************/
00309 idx_t IsSeparable(graph_t *graph)
00310 {
00311   idx_t i, j, nvtxs, other;
00312   idx_t *xadj, *adjncy, *where;
00313 
00314   nvtxs = graph->nvtxs;
00315   xadj = graph->xadj;
00316   adjncy = graph->adjncy;
00317   where = graph->where;
00318 
00319   for (i=0; i<nvtxs; i++) {
00320     if (where[i] == 2)
00321       continue;
00322     other = (where[i]+1)%2;
00323     for (j=xadj[i]; j<xadj[i+1]; j++) {
00324       ASSERTP(where[adjncy[j]] != other, 
00325           ("%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n", 
00326            i, where[i], adjncy[j], where[adjncy[j]], xadj[i+1]-xadj[i], 
00327            xadj[adjncy[j]+1]-xadj[adjncy[j]]));
00328     }
00329   }
00330 
00331   return 1;
00332 }
00333 
00334 
00335 /*************************************************************************/
00338 /*************************************************************************/
00339 void CheckKWayVolPartitionParams(ctrl_t *ctrl, graph_t *graph)
00340 {
00341   idx_t i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
00342   idx_t *xadj, *vsize, *adjncy, *pwgts, *where, *bndind, *bndptr;
00343   vkrinfo_t *rinfo, *myrinfo, *orinfo, tmprinfo;
00344   vnbr_t *mynbrs, *onbrs, *tmpnbrs;
00345 
00346   WCOREPUSH;
00347 
00348   nvtxs  = graph->nvtxs;
00349   xadj   = graph->xadj;
00350   vsize  = graph->vsize;
00351   adjncy = graph->adjncy;
00352   where  = graph->where;
00353   rinfo  = graph->vkrinfo;
00354 
00355   tmpnbrs = (vnbr_t *)wspacemalloc(ctrl, ctrl->nparts*sizeof(vnbr_t));
00356 
00357   /*------------------------------------------------------------
00358   / Compute now the iv/ev degrees
00359   /------------------------------------------------------------*/
00360   for (i=0; i<nvtxs; i++) {
00361     me = where[i];
00362 
00363     myrinfo = rinfo+i;
00364     mynbrs  = ctrl->vnbrpool + myrinfo->inbr;
00365 
00366     for (k=0; k<myrinfo->nnbrs; k++)
00367       tmpnbrs[k] = mynbrs[k];
00368 
00369     tmprinfo.nnbrs = myrinfo->nnbrs;
00370     tmprinfo.nid    = myrinfo->nid;
00371     tmprinfo.ned    = myrinfo->ned;
00372 
00373     myrinfo = &tmprinfo;
00374     mynbrs  = tmpnbrs;
00375 
00376     for (k=0; k<myrinfo->nnbrs; k++)
00377       mynbrs[k].gv = 0;
00378 
00379     for (j=xadj[i]; j<xadj[i+1]; j++) {
00380       ii     = adjncy[j];
00381       other  = where[ii];
00382       orinfo = rinfo+ii;
00383       onbrs  = ctrl->vnbrpool + orinfo->inbr;
00384 
00385       if (me == other) {
00386         /* Find which domains 'i' is connected and 'ii' is not and update their gain */
00387         for (k=0; k<myrinfo->nnbrs; k++) {
00388           pid = mynbrs[k].pid;
00389           for (kk=0; kk<orinfo->nnbrs; kk++) {
00390             if (onbrs[kk].pid == pid)
00391               break;
00392           }
00393           if (kk == orinfo->nnbrs) 
00394             mynbrs[k].gv -= vsize[ii];
00395         }
00396       }
00397       else {
00398         /* Find the orinfo[me].ed and see if I'm the only connection */
00399         for (k=0; k<orinfo->nnbrs; k++) {
00400           if (onbrs[k].pid == me)
00401             break;
00402         }
00403 
00404         if (onbrs[k].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
00405           for (k=0; k<myrinfo->nnbrs; k++) {
00406             if (mynbrs[k].pid == other) {
00407               mynbrs[k].gv += vsize[ii];
00408               break;
00409             }
00410           }
00411 
00412           /* Increase the gains for all the common domains between 'i' and 'ii' */
00413           for (k=0; k<myrinfo->nnbrs; k++) {
00414             if ((pid = mynbrs[k].pid) == other)
00415               continue;
00416             for (kk=0; kk<orinfo->nnbrs; kk++) {
00417               if (onbrs[kk].pid == pid) {
00418                 mynbrs[k].gv += vsize[ii];
00419                 break;
00420               }
00421             }
00422           }
00423 
00424         }
00425         else {
00426           /* Find which domains 'i' is connected and 'ii' is not and update their gain */
00427           for (k=0; k<myrinfo->nnbrs; k++) {
00428             if ((pid = mynbrs[k].pid) == other)
00429               continue;
00430             for (kk=0; kk<orinfo->nnbrs; kk++) {
00431               if (onbrs[kk].pid == pid)
00432                 break;
00433             }
00434             if (kk == orinfo->nnbrs) 
00435               mynbrs[k].gv -= vsize[ii];
00436           }
00437         }
00438       }
00439     }
00440 
00441     myrinfo = rinfo+i;
00442     mynbrs  = ctrl->vnbrpool + myrinfo->inbr;
00443 
00444     for (k=0; k<myrinfo->nnbrs; k++) {
00445       pid = mynbrs[k].pid;
00446       for (kk=0; kk<tmprinfo.nnbrs; kk++) {
00447         if (tmpnbrs[kk].pid == pid) {
00448           if (tmpnbrs[kk].gv != mynbrs[k].gv)
00449             printf("[%8"PRIDX" %8"PRIDX" %8"PRIDX" %+8"PRIDX" %+8"PRIDX"]\n", 
00450                 i, where[i], pid, mynbrs[k].gv, tmpnbrs[kk].gv);
00451           break;
00452         }
00453       }
00454     }
00455 
00456   }
00457 
00458   WCOREPOP;
00459 }
00460 
00461
libs/ck-libs/metis/libmetis/debug.c
