1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * mkwayrefine.c
5 *
6 * This file contains the driving routines for multilevel k-way refinement
7 *
8 * Started 7/28/97
9 * George
10 *
11 * $Id: mkwayrefine.c,v 1.2 1998/11/27 18:16:19 karypis Exp $
12 */
13
14 #include "metis.h"
15
16
17 /*************************************************************************
18 * This function is the entry point of refinement
19 **************************************************************************/
MocRefineKWayHorizontal(CtrlType * ctrl,GraphType * orggraph,GraphType * graph,int nparts,float * ubvec)20 void MocRefineKWayHorizontal(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts,
21 float *ubvec)
22 {
23
24 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
25
26 /* Compute the parameters of the coarsest graph */
27 MocComputeKWayPartitionParams(ctrl, graph, nparts);
28
29 for (;;) {
30 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
31
32 if (!MocIsHBalanced(graph->ncon, nparts, graph->npwgts, ubvec)) {
33 MocComputeKWayBalanceBoundary(ctrl, graph, nparts);
34 MCGreedy_KWayEdgeBalanceHorizontal(ctrl, graph, nparts, ubvec, 4);
35 ComputeKWayBoundary(ctrl, graph, nparts);
36 }
37
38 MCRandom_KWayEdgeRefineHorizontal(ctrl, graph, nparts, ubvec, 10);
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 MocProjectKWayPartition(ctrl, graph, nparts);
48 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
49 }
50
51 if (!MocIsHBalanced(graph->ncon, nparts, graph->npwgts, ubvec)) {
52 MocComputeKWayBalanceBoundary(ctrl, graph, nparts);
53 MCGreedy_KWayEdgeBalanceHorizontal(ctrl, graph, nparts, ubvec, 4);
54 ComputeKWayBoundary(ctrl, graph, nparts);
55 MCRandom_KWayEdgeRefineHorizontal(ctrl, graph, nparts, ubvec, 10);
56 }
57
58 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
59 }
60
61
62
63
64 /*************************************************************************
65 * This function allocates memory for k-way edge refinement
66 **************************************************************************/
MocAllocateKWayPartitionMemory(CtrlType * ctrl,GraphType * graph,int nparts)67 void MocAllocateKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
68 {
69 int nvtxs, ncon, pad64;
70
71 nvtxs = graph->nvtxs;
72 ncon = graph->ncon;
73
74 pad64 = (3*nvtxs)%2;
75
76 graph->rdata = idxmalloc(3*nvtxs+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
77 graph->where = graph->rdata;
78 graph->bndptr = graph->rdata + nvtxs;
79 graph->bndind = graph->rdata + 2*nvtxs;
80 graph->rinfo = (RInfoType *)(graph->rdata + 3*nvtxs + pad64);
81
82 graph->npwgts = fmalloc(ncon*nparts, "MocAllocateKWayPartitionMemory: npwgts");
83 }
84
85
86 /*************************************************************************
87 * This function computes the initial id/ed
88 **************************************************************************/
MocComputeKWayPartitionParams(CtrlType * ctrl,GraphType * graph,int nparts)89 void MocComputeKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
90 {
91 int i, j, k, l, nvtxs, ncon, nbnd, mincut, me, other;
92 idxtype *xadj, *adjncy, *adjwgt, *where, *bndind, *bndptr;
93 RInfoType *rinfo, *myrinfo;
94 EDegreeType *myedegrees;
95 float *nvwgt, *npwgts;
96
97 nvtxs = graph->nvtxs;
98 ncon = graph->ncon;
99 xadj = graph->xadj;
100 nvwgt = graph->nvwgt;
101 adjncy = graph->adjncy;
102 adjwgt = graph->adjwgt;
103
104 where = graph->where;
105 npwgts = sset(ncon*nparts, 0.0, graph->npwgts);
106 bndind = graph->bndind;
107 bndptr = idxset(nvtxs, -1, graph->bndptr);
108 rinfo = graph->rinfo;
109
110
111 /*------------------------------------------------------------
112 / Compute now the id/ed degrees
113 /------------------------------------------------------------*/
114 ctrl->wspace.cdegree = 0;
115 nbnd = mincut = 0;
116 for (i=0; i<nvtxs; i++) {
117 me = where[i];
118 saxpy(ncon, 1.0, nvwgt+i*ncon, 1, npwgts+me*ncon, 1);
119
120 myrinfo = rinfo+i;
121 myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
122 myrinfo->edegrees = NULL;
123
124 for (j=xadj[i]; j<xadj[i+1]; j++) {
125 if (me != where[adjncy[j]])
126 myrinfo->ed += adjwgt[j];
127 }
128 myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
129
130 if (myrinfo->ed > 0)
131 mincut += myrinfo->ed;
132
133 if (myrinfo->ed-myrinfo->id >= 0)
134 BNDInsert(nbnd, bndind, bndptr, i);
135
136 /* Time to compute the particular external degrees */
137 if (myrinfo->ed > 0) {
138 myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
139 ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
140
141 for (j=xadj[i]; j<xadj[i+1]; j++) {
142 other = where[adjncy[j]];
143 if (me != other) {
144 for (k=0; k<myrinfo->ndegrees; k++) {
145 if (myedegrees[k].pid == other) {
146 myedegrees[k].ed += adjwgt[j];
147 break;
148 }
149 }
150 if (k == myrinfo->ndegrees) {
151 myedegrees[myrinfo->ndegrees].pid = other;
152 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
153 }
154 }
155 }
156
157 ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
158 }
159 }
160
161 graph->mincut = mincut/2;
162 graph->nbnd = nbnd;
163
164 }
165
166
167
168 /*************************************************************************
169 * This function projects a partition, and at the same time computes the
170 * parameters for refinement.
171 **************************************************************************/
MocProjectKWayPartition(CtrlType * ctrl,GraphType * graph,int nparts)172 void MocProjectKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
173 {
174 int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
175 idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
176 idxtype *cmap, *where, *bndptr, *bndind;
177 idxtype *cwhere;
178 GraphType *cgraph;
179 RInfoType *crinfo, *rinfo, *myrinfo;
180 EDegreeType *myedegrees;
181 idxtype *htable;
182
183 cgraph = graph->coarser;
184 cwhere = cgraph->where;
185 crinfo = cgraph->rinfo;
186
187 nvtxs = graph->nvtxs;
188 cmap = graph->cmap;
189 xadj = graph->xadj;
190 adjncy = graph->adjncy;
191 adjwgt = graph->adjwgt;
192 adjwgtsum = graph->adjwgtsum;
193
194 MocAllocateKWayPartitionMemory(ctrl, graph, nparts);
195 where = graph->where;
196 rinfo = graph->rinfo;
197 bndind = graph->bndind;
198 bndptr = idxset(nvtxs, -1, graph->bndptr);
199
200 /* Go through and project partition and compute id/ed for the nodes */
201 for (i=0; i<nvtxs; i++) {
202 k = cmap[i];
203 where[i] = cwhere[k];
204 cmap[i] = crinfo[k].ed; /* For optimization */
205 }
206
207 htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
208
209 ctrl->wspace.cdegree = 0;
210 for (nbnd=0, i=0; i<nvtxs; i++) {
211 me = where[i];
212
213 myrinfo = rinfo+i;
214 myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
215 myrinfo->edegrees = NULL;
216
217 myrinfo->id = adjwgtsum[i];
218
219 if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
220 istart = xadj[i];
221 iend = xadj[i+1];
222
223 myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
224 ctrl->wspace.cdegree += iend-istart;
225
226 ndegrees = 0;
227 for (j=istart; j<iend; j++) {
228 other = where[adjncy[j]];
229 if (me != other) {
230 myrinfo->ed += adjwgt[j];
231 if ((k = htable[other]) == -1) {
232 htable[other] = ndegrees;
233 myedegrees[ndegrees].pid = other;
234 myedegrees[ndegrees++].ed = adjwgt[j];
235 }
236 else {
237 myedegrees[k].ed += adjwgt[j];
238 }
239 }
240 }
241 myrinfo->id -= myrinfo->ed;
242
243 /* Remove space for edegrees if it was interior */
244 if (myrinfo->ed == 0) {
245 myrinfo->edegrees = NULL;
246 ctrl->wspace.cdegree -= iend-istart;
247 }
248 else {
249 if (myrinfo->ed-myrinfo->id >= 0)
250 BNDInsert(nbnd, bndind, bndptr, i);
251
252 myrinfo->ndegrees = ndegrees;
253
254 for (j=0; j<ndegrees; j++)
255 htable[myedegrees[j].pid] = -1;
256 }
257 }
258 }
259
260 scopy(graph->ncon*nparts, cgraph->npwgts, graph->npwgts);
261 graph->mincut = cgraph->mincut;
262 graph->nbnd = nbnd;
263
264 FreeGraph(graph->coarser);
265 graph->coarser = NULL;
266
267 idxwspacefree(ctrl, nparts);
268
269 ASSERT(CheckBnd2(graph));
270
271 }
272
273
274
275 /*************************************************************************
276 * This function computes the boundary definition for balancing
277 **************************************************************************/
MocComputeKWayBalanceBoundary(CtrlType * ctrl,GraphType * graph,int nparts)278 void MocComputeKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
279 {
280 int i, nvtxs, nbnd;
281 idxtype *bndind, *bndptr;
282
283 nvtxs = graph->nvtxs;
284 bndind = graph->bndind;
285 bndptr = idxset(nvtxs, -1, graph->bndptr);
286
287
288 /* Compute the new boundary */
289 nbnd = 0;
290 for (i=0; i<nvtxs; i++) {
291 if (graph->rinfo[i].ed > 0)
292 BNDInsert(nbnd, bndind, bndptr, i);
293 }
294
295 graph->nbnd = nbnd;
296 }
297
298