[2051] | 1 | /* |
---|
| 2 | * mcoarsen.c |
---|
| 3 | * |
---|
| 4 | * This file contains the driving routines for the coarsening process |
---|
| 5 | * |
---|
| 6 | * Started 7/23/97 |
---|
| 7 | * George |
---|
| 8 | * |
---|
| 9 | * $Id: mcoarsen.c,v 1.1 1998/11/27 17:59:19 karypis Exp $ |
---|
| 10 | * |
---|
| 11 | */ |
---|
| 12 | |
---|
| 13 | #include <metis.h> |
---|
| 14 | |
---|
| 15 | |
---|
| 16 | /************************************************************************* |
---|
| 17 | * This function takes a graph and creates a sequence of coarser graphs |
---|
| 18 | **************************************************************************/ |
---|
| 19 | GraphType *MCCoarsen2Way(CtrlType *ctrl, GraphType *graph) |
---|
| 20 | { |
---|
| 21 | int i, clevel; |
---|
| 22 | GraphType *cgraph; |
---|
| 23 | |
---|
| 24 | IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->CoarsenTmr)); |
---|
| 25 | |
---|
| 26 | cgraph = graph; |
---|
| 27 | |
---|
| 28 | clevel = 0; |
---|
| 29 | do { |
---|
| 30 | if (ctrl->dbglvl&DBG_COARSEN) { |
---|
| 31 | printf("%6d %7d %10d [%d] [%6.4f", cgraph->nvtxs, cgraph->nedges, |
---|
| 32 | idxsum(cgraph->nvtxs, cgraph->adjwgtsum), ctrl->CoarsenTo, ctrl->nmaxvwgt); |
---|
| 33 | for (i=0; i<graph->ncon; i++) |
---|
| 34 | printf(" %5.3f", ssum_strd(cgraph->nvtxs, cgraph->nvwgt+i, cgraph->ncon)); |
---|
| 35 | printf("]\n"); |
---|
| 36 | } |
---|
| 37 | |
---|
| 38 | switch (ctrl->CType) { |
---|
| 39 | case MATCH_RM: |
---|
| 40 | MCMatch_RM(ctrl, cgraph); |
---|
| 41 | break; |
---|
| 42 | case MATCH_HEM: |
---|
| 43 | if (clevel < 1) |
---|
| 44 | MCMatch_RM(ctrl, cgraph); |
---|
| 45 | else |
---|
| 46 | MCMatch_HEM(ctrl, cgraph); |
---|
| 47 | break; |
---|
| 48 | case MATCH_SHEM: |
---|
| 49 | if (clevel < 1) |
---|
| 50 | MCMatch_RM(ctrl, cgraph); |
---|
| 51 | else |
---|
| 52 | MCMatch_SHEM(ctrl, cgraph); |
---|
| 53 | break; |
---|
| 54 | case MATCH_SHEMKWAY: |
---|
| 55 | MCMatch_SHEM(ctrl, cgraph); |
---|
| 56 | break; |
---|
| 57 | case MATCH_SHEBM_ONENORM: |
---|
| 58 | MCMatch_SHEBM(ctrl, cgraph, 1); |
---|
| 59 | break; |
---|
| 60 | case MATCH_SHEBM_INFNORM: |
---|
| 61 | MCMatch_SHEBM(ctrl, cgraph, -1); |
---|
| 62 | break; |
---|
| 63 | case MATCH_SBHEM_ONENORM: |
---|
| 64 | MCMatch_SBHEM(ctrl, cgraph, 1); |
---|
| 65 | break; |
---|
| 66 | case MATCH_SBHEM_INFNORM: |
---|
| 67 | MCMatch_SBHEM(ctrl, cgraph, -1); |
---|
| 68 | break; |
---|
| 69 | default: |
---|
| 70 | errexit("Unknown CType: %d\n", ctrl->CType); |
---|
| 71 | } |
---|
| 72 | |
---|
| 73 | cgraph = cgraph->coarser; |
---|
| 74 | clevel++; |
---|
| 75 | |
---|
| 76 | } while (cgraph->nvtxs > ctrl->CoarsenTo && cgraph->nvtxs < COARSEN_FRACTION2*cgraph->finer->nvtxs && cgraph->nedges > cgraph->nvtxs/2); |
---|
| 77 | |
---|
| 78 | if (ctrl->dbglvl&DBG_COARSEN) { |
---|
| 79 | printf("%6d %7d %10d [%d] [%6.4f", cgraph->nvtxs, cgraph->nedges, |
---|
| 80 | idxsum(cgraph->nvtxs, cgraph->adjwgtsum), ctrl->CoarsenTo, ctrl->nmaxvwgt); |
---|
| 81 | for (i=0; i<graph->ncon; i++) |
---|
| 82 | printf(" %5.3f", ssum_strd(cgraph->nvtxs, cgraph->nvwgt+i, cgraph->ncon)); |
---|
| 83 | printf("]\n"); |
---|
| 84 | } |
---|
| 85 | |
---|
| 86 | |
---|
| 87 | IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->CoarsenTmr)); |
---|
| 88 | |
---|
| 89 | return cgraph; |
---|
| 90 | } |
---|
| 91 | |
---|