← Back to branch summary

~elmer-csc-ubuntu/elmercsc/devel

« back to all changes in this revision

Viewing changes to elmergrid/src/metis-5.1.0/libmetis/balance.c

  • Committer: GitHub
  • Author(s): Peter R
  • Date: 2017-10-04 13:47:14 UTC
  • mfrom: (575.1.17)
  • Revision ID: git-v1:91780af69137b74ec539fedc4ad70c9ec52d732a
Merge pull request #115 from ElmerCSC/metis_update

Updated to new Metis API for devel branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
elmergrid/src/metis-5.1.0/libmetis/balance.c
 
1
/*!
 
2
\file
 
3
\brief Functions for the edge-based balancing 
 
4
 
 
5
\date Started 7/23/97
 
6
\author George  
 
7
\author Copyright 1997-2011, Regents of the University of Minnesota 
 
8
\version\verbatim $Id: balance.c 10187 2011-06-13 13:46:57Z karypis $ \endverbatim
 
9
*/
 
10
 
 
11
#include "metislib.h"
 
12
 
 
13
/*************************************************************************
 
14
* This function is the entry poidx_t of the bisection balancing algorithms.
 
15
**************************************************************************/
 
16
void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
17
{
 
18
  if (ComputeLoadImbalanceDiff(graph, 2, ctrl->pijbm, ctrl->ubfactors) <= 0) 
 
19
    return;
 
20
 
 
21
  if (graph->ncon == 1) {
 
22
    /* return right away if the balance is OK */
 
23
    if (iabs(ntpwgts[0]*graph->tvwgt[0]-graph->pwgts[0]) < 3*graph->tvwgt[0]/graph->nvtxs)
 
24
      return;
 
25
 
 
26
    if (graph->nbnd > 0)
 
27
      Bnd2WayBalance(ctrl, graph, ntpwgts);
 
28
    else
 
29
      General2WayBalance(ctrl, graph, ntpwgts);
 
30
  }
 
31
  else {
 
32
    McGeneral2WayBalance(ctrl, graph, ntpwgts);
 
33
  }
 
34
}
 
35
 
 
36
 
 
37
/*************************************************************************
 
38
* This function balances two partitions by moving boundary nodes
 
39
* from the domain that is overweight to the one that is underweight.
 
40
**************************************************************************/
 
41
void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
42
{
 
43
  idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
 
44
  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
 
45
  idx_t *moved, *perm;
 
46
  rpq_t *queue;
 
47
  idx_t higain, mincut, mindiff;
 
48
  idx_t tpwgts[2];
 
49
 
 
50
  WCOREPUSH;
 
51
 
 
52
  nvtxs  = graph->nvtxs;
 
53
  xadj   = graph->xadj;
 
54
  vwgt   = graph->vwgt;
 
55
  adjncy = graph->adjncy;
 
56
  adjwgt = graph->adjwgt;
 
57
  where  = graph->where;
 
58
  id     = graph->id;
 
59
  ed     = graph->ed;
 
60
  pwgts  = graph->pwgts;
 
61
  bndptr = graph->bndptr;
 
62
  bndind = graph->bndind;
 
63
 
 
64
  moved = iwspacemalloc(ctrl, nvtxs);
 
65
  perm  = iwspacemalloc(ctrl, nvtxs);
 
66
 
 
67
  /* Determine from which domain you will be moving data */
 
68
  tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
 
69
  tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
 
70
  mindiff   = iabs(tpwgts[0]-pwgts[0]);
 
71
  from      = (pwgts[0] < tpwgts[0] ? 1 : 0);
 
72
  to        = (from+1)%2;
 
73
 
 
74
  IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
 
75
     printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
 
76
             pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, 
 
77
             graph->mincut));
 
78
 
 
79
  queue = rpqCreate(nvtxs);
 
80
 
 
81
  iset(nvtxs, -1, moved);
 
82
 
 
83
  ASSERT(ComputeCut(graph, where) == graph->mincut);
 
84
  ASSERT(CheckBnd(graph));
 
85
 
 
86
  /* Insert the boundary nodes of the proper partition whose size is OK in the priority queue */
 
87
  nbnd = graph->nbnd;
 
88
  irandArrayPermute(nbnd, perm, nbnd/5, 1);
 
89
  for (ii=0; ii<nbnd; ii++) {
 
90
    i = perm[ii];
 
91
    ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
 
92
    ASSERT(bndptr[bndind[i]] != -1);
 
93
    if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)
 
94
      rpqInsert(queue, bndind[i], ed[bndind[i]]-id[bndind[i]]);
 
95
  }
 
96
 
 
97
  mincut = graph->mincut;
 
98
  for (nswaps=0; nswaps<nvtxs; nswaps++) {
 
99
    if ((higain = rpqGetTop(queue)) == -1)
 
100
      break;
 
101
    ASSERT(bndptr[higain] != -1);
 
102
 
 
103
    if (pwgts[to]+vwgt[higain] > tpwgts[to])
 
104
      break;
 
105
 
 
106
    mincut -= (ed[higain]-id[higain]);
 
107
    INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
 
108
 
 
109
    where[higain] = to;
 
110
    moved[higain] = nswaps;
 
111
 
 
112
    IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
 
113
      printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
 
114
 
 
115
    /**************************************************************
 
116
    * Update the id[i]/ed[i] values of the affected nodes
 
117
    ***************************************************************/
 
118
    SWAP(id[higain], ed[higain], tmp);
 
119
    if (ed[higain] == 0 && xadj[higain] < xadj[higain+1]) 
 
120
      BNDDelete(nbnd, bndind,  bndptr, higain);
 
121
 
 
122
    for (j=xadj[higain]; j<xadj[higain+1]; j++) {
 
123
      k = adjncy[j];
 
124
      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
 
125
      INC_DEC(id[k], ed[k], kwgt);
 
126
 
 
127
      /* Update its boundary information and queue position */
 
128
      if (bndptr[k] != -1) { /* If k was a boundary vertex */
 
129
        if (ed[k] == 0) { /* Not a boundary vertex any more */
 
130
          BNDDelete(nbnd, bndind, bndptr, k);
 
131
          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)  /* Remove it if in the queues */
 
132
            rpqDelete(queue, k);
 
133
        }
 
134
        else { /* If it has not been moved, update its position in the queue */
 
135
          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
 
136
            rpqUpdate(queue, k, ed[k]-id[k]);
 
137
        }
 
138
      }
 
139
      else {
 
140
        if (ed[k] > 0) {  /* It will now become a boundary vertex */
 
141
          BNDInsert(nbnd, bndind, bndptr, k);
 
142
          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff) 
 
143
            rpqInsert(queue, k, ed[k]-id[k]);
 
144
        }
 
145
      }
 
146
    }
 
147
  }
 
148
 
 
149
  IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
 
150
    printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
 
151
 
 
152
  graph->mincut = mincut;
 
153
  graph->nbnd   = nbnd;
 
154
 
 
155
  rpqDestroy(queue);
 
156
 
 
157
  WCOREPOP;
 
158
}
 
159
 
 
160
 
 
161
/*************************************************************************
 
162
* This function balances two partitions by moving the highest gain 
 
163
* (including negative gain) vertices to the other domain.
 
164
* It is used only when tha unbalance is due to non contigous
 
165
* subdomains. That is, the are no boundary vertices.
 
166
* It moves vertices from the domain that is overweight to the one that 
 
167
* is underweight.
 
168
**************************************************************************/
 
169
void General2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
170
{
 
171
  idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
 
172
  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
 
173
  idx_t *moved, *perm;
 
174
  rpq_t *queue;
 
175
  idx_t higain, mincut, mindiff;
 
176
  idx_t tpwgts[2];
 
177
 
 
178
  WCOREPUSH;
 
179
 
 
180
  nvtxs  = graph->nvtxs;
 
181
  xadj   = graph->xadj;
 
182
  vwgt   = graph->vwgt;
 
183
  adjncy = graph->adjncy;
 
184
  adjwgt = graph->adjwgt;
 
185
  where  = graph->where;
 
186
  id     = graph->id;
 
187
  ed     = graph->ed;
 
188
  pwgts  = graph->pwgts;
 
189
  bndptr = graph->bndptr;
 
190
  bndind = graph->bndind;
 
191
 
 
192
  moved = iwspacemalloc(ctrl, nvtxs);
 
193
  perm  = iwspacemalloc(ctrl, nvtxs);
 
194
 
 
195
  /* Determine from which domain you will be moving data */
 
196
  tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
 
197
  tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
 
198
  mindiff   = iabs(tpwgts[0]-pwgts[0]);
 
199
  from      = (pwgts[0] < tpwgts[0] ? 1 : 0);
 
200
  to        = (from+1)%2;
 
201
 
 
202
  IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
 
203
     printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
 
204
             pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
 
205
 
 
206
  queue = rpqCreate(nvtxs);
 
207
 
 
208
  iset(nvtxs, -1, moved);
 
209
 
 
210
  ASSERT(ComputeCut(graph, where) == graph->mincut);
 
211
  ASSERT(CheckBnd(graph));
 
212
 
 
213
  /* Insert the nodes of the proper partition whose size is OK in the priority queue */
 
214
  irandArrayPermute(nvtxs, perm, nvtxs/5, 1);
 
215
  for (ii=0; ii<nvtxs; ii++) {
 
216
    i = perm[ii];
 
217
    if (where[i] == from && vwgt[i] <= mindiff)
 
218
      rpqInsert(queue, i, ed[i]-id[i]);
 
219
  }
 
220
 
 
221
  mincut = graph->mincut;
 
222
  nbnd = graph->nbnd;
 
223
  for (nswaps=0; nswaps<nvtxs; nswaps++) {
 
224
    if ((higain = rpqGetTop(queue)) == -1)
 
225
      break;
 
226
 
 
227
    if (pwgts[to]+vwgt[higain] > tpwgts[to])
 
228
      break;
 
229
 
 
230
    mincut -= (ed[higain]-id[higain]);
 
231
    INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
 
232
 
 
233
    where[higain] = to;
 
234
    moved[higain] = nswaps;
 
235
 
 
236
    IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
 
237
      printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
 
238
 
 
239
    /**************************************************************
 
240
    * Update the id[i]/ed[i] values of the affected nodes
 
241
    ***************************************************************/
 
242
    SWAP(id[higain], ed[higain], tmp);
 
243
    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1]) 
 
244
      BNDDelete(nbnd, bndind,  bndptr, higain);
 
245
    if (ed[higain] > 0 && bndptr[higain] == -1)
 
246
      BNDInsert(nbnd, bndind,  bndptr, higain);
 
247
 
 
248
    for (j=xadj[higain]; j<xadj[higain+1]; j++) {
 
249
      k = adjncy[j];
 
250
 
 
251
      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
 
252
      INC_DEC(id[k], ed[k], kwgt);
 
253
 
 
254
      /* Update the queue position */
 
255
      if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
 
256
        rpqUpdate(queue, k, ed[k]-id[k]);
 
257
 
 
258
      /* Update its boundary information */
 
259
      if (ed[k] == 0 && bndptr[k] != -1) 
 
260
        BNDDelete(nbnd, bndind, bndptr, k);
 
261
      else if (ed[k] > 0 && bndptr[k] == -1)  
 
262
        BNDInsert(nbnd, bndind, bndptr, k);
 
263
    }
 
264
  }
 
265
 
 
266
  IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
 
267
    printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
 
268
 
 
269
  graph->mincut = mincut;
 
270
  graph->nbnd   = nbnd;
 
271
 
 
272
  rpqDestroy(queue);
 
273
 
 
274
  WCOREPOP;
 
275
}
 
276
 
 
277
 
 
278
/*************************************************************************
 
279
* This function performs an edge-based FM refinement
 
280
**************************************************************************/
 
281
void McGeneral2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
282
{
 
283
  idx_t i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, 
 
284
        me, limit, tmp, cnum;
 
285
  idx_t *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *id, *ed, *bndptr, *bndind;
 
286
  idx_t *moved, *swaps, *perm, *qnum, *qsizes;
 
287
  idx_t higain, mincut, newcut, mincutorder;
 
288
  real_t *invtvwgt, *minbalv, *newbalv, minbal, newbal;
 
289
  rpq_t **queues;
 
290
 
 
291
  WCOREPUSH;
 
292
 
 
293
  nvtxs    = graph->nvtxs;
 
294
  ncon     = graph->ncon;
 
295
  xadj     = graph->xadj;
 
296
  vwgt     = graph->vwgt;
 
297
  adjncy   = graph->adjncy;
 
298
  adjwgt   = graph->adjwgt;
 
299
  invtvwgt = graph->invtvwgt;
 
300
  where    = graph->where;
 
301
  id       = graph->id;
 
302
  ed       = graph->ed;
 
303
  pwgts    = graph->pwgts;
 
304
  bndptr   = graph->bndptr;
 
305
  bndind   = graph->bndind;
 
306
 
 
307
  moved   = iwspacemalloc(ctrl, nvtxs);
 
308
  swaps   = iwspacemalloc(ctrl, nvtxs);
 
309
  perm    = iwspacemalloc(ctrl, nvtxs);
 
310
  qnum    = iwspacemalloc(ctrl, nvtxs);
 
311
  newbalv = rwspacemalloc(ctrl, ncon);
 
312
  minbalv = rwspacemalloc(ctrl, ncon);
 
313
  qsizes  = iwspacemalloc(ctrl, 2*ncon);
 
314
 
 
315
  limit = gk_min(gk_max(0.01*nvtxs, 15), 100);
 
316
 
 
317
  /* Initialize the queues */
 
318
  queues = (rpq_t **)wspacemalloc(ctrl, 2*ncon*sizeof(rpq_t *));
 
319
  for (i=0; i<2*ncon; i++) {
 
320
    queues[i] = rpqCreate(nvtxs);
 
321
    qsizes[i] = 0;
 
322
  }
 
323
 
 
324
  for (i=0; i<nvtxs; i++) {
 
325
    qnum[i] = iargmax_nrm(ncon, vwgt+i*ncon, invtvwgt);
 
326
    qsizes[2*qnum[i]+where[i]]++;
 
327
  }
 
328
 
 
329
 
 
330
  /* for the empty queues, move into them vertices from other queues */
 
331
  for (from=0; from<2; from++) {
 
332
    for (j=0; j<ncon; j++) {
 
333
      if (qsizes[2*j+from] == 0) {
 
334
        for (i=0; i<nvtxs; i++) {
 
335
          if (where[i] != from)
 
336
            continue;
 
337
 
 
338
          k = iargmax2_nrm(ncon, vwgt+i*ncon, invtvwgt);
 
339
          if (k == j && 
 
340
              qsizes[2*qnum[i]+from] > qsizes[2*j+from] && 
 
341
              vwgt[i*ncon+qnum[i]]*invtvwgt[qnum[i]] < 1.3*vwgt[i*ncon+j]*invtvwgt[j]) {
 
342
            qsizes[2*qnum[i]+from]--;
 
343
            qsizes[2*j+from]++;
 
344
            qnum[i] = j;
 
345
          }
 
346
        }
 
347
      }
 
348
    }
 
349
  }
 
350
 
 
351
 
 
352
  minbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, minbalv);
 
353
  ASSERT(minbal > 0.0);
 
354
 
 
355
  newcut = mincut = graph->mincut;
 
356
  mincutorder = -1;
 
357
 
 
358
  if (ctrl->dbglvl&METIS_DBG_REFINE) {
 
359
    printf("Parts: [");
 
360
    for (l=0; l<ncon; l++)
 
361
      printf("(%6"PRIDX" %6"PRIDX" %.3"PRREAL" %.3"PRREAL") ", 
 
362
          pwgts[l], pwgts[ncon+l], ntpwgts[l], ntpwgts[ncon+l]);
 
363
    printf("] Nv-Nb[%5"PRIDX", %5"PRIDX"]. ICut: %6"PRIDX", LB: %+.3"PRREAL" [B]\n", 
 
364
           graph->nvtxs, graph->nbnd, graph->mincut, minbal);
 
365
  }
 
366
 
 
367
  iset(nvtxs, -1, moved);
 
368
 
 
369
  ASSERT(ComputeCut(graph, where) == graph->mincut);
 
370
  ASSERT(CheckBnd(graph));
 
371
 
 
372
  /* Insert all nodes in the priority queues */
 
373
  nbnd = graph->nbnd;
 
374
  irandArrayPermute(nvtxs, perm, nvtxs/10, 1);
 
375
  for (ii=0; ii<nvtxs; ii++) {
 
376
    i = perm[ii];
 
377
    rpqInsert(queues[2*qnum[i]+where[i]], i, ed[i]-id[i]);
 
378
  }
 
379
 
 
380
  for (nswaps=0; nswaps<nvtxs; nswaps++) {
 
381
    if (minbal <= 0.0)
 
382
      break;
 
383
 
 
384
    SelectQueue(graph, ctrl->pijbm, ctrl->ubfactors, queues, &from, &cnum);
 
385
    to = (from+1)%2;
 
386
 
 
387
    if (from == -1 || (higain = rpqGetTop(queues[2*cnum+from])) == -1)
 
388
      break;
 
389
 
 
390
    newcut -= (ed[higain]-id[higain]);
 
391
 
 
392
    iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+to*ncon,   1);
 
393
    iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
 
394
    newbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, newbalv);
 
395
 
 
396
    if (newbal < minbal || (newbal == minbal && 
 
397
        (newcut < mincut || 
 
398
         (newcut == mincut && BetterBalance2Way(ncon, minbalv, newbalv))))) {
 
399
      mincut      = newcut;
 
400
      minbal      = newbal;
 
401
      mincutorder = nswaps;
 
402
      rcopy(ncon, newbalv, minbalv);
 
403
    }
 
404
    else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
 
405
      newcut += (ed[higain]-id[higain]);
 
406
      iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
 
407
      iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+to*ncon,   1);
 
408
      break;
 
409
    }
 
410
 
 
411
    where[higain] = to;
 
412
    moved[higain] = nswaps;
 
413
    swaps[nswaps] = higain;
 
414
 
 
415
    if (ctrl->dbglvl&METIS_DBG_MOVEINFO) {
 
416
      printf("Moved %6"PRIDX" from %"PRIDX"(%"PRIDX"). Gain: %5"PRIDX", "
 
417
             "Cut: %5"PRIDX", NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
 
418
      for (l=0; l<ncon; l++) 
 
419
        printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
 
420
      printf(", %+.3"PRREAL" LB: %+.3"PRREAL"\n", minbal, newbal);
 
421
    }
 
422
 
 
423
 
 
424
    /**************************************************************
 
425
    * Update the id[i]/ed[i] values of the affected nodes
 
426
    ***************************************************************/
 
427
    SWAP(id[higain], ed[higain], tmp);
 
428
    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1]) 
 
429
      BNDDelete(nbnd, bndind,  bndptr, higain);
 
430
    if (ed[higain] > 0 && bndptr[higain] == -1)
 
431
      BNDInsert(nbnd, bndind,  bndptr, higain);
 
432
 
 
433
    for (j=xadj[higain]; j<xadj[higain+1]; j++) {
 
434
      k = adjncy[j];
 
435
 
 
436
      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
 
437
      INC_DEC(id[k], ed[k], kwgt);
 
438
 
 
439
      /* Update the queue position */
 
440
      if (moved[k] == -1)
 
441
        rpqUpdate(queues[2*qnum[k]+where[k]], k, ed[k]-id[k]);
 
442
 
 
443
      /* Update its boundary information */
 
444
      if (ed[k] == 0 && bndptr[k] != -1) 
 
445
        BNDDelete(nbnd, bndind, bndptr, k);
 
446
      else if (ed[k] > 0 && bndptr[k] == -1)  
 
447
        BNDInsert(nbnd, bndind, bndptr, k);
 
448
    }
 
449
  }
 
450
 
 
451
 
 
452
 
 
453
  /****************************************************************
 
454
  * Roll back computations
 
455
  *****************************************************************/
 
456
  for (nswaps--; nswaps>mincutorder; nswaps--) {
 
457
    higain = swaps[nswaps];
 
458
 
 
459
    to = where[higain] = (where[higain]+1)%2;
 
460
    SWAP(id[higain], ed[higain], tmp);
 
461
    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
 
462
      BNDDelete(nbnd, bndind,  bndptr, higain);
 
463
    else if (ed[higain] > 0 && bndptr[higain] == -1)
 
464
      BNDInsert(nbnd, bndind,  bndptr, higain);
 
465
 
 
466
    iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+to*ncon,         1);
 
467
    iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+((to+1)%2)*ncon, 1);
 
468
    for (j=xadj[higain]; j<xadj[higain+1]; j++) {
 
469
      k = adjncy[j];
 
470
 
 
471
      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
 
472
      INC_DEC(id[k], ed[k], kwgt);
 
473
 
 
474
      if (bndptr[k] != -1 && ed[k] == 0)
 
475
        BNDDelete(nbnd, bndind, bndptr, k);
 
476
      if (bndptr[k] == -1 && ed[k] > 0)
 
477
        BNDInsert(nbnd, bndind, bndptr, k);
 
478
    }
 
479
  }
 
480
 
 
481
  if (ctrl->dbglvl&METIS_DBG_REFINE) {
 
482
    printf("\tMincut: %6"PRIDX" at %5"PRIDX", NBND: %6"PRIDX", NPwgts: [", 
 
483
        mincut, mincutorder, nbnd);
 
484
    for (l=0; l<ncon; l++)
 
485
      printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
 
486
    printf("], LB: %.3"PRREAL"\n", ComputeLoadImbalance(graph, 2, ctrl->pijbm));
 
487
  }
 
488
 
 
489
  graph->mincut = mincut;
 
490
  graph->nbnd   = nbnd;
 
491
 
 
492
 
 
493
  for (i=0; i<2*ncon; i++) 
 
494
    rpqDestroy(queues[i]);
 
495
 
 
496
  WCOREPOP;
 
497
}
 
498