← Back to branch summary

~chaffra/+junk/trilinos

« back to all changes in this revision

Viewing changes to packages/zoltan/src/util/converters_for_JPDC_adaptive_mesh_experiments/exo2chaco/chaco/klvspiff/nway_klv.c

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme, Christophe Prud'homme, Johannes Ring
  • Date: 2009-12-13 12:53:22 UTC
  • mfrom: (5.1.2 sid)
  • Revision ID: james.westby@ubuntu.com-20091213125322-in0nrdjc55deqsw9
Tags: 10.0.3.dfsg-1
[Christophe Prud'homme]
* New upstream release

[Johannes Ring]
* debian/patches/libname.patch: Add prefix 'libtrilinos_' to all
  libraries. 
* debian/patches/soname.patch: Add soversion to libraries.
* debian/watch: Update download URL.
* debian/control:
  - Remove python-numeric from Build-Depends (virtual package).
  - Remove automake and autotools from Build-Depends and add cmake to
    reflect switch to CMake.
  - Add python-support to Build-Depends.
* debian/rules: 
  - Cleanup and updates for switch to CMake.

Show diffs side-by-side

added added

removed removed

Lines of Context:
packages/zoltan/src/util/converters_for_JPDC_adaptive_mesh_experiments/exo2chaco/chaco/klvspiff/nway_klv.c
 
1
/* This software was developed by Bruce Hendrickson and Robert Leland   *
 
2
 * at Sandia National Laboratories under US Department of Energy        *
 
3
 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
 
4
 
 
5
#include        <stdio.h>
 
6
#include        <math.h>
 
7
#include        "structs.h"
 
8
#include        "defs.h"
 
9
#include "smalloc.h"
 
10
 
 
11
/*
 
12
   Keep guys moved in and guys moving out of separator.
 
13
 
 
14
   To restore, move all undesirable guys back.
 
15
     (1) guys moved out of separator get put back in.
 
16
     (2) guys moved into separator (bspace) get put back.
 
17
         Note: Should be done in this order.
 
18
         Note: No neighbors need be considered.
 
19
 
 
20
     (3) To clear dvals, I should compute touch all guys that
 
21
         were ever in separator (bspace) and their neighbors.
 
22
*/
 
23
 
 
24
 
 
25
int       nway_klv(graph, nvtxs, lbuckets, rbuckets, llistspace, rlistspace,
 
26
                           ldvals, rdvals, sets, maxdval, goal, max_dev, bndy_list,
 
27
                             weightsum)
 
28
struct vtx_data **graph;        /* data structure for graph */
 
29
int       nvtxs;                /* number of vtxs in graph */
 
30
struct bilist **lbuckets;       /* array of lists for bucket sort */
 
31
struct bilist **rbuckets;       /* array of lists for bucket sort */
 
32
struct bilist *llistspace;      /* list data structure for each vertex */
 
33
struct bilist *rlistspace;      /* list data structure for each vertex */
 
34
int      *ldvals;               /* d-values for each transition */
 
35
int      *rdvals;               /* d-values for each transition */
 
36
short    *sets;                 /* processor each vertex is assigned to */
 
37
int       maxdval;              /* maximum d-value for a vertex */
 
38
double   *goal;                 /* desired set sizes */
 
39
int       max_dev;              /* largest allowed deviation from balance */
 
40
int     **bndy_list;            /* list of vertices on boundary (0 ends) */
 
41
double   *weightsum;            /* sum of vweights in each set (in and out) */
 
42
{
 
43
    struct bilist **to_buckets; /* buckets I'm moving to */
 
44
    struct bilist **from_buckets;       /* buckets I'm moving from */
 
45
    struct bilist *to_listspace;/* list structure I'm moving to */
 
46
    struct bilist *from_listspace;      /* list structure I'm moving from */
 
47
    struct bilist *out_list;    /* list of vtxs moved out of separator */
 
48
    int      *to_dvals;         /* d-values I'm moving to */
 
49
    int      *from_dvals;       /* d-values I'm moving from */
 
50
    extern double kl_bucket_time;       /* time spent in KL bucketsort */
 
51
    extern int KL_BAD_MOVES;    /* # bad moves in a row to stop KL */
 
52
    extern int DEBUG_KL;        /* debug flag for KL */
 
53
    extern int KL_NTRIES_BAD;   /* number of unhelpful passes before quitting */
 
54
    extern int KL_MAX_PASS;     /* maximum # outer KL loops */
 
55
    int      *bspace;           /* list of active vertices for bucketsort */
 
56
    int      *edges;            /* edge list for a vertex */
 
57
    int      *edges2;           /* edge list for a vertex */
 
58
    int      *bdy_ptr;          /* loops through bndy_list */
 
59
    double    total_weight;     /* weight of all vertices */
 
60
    double    partial_weight;   /* weight of vertices not in separator */
 
61
    double    ratio;            /* fraction of weight not in separator */
 
62
    double    time;             /* timing parameter */
 
63
    double    delta0;           /* largest negative deviation from goal size */
 
64
    double    delta1;           /* largest negative deviation from goal size */
 
65
    double    left_imbalance;   /* imbalance if I move to the left */
 
66
    double    right_imbalance;  /* imbalance if I move to the right */
 
67
    double    balance_val;      /* how imbalanced is it */
 
68
    double    balance_best;     /* best balance yet if trying hard */
 
69
    int       flag;             /* condition indicator */
 
70
    int       to, from;         /* sets moving into / out of */
 
71
    int       rtop, ltop;       /* top of each set of buckets */
 
72
    int      *to_top;           /* ptr to top of set moving to */
 
73
    int       lvtx, rvtx;       /* next vertex to move left/right */
 
74
    int       lweight, rweight; /* weights of moving vertices */
 
75
    int       weightfrom;       /* weight moving out of a set */
 
76
    int       list_length;      /* how long is list of vertices to bucketsort? */
 
77
    int       balanced;         /* is partition balanced? */
 
78
    int       temp_balanced;    /* is intermediate partition balanced? */
 
79
    int       ever_balanced;    /* has any partition been balanced? */
 
80
    int       bestvtx;          /* best vertex to move */
 
81
    int       bestval;          /* best change in value for a vtx move */
 
82
    int       vweight;          /* weight of best vertex */
 
83
    int       gtotal;           /* sum of changes from moving */
 
84
    int       improved;         /* total improvement from KL */
 
85
    double    bestg;            /* maximum gtotal found in KL loop */
 
86
    double    bestg_min;        /* smaller than any possible bestg */
 
87
    int       beststep;         /* step where maximum value occurred */
 
88
    int       bestlength;       /* step where maximum value occurred */
 
89
    int       neighbor;         /* neighbor of a vertex */
 
90
    int       step_cutoff;      /* number of negative steps in a row allowed */
 
91
    int       cost_cutoff;      /* amount of negative d-values allowed */
 
92
    int       neg_steps;        /* number of negative steps in a row */
 
93
    int       neg_cost;         /* decrease in sum of d-values */
 
94
    int       vtx;              /* vertex number */
 
95
    int       dval;             /* dval of a vertex */
 
96
    int       group, group2;    /* set that a vertex is assigned to */
 
97
    int       left_too_big;     /* is left set too large? */
 
98
    int       right_too_big;    /* is right set too large? */
 
99
    int       vwgt;             /* weight of a vertex */
 
100
    int       gain;             /* reduction in separator due to a move */
 
101
    int       neighbor2;        /* neighbor of a vertex */
 
102
    int       step;             /* loops through movements of vertices */
 
103
    int       parity;           /* sort forwards or backwards? */
 
104
    int       done;             /* has termination criteria been achieved? */
 
105
    int       nbad;             /* number of unhelpful passes in a row */
 
106
    int       npass;            /* total number of passes */
 
107
    int       nbadtries;        /* number of unhelpful passes before quitting */
 
108
    int       enforce_balance;  /* force a balanced partition? */
 
109
    int       enforce_balance_hard;     /* really force a balanced partition? */
 
110
    int       i, j, k;          /* loop counters */
 
111
 
 
112
    double    seconds(), drandom();
 
113
    int       make_sep_list();
 
114
    void      bucketsortsv(), clear_dvals(), p1bucket();
 
115
    void      removebilist(), movebilist(), add2bilist();
 
116
 
 
117
    nbadtries = KL_NTRIES_BAD;
 
118
 
 
119
    enforce_balance = FALSE;
 
120
    enforce_balance_hard = FALSE;
 
121
 
 
122
    total_weight = goal[0] + goal[1];
 
123
 
 
124
    bspace = smalloc_ret((nvtxs + 1) * sizeof(int));
 
125
 
 
126
    if (bspace == NULL) {
 
127
        return (1);
 
128
    }
 
129
 
 
130
    bdy_ptr = *bndy_list;
 
131
    list_length = 0;
 
132
    while (*bdy_ptr != 0) {
 
133
        bspace[list_length++] = *bdy_ptr++;
 
134
    }
 
135
 
 
136
    sfree(*bndy_list);
 
137
 
 
138
    clear_dvals(graph, nvtxs, ldvals, rdvals, bspace, list_length);
 
139
 
 
140
    step_cutoff = KL_BAD_MOVES;
 
141
    cost_cutoff = maxdval * step_cutoff / 7;
 
142
    if (cost_cutoff < step_cutoff)
 
143
        cost_cutoff = step_cutoff;
 
144
 
 
145
    partial_weight = weightsum[0] + weightsum[1];
 
146
    ratio = partial_weight / total_weight;
 
147
    delta0 = fabs(weightsum[0] - goal[0] * ratio);
 
148
    delta1 = fabs(weightsum[1] - goal[1] * ratio);
 
149
    balanced = (delta0 + delta1 <= max_dev) &&
 
150
       weightsum[0] != total_weight &&
 
151
       weightsum[1] != total_weight;
 
152
 
 
153
    bestg_min = -2.0 * nvtxs * maxdval;
 
154
    parity = FALSE;
 
155
    nbad = 0;
 
156
    npass = 0;
 
157
    improved = 0;
 
158
    done = FALSE;
 
159
    while (!done) {
 
160
        npass++;
 
161
        ever_balanced = FALSE;
 
162
        balance_best = delta0 + delta1;
 
163
 
 
164
        /* Initialize various quantities. */
 
165
        ltop = rtop = 2 * maxdval;
 
166
 
 
167
        gtotal = 0;
 
168
        bestg = bestg_min;
 
169
        beststep = -1;
 
170
        bestlength = list_length;
 
171
        out_list = NULL;
 
172
 
 
173
        neg_steps = 0;
 
174
 
 
175
        /* Compute the initial d-values, and bucket-sort them. */
 
176
        time = seconds();
 
177
        bucketsortsv(graph, nvtxs, lbuckets, rbuckets, llistspace,
 
178
                     rlistspace, ldvals, rdvals, sets, maxdval, parity,
 
179
                     bspace, list_length);
 
180
        parity = !parity;
 
181
        kl_bucket_time += seconds() - time;
 
182
 
 
183
        if (DEBUG_KL > 2) {
 
184
            printf("After sorting, left buckets:\n");
 
185
            p1bucket(lbuckets, llistspace, maxdval);
 
186
            printf("              right buckets:\n");
 
187
            p1bucket(rbuckets, rlistspace, maxdval);
 
188
        }
 
189
 
 
190
        /* Now determine the set of vertex moves. */
 
191
 
 
192
        for (step = 1;; step++) {
 
193
 
 
194
            /* Find the highest d-value in each set. */
 
195
            /* But only consider moves from large to small sets, or moves */
 
196
            /* in which balance is preserved. */
 
197
            /* Break ties in some nonarbitrary manner. */
 
198
            bestval = -maxdval - 1;
 
199
 
 
200
            partial_weight = weightsum[0] + weightsum[1];
 
201
            ratio = partial_weight / total_weight;
 
202
            left_too_big = (weightsum[0] > (goal[0] + .5 * max_dev) * ratio);
 
203
            right_too_big = (weightsum[1] > (goal[1] + .5 * max_dev) * ratio);
 
204
 
 
205
            while (ltop >= 0 && lbuckets[ltop] == NULL) {
 
206
                --ltop;
 
207
            }
 
208
            if (ltop >= 0 && !left_too_big) {
 
209
                lvtx = ((long) lbuckets[ltop] - (long) llistspace) /
 
210
                   sizeof(struct bilist);
 
211
                lweight = graph[lvtx]->vwgt;
 
212
                rweight = lweight - (ltop - maxdval);
 
213
                weightfrom = rweight;
 
214
                to = 0;
 
215
                bestvtx = lvtx;
 
216
                bestval = ltop - maxdval;
 
217
                partial_weight = weightsum[0] + lweight +
 
218
                   weightsum[1] - rweight;
 
219
                ratio = partial_weight / total_weight;
 
220
                left_imbalance = max(fabs(weightsum[0] + lweight - goal[0] * ratio),
 
221
                                   fabs(weightsum[1] - rweight - goal[1] * ratio));
 
222
            }
 
223
 
 
224
            while (rtop >= 0 && rbuckets[rtop] == NULL) {
 
225
                --rtop;
 
226
            }
 
227
            if (rtop >= 0 && !right_too_big) {
 
228
                rvtx = ((long) rbuckets[rtop] - (long) rlistspace) /
 
229
                   sizeof(struct bilist);
 
230
                rweight = graph[rvtx]->vwgt;
 
231
                lweight = rweight - (rtop - maxdval);
 
232
                partial_weight = weightsum[0] - lweight +
 
233
                   weightsum[1] + rweight;
 
234
                ratio = partial_weight / total_weight;
 
235
                right_imbalance = max(fabs(weightsum[0] - lweight - goal[0] * ratio),
 
236
                                   fabs(weightsum[1] + rweight - goal[1] * ratio));
 
237
                if (rtop - maxdval > bestval ||
 
238
                        (rtop - maxdval == bestval &&
 
239
                         (right_imbalance < left_imbalance ||
 
240
                          (right_imbalance == left_imbalance &&
 
241
                           drandom() < .5)))) {
 
242
                    to = 1;
 
243
                    weightfrom = lweight;
 
244
                    bestvtx = rvtx;
 
245
                    bestval = rtop - maxdval;
 
246
                }
 
247
            }
 
248
 
 
249
            if (bestval == -maxdval - 1) {      /* No allowed moves */
 
250
                if (DEBUG_KL > 0) {
 
251
                    printf("No KLV moves at step %d.  bestg = %g at step %d.\n",
 
252
                           step, bestg, beststep);
 
253
                }
 
254
                break;
 
255
            }
 
256
 
 
257
            if (to == 0) {
 
258
                from = 1;
 
259
                to_listspace = llistspace;
 
260
                from_listspace = rlistspace;
 
261
                to_dvals = ldvals;
 
262
                from_dvals = rdvals;
 
263
                to_buckets = lbuckets;
 
264
                from_buckets = rbuckets;
 
265
                to_top = &ltop;
 
266
            }
 
267
            else {
 
268
                from = 0;
 
269
                to_listspace = rlistspace;
 
270
                from_listspace = llistspace;
 
271
                to_dvals = rdvals;
 
272
                from_dvals = ldvals;
 
273
                to_buckets = rbuckets;
 
274
                from_buckets = lbuckets;
 
275
                to_top = &rtop;
 
276
            }
 
277
 
 
278
            vweight = graph[bestvtx]->vwgt;
 
279
 
 
280
            weightsum[to] += vweight;
 
281
            weightsum[from] -= weightfrom;
 
282
 
 
283
            /* Check if this partition is balanced. */
 
284
            partial_weight = weightsum[0] + weightsum[1];
 
285
            ratio = partial_weight / total_weight;
 
286
            delta0 = fabs(weightsum[0] - goal[0] * ratio);
 
287
            delta1 = fabs(weightsum[1] - goal[1] * ratio);
 
288
            temp_balanced = (delta0 + delta1 <= max_dev) &&
 
289
               weightsum[0] != total_weight &&
 
290
               weightsum[1] != total_weight;
 
291
            ever_balanced = (ever_balanced || temp_balanced);
 
292
            balance_val = delta0 + delta1;
 
293
 
 
294
            gtotal += bestval;
 
295
 
 
296
            if ((gtotal > bestg && temp_balanced) ||
 
297
                    (enforce_balance_hard && balance_val < balance_best)) {
 
298
                bestg = gtotal;
 
299
                beststep = step;
 
300
                if (balance_val < balance_best) {
 
301
                    balance_best = balance_val;
 
302
                }
 
303
                if (temp_balanced) {
 
304
                    enforce_balance_hard = FALSE;
 
305
                }
 
306
            }
 
307
 
 
308
            if (DEBUG_KL > 1) {
 
309
                printf("At KLV step %d, bestvtx=%d, bestval=%d (2->%d), wt0 = %g, wt1 = %g\n",
 
310
                       step, bestvtx, bestval, to, weightsum[0], weightsum[1]);
 
311
            }
 
312
 
 
313
            /* Monitor the stopping criteria. */
 
314
            if (bestval < 0) {
 
315
                if (!enforce_balance || ever_balanced)
 
316
                    neg_steps++;
 
317
                if (bestg != bestg_min)
 
318
                    neg_cost = bestg - gtotal;
 
319
                else
 
320
                    neg_cost = -maxdval - 1;
 
321
                if ((neg_steps > step_cutoff || neg_cost > cost_cutoff) &&
 
322
                        !(enforce_balance && bestg == bestg_min)) {
 
323
                    if (DEBUG_KL > 0) {
 
324
                        if (neg_steps > step_cutoff) {
 
325
                            printf("KLV step cutoff at step %d.  bestg = %g at step %d.\n",
 
326
                                   step, bestg, beststep);
 
327
                        }
 
328
                        else if (neg_cost > cost_cutoff) {
 
329
                            printf("KLV cost cutoff at step %d.  bestg = %g at step %d.\n",
 
330
                                   step, bestg, beststep);
 
331
                        }
 
332
                    }
 
333
                    gtotal -= bestval;
 
334
                    weightsum[to] -= vweight;
 
335
                    weightsum[from] += weightfrom;
 
336
                    break;
 
337
                }
 
338
            }
 
339
            else if (bestval > 0) {
 
340
                neg_steps = 0;
 
341
            }
 
342
 
 
343
            /* Remove vertex from its buckets, and flag it as finished. */
 
344
            sets[bestvtx] = to;
 
345
            removebilist(&to_listspace[bestvtx],
 
346
                         &to_buckets[bestval + maxdval]);
 
347
/*
 
348
            printf("After to removebilist\n");
 
349
            p1bucket(to_buckets, to_listspace, maxdval);
 
350
*/
 
351
 
 
352
            if (from_dvals[bestvtx] != -maxdval - 1) {
 
353
                removebilist(&from_listspace[bestvtx],
 
354
                             &from_buckets[from_dvals[bestvtx] + maxdval]);
 
355
/*
 
356
                printf("After from removebilist\n");
 
357
                p1bucket(from_buckets, from_listspace, maxdval);
 
358
*/
 
359
            }
 
360
            from_dvals[bestvtx] = -maxdval - 1;
 
361
 
 
362
            /* Now keep track of vertices moved out of separator so */
 
363
            /* I can restore them as needed. */
 
364
            llistspace[bestvtx].next = out_list;
 
365
            out_list = &(llistspace[bestvtx]);
 
366
 
 
367
 
 
368
            /* Now update the d-values of all the neighbors */
 
369
/* And neighbors of neighbors ... */
 
370
 
 
371
/* If left move:
 
372
   1. Separator neighbors right gain => infinity
 
373
   2. Left neighbors unaffected.
 
374
   3. Right neighbors move into separator.
 
375
      A. Right gain = infinity.
 
376
      B. Left gain = computed.
 
377
      C. For any of their neighbors in separator increase left gain.
 
378
*/
 
379
 
 
380
            edges = graph[bestvtx]->edges;
 
381
            for (j = graph[bestvtx]->nedges - 1; j; j--) {
 
382
                neighbor = *(++edges);
 
383
 
 
384
                group = sets[neighbor];
 
385
 
 
386
                if (group == 2) {       /* In separator. */
 
387
                    gain = from_dvals[neighbor] + maxdval;
 
388
                    /* Gain in the from direction => -infinity */
 
389
                    if (gain >= 0) {
 
390
                        removebilist(&from_listspace[neighbor], &from_buckets[gain]);
 
391
/*
 
392
                        printf("\n  After removing %d\n", neighbor);
 
393
                        p1bucket(from_buckets, from_listspace, maxdval);
 
394
*/
 
395
                        from_dvals[neighbor] = -maxdval - 1;
 
396
                    }
 
397
                }
 
398
                else if (group == from) {
 
399
                    /* Gain in the from direction => -infinity */
 
400
                    sets[neighbor] = 2;
 
401
                    from_dvals[neighbor] = -maxdval - 1;
 
402
 
 
403
                    if (to == 0) {
 
404
                        bspace[list_length++] = -neighbor;
 
405
                    }
 
406
                    else {
 
407
                        bspace[list_length++] = neighbor;
 
408
                    }
 
409
 
 
410
                    edges2 = graph[neighbor]->edges;
 
411
                    vwgt = graph[neighbor]->vwgt;
 
412
                    gain = graph[neighbor]->vwgt;
 
413
                    flag = FALSE;
 
414
                    for (k = graph[neighbor]->nedges - 1; k; k--) {
 
415
                        neighbor2 = *(++edges2);
 
416
                        group2 = sets[neighbor2];
 
417
                        if (group2 == 2) {
 
418
                            dval = to_dvals[neighbor2] + maxdval;
 
419
                            if (dval >= 0) {
 
420
                                movebilist(&to_listspace[neighbor2],
 
421
                                           &to_buckets[dval],
 
422
                                           &to_buckets[dval + vwgt]);
 
423
/*
 
424
                                printf("\n  After moving %d from bucket %d to bucket %d\n", neighbor2, dval, dval + vwgt);
 
425
                                p1bucket(to_buckets, to_listspace, maxdval);
 
426
*/
 
427
                                to_dvals[neighbor2] += vwgt;
 
428
                                dval += vwgt;
 
429
                                if (dval > *to_top) {
 
430
                                    *to_top = dval;
 
431
                                }
 
432
                            }
 
433
                        }
 
434
                        else if (group2 == from) {
 
435
                            gain -= graph[neighbor2]->vwgt;
 
436
                            if (to_dvals[neighbor2] + maxdval < 0) {
 
437
                                flag = TRUE;
 
438
                            }
 
439
                        }
 
440
                    }
 
441
 
 
442
                    if (flag) { /* Not allowed to move further. */
 
443
                        to_dvals[neighbor] = -maxdval - 1;
 
444
                    }
 
445
                    else {
 
446
                        to_dvals[neighbor] = gain;
 
447
                        /* place in appropriate bucket */
 
448
 
 
449
                        gain += maxdval;
 
450
                        add2bilist(&to_listspace[neighbor], &to_buckets[gain]);
 
451
/*
 
452
                        printf("\nAfter adding %d to bucket %d\n", neighbor, gain - maxdval);
 
453
                        p1bucket(to_buckets, to_listspace, maxdval);
 
454
*/
 
455
 
 
456
                        if (gain > *to_top)
 
457
                            *to_top = gain;
 
458
 
 
459
                    }
 
460
                }
 
461
            }
 
462
            if (beststep == step) {
 
463
                bestlength = list_length;
 
464
            }
 
465
            if (DEBUG_KL > 2) {
 
466
                printf("\n-- After step, left buckets:\n");
 
467
                p1bucket(lbuckets, llistspace, maxdval);
 
468
                printf("             right buckets:\n");
 
469
                p1bucket(rbuckets, rlistspace, maxdval);
 
470
            }
 
471
        }
 
472
 
 
473
 
 
474
        /* Done with a pass; should we actually perform any swaps? */
 
475
        if (bestg > 0 || (bestg != bestg_min && !balanced && enforce_balance)) {
 
476
            improved += bestg;
 
477
        }
 
478
        else {
 
479
            if (enforce_balance_hard) {
 
480
                /* I've done the best I can, give up. */
 
481
                done = TRUE;
 
482
            }
 
483
            if (enforce_balance) {
 
484
                enforce_balance_hard = TRUE;
 
485
            }
 
486
            enforce_balance = TRUE;
 
487
            nbad++;
 
488
        }
 
489
 
 
490
        /* Work backwards, undoing all the undesirable moves. */
 
491
 
 
492
        /* First reset vertices moved out of the separator. */
 
493
        if (out_list) {
 
494
            if (beststep < 0)
 
495
                beststep = 0;
 
496
            for (i = step - 1; i > beststep; i--) {
 
497
                vtx = ((long) out_list - (long) llistspace) /
 
498
                   sizeof(struct bilist);
 
499
                if (sets[vtx] != 2) {
 
500
                    weightsum[sets[vtx]] -= graph[vtx]->vwgt;
 
501
                }
 
502
                sets[vtx] = 2;
 
503
                out_list = out_list->next;
 
504
            }
 
505
        }
 
506
 
 
507
        for (i = list_length - 1; i >= bestlength; i--) {
 
508
            vtx = bspace[i];
 
509
            if (vtx < 0) {
 
510
                if (sets[-vtx] == 2) {
 
511
                    weightsum[1] += graph[-vtx]->vwgt;
 
512
                }
 
513
                sets[-vtx] = 1;
 
514
            }
 
515
            else {
 
516
                if (sets[vtx] == 2) {
 
517
                    weightsum[0] += graph[vtx]->vwgt;
 
518
                }
 
519
                sets[vtx] = 0;
 
520
            }
 
521
        }
 
522
 
 
523
        partial_weight = weightsum[0] + weightsum[1];
 
524
        ratio = partial_weight / total_weight;
 
525
        delta0 = fabs(weightsum[0] - goal[0] * ratio);
 
526
        delta1 = fabs(weightsum[1] - goal[1] * ratio);
 
527
        balanced = (delta0 + delta1 <= max_dev) &&
 
528
           weightsum[0] != total_weight &&
 
529
           weightsum[1] != total_weight;
 
530
 
 
531
        done = done || (nbad >= nbadtries && balanced);
 
532
        if (KL_MAX_PASS > 0) {
 
533
            done = done || (npass == KL_MAX_PASS && balanced);
 
534
        }
 
535
 
 
536
        if (!done) {            /* Rezero dval values. */
 
537
            clear_dvals(graph, nvtxs, ldvals, rdvals, bspace, list_length);
 
538
        }
 
539
 
 
540
        /* Construct list of separator vertices to pass to buckets or return */
 
541
        list_length = make_sep_list(bspace, list_length, sets);
 
542
 
 
543
        if (done) {
 
544
            bspace[list_length] = 0;
 
545
            bspace = srealloc(bspace, (list_length + 1) * sizeof(int));
 
546
            *bndy_list = bspace;
 
547
        }
 
548
 
 
549
        gain = 0;
 
550
        j = k = 0;
 
551
        for (i = 1; i <= nvtxs; i++) {
 
552
            if (sets[i] == 0)
 
553
                j += graph[i]->vwgt;
 
554
            else if (sets[i] == 1)
 
555
                k += graph[i]->vwgt;
 
556
            else if (sets[i] == 2)
 
557
                gain += graph[i]->vwgt;
 
558
        }
 
559
/*
 
560
        printf("\nAfter pass of KLV: sets = %d/%d, sep = %d  (bestg = %g)\n\n\n",
 
561
               j, k, gain, bestg);
 
562
*/
 
563
    }
 
564
 
 
565
    if (DEBUG_KL > 0) {
 
566
        printf("   KLV required %d passes to improve by %d.\n", npass, improved);
 
567
    }
 
568
 
 
569
    return (0);
 
570
}