Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
refine.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * refine.c
5  *
6  * This file contains the driving routines for multilevel refinement
7  *
8  * Started 7/24/97
9  * George
10  *
11  * $Id: refine.c,v 1.1 1998/11/27 17:59:29 karypis Exp $
12  */
13 
14 #include <metis.h>
15 
16 
17 /*************************************************************************
18 * This function is the entry point of refinement
19 **************************************************************************/
20 void Refine2Way(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int *tpwgts, float ubfactor)
21 {
22 
24 
25  /* Compute the parameters of the coarsest graph */
26  Compute2WayPartitionParams(ctrl, graph);
27 
28  for (;;) {
29  ASSERT(CheckBnd(graph));
30 
31  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
32  switch (ctrl->RType) {
33  case 1:
34  Balance2Way(ctrl, graph, tpwgts, ubfactor);
35  FM_2WayEdgeRefine(ctrl, graph, tpwgts, 8);
36  break;
37  default:
38  errexit("Unknown refinement type: %d\n", ctrl->RType);
39  }
40  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
41 
42  if (graph == orggraph)
43  break;
44 
45  graph = graph->finer;
46  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
47  Project2WayPartition(ctrl, graph);
48  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
49  }
50 
51  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
52 }
53 
54 
55 /*************************************************************************
56 * This function allocates memory for 2-way edge refinement
57 **************************************************************************/
59 {
60  int nvtxs;
61 
62  nvtxs = graph->nvtxs;
63 
64  graph->rdata = idxmalloc(5*nvtxs+2, "Allocate2WayPartitionMemory: rdata");
65  graph->pwgts = graph->rdata;
66  graph->where = graph->rdata + 2;
67  graph->id = graph->rdata + nvtxs + 2;
68  graph->ed = graph->rdata + 2*nvtxs + 2;
69  graph->bndptr = graph->rdata + 3*nvtxs + 2;
70  graph->bndind = graph->rdata + 4*nvtxs + 2;
71 }
72 
73 
74 /*************************************************************************
75 * This function computes the initial id/ed
76 **************************************************************************/
78 {
79  int i, j, k, l, nvtxs, nbnd, mincut;
80  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts;
81  idxtype *id, *ed, *where;
82  idxtype *bndptr, *bndind;
83  int me, other;
84 
85  nvtxs = graph->nvtxs;
86  xadj = graph->xadj;
87  vwgt = graph->vwgt;
88  adjncy = graph->adjncy;
89  adjwgt = graph->adjwgt;
90 
91  where = graph->where;
92  pwgts = idxset(2, 0, graph->pwgts);
93  id = idxset(nvtxs, 0, graph->id);
94  ed = idxset(nvtxs, 0, graph->ed);
95  bndptr = idxset(nvtxs, -1, graph->bndptr);
96  bndind = graph->bndind;
97 
98 
99  /*------------------------------------------------------------
100  / Compute now the id/ed degrees
101  /------------------------------------------------------------*/
102  nbnd = mincut = 0;
103  for (i=0; i<nvtxs; i++) {
104  ASSERT(where[i] >= 0 && where[i] <= 1);
105  me = where[i];
106  pwgts[me] += vwgt[i];
107 
108  for (j=xadj[i]; j<xadj[i+1]; j++) {
109  if (me == where[adjncy[j]])
110  id[i] += adjwgt[j];
111  else
112  ed[i] += adjwgt[j];
113  }
114 
115  if (ed[i] > 0 || xadj[i] == xadj[i+1]) {
116  mincut += ed[i];
117  bndptr[i] = nbnd;
118  bndind[nbnd++] = i;
119  }
120  }
121 
122  graph->mincut = mincut/2;
123  graph->nbnd = nbnd;
124 
125  ASSERT(pwgts[0]+pwgts[1] == idxsum(nvtxs, vwgt));
126 }
127 
128 
129 
130 /*************************************************************************
131 * This function projects a partition, and at the same time computes the
132 * parameters for refinement.
133 **************************************************************************/
135 {
136  int i, j, k, nvtxs, nbnd, me;
137  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
138  idxtype *cmap, *where, *id, *ed, *bndptr, *bndind;
139  idxtype *cwhere, *cid, *ced, *cbndptr;
140  GraphType *cgraph;
141 
142  cgraph = graph->coarser;
143  cwhere = cgraph->where;
144  cid = cgraph->id;
145  ced = cgraph->ed;
146  cbndptr = cgraph->bndptr;
147 
148  nvtxs = graph->nvtxs;
149  cmap = graph->cmap;
150  xadj = graph->xadj;
151  adjncy = graph->adjncy;
152  adjwgt = graph->adjwgt;
153  adjwgtsum = graph->adjwgtsum;
154 
155  Allocate2WayPartitionMemory(ctrl, graph);
156 
157  where = graph->where;
158  id = idxset(nvtxs, 0, graph->id);
159  ed = idxset(nvtxs, 0, graph->ed);
160  bndptr = idxset(nvtxs, -1, graph->bndptr);
161  bndind = graph->bndind;
162 
163 
164  /* Go through and project partition and compute id/ed for the nodes */
165  for (i=0; i<nvtxs; i++) {
166  k = cmap[i];
167  where[i] = cwhere[k];
168  cmap[i] = cbndptr[k];
169  }
170 
171  for (nbnd=0, i=0; i<nvtxs; i++) {
172  me = where[i];
173 
174  id[i] = adjwgtsum[i];
175 
176  if (xadj[i] == xadj[i+1]) {
177  bndptr[i] = nbnd;
178  bndind[nbnd++] = i;
179  }
180  else {
181  if (cmap[i] != -1) { /* If it is an interface node. Note that cmap[i] = cbndptr[cmap[i]] */
182  for (j=xadj[i]; j<xadj[i+1]; j++) {
183  if (me != where[adjncy[j]])
184  ed[i] += adjwgt[j];
185  }
186  id[i] -= ed[i];
187 
188  if (ed[i] > 0 || xadj[i] == xadj[i+1]) {
189  bndptr[i] = nbnd;
190  bndind[nbnd++] = i;
191  }
192  }
193  }
194  }
195 
196  graph->mincut = cgraph->mincut;
197  graph->nbnd = nbnd;
198  idxcopy(2, cgraph->pwgts, graph->pwgts);
199 
200  FreeGraph(graph->coarser);
201  graph->coarser = NULL;
202 
203 }
204 
timer ProjectTmr
Definition: struct.h:230
timer RefTmr
Definition: struct.h:230
#define Balance2Way
Definition: rename.h:16
#define Project2WayPartition
Definition: rename.h:331
idxtype * pwgts
Definition: struct.h:176
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
int nbnd
Definition: struct.h:177
idxtype * ed
Definition: struct.h:181
idxtype * id
Definition: struct.h:181
#define FreeGraph
Definition: rename.h:169
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
#define Compute2WayPartitionParams
Definition: rename.h:330
struct graphdef * coarser
Definition: struct.h:198
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
struct graphdef * finer
Definition: struct.h:198
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define Refine2Way
Definition: rename.h:328
int idxtype
Definition: struct.h:19
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define CheckBnd
Definition: rename.h:44
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxcopy(n, a, b)
Definition: macros.h:44
idxtype * bndind
Definition: struct.h:178
timer UncoarsenTmr
Definition: struct.h:230
#define errexit
Definition: rename.h:379
#define FM_2WayEdgeRefine
Definition: rename.h:58
idxtype * vwgt
Definition: struct.h:163
#define Allocate2WayPartitionMemory
Definition: rename.h:329
#define DBG_TIME
Definition: defs.h:154
int RType
Definition: struct.h:219
#define idxmalloc
Definition: rename.h:383
int nvtxs
Definition: struct.h:161
#define ASSERT(expr)
Definition: macros.h:130
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53