SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/kwayfm.c
ViewVC logotype

Annotation of /pkg/src/Metis/kwayfm.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (view) (download) (as text)

1 : bates 10 /*
2 :     * kwayfm.c
3 :     *
4 :     * This file contains code that implements the multilevel k-way refinement
5 :     *
6 :     * Started 7/28/97
7 :     * George
8 :     *
9 :     * $Id: kwayfm.c,v 1.1 2003/12/31 21:32:30 bates Exp $
10 :     *
11 :     */
12 :    
13 :     #include <metis.h>
14 :    
15 :    
16 :     /*************************************************************************
17 :     * This function performs k-way refinement
18 :     **************************************************************************/
19 :     void Random_KWayEdgeRefine(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses, int ffactor)
20 :     {
21 :     int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees;
22 :     int from, me, to, oldcut, vwgt, gain;
23 :     idxtype *xadj, *adjncy, *adjwgt;
24 :     idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
25 :     EDegreeType *myedegrees;
26 :     RInfoType *myrinfo;
27 :    
28 :     nvtxs = graph->nvtxs;
29 :     xadj = graph->xadj;
30 :     adjncy = graph->adjncy;
31 :     adjwgt = graph->adjwgt;
32 :    
33 :     bndptr = graph->bndptr;
34 :     bndind = graph->bndind;
35 :    
36 :     where = graph->where;
37 :     pwgts = graph->pwgts;
38 :    
39 :     /* Setup the weight intervals of the various subdomains */
40 :     minwgt = idxwspacemalloc(ctrl, nparts);
41 :     maxwgt = idxwspacemalloc(ctrl, nparts);
42 :     itpwgts = idxwspacemalloc(ctrl, nparts);
43 :     tvwgt = idxsum(nparts, pwgts);
44 :     ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
45 :    
46 :     for (i=0; i<nparts; i++) {
47 :     itpwgts[i] = tpwgts[i]*tvwgt;
48 :     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
49 :     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
50 :     }
51 :    
52 :     perm = idxwspacemalloc(ctrl, nvtxs);
53 :    
54 :     IFSET(ctrl->dbglvl, DBG_REFINE,
55 :     printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
56 :     pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
57 :     1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
58 :     graph->mincut));
59 :    
60 :     for (pass=0; pass<npasses; pass++) {
61 :     ASSERT(ComputeCut(graph, where) == graph->mincut);
62 :    
63 :     oldcut = graph->mincut;
64 :     nbnd = graph->nbnd;
65 :    
66 :     RandomPermute(nbnd, perm, 1);
67 :     for (nmoves=iii=0; iii<graph->nbnd; iii++) {
68 :     ii = perm[iii];
69 :     if (ii >= nbnd)
70 :     continue;
71 :     i = bndind[ii];
72 :    
73 :     myrinfo = graph->rinfo+i;
74 :    
75 :     if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */
76 :     from = where[i];
77 :     vwgt = graph->vwgt[i];
78 :    
79 :     if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from])
80 :     continue; /* This cannot be moved! */
81 :    
82 :     myedegrees = myrinfo->edegrees;
83 :     myndegrees = myrinfo->ndegrees;
84 :    
85 :     j = myrinfo->id;
86 :     for (k=0; k<myndegrees; k++) {
87 :     to = myedegrees[k].pid;
88 :     gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */
89 :     if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0)
90 :     break;
91 :     }
92 :     if (k == myndegrees)
93 :     continue; /* break out if you did not find a candidate */
94 :    
95 :     for (j=k+1; j<myndegrees; j++) {
96 :     to = myedegrees[j].pid;
97 :     if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
98 :     (myedegrees[j].ed == myedegrees[k].ed &&
99 :     itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
100 :     k = j;
101 :     }
102 :    
103 :     to = myedegrees[k].pid;
104 :    
105 :     j = 0;
106 :     if (myedegrees[k].ed-myrinfo->id > 0)
107 :     j = 1;
108 :     else if (myedegrees[k].ed-myrinfo->id == 0) {
109 :     if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
110 :     j = 1;
111 :     }
112 :     if (j == 0)
113 :     continue;
114 :    
115 :     /*=====================================================================
116 :     * If we got here, we can now move the vertex from 'from' to 'to'
117 :     *======================================================================*/
118 :     graph->mincut -= myedegrees[k].ed-myrinfo->id;
119 :    
120 :     IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
121 :    
122 :     /* Update where, weight, and ID/ED information of the vertex you moved */
123 :     where[i] = to;
124 :     INC_DEC(pwgts[to], pwgts[from], vwgt);
125 :     myrinfo->ed += myrinfo->id-myedegrees[k].ed;
126 :     SWAP(myrinfo->id, myedegrees[k].ed, j);
127 :     if (myedegrees[k].ed == 0)
128 :     myedegrees[k] = myedegrees[--myrinfo->ndegrees];
129 :     else
130 :     myedegrees[k].pid = from;
131 :    
132 :     if (myrinfo->ed-myrinfo->id < 0)
133 :     BNDDelete(nbnd, bndind, bndptr, i);
134 :    
135 :     /* Update the degrees of adjacent vertices */
136 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
137 :     ii = adjncy[j];
138 :     me = where[ii];
139 :    
140 :     myrinfo = graph->rinfo+ii;
141 :     if (myrinfo->edegrees == NULL) {
142 :     myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
143 :     ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
144 :     }
145 :     myedegrees = myrinfo->edegrees;
146 :    
147 :     ASSERT(CheckRInfo(myrinfo));
148 :    
149 :     if (me == from) {
150 :     INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
151 :    
152 :     if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
153 :     BNDInsert(nbnd, bndind, bndptr, ii);
154 :     }
155 :     else if (me == to) {
156 :     INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
157 :    
158 :     if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
159 :     BNDDelete(nbnd, bndind, bndptr, ii);
160 :     }
161 :    
162 :     /* Remove contribution from the .ed of 'from' */
163 :     if (me != from) {
164 :     for (k=0; k<myrinfo->ndegrees; k++) {
165 :     if (myedegrees[k].pid == from) {
166 :     if (myedegrees[k].ed == adjwgt[j])
167 :     myedegrees[k] = myedegrees[--myrinfo->ndegrees];
168 :     else
169 :     myedegrees[k].ed -= adjwgt[j];
170 :     break;
171 :     }
172 :     }
173 :     }
174 :    
175 :     /* Add contribution to the .ed of 'to' */
176 :     if (me != to) {
177 :     for (k=0; k<myrinfo->ndegrees; k++) {
178 :     if (myedegrees[k].pid == to) {
179 :     myedegrees[k].ed += adjwgt[j];
180 :     break;
181 :     }
182 :     }
183 :     if (k == myrinfo->ndegrees) {
184 :     myedegrees[myrinfo->ndegrees].pid = to;
185 :     myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
186 :     }
187 :     }
188 :    
189 :     ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
190 :     ASSERT(CheckRInfo(myrinfo));
191 :    
192 :     }
193 :     nmoves++;
194 :     }
195 :     }
196 :    
197 :     graph->nbnd = nbnd;
198 :    
199 :     IFSET(ctrl->dbglvl, DBG_REFINE,
200 :     printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
201 :     pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
202 :     1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut, ComputeVolume(graph, where)));
203 :    
204 :     if (graph->mincut == oldcut)
205 :     break;
206 :     }
207 :    
208 :     idxwspacefree(ctrl, nparts);
209 :     idxwspacefree(ctrl, nparts);
210 :     idxwspacefree(ctrl, nparts);
211 :     idxwspacefree(ctrl, nvtxs);
212 :     }
213 :    
214 :    
215 :    
216 :    
217 :    
218 :    
219 :     /*************************************************************************
220 :     * This function performs k-way refinement
221 :     **************************************************************************/
222 :     void Greedy_KWayEdgeRefine(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses)
223 :     {
224 :     int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain;
225 :     int from, me, to, oldcut, vwgt;
226 :     idxtype *xadj, *adjncy, *adjwgt;
227 :     idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
228 :     EDegreeType *myedegrees;
229 :     RInfoType *myrinfo;
230 :     PQueueType queue;
231 :    
232 :     nvtxs = graph->nvtxs;
233 :     xadj = graph->xadj;
234 :     adjncy = graph->adjncy;
235 :     adjwgt = graph->adjwgt;
236 :    
237 :     bndind = graph->bndind;
238 :     bndptr = graph->bndptr;
239 :    
240 :     where = graph->where;
241 :     pwgts = graph->pwgts;
242 :    
243 :     /* Setup the weight intervals of the various subdomains */
244 :     minwgt = idxwspacemalloc(ctrl, nparts);
245 :     maxwgt = idxwspacemalloc(ctrl, nparts);
246 :     itpwgts = idxwspacemalloc(ctrl, nparts);
247 :     tvwgt = idxsum(nparts, pwgts);
248 :     ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
249 :    
250 :     for (i=0; i<nparts; i++) {
251 :     itpwgts[i] = tpwgts[i]*tvwgt;
252 :     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
253 :     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
254 :     }
255 :    
256 :     perm = idxwspacemalloc(ctrl, nvtxs);
257 :     moved = idxwspacemalloc(ctrl, nvtxs);
258 :    
259 :     PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
260 :    
261 :     IFSET(ctrl->dbglvl, DBG_REFINE,
262 :     printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
263 :     pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
264 :     1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
265 :     graph->mincut));
266 :    
267 :     for (pass=0; pass<npasses; pass++) {
268 :     ASSERT(ComputeCut(graph, where) == graph->mincut);
269 :    
270 :     PQueueReset(&queue);
271 :     idxset(nvtxs, -1, moved);
272 :    
273 :     oldcut = graph->mincut;
274 :     nbnd = graph->nbnd;
275 :    
276 :     RandomPermute(nbnd, perm, 1);
277 :     for (ii=0; ii<nbnd; ii++) {
278 :     i = bndind[perm[ii]];
279 :     PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
280 :     moved[i] = 2;
281 :     }
282 :    
283 :     for (iii=0;;iii++) {
284 :     if ((i = PQueueGetMax(&queue)) == -1)
285 :     break;
286 :     moved[i] = 1;
287 :    
288 :     myrinfo = graph->rinfo+i;
289 :     from = where[i];
290 :     vwgt = graph->vwgt[i];
291 :    
292 :     if (pwgts[from]-vwgt < minwgt[from])
293 :     continue; /* This cannot be moved! */
294 :    
295 :     myedegrees = myrinfo->edegrees;
296 :     myndegrees = myrinfo->ndegrees;
297 :    
298 :     j = myrinfo->id;
299 :     for (k=0; k<myndegrees; k++) {
300 :     to = myedegrees[k].pid;
301 :     gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */
302 :     if (pwgts[to]+vwgt <= maxwgt[to]+gain && gain >= 0)
303 :     break;
304 :     }
305 :     if (k == myndegrees)
306 :     continue; /* break out if you did not find a candidate */
307 :    
308 :     for (j=k+1; j<myndegrees; j++) {
309 :     to = myedegrees[j].pid;
310 :     if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
311 :     (myedegrees[j].ed == myedegrees[k].ed &&
312 :     itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
313 :     k = j;
314 :     }
315 :    
316 :     to = myedegrees[k].pid;
317 :    
318 :     j = 0;
319 :     if (myedegrees[k].ed-myrinfo->id > 0)
320 :     j = 1;
321 :     else if (myedegrees[k].ed-myrinfo->id == 0) {
322 :     if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
323 :     j = 1;
324 :     }
325 :     if (j == 0)
326 :     continue;
327 :    
328 :     /*=====================================================================
329 :     * If we got here, we can now move the vertex from 'from' to 'to'
330 :     *======================================================================*/
331 :     graph->mincut -= myedegrees[k].ed-myrinfo->id;
332 :    
333 :     IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
334 :    
335 :     /* Update where, weight, and ID/ED information of the vertex you moved */
336 :     where[i] = to;
337 :     INC_DEC(pwgts[to], pwgts[from], vwgt);
338 :     myrinfo->ed += myrinfo->id-myedegrees[k].ed;
339 :     SWAP(myrinfo->id, myedegrees[k].ed, j);
340 :     if (myedegrees[k].ed == 0)
341 :     myedegrees[k] = myedegrees[--myrinfo->ndegrees];
342 :     else
343 :     myedegrees[k].pid = from;
344 :    
345 :     if (myrinfo->ed < myrinfo->id)
346 :     BNDDelete(nbnd, bndind, bndptr, i);
347 :    
348 :     /* Update the degrees of adjacent vertices */
349 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
350 :     ii = adjncy[j];
351 :     me = where[ii];
352 :    
353 :     myrinfo = graph->rinfo+ii;
354 :     if (myrinfo->edegrees == NULL) {
355 :     myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
356 :     ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
357 :     }
358 :     myedegrees = myrinfo->edegrees;
359 :    
360 :     ASSERT(CheckRInfo(myrinfo));
361 :    
362 :     oldgain = (myrinfo->ed-myrinfo->id);
363 :    
364 :     if (me == from) {
365 :     INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
366 :    
367 :     if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
368 :     BNDInsert(nbnd, bndind, bndptr, ii);
369 :     }
370 :     else if (me == to) {
371 :     INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
372 :    
373 :     if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
374 :     BNDDelete(nbnd, bndind, bndptr, ii);
375 :     }
376 :    
377 :     /* Remove contribution from the .ed of 'from' */
378 :     if (me != from) {
379 :     for (k=0; k<myrinfo->ndegrees; k++) {
380 :     if (myedegrees[k].pid == from) {
381 :     if (myedegrees[k].ed == adjwgt[j])
382 :     myedegrees[k] = myedegrees[--myrinfo->ndegrees];
383 :     else
384 :     myedegrees[k].ed -= adjwgt[j];
385 :     break;
386 :     }
387 :     }
388 :     }
389 :    
390 :     /* Add contribution to the .ed of 'to' */
391 :     if (me != to) {
392 :     for (k=0; k<myrinfo->ndegrees; k++) {
393 :     if (myedegrees[k].pid == to) {
394 :     myedegrees[k].ed += adjwgt[j];
395 :     break;
396 :     }
397 :     }
398 :     if (k == myrinfo->ndegrees) {
399 :     myedegrees[myrinfo->ndegrees].pid = to;
400 :     myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
401 :     }
402 :     }
403 :    
404 :     /* Update the queue */
405 :     if (me == to || me == from) {
406 :     gain = myrinfo->ed-myrinfo->id;
407 :     if (moved[ii] == 2) {
408 :     if (gain >= 0)
409 :     PQueueUpdate(&queue, ii, oldgain, gain);
410 :     else {
411 :     PQueueDelete(&queue, ii, oldgain);
412 :     moved[ii] = -1;
413 :     }
414 :     }
415 :     else if (moved[ii] == -1 && gain >= 0) {
416 :     PQueueInsert(&queue, ii, gain);
417 :     moved[ii] = 2;
418 :     }
419 :     }
420 :    
421 :     ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
422 :     ASSERT(CheckRInfo(myrinfo));
423 :    
424 :     }
425 :     }
426 :    
427 :     graph->nbnd = nbnd;
428 :    
429 :     IFSET(ctrl->dbglvl, DBG_REFINE,
430 :     printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Cut: %6d\n",
431 :     pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
432 :     1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, graph->mincut));
433 :    
434 :     if (graph->mincut == oldcut)
435 :     break;
436 :     }
437 :    
438 :     PQueueFree(ctrl, &queue);
439 :    
440 :     idxwspacefree(ctrl, nparts);
441 :     idxwspacefree(ctrl, nparts);
442 :     idxwspacefree(ctrl, nparts);
443 :     idxwspacefree(ctrl, nvtxs);
444 :     idxwspacefree(ctrl, nvtxs);
445 :    
446 :     }
447 :    
448 :    
449 :     /*************************************************************************
450 :     * This function performs k-way refinement
451 :     **************************************************************************/
452 :     void Greedy_KWayEdgeBalance(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses)
453 :     {
454 :     int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves;
455 :     int from, me, to, oldcut, vwgt;
456 :     idxtype *xadj, *adjncy, *adjwgt;
457 :     idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
458 :     EDegreeType *myedegrees;
459 :     RInfoType *myrinfo;
460 :     PQueueType queue;
461 :    
462 :     nvtxs = graph->nvtxs;
463 :     xadj = graph->xadj;
464 :     adjncy = graph->adjncy;
465 :     adjwgt = graph->adjwgt;
466 :    
467 :     bndind = graph->bndind;
468 :     bndptr = graph->bndptr;
469 :    
470 :     where = graph->where;
471 :     pwgts = graph->pwgts;
472 :    
473 :     /* Setup the weight intervals of the various subdomains */
474 :     minwgt = idxwspacemalloc(ctrl, nparts);
475 :     maxwgt = idxwspacemalloc(ctrl, nparts);
476 :     itpwgts = idxwspacemalloc(ctrl, nparts);
477 :     tvwgt = idxsum(nparts, pwgts);
478 :     ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
479 :    
480 :     for (i=0; i<nparts; i++) {
481 :     itpwgts[i] = tpwgts[i]*tvwgt;
482 :     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
483 :     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
484 :     }
485 :    
486 :     perm = idxwspacemalloc(ctrl, nvtxs);
487 :     moved = idxwspacemalloc(ctrl, nvtxs);
488 :    
489 :     PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
490 :    
491 :     IFSET(ctrl->dbglvl, DBG_REFINE,
492 :     printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
493 :     pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
494 :     1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
495 :     graph->mincut));
496 :    
497 :     for (pass=0; pass<npasses; pass++) {
498 :     ASSERT(ComputeCut(graph, where) == graph->mincut);
499 :    
500 :     /* Check to see if things are out of balance, given the tolerance */
501 :     for (i=0; i<nparts; i++) {
502 :     if (pwgts[i] > maxwgt[i])
503 :     break;
504 :     }
505 :     if (i == nparts) /* Things are balanced. Return right away */
506 :     break;
507 :    
508 :     PQueueReset(&queue);
509 :     idxset(nvtxs, -1, moved);
510 :    
511 :     oldcut = graph->mincut;
512 :     nbnd = graph->nbnd;
513 :    
514 :     RandomPermute(nbnd, perm, 1);
515 :     for (ii=0; ii<nbnd; ii++) {
516 :     i = bndind[perm[ii]];
517 :     PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
518 :     moved[i] = 2;
519 :     }
520 :    
521 :     nmoves = 0;
522 :     for (;;) {
523 :     if ((i = PQueueGetMax(&queue)) == -1)
524 :     break;
525 :     moved[i] = 1;
526 :    
527 :     myrinfo = graph->rinfo+i;
528 :     from = where[i];
529 :     vwgt = graph->vwgt[i];
530 :    
531 :     if (pwgts[from]-vwgt < minwgt[from])
532 :     continue; /* This cannot be moved! */
533 :    
534 :     myedegrees = myrinfo->edegrees;
535 :     myndegrees = myrinfo->ndegrees;
536 :    
537 :     for (k=0; k<myndegrees; k++) {
538 :     to = myedegrees[k].pid;
539 :     if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
540 :     break;
541 :     }
542 :     if (k == myndegrees)
543 :     continue; /* break out if you did not find a candidate */
544 :    
545 :     for (j=k+1; j<myndegrees; j++) {
546 :     to = myedegrees[j].pid;
547 :     if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])
548 :     k = j;
549 :     }
550 :    
551 :     to = myedegrees[k].pid;
552 :    
553 :     if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->id < 0)
554 :     continue;
555 :    
556 :     /*=====================================================================
557 :     * If we got here, we can now move the vertex from 'from' to 'to'
558 :     *======================================================================*/
559 :     graph->mincut -= myedegrees[k].ed-myrinfo->id;
560 :    
561 :     IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
562 :    
563 :     /* Update where, weight, and ID/ED information of the vertex you moved */
564 :     where[i] = to;
565 :     INC_DEC(pwgts[to], pwgts[from], vwgt);
566 :     myrinfo->ed += myrinfo->id-myedegrees[k].ed;
567 :     SWAP(myrinfo->id, myedegrees[k].ed, j);
568 :     if (myedegrees[k].ed == 0)
569 :     myedegrees[k] = myedegrees[--myrinfo->ndegrees];
570 :     else
571 :     myedegrees[k].pid = from;
572 :    
573 :     if (myrinfo->ed == 0)
574 :     BNDDelete(nbnd, bndind, bndptr, i);
575 :    
576 :     /* Update the degrees of adjacent vertices */
577 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
578 :     ii = adjncy[j];
579 :     me = where[ii];
580 :    
581 :     myrinfo = graph->rinfo+ii;
582 :     if (myrinfo->edegrees == NULL) {
583 :     myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
584 :     ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
585 :     }
586 :     myedegrees = myrinfo->edegrees;
587 :    
588 :     ASSERT(CheckRInfo(myrinfo));
589 :    
590 :     oldgain = (myrinfo->ed-myrinfo->id);
591 :    
592 :     if (me == from) {
593 :     INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
594 :    
595 :     if (myrinfo->ed > 0 && bndptr[ii] == -1)
596 :     BNDInsert(nbnd, bndind, bndptr, ii);
597 :     }
598 :     else if (me == to) {
599 :     INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
600 :    
601 :     if (myrinfo->ed == 0 && bndptr[ii] != -1)
602 :     BNDDelete(nbnd, bndind, bndptr, ii);
603 :     }
604 :    
605 :     /* Remove contribution from the .ed of 'from' */
606 :     if (me != from) {
607 :     for (k=0; k<myrinfo->ndegrees; k++) {
608 :     if (myedegrees[k].pid == from) {
609 :     if (myedegrees[k].ed == adjwgt[j])
610 :     myedegrees[k] = myedegrees[--myrinfo->ndegrees];
611 :     else
612 :     myedegrees[k].ed -= adjwgt[j];
613 :     break;
614 :     }
615 :     }
616 :     }
617 :    
618 :     /* Add contribution to the .ed of 'to' */
619 :     if (me != to) {
620 :     for (k=0; k<myrinfo->ndegrees; k++) {
621 :     if (myedegrees[k].pid == to) {
622 :     myedegrees[k].ed += adjwgt[j];
623 :     break;
624 :     }
625 :     }
626 :     if (k == myrinfo->ndegrees) {
627 :     myedegrees[myrinfo->ndegrees].pid = to;
628 :     myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
629 :     }
630 :     }
631 :    
632 :     /* Update the queue */
633 :     if (me == to || me == from) {
634 :     gain = myrinfo->ed-myrinfo->id;
635 :     if (moved[ii] == 2) {
636 :     if (myrinfo->ed > 0)
637 :     PQueueUpdate(&queue, ii, oldgain, gain);
638 :     else {
639 :     PQueueDelete(&queue, ii, oldgain);
640 :     moved[ii] = -1;
641 :     }
642 :     }
643 :     else if (moved[ii] == -1 && myrinfo->ed > 0) {
644 :     PQueueInsert(&queue, ii, gain);
645 :     moved[ii] = 2;
646 :     }
647 :     }
648 :    
649 :     ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
650 :     ASSERT(CheckRInfo(myrinfo));
651 :     }
652 :     nmoves++;
653 :     }
654 :    
655 :     graph->nbnd = nbnd;
656 :    
657 :     IFSET(ctrl->dbglvl, DBG_REFINE,
658 :     printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d\n",
659 :     pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
660 :     1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut));
661 :     }
662 :    
663 :     PQueueFree(ctrl, &queue);
664 :    
665 :     idxwspacefree(ctrl, nparts);
666 :     idxwspacefree(ctrl, nparts);
667 :     idxwspacefree(ctrl, nparts);
668 :     idxwspacefree(ctrl, nvtxs);
669 :     idxwspacefree(ctrl, nvtxs);
670 :    
671 :     }
672 :    

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge