| 1 | /* |
|---|
| 2 | * coarsen.c |
|---|
| 3 | * |
|---|
| 4 | * This file contains the driving routines for the coarsening process |
|---|
| 5 | * |
|---|
| 6 | * Started 7/23/97 |
|---|
| 7 | * George |
|---|
| 8 | * |
|---|
| 9 | * $Id: coarsen.c,v 1.1 1998/11/27 17:59:12 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 *Coarsen2Way(CtrlType *ctrl, GraphType *graph) |
|---|
| 20 | { |
|---|
| 21 | int clevel; |
|---|
| 22 | GraphType *cgraph; |
|---|
| 23 | |
|---|
| 24 | IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->CoarsenTmr)); |
|---|
| 25 | |
|---|
| 26 | cgraph = graph; |
|---|
| 27 | |
|---|
| 28 | /* The following is ahack to allow the multiple bisections to go through with correct |
|---|
| 29 | coarsening */ |
|---|
| 30 | if (ctrl->CType > 20) { |
|---|
| 31 | clevel = 1; |
|---|
| 32 | ctrl->CType -= 20; |
|---|
| 33 | } |
|---|
| 34 | else |
|---|
| 35 | clevel = 0; |
|---|
| 36 | |
|---|
| 37 | do { |
|---|
| 38 | IFSET(ctrl->dbglvl, DBG_COARSEN, printf("%6d %7d [%d] [%d %d]\n", |
|---|
| 39 | cgraph->nvtxs, cgraph->nedges, ctrl->CoarsenTo, ctrl->maxvwgt, |
|---|
| 40 | (cgraph->vwgt ? idxsum(cgraph->nvtxs, cgraph->vwgt) : cgraph->nvtxs))); |
|---|
| 41 | |
|---|
| 42 | if (cgraph->adjwgt) { |
|---|
| 43 | switch (ctrl->CType) { |
|---|
| 44 | case MATCH_RM: |
|---|
| 45 | Match_RM(ctrl, cgraph); |
|---|
| 46 | break; |
|---|
| 47 | case MATCH_HEM: |
|---|
| 48 | if (clevel < 1) |
|---|
| 49 | Match_RM(ctrl, cgraph); |
|---|
| 50 | else |
|---|
| 51 | Match_HEM(ctrl, cgraph); |
|---|
| 52 | break; |
|---|
| 53 | case MATCH_SHEM: |
|---|
| 54 | if (clevel < 1) |
|---|
| 55 | Match_RM(ctrl, cgraph); |
|---|
| 56 | else |
|---|
| 57 | Match_SHEM(ctrl, cgraph); |
|---|
| 58 | break; |
|---|
| 59 | case MATCH_SHEMKWAY: |
|---|
| 60 | Match_SHEM(ctrl, cgraph); |
|---|
| 61 | break; |
|---|
| 62 | default: |
|---|
| 63 | errexit("Unknown CType: %d\n", ctrl->CType); |
|---|
| 64 | } |
|---|
| 65 | } |
|---|
| 66 | else { |
|---|
| 67 | Match_RM_NVW(ctrl, cgraph); |
|---|
| 68 | } |
|---|
| 69 | |
|---|
| 70 | cgraph = cgraph->coarser; |
|---|
| 71 | clevel++; |
|---|
| 72 | |
|---|
| 73 | } while (cgraph->nvtxs > ctrl->CoarsenTo && cgraph->nvtxs < COARSEN_FRACTION2*cgraph->finer->nvtxs && cgraph->nedges > cgraph->nvtxs/2); |
|---|
| 74 | |
|---|
| 75 | IFSET(ctrl->dbglvl, DBG_COARSEN, printf("%6d %7d [%d] [%d %d]\n", |
|---|
| 76 | cgraph->nvtxs, cgraph->nedges, ctrl->CoarsenTo, ctrl->maxvwgt, |
|---|
| 77 | (cgraph->vwgt ? idxsum(cgraph->nvtxs, cgraph->vwgt) : cgraph->nvtxs))); |
|---|
| 78 | |
|---|
| 79 | IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->CoarsenTmr)); |
|---|
| 80 | |
|---|
| 81 | return cgraph; |
|---|
| 82 | } |
|---|
| 83 | |
|---|
