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