| 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 | |
|---|
