Charm++: Charm Source Code Documentation

00001 /*
00002  * coarsen.c
00003  *
00004  * This file contains the driving routines for the coarsening process 
00005  *
00006  * Started 7/23/97
00007  * George
00008  *
00009  * $Id$
00010  *
00011  */
00012 
00013 #include <metis.h>
00014 
00015 
00016 /*************************************************************************
00017 * This function takes a graph and creates a sequence of coarser graphs
00018 **************************************************************************/
00019 GraphType *Coarsen2Way(CtrlType *ctrl, GraphType *graph)
00020 {
00021   int clevel;
00022   GraphType *cgraph;
00023 
00024   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->CoarsenTmr));
00025 
00026   cgraph = graph;
00027 
00028   /* The following is ahack to allow the multiple bisections to go through with correct
00029      coarsening */
00030   if (ctrl->CType > 20) {
00031     clevel = 1;
00032     ctrl->CType -= 20;
00033   }
00034   else
00035     clevel = 0;
00036 
00037   do {
00038     IFSET(ctrl->dbglvl, DBG_COARSEN, printf("%6d %7d [%d] [%d %d]\n",
00039           cgraph->nvtxs, cgraph->nedges, ctrl->CoarsenTo, ctrl->maxvwgt, 
00040           (cgraph->vwgt ? idxsum(cgraph->nvtxs, cgraph->vwgt) : cgraph->nvtxs)));
00041 
00042     if (cgraph->adjwgt) {
00043       switch (ctrl->CType) {
00044         case MATCH_RM:
00045           Match_RM(ctrl, cgraph);
00046           break;
00047         case MATCH_HEM:
00048           if (clevel < 1 || cgraph->nedges == 0)
00049             Match_RM(ctrl, cgraph);
00050           else
00051             Match_HEM(ctrl, cgraph);
00052           break;
00053         case MATCH_SHEM:
00054           if (clevel < 1 || cgraph->nedges == 0)
00055             Match_RM(ctrl, cgraph);
00056           else
00057             Match_SHEM(ctrl, cgraph);
00058           break;
00059         case MATCH_SHEMKWAY:
00060           if (cgraph->nedges == 0)
00061             Match_RM(ctrl, cgraph);
00062           else
00063             Match_SHEM(ctrl, cgraph);
00064           break;
00065         default:
00066           errexit("Unknown CType: %d\n", ctrl->CType);
00067       }
00068     }
00069     else {
00070       Match_RM_NVW(ctrl, cgraph);
00071     }
00072 
00073     cgraph = cgraph->coarser;
00074     clevel++;
00075 
00076   } while (cgraph->nvtxs > ctrl->CoarsenTo && cgraph->nvtxs < COARSEN_FRACTION2*cgraph->finer->nvtxs && cgraph->nedges > cgraph->nvtxs/2); 
00077 
00078   IFSET(ctrl->dbglvl, DBG_COARSEN, printf("%6d %7d [%d] [%d %d]\n",
00079         cgraph->nvtxs, cgraph->nedges, ctrl->CoarsenTo, ctrl->maxvwgt, 
00080         (cgraph->vwgt ? idxsum(cgraph->nvtxs, cgraph->vwgt) : cgraph->nvtxs)));
00081 
00082   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->CoarsenTmr));
00083 
00084   return cgraph;
00085 }
00086
libs/ck-libs/parmetis/METISLib/coarsen.c
