Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
coarsen.c
Go to the documentation of this file.
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 **************************************************************************/
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 
#define MATCH_RM
Definition: defs.h:98
#define Match_RM
Definition: rename.h:139
#define Coarsen2Way
Definition: rename.h:34
struct graphdef * coarser
Definition: struct.h:198
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
#define Match_HEM
Definition: rename.h:141
struct graphdef * finer
Definition: struct.h:198
#define MATCH_SHEM
Definition: defs.h:100
HitTile_Vector graph
int CType
Definition: struct.h:217
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
idxtype * adjwgt
Definition: struct.h:166
int CoarsenTo
Definition: struct.h:215
#define MATCH_SHEMKWAY
Definition: defs.h:101
#define errexit
Definition: rename.h:379
#define Match_SHEM
Definition: rename.h:142
#define COARSEN_FRACTION2
Definition: defs.h:142
idxtype * vwgt
Definition: struct.h:163
timer CoarsenTmr
Definition: struct.h:230
#define DBG_TIME
Definition: defs.h:154
int nedges
Definition: struct.h:161
int maxvwgt
Definition: struct.h:220
int nvtxs
Definition: struct.h:161
#define DBG_COARSEN
Definition: defs.h:156
#define Match_RM_NVW
Definition: rename.h:140
#define MATCH_HEM
Definition: defs.h:99
#define starttimer(tmr)
Definition: macros.h:53