Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
kwayfm.c
Go to the documentation of this file.
1 /*
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 1998/11/27 17:59:16 karypis 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 
EDegreeType * edegrees
Definition: struct.h:102
#define idxwspacefree
Definition: rename.h:165
#define PQueueUpdate
Definition: rename.h:320
int ndegrees
Definition: struct.h:121
#define Greedy_KWayEdgeBalance
Definition: rename.h:102
idxtype * pwgts
Definition: struct.h:176
idxtype * adjwgtsum
Definition: struct.h:168
#define DBG_REFINE
Definition: defs.h:157
int nbnd
Definition: struct.h:177
idxtype ed
Definition: struct.h:79
#define Random_KWayEdgeRefine
Definition: rename.h:100
idxtype pid
Definition: struct.h:78
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int mincut
Definition: struct.h:175
#define DBG_MOVEINFO
Definition: defs.h:159
idxtype * bndptr
Definition: struct.h:178
#define idxwspacemalloc
Definition: rename.h:164
#define idxsum
Definition: rename.h:399
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define Greedy_KWayEdgeRefine
Definition: rename.h:101
int idxtype
Definition: struct.h:19
#define PQueueReset
Definition: rename.h:316
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
int ed
Definition: struct.h:120
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxamin
Definition: rename.h:397
RInfoType * rinfo
Definition: struct.h:184
int cdegree
Definition: struct.h:104
#define ComputeVolume
Definition: rename.h:122
#define CheckRInfo
Definition: rename.h:47
#define BNDDelete(nbnd, bndind, bndptr, vtx)
Definition: macros.h:109
idxtype * bndind
Definition: struct.h:178
#define idxamax
Definition: rename.h:393
idxtype * vwgt
Definition: struct.h:163
#define INC_DEC(a, b, val)
Definition: macros.h:39
#define PQueueGetMax
Definition: rename.h:322
EDegreeType * edegrees
Definition: struct.h:122
#define PQueueInsert
Definition: rename.h:318
int nvtxs
Definition: struct.h:161
#define RandomPermute
Definition: rename.h:410
WorkSpaceType wspace
Definition: struct.h:227
#define ASSERT(expr)
Definition: macros.h:130
#define SWAP(a, b, tmp)
Definition: macros.h:36
#define ComputeCut
Definition: rename.h:43
#define PQueueDelete
Definition: rename.h:319
#define PQueueFree
Definition: rename.h:317
int id
Definition: struct.h:120
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define PQueueInit
Definition: rename.h:315