← Back to branch summary

~ubuntu-branches/ubuntu/trusty/scotch/trusty

« back to all changes in this revision

Viewing changes to src/libscotch/bgraph_bipart_fm.c

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme
  • Date: 2008-01-25 09:13:53 UTC
  • Revision ID: james.westby@ubuntu.com-20080125091353-zghdao60dfsyc2bt
Tags: upstream-5.0.1.dfsg
Import upstream version 5.0.1.dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libscotch/bgraph_bipart_fm.c
 
1
/* Copyright 2004,2007 ENSEIRB, INRIA & CNRS
 
2
**
 
3
** This file is part of the Scotch software package for static mapping,
 
4
** graph partitioning and sparse matrix ordering.
 
5
**
 
6
** This software is governed by the CeCILL-C license under French law
 
7
** and abiding by the rules of distribution of free software. You can
 
8
** use, modify and/or redistribute the software under the terms of the
 
9
** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
 
10
** URL: "http://www.cecill.info".
 
11
** 
 
12
** As a counterpart to the access to the source code and rights to copy,
 
13
** modify and redistribute granted by the license, users are provided
 
14
** only with a limited warranty and the software's author, the holder of
 
15
** the economic rights, and the successive licensors have only limited
 
16
** liability.
 
17
** 
 
18
** In this respect, the user's attention is drawn to the risks associated
 
19
** with loading, using, modifying and/or developing or reproducing the
 
20
** software by the user in light of its specific status of free software,
 
21
** that may mean that it is complicated to manipulate, and that also
 
22
** therefore means that it is reserved for developers and experienced
 
23
** professionals having in-depth computer knowledge. Users are therefore
 
24
** encouraged to load and test the software's suitability as regards
 
25
** their requirements in conditions enabling the security of their
 
26
** systems and/or data to be ensured and, more generally, to use and
 
27
** operate it in the same conditions as regards security.
 
28
** 
 
29
** The fact that you are presently reading this means that you have had
 
30
** knowledge of the CeCILL-C license and that you accept its terms.
 
31
*/
 
32
/************************************************************/
 
33
/**                                                        **/
 
34
/**   NAME       : bipart_fm.c                             **/
 
35
/**                                                        **/
 
36
/**   AUTHOR     : Francois PELLEGRINI                     **/
 
37
/**                                                        **/
 
38
/**   FUNCTION   : This module bipartitions an active      **/
 
39
/**                graph using our improvements of the     **/
 
40
/**                Fiduccia-Mattheyses heuristics.         **/
 
41
/**                                                        **/
 
42
/**   DATES      : # Version 1.0  : from : 30 sep 1993     **/
 
43
/**                                 to     09 oct 1993     **/
 
44
/**                # Version 1.1  : from : 15 oct 1993     **/
 
45
/**                                 to     15 oct 1993     **/
 
46
/**                # Version 1.2  : from : 07 feb 1994     **/
 
47
/**                                 to     15 feb 1994     **/
 
48
/**                # Version 1.3  : from : 06 apr 1994     **/
 
49
/**                                 to     30 apr 1994     **/
 
50
/**                # Version 2.0  : from : 06 jun 1994     **/
 
51
/**                                 to     03 nov 1994     **/
 
52
/**                # Version 3.1  : from : 06 nov 1995     **/
 
53
/**                                 to     07 jun 1996     **/
 
54
/**                # Version 3.2  : from : 21 sep 1996     **/
 
55
/**                                 to     13 sep 1998     **/
 
56
/**                # Version 3.3  : from : 01 oct 1998     **/
 
57
/**                                 to     12 mar 1999     **/
 
58
/**                # Version 3.4  : from : 01 jun 2001     **/
 
59
/**                                 to     01 jun 2001     **/
 
60
/**                # Version 4.0  : from : 20 dec 2003     **/
 
61
/**                                 to     05 may 2006     **/
 
62
/**                                                        **/
 
63
/************************************************************/
 
64
 
 
65
/*
 
66
**  The defines and includes.
 
67
*/
 
68
 
 
69
#define BGRAPH_BIPART_FM
 
70
 
 
71
#include "module.h"
 
72
#include "common.h"
 
73
#include "gain.h"
 
74
#include "graph.h"
 
75
#include "arch.h"
 
76
#include "bgraph.h"
 
77
#include "bgraph_bipart_fm.h"
 
78
#include "bgraph_bipart_gg.h"
 
79
 
 
80
/*********************************/
 
81
/*                               */
 
82
/* Gain table handling routines. */
 
83
/*                               */
 
84
/*********************************/
 
85
 
 
86
/* This routine returns the vertex of best gain
 
87
** whose swap will keep the balance correct.
 
88
** It returns:
 
89
** - !NULL  : pointer to the vertex.
 
90
** - NULL   : if no more vertices available.
 
91
*/
 
92
 
 
93
static
 
94
BgraphBipartFmVertex *
 
95
bgraphBipartFmTablGet (
 
96
GainTabl * restrict const   tablptr,              /*+ Gain table        +*/
 
97
const Gnum                  deltcur,              /*+ Current imbalance +*/
 
98
const Gnum                  deltmax)              /*+ Maximum imbalance +*/
 
99
{
 
100
  BgraphBipartFmVertex * restrict vexxptr;
 
101
  BgraphBipartFmVertex * restrict vertbest;
 
102
  Gnum                            gainbest;
 
103
  const GainEntr * restrict       tablbest;
 
104
  Gnum                            deltbest;
 
105
 
 
106
  tablbest = tablptr->tend;                       /* Assume no candidate vertex found yet */
 
107
  gainbest = GAINMAX;
 
108
  vertbest = NULL;
 
109
  deltbest = deltmax;
 
110
 
 
111
  for (vexxptr = (BgraphBipartFmVertex *) gainTablFrst (tablptr); /* Select candidate vertices */
 
112
       (vexxptr != NULL) && (vexxptr->gainlink.tabl < tablbest);
 
113
       vexxptr = (BgraphBipartFmVertex *) gainTablNext (tablptr, &vexxptr->gainlink)) {
 
114
    Gnum                deltnew;
 
115
 
 
116
    deltnew = abs (deltcur + vexxptr->compgain);
 
117
    if (deltnew <= deltmax) {                     /* If vertex enforces balance  */
 
118
      if ((vexxptr->commgain < gainbest) ||       /* And if it gives better gain */
 
119
          ((vexxptr->commgain == gainbest) &&     /* Or if it gives better load  */
 
120
           (deltnew < deltbest))) {
 
121
        tablbest = vexxptr->gainlink.tabl;        /* Select it */
 
122
        gainbest = vexxptr->commgain;
 
123
        vertbest = vexxptr;
 
124
        deltbest = deltnew;
 
125
      }
 
126
    }
 
127
  }
 
128
 
 
129
  return (vertbest);
 
130
}
 
131
 
 
132
/*****************************/
 
133
/*                           */
 
134
/* This is the main routine. */
 
135
/*                           */
 
136
/*****************************/
 
137
 
 
138
/* This routine performs the bipartitioning.
 
139
** It returns:
 
140
** - 0 : if bipartitioning could be computed.
 
141
** - 1 : on error.
 
142
*/
 
143
 
 
144
int
 
145
bgraphBipartFm (
 
146
Bgraph * restrict const           grafptr,        /*+ Active graph      +*/
 
147
const BgraphBipartFmParam * const paraptr)        /*+ Method parameters +*/
 
148
{
 
149
  GainTabl * restrict             tablptr;        /* Pointer to gain table                 */
 
150
  INT                             passnbr;        /* Maximum number of passes to go        */
 
151
  BgraphBipartFmSave * restrict   savetab;        /* Pointer to move array                 */
 
152
  Gnum                            movenbr;        /* Number of uneffective moves done      */
 
153
  Gnum                            savenbr;        /* Number of recorded backtrack moves    */
 
154
  Gnum                            mswpnum;        /* Current number of recording sweep     */
 
155
  int                             moveflag;       /* Flag set if useful moves made         */
 
156
  int                             swapval;        /* Flag set if global swap performed     */
 
157
  int                             swapvalbst;     /* Recorded swap value for best position */
 
158
  Gnum                            hashsiz;        /* Size of hash table                    */
 
159
  Gnum                            hashmsk;        /* Mask for access to hash table         */
 
160
  Gnum                            hashnum;        /* Hash value                            */
 
161
  BgraphBipartFmVertex *          lockptr;        /* Linked list of locked vertices        */
 
162
  BgraphBipartFmVertex * restrict hashtab;        /* Extended vertex array                 */
 
163
  Gnum                            hashmax;
 
164
  Gnum                            hashnbr;
 
165
 
 
166
  Gnum               fronnbr;
 
167
  Gnum               compload0dltmat;            /* Theoretical latgest unbalance allowed   */
 
168
  Gnum               compload0dltmax;            /* Largest unbalance allowed               */
 
169
  Gnum               compload0dltbst;            /* Best unbalance value found to date      */
 
170
  Gnum               compload0dlt;               /* Current imbalance                       */
 
171
  Gnum               compsize0dlt;               /* Update of size of part 0                */
 
172
  Gnum               commgainextn;               /* Current external communication gain     */
 
173
  Gnum               commgainextnbst;            /* External gain of best recorded position */
 
174
  Gnum               commload;                   /* Communication load of current position  */
 
175
  Gnum               commloadbst;                /* Best communication load to date         */
 
176
  Gnum               domdist;                    /* Distance between the two subdomains     */
 
177
  Gnum               fronnum;
 
178
 
 
179
  compload0dltmat = (paraptr->deltrat > 0.0L) ? ((Gnum) (paraptr->deltrat * (double) grafptr->s.velosum) + 1) : 0;
 
180
  compload0dltmax = MAX (compload0dltmat, abs (grafptr->compload0dlt)); /* Set current maximum distance */
 
181
 
 
182
  if (grafptr->fronnbr == 0) {                    /* If no current frontier      */
 
183
    if (abs (grafptr->compload0dlt) <= compload0dltmat) /* If balance is correct */
 
184
      return (0);                                 /* Nothing to do               */
 
185
    else {                                        /* Imbalance must be fought    */
 
186
      BgraphBipartGgParam   paradat;
 
187
 
 
188
      paradat.passnbr = 4;                        /* Use a standard algorithm */
 
189
      bgraphBipartGg (grafptr, &paradat);
 
190
      if (grafptr->fronnbr == 0)                  /* If new partition has no frontier */
 
191
        return (0);                               /* This algorithm is still useless  */
 
192
      compload0dltmax = MAX (compload0dltmat, abs (grafptr->compload0dlt));
 
193
    }
 
194
  }
 
195
 
 
196
#ifdef SCOTCH_DEBUG_BGRAPH2
 
197
  hashnbr = 2 * grafptr->fronnbr + 1;             /* Ensure resizing will be performed, for maximum code coverage */
 
198
#else /* SCOTCH_DEBUG_BGRAPH2 */
 
199
  hashnbr = 4 * (grafptr->fronnbr + paraptr->movenbr + grafptr->s.degrmax);
 
200
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
201
  if (hashnbr > grafptr->s.vertnbr)
 
202
    hashnbr = grafptr->s.vertnbr;
 
203
 
 
204
  for (hashsiz = 256; hashsiz < hashnbr; hashsiz <<= 1) ; /* Get upper power of two */
 
205
  hashmsk = hashsiz - 1;
 
206
  hashmax = hashsiz >> 2;
 
207
 
 
208
  if ((tablptr = gainTablInit (GAIN_LINMAX, BGRAPHBIPARTFMSUBBITS)) != NULL) {
 
209
    void *                          hashtmp;      /* Temporary variable for vertex array to avoid problems wirh "restrict" */
 
210
 
 
211
    if (memAllocGroup ((void **)
 
212
                       &hashtmp, (size_t) (hashsiz * sizeof (BgraphBipartFmVertex)),
 
213
                       &savetab, (size_t) (hashsiz * sizeof (BgraphBipartFmSave)), NULL) == NULL) {
 
214
      errorPrint   ("bgraphBipartFm: out of memory (1)");
 
215
      gainTablExit (tablptr);
 
216
      return       (1);
 
217
    }
 
218
    hashtab = hashtmp;
 
219
  }
 
220
  else
 
221
    return (1);  
 
222
  memset (hashtab, ~0, hashsiz * sizeof (BgraphBipartFmVertex)); /* Set all vertex numbers to ~0 */
 
223
 
 
224
  domdist = grafptr->domdist;
 
225
 
 
226
  for (fronnum = 0, hashnbr = grafptr->fronnbr;   /* Set initial gains */
 
227
       fronnum < hashnbr; fronnum ++) {
 
228
    Gnum                vertnum;
 
229
    Gnum                veloval;
 
230
    Gnum                hashnum;
 
231
    Gnum                edgenum;
 
232
    Gnum                edloval;
 
233
    Gnum                commcut;
 
234
    Gnum                commgain;
 
235
    int                 partval;
 
236
    int                 partdlt;
 
237
 
 
238
    vertnum = grafptr->frontab[fronnum];
 
239
    partval = grafptr->parttax[vertnum];
 
240
 
 
241
    for (edgenum = grafptr->s.verttax[vertnum], commcut = commgain = 0, edloval = 1;
 
242
         edgenum < grafptr->s.vendtax[vertnum]; edgenum ++) {
 
243
      Gnum                vertend;
 
244
      int                 partend;
 
245
      int                 partdlt;
 
246
 
 
247
      vertend = grafptr->s.edgetax[edgenum];
 
248
      partend = grafptr->parttax[vertend];
 
249
      if (grafptr->s.edlotax != NULL)
 
250
        edloval = grafptr->s.edlotax[edgenum];
 
251
 
 
252
      partdlt   = partval ^ partend;
 
253
      commcut  += partdlt;
 
254
      commgain += (1 - 2 * partdlt) * edloval;
 
255
    }
 
256
    commgain *= domdist;                          /* Adjust internal gains with respect to external gains */
 
257
    partdlt   = 2 * partval - 1;
 
258
    veloval   = (grafptr->s.velotax != NULL) ? grafptr->s.velotax[vertnum] : 1;
 
259
 
 
260
    for (hashnum = (vertnum * BGRAPHBIPARTFMHASHPRIME) & hashmsk; hashtab[hashnum].vertnum != ~0; hashnum = (hashnum + 1) & hashmsk) ;
 
261
 
 
262
    hashtab[hashnum].vertnum  = vertnum;          /* Implicitely set slot as used */
 
263
    hashtab[hashnum].partval  = partval;
 
264
    hashtab[hashnum].compgain = partdlt * veloval;
 
265
    hashtab[hashnum].commgain = (grafptr->veextax == NULL) ? commgain : (commgain - partdlt * grafptr->veextax[vertnum]);
 
266
    hashtab[hashnum].commcut  = commcut;
 
267
    hashtab[hashnum].mswpnum  = 0;                /* Implicitely set slot as used */
 
268
    gainTablAdd (tablptr, &hashtab[hashnum], hashtab[hashnum].commgain);
 
269
  }
 
270
 
 
271
  compload0dltbst = grafptr->compload0dlt;
 
272
  commloadbst     = grafptr->commload;
 
273
  commgainextnbst = grafptr->commgainextn;
 
274
  swapvalbst      = 0;                            /* No global swap performed yet */
 
275
 
 
276
#ifdef SCOTCH_DEBUG_BGRAPH2
 
277
#ifdef SCOTCH_DEBUG_BGRAPH3
 
278
  if (bgraphBipartFmCheck (grafptr, hashtab, hashmsk, 0, compload0dltbst, commloadbst, commgainextnbst) != 0) {
 
279
    errorPrint ("bgraphBipartFm: internal error (1)");
 
280
    return     (1);
 
281
  }
 
282
#endif /* SCOTCH_DEBUG_BGRAPH3 */
 
283
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
284
 
 
285
  passnbr = paraptr->passnbr;                     /* Set remaining number of passes    */
 
286
  savenbr = 0;                                    /* For empty backtrack of first pass */
 
287
  mswpnum = 0;                                    /* Will be incremented afterwards    */
 
288
  lockptr = NULL;                                 /* Locked list is empty              */
 
289
 
 
290
  do {                                            /* As long as there are improvements */
 
291
    BgraphBipartFmVertex *    vexxptr;
 
292
 
 
293
    while (savenbr -- > 0) {                      /* Delete exceeding moves */
 
294
      Gnum                hashnum;
 
295
      int                 partval;
 
296
 
 
297
      hashnum = savetab[savenbr].hashnum;
 
298
      partval = savetab[savenbr].partval;
 
299
      hashtab[hashnum].partval  = partval;        /* Restore vertex data */
 
300
      hashtab[hashnum].compgain = savetab[savenbr].compgain;
 
301
      hashtab[hashnum].commgain = savetab[savenbr].commgain;
 
302
      hashtab[hashnum].commcut  = savetab[savenbr].commcut;
 
303
 
 
304
      if (hashtab[hashnum].gainlink.next >= BGRAPHBIPARTFMSTATELINK) { /* If vertex is linked */
 
305
        gainTablDel (tablptr, &hashtab[hashnum].gainlink); /* Unlink it                       */
 
306
        hashtab[hashnum].gainlink.next = BGRAPHBIPARTFMSTATEFREE; /* Set it as free           */
 
307
      }
 
308
      if ((hashtab[hashnum].gainlink.next == BGRAPHBIPARTFMSTATEFREE) && (partval == 2)) /* If vertex not locked and in separator */
 
309
        gainTablAdd (tablptr, &hashtab[hashnum].gainlink, hashtab[hashnum].commgain); /* Re-link it                               */
 
310
    }
 
311
    compload0dlt = compload0dltbst;               /* Restore best separator parameters */
 
312
    commload     = commloadbst;
 
313
    commgainextn = commgainextnbst;
 
314
    swapval      = swapvalbst;
 
315
    mswpnum ++;                                   /* Forget all recorded moves */
 
316
 
 
317
#ifdef SCOTCH_DEBUG_BGRAPH2
 
318
#ifdef SCOTCH_DEBUG_BGRAPH3
 
319
    if (bgraphBipartFmCheck (grafptr, hashtab, hashmsk, swapval, compload0dlt, commload, commgainextn) != 0) {
 
320
      errorPrint ("bgraphBipartFm: internal error (2)");
 
321
      return     (1);
 
322
    }
 
323
#endif /* SCOTCH_DEBUG_BGRAPH3 */
 
324
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
325
 
 
326
    while (lockptr != NULL) {                     /* For all vertices in locked list */
 
327
      BgraphBipartFmVertex *    vexxptr;
 
328
 
 
329
      vexxptr = lockptr;                          /* Unlink vertex from list */
 
330
      lockptr = (BgraphBipartFmVertex *) vexxptr->gainlink.prev;
 
331
 
 
332
      if (vexxptr->commcut > 0)                   /* If vertex has cut edges  */
 
333
        gainTablAdd (tablptr, vexxptr, vexxptr->commgain); /* Put it in table */
 
334
      else
 
335
        vexxptr->gainlink.next = BGRAPHBIPARTFMSTATEFREE; /* Set it free anyway */
 
336
    }
 
337
 
 
338
    moveflag = 0;                                 /* No useful moves made              */
 
339
    movenbr  = 0;                                 /* No uneffective moves recorded yet */
 
340
    savenbr  = 0;                                 /* Back up to beginning of table     */
 
341
 
 
342
    while ((movenbr < paraptr->movenbr) &&        /* As long as we can find effective vertices */
 
343
           ((vexxptr = (BgraphBipartFmVertex *) bgraphBipartFmTablGet (tablptr, compload0dlt, compload0dltmax)) != NULL)) {
 
344
      Gnum               vertnum;                 /* Number of current vertex */
 
345
      int                partval;                 /* Part of current vertex   */
 
346
      Gnum               edgenum;
 
347
      Gnum               edloval;
 
348
 
 
349
      gainTablDel (tablptr, &vexxptr->gainlink);  /* Remove it from table  */
 
350
      vexxptr->gainlink.next = BGRAPHBIPARTFMSTATEUSED; /* Mark it as used */
 
351
      vexxptr->gainlink.prev = (GainLink *) lockptr; /* Lock it            */
 
352
      lockptr                = vexxptr;
 
353
 
 
354
      vertnum = vexxptr->vertnum;
 
355
      partval = vexxptr->partval;
 
356
 
 
357
      if (vexxptr->mswpnum != mswpnum) {          /* If vertex data not yet recorded */
 
358
        vexxptr->mswpnum = mswpnum;
 
359
        savetab[savenbr].hashnum  = vexxptr - hashtab;
 
360
        savetab[savenbr].partval  = partval;
 
361
        savetab[savenbr].compgain = vexxptr->compgain;
 
362
        savetab[savenbr].commgain = vexxptr->commgain;
 
363
        savetab[savenbr].commcut  = vexxptr->commcut;
 
364
        savenbr ++;                               /* One more move recorded */
 
365
      }
 
366
      movenbr ++;                                 /* One more move done */
 
367
 
 
368
      commload     += vexxptr->commgain;
 
369
      compload0dlt += vexxptr->compgain;
 
370
      if (grafptr->veextax != NULL)
 
371
        commgainextn += 2 * (2 * partval - 1) * grafptr->veextax[vertnum];
 
372
 
 
373
      vexxptr->partval  = partval ^ 1;            /* Swap vertex first in case neighbors are added */
 
374
      vexxptr->compgain = - vexxptr->compgain;
 
375
      vexxptr->commgain = - vexxptr->commgain;
 
376
      vexxptr->commcut  = grafptr->s.vendtax[vertnum] - grafptr->s.verttax[vertnum] - vexxptr->commcut;
 
377
 
 
378
      edloval = 1;
 
379
      for (edgenum = grafptr->s.verttax[vertnum]; /* (Re-)link neighbors */
 
380
           edgenum < grafptr->s.vendtax[vertnum]; edgenum ++) {
 
381
        Gnum                vertend;              /* Number of current end neighbor vertex */
 
382
        Gnum                hashnum;
 
383
 
 
384
        vertend = grafptr->s.edgetax[edgenum];
 
385
        if (grafptr->s.edlotax != NULL)
 
386
          edloval = grafptr->s.edlotax[edgenum];
 
387
 
 
388
        for (hashnum = (vertend * BGRAPHBIPARTFMHASHPRIME) & hashmsk; ; hashnum = (hashnum + 1) & hashmsk) {
 
389
          if (hashtab[hashnum].vertnum == vertend) { /* If hash slot found */
 
390
            int                 partdlt;
 
391
 
 
392
            if (hashtab[hashnum].mswpnum != mswpnum) { /* If vertex data not yet recorded */
 
393
              savetab[savenbr].hashnum  = hashnum; /* Record them                         */
 
394
              savetab[savenbr].partval  = hashtab[hashnum].partval;
 
395
              savetab[savenbr].compgain = hashtab[hashnum].compgain;
 
396
              savetab[savenbr].commgain = hashtab[hashnum].commgain;
 
397
              savetab[savenbr].commcut  = hashtab[hashnum].commcut;
 
398
              hashtab[hashnum].mswpnum  = mswpnum;
 
399
              savenbr ++;
 
400
            }
 
401
 
 
402
            partdlt = 2 * (partval ^ hashtab[hashnum].partval) - 1;
 
403
            hashtab[hashnum].commgain += (domdist * 2) * edloval * partdlt;
 
404
            hashtab[hashnum].commcut  -= partdlt;
 
405
 
 
406
            if (hashtab[hashnum].gainlink.next != BGRAPHBIPARTFMSTATEUSED) { /* If vertex is of use   */
 
407
              if (hashtab[hashnum].gainlink.next >= BGRAPHBIPARTFMSTATELINK) { /* If vertex is linked */
 
408
                gainTablDel (tablptr, &hashtab[hashnum].gainlink); /* Remove it from table            */
 
409
                hashtab[hashnum].gainlink.next = BGRAPHBIPARTFMSTATEFREE; /* Mark it as free anyway   */
 
410
              }
 
411
              if (hashtab[hashnum].commcut > 0)   /* If vertex belongs to the frontier */
 
412
                gainTablAdd (tablptr, &hashtab[hashnum].gainlink, hashtab[hashnum].commgain); /* Re-link it */
 
413
            }
 
414
            break;
 
415
          }
 
416
          if (hashtab[hashnum].vertnum == ~0) {   /* If hash slot empty */
 
417
            Gnum                commgain;         /* Communication gain of current vertex     */
 
418
            Gnum                commgainold;      /* Old communication gain of current vertex */
 
419
            Gnum                veloval;
 
420
            Gnum                veexval;
 
421
            int                 partold;
 
422
            int                 partdlt;
 
423
 
 
424
            if (hashnbr >= hashmax) {             /* If extended vertex table is already full */
 
425
              if (bgraphBipartFmResize (&hashtab, &hashmax, &hashmsk, &savetab, savenbr, tablptr, &lockptr) != 0) {
 
426
                errorPrint   ("bgraphBipartFm: out of memory (2)");
 
427
                memFree      (hashtab);           /* Free group leader */
 
428
                gainTablExit (tablptr);
 
429
              }
 
430
              for (hashnum = (vertend * BGRAPHBIPARTFMHASHPRIME) & hashmsk; hashtab[hashnum].vertnum != ~0; hashnum = (hashnum + 1) & hashmsk) ; /* Search for new first free slot */
 
431
            }
 
432
 
 
433
            if (grafptr->s.edlotax != NULL) {     /* If graph edges are weighted */
 
434
              Gnum               edgeend;
 
435
 
 
436
              for (edgeend = grafptr->s.verttax[vertend], commgainold = 0; /* Compute neighbor edge load sum */
 
437
                   edgeend < grafptr->s.vendtax[vertend]; edgeend ++)
 
438
                commgainold += grafptr->s.edlotax[edgeend];
 
439
              commgain = commgainold - 2 * edloval;
 
440
            }
 
441
            else {                                /* Graph edges are not weighted */
 
442
              commgainold = grafptr->s.vendtax[vertend] - grafptr->s.verttax[vertend];
 
443
              commgain    = commgainold - 2;
 
444
            }
 
445
 
 
446
            veloval = 1;
 
447
            if (grafptr->s.velotax != NULL)
 
448
              veloval = grafptr->s.velotax[vertend];
 
449
            veexval = 0;
 
450
            if (grafptr->veextax != NULL)
 
451
              veexval = grafptr->veextax[vertend];
 
452
 
 
453
#ifdef SCOTCH_DEBUG_BGRAPH2
 
454
            if (grafptr->parttax[vertend] != (partval ^ swapval)) {
 
455
              errorPrint ("bgraphBipartFm: internal error (3)");
 
456
              return     (1);
 
457
            }
 
458
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
459
            partold = partval ^ swapval ^ swapvalbst; /* Get part of vertex as in latest accepted configuration               */
 
460
            partdlt = 2 * partold - 1;            /* Compute values to fill save table according to last stable configuration */
 
461
            savetab[savenbr].hashnum  = hashnum;  /* Record initial state of new vertex                                       */
 
462
            savetab[savenbr].partval  = partold;
 
463
            savetab[savenbr].compgain = partdlt * veloval;
 
464
            savetab[savenbr].commgain = commgainold * domdist - (partdlt * veexval);
 
465
            savetab[savenbr].commcut  = 0;
 
466
            savenbr ++;
 
467
 
 
468
            partdlt = 2 * partval - 1;            /* Compute values to fill hash table according to current configuration */
 
469
            hashtab[hashnum].vertnum  = vertend;
 
470
            hashtab[hashnum].partval  = partval;  /* It was a neighbor of the moved vertex, in current global swap state */
 
471
            hashtab[hashnum].compgain = partdlt * veloval;
 
472
            hashtab[hashnum].commgain = commgain * domdist - (partdlt * veexval);
 
473
            hashtab[hashnum].commcut  = 1;
 
474
            hashtab[hashnum].mswpnum  = mswpnum;  /* Vertex has just been saved    */
 
475
            hashnbr ++;                           /* One more vertex in hash table */
 
476
 
 
477
            gainTablAdd (tablptr, &hashtab[hashnum], hashtab[hashnum].commgain);
 
478
            break;
 
479
          }
 
480
        }
 
481
      }
 
482
 
 
483
      if (commload < commloadbst) {               /* If move improves the cost */
 
484
        compload0dltbst = compload0dlt;           /* This move was effective   */
 
485
        commloadbst     = commload;
 
486
        commgainextnbst = commgainextn;
 
487
        swapvalbst      = swapval;
 
488
        moveflag        = 1;
 
489
        movenbr         =
 
490
        savenbr         = 0;
 
491
        mswpnum ++;
 
492
      } else if (commload == commloadbst) {
 
493
        if (abs (compload0dlt) < abs (compload0dltbst)) {
 
494
          compload0dltbst = compload0dlt;         /* This move was effective */
 
495
          commgainextnbst = commgainextn;
 
496
          swapvalbst      = swapval;
 
497
          moveflag        = 1;
 
498
          movenbr         =
 
499
          savenbr         = 0;
 
500
          mswpnum ++;
 
501
        }
 
502
        else if (abs (compload0dlt) == abs (compload0dltbst)) {
 
503
          compload0dltbst = compload0dlt;         /* Forget backtracking */
 
504
          commgainextnbst = commgainextn;
 
505
          swapvalbst      = swapval;
 
506
          savenbr         = 0;                   
 
507
          mswpnum ++;
 
508
        }
 
509
      }
 
510
      if (compload0dltmax > compload0dltmat) {    /* If must restrict distance bounds */
 
511
        Gnum                compload0dlttmp;
 
512
 
 
513
        compload0dlttmp = compload0dltmax;        /* Save old working compdeltmax value */
 
514
        compload0dltmax = MAX (compload0dltmat,   /* Restrict at most to maximum        */
 
515
                               abs (compload0dlt));
 
516
        if (compload0dltmax < compload0dlttmp) {  /* If we have done something useful */
 
517
          compload0dltbst = compload0dlt;         /* Then record best move done       */
 
518
          commloadbst     = commload;
 
519
          commgainextnbst = commgainextn;
 
520
          swapvalbst      = swapval;
 
521
          moveflag        = 1;
 
522
          movenbr         =
 
523
          savenbr         = 0;
 
524
          mswpnum ++;
 
525
        }
 
526
      }
 
527
#ifdef SCOTCH_DEBUG_BGRAPH2
 
528
#ifdef SCOTCH_DEBUG_BGRAPH3
 
529
      if (bgraphBipartFmCheck (grafptr, hashtab, hashmsk, swapval, compload0dlt, commload, commgainextn) != 0) {
 
530
        errorPrint ("bgraphBipartFm: internal error (4)");
 
531
        return     (1);
 
532
      }
 
533
#endif /* SCOTCH_DEBUG_BGRAPH3 */
 
534
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
535
 
 
536
      if (commgainextn < 0) {                     /* If global swap improves gain */
 
537
        Gnum                compload0dlttmp;
 
538
 
 
539
#ifdef SCOTCH_DEBUG_BGRAPH2
 
540
        if (grafptr->veextax == NULL) {           /* commgainextn should always be 0 if (veextab == NULL) */
 
541
          errorPrint ("bgraphBipartFm: internal error (5)");
 
542
          return     (1);
 
543
        }
 
544
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
545
 
 
546
        compload0dlttmp = grafptr->s.velosum - compload0dlt - 2 * grafptr->compload0avg;
 
547
        if (abs (compload0dlttmp) <= compload0dltmax) { /* If still within bounds, perform actual swapping */
 
548
          Gnum                    hashnum;
 
549
 
 
550
          commload    +=   commgainextn;          /* Perform global swap */
 
551
          commgainextn = - commgainextn;
 
552
          compload0dlt =   compload0dlttmp;
 
553
          swapval     ^= 1;
 
554
 
 
555
          for (hashnum = 0; hashnum <= hashmsk; hashnum ++) { /* hashsiz no longer valid after resizing, so use hashmsk */
 
556
            Gnum                commgain;
 
557
 
 
558
            if (hashtab[hashnum].mswpnum == ~0)   /* If hash slot not used, skip it */
 
559
              continue;
 
560
 
 
561
            if (hashtab[hashnum].mswpnum != mswpnum) { /* And vertex data not yet recorded */
 
562
              hashtab[hashnum].mswpnum  = mswpnum; /* Record them                          */
 
563
              savetab[savenbr].hashnum  = hashnum;
 
564
              savetab[savenbr].partval  = hashtab[hashnum].partval;
 
565
              savetab[savenbr].compgain = hashtab[hashnum].compgain;
 
566
              savetab[savenbr].commgain = hashtab[hashnum].commgain;
 
567
              savetab[savenbr].commcut  = hashtab[hashnum].commcut;
 
568
              savenbr ++;
 
569
            }
 
570
 
 
571
            hashtab[hashnum].partval ^= 1;        /* Swap the vertex */
 
572
            hashtab[hashnum].compgain = - hashtab[hashnum].compgain;
 
573
 
 
574
            commgain = grafptr->veextax[hashtab[hashnum].vertnum];
 
575
            if (commgain != 0) {                  /* If vertex has external cocycle edges                         */
 
576
              hashtab[hashnum].commgain += 2 * (1 - 2 * hashtab[hashnum].partval) * commgain; /* Compute new gain */
 
577
              if (hashtab[hashnum].gainlink.next >= BGRAPHBIPARTFMSTATELINK) { /* If vertex is linked             */
 
578
                gainTablDel (tablptr, &hashtab[hashnum].gainlink); /* Remove it from table                        */
 
579
                gainTablAdd (tablptr, &hashtab[hashnum].gainlink, hashtab[hashnum].commgain); /* Re-link it       */
 
580
              }
 
581
            }
 
582
          }
 
583
 
 
584
          if ((commload < commloadbst) ||         /* If move improves cost */
 
585
              ((commload == commloadbst) &&
 
586
               (abs (compload0dlt) < abs (compload0dltbst)))) {
 
587
            compload0dltbst = compload0dlt;       /* Then record best move done */
 
588
            commloadbst     = commload;
 
589
            commgainextnbst = commgainextn;
 
590
            swapvalbst      = swapval;
 
591
            moveflag        = 1;
 
592
            movenbr         =
 
593
            savenbr         = 0;
 
594
            mswpnum ++;
 
595
          }
 
596
 
 
597
#ifdef SCOTCH_DEBUG_BGRAPH2
 
598
#ifdef SCOTCH_DEBUG_BGRAPH3
 
599
          if (bgraphBipartFmCheck (grafptr, hashtab, hashmsk, swapval, compload0dlt, commload, commgainextn) != 0) {
 
600
            errorPrint ("bgraphBipartFm: internal error (6)");
 
601
            return     (1);
 
602
          }
 
603
#endif /* SCOTCH_DEBUG_BGRAPH3 */
 
604
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
605
        }
 
606
      }
 
607
    }
 
608
  } while ((moveflag != 0) &&                     /* As long as vertices are moved */
 
609
           (-- passnbr > 0));                     /* And we are allowed to loop    */
 
610
 
 
611
#ifdef SCOTCH_DEBUG_BGRAPH2
 
612
#ifdef SCOTCH_DEBUG_BGRAPH3
 
613
  if (bgraphBipartFmCheck (grafptr, hashtab, hashmsk, swapval, compload0dlt, commload, commgainextn) != 0) {
 
614
    errorPrint ("bgraphBipartFm: internal error (7)");
 
615
    return     (1);
 
616
  }
 
617
#endif /* SCOTCH_DEBUG_BGRAPH3 */
 
618
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
619
 
 
620
  compsize0dlt = 0;                               /* No difference to number of vertices yet */
 
621
  if (swapvalbst != 0) {                          /* If global swap needed                   */
 
622
    Gnum                vertnum;
 
623
 
 
624
    compsize0dlt = grafptr->s.vertnbr - 2 * grafptr->compsize0; /* Set difference so as to swap all vertices        */
 
625
    for (vertnum = grafptr->s.baseval; vertnum < grafptr->s.vertnnd; vertnum ++) /* Swap all vertices in part array */
 
626
      grafptr->parttax[vertnum] ^= 1;
 
627
  }
 
628
 
 
629
  while (savenbr -- > 0) {                        /* Delete exceeding moves */
 
630
    Gnum                hashnum;
 
631
 
 
632
    hashnum = savetab[savenbr].hashnum;
 
633
    hashtab[hashnum].partval = savetab[savenbr].partval; /* Restore vertex data */
 
634
    hashtab[hashnum].commcut = savetab[savenbr].commcut;
 
635
  }
 
636
  compload0dlt = compload0dltbst;                 /* Restore best separator parameters */
 
637
  commload     = commloadbst;
 
638
  commgainextn = commgainextnbst;
 
639
 
 
640
  for (hashnum = fronnbr = 0;                     /* Build new frontier                                     */
 
641
       hashnum <= hashmsk; hashnum ++) {          /* hashsiz no longer valid after resizing, so use hashmsk */
 
642
    Gnum                vertnum;
 
643
    int                 partval;
 
644
 
 
645
    vertnum = hashtab[hashnum].vertnum;           /* Get vertex data from slot */
 
646
    if (vertnum == ~0)
 
647
      continue;
 
648
 
 
649
    partval = hashtab[hashnum].partval;
 
650
 
 
651
    if (grafptr->parttax[vertnum] != partval) {   /* If vertex part changed            */
 
652
      grafptr->parttax[vertnum] = partval;        /* Set new part value                */
 
653
      compsize0dlt += (1 - 2 * partval);          /* Adjust size of part 0 accordingly */
 
654
    }
 
655
    if (hashtab[hashnum].commcut > 0)             /* If vertex belongs to cut */
 
656
      grafptr->frontab[fronnbr ++] = vertnum;     /* Add vertex to frontier   */
 
657
  }
 
658
  grafptr->fronnbr      = fronnbr;
 
659
  grafptr->compload0    = compload0dlt + grafptr->compload0avg;
 
660
  grafptr->compload0dlt = compload0dlt;
 
661
  grafptr->compsize0   += compsize0dlt;
 
662
  grafptr->commload     = commload;
 
663
  grafptr->commgainextn = commgainextn;
 
664
 
 
665
#ifdef SCOTCH_DEBUG_BGRAPH2
 
666
  if (bgraphCheck (grafptr) != 0) {
 
667
    errorPrint ("bgraphBipartFm: inconsistent graph data");
 
668
    return     (1);
 
669
  }
 
670
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
671
 
 
672
  memFree      (hashtab);                         /* Free group leader */
 
673
  gainTablExit (tablptr);
 
674
 
 
675
  return (0);
 
676
}
 
677
 
 
678
/* This routine doubles the size all of the arrays
 
679
** involved in handling the hash table and hash
 
680
** vertex arrays.
 
681
** It returns:
 
682
** - 0   : if resizing succeeded.
 
683
** - !0  : if out of memory.
 
684
*/
 
685
 
 
686
static
 
687
int
 
688
bgraphBipartFmResize (
 
689
BgraphBipartFmVertex * restrict * hashtabptr,     /*+ Extended vertex array      +*/
 
690
Gnum * restrict const             hashmaxptr,     /*+ Size of vertex array       +*/
 
691
Gnum * const                      hashmskptr,     /*+ Pointer to hash table mask +*/
 
692
BgraphBipartFmSave * restrict *   savetabptr,     /*+ Move array                 +*/
 
693
const Gnum                        savenbr,        /*+ Number of moves recorded   +*/
 
694
GainTabl * const                  tablptr,        /*+ Gain table                 +*/
 
695
BgraphBipartFmVertex ** const     lockptr)        /*+ Pointer to locked list     +*/
 
696
{
 
697
  BgraphBipartFmVertex * restrict hashtab;        /* Extended vertex array                */
 
698
  BgraphBipartFmSave * restrict   savetab;        /* Move backtracking array              */
 
699
  BgraphBipartFmSave * restrict   saveold;        /* Pointer to translated old save array */
 
700
  Gnum                            savenum;
 
701
  Gnum                            hashold;        /* Size of old hash table (half of new) */
 
702
  Gnum                            hashsiz;
 
703
  Gnum                            hashmax;
 
704
  Gnum                            hashmsk;
 
705
  Gnum                            hashnum;
 
706
 
 
707
  hashmax = *hashmaxptr << 1;                     /* Compute new sizes */
 
708
  hashold = *hashmaxptr << 2;
 
709
  hashsiz = *hashmaxptr << 3;
 
710
  hashmsk = hashsiz - 1;
 
711
 
 
712
#ifdef SCOTCH_DEBUG_BGRAPH2
 
713
  if (sizeof (BgraphBipartFmVertex) < sizeof (BgraphBipartFmSave)) { /* Should always be true */
 
714
    errorPrint ("bgraphBipartFmResize: internal error (1)");
 
715
    return     (1);
 
716
  }
 
717
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
718
 
 
719
  if (memReallocGroup ((void *) *hashtabptr,
 
720
                       &hashtab, (size_t) (hashsiz * sizeof (BgraphBipartFmVertex)),
 
721
                       &savetab, (size_t) (hashsiz * sizeof (BgraphBipartFmSave)), NULL) == NULL) {
 
722
    errorPrint ("bgraphBipartFmResize: out of memory");
 
723
    return (1);
 
724
  }
 
725
 
 
726
  saveold = (BgraphBipartFmSave *) ((byte *) hashtab + ((byte *) *savetabptr - (byte *) *hashtabptr));
 
727
  for (savenum = savenbr - 1; savenum >= 0; savenum --) { /* Move save array, in reverse order */
 
728
    savetab[savenum].commcut  = saveold[savenum].commcut;
 
729
    savetab[savenum].commgain = saveold[savenum].commgain;
 
730
    savetab[savenum].compgain = saveold[savenum].compgain;
 
731
    savetab[savenum].partval  = saveold[savenum].partval;
 
732
    savetab[savenum].hashnum  = hashtab[saveold[savenum].hashnum].vertnum; /* Temporarily translate from hash index to number */
 
733
  }
 
734
 
 
735
  *hashtabptr = hashtab;
 
736
  *hashmaxptr = hashmax;
 
737
  *hashmskptr = hashmsk;
 
738
  *savetabptr = savetab;
 
739
 
 
740
  memSet (hashtab + hashold, ~0, hashold * sizeof (BgraphBipartFmVertex));
 
741
 
 
742
  gainTablFree (tablptr);                         /* Reset gain table  */
 
743
  *lockptr = NULL;                                /* Rebuild lock list */
 
744
 
 
745
  if (hashtab[0].vertnum != ~0) {                 /* If vertex overflowing may have occured in old hash table */
 
746
    Gnum                        hashtmp;
 
747
    Gnum                        hashnew;
 
748
 
 
749
    for (hashtmp = hashold - 1, hashnew = 0;      /* Temporarily move vertices away from end of old table to prevent overflowing */
 
750
         hashtab[hashtmp].vertnum != ~0; hashtmp --) {
 
751
      while (hashtab[++ hashnew].vertnum != ~0) ; /* Find an empty slot to receive moved vertex */
 
752
#ifdef SCOTCH_DEBUG_BGRAPH2
 
753
      if (hashnew >= hashtmp) {
 
754
        errorPrint ("bgraphBipartFmResize: internal error (2)");
 
755
        return     (1);
 
756
      }
 
757
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
758
 
 
759
      hashtab[hashnew] = hashtab[hashtmp];        /* Move vertex from end of table */
 
760
      hashtab[hashtmp].mswpnum = ~0;              /* TRICK: not tested at creation */
 
761
      hashtab[hashtmp].vertnum = ~0;              /* Set old slot as free          */
 
762
    }
 
763
  }
 
764
 
 
765
  for (hashnum = 0; hashnum < hashold; hashnum ++) { /* Re-compute position of vertices in new table */
 
766
    Gnum                        vertnum;
 
767
 
 
768
    vertnum = hashtab[hashnum].vertnum;
 
769
    if (vertnum != ~0) {                          /* If hash slot used */
 
770
      Gnum                        hashnew;
 
771
 
 
772
      for (hashnew = (vertnum * BGRAPHBIPARTFMHASHPRIME) & hashmsk; ; hashnew = (hashnew + 1) & hashmsk) {
 
773
        if (hashnew == hashnum)                   /* If hash slot is the same      */
 
774
          break;                                  /* There is nothing to do        */
 
775
        if (hashtab[hashnew].vertnum == ~0) {     /* If new slot is empty          */
 
776
          hashtab[hashnew] = hashtab[hashnum];    /* Copy data to new slot         */
 
777
          hashtab[hashnum].mswpnum = ~0;          /* TRICK: not tested at creation */
 
778
          hashtab[hashnum].vertnum = ~0;          /* Make old slot empty           */
 
779
          break;
 
780
        }
 
781
      }
 
782
      if ((hashnew > hashnum) && (hashnew < hashold)) /* If vertex was an overflowed vertex which will be replaced at end of old table */
 
783
        continue;                                 /* It will be re-processed again and re-linked once for good at the end of the loop  */
 
784
 
 
785
      if (hashtab[hashnew].gainlink.next >= BGRAPHBIPARTFMSTATELINK) /* If vertex was linked, re-link it */
 
786
        gainTablAdd (tablptr, &hashtab[hashnew].gainlink, hashtab[hashnew].compgain);
 
787
      else if (hashtab[hashnew].gainlink.next == BGRAPHBIPARTFMSTATEUSED) { /* Re-lock used vertices */
 
788
        hashtab[hashnew].gainlink.prev = (GainLink *) *lockptr; /* Lock it */
 
789
        *lockptr = &hashtab[hashnew];
 
790
      }
 
791
    }
 
792
  }
 
793
 
 
794
  for (savenum = 0; savenum < savenbr; savenum ++) {
 
795
    Gnum                  vertnum;
 
796
    Gnum                  hashnum;
 
797
 
 
798
    vertnum = savetab[savenum].hashnum;           /* Get vertex number temporarily saved */
 
799
    for (hashnum = (vertnum * BGRAPHBIPARTFMHASHPRIME) & hashmsk; hashtab[hashnum].vertnum != vertnum; hashnum = (hashnum + 1) & hashmsk) {
 
800
#ifdef SCOTCH_DEBUG_BGRAPH2
 
801
      if (hashtab[hashnum].vertnum == ~0) {
 
802
        errorPrint ("bgraphBipartFmResize: internal error (3)");
 
803
        return     (1);
 
804
      }
 
805
#endif /* SCOTCH_DEBUG_BGRAPH2 */
 
806
    }
 
807
    savetab[savenum].hashnum = hashnum;           /* Set new hash table index */
 
808
  }
 
809
 
 
810
  return (0);
 
811
}
 
812
 
 
813
/* This routine checks the consistency of
 
814
** the hash structures.
 
815
** It returns:
 
816
** - 0   : in case of success.
 
817
** - !0  : in case of error.
 
818
*/
 
819
 
 
820
#ifdef SCOTCH_DEBUG_BGRAPH2
 
821
#ifdef SCOTCH_DEBUG_BGRAPH3
 
822
static
 
823
int
 
824
bgraphBipartFmCheck (
 
825
const Bgraph * restrict const               grafptr,
 
826
const BgraphBipartFmVertex * restrict const hashtab,
 
827
const Gnum                                  hashmsk,
 
828
const int                                   swapval,
 
829
const Gnum                                  compload0dlt,
 
830
const Gnum                                  commload,
 
831
const Gnum                                  commgainextn)
 
832
{
 
833
  Gnum                  domdist;
 
834
  Gnum                  hashnum;
 
835
  Gnum                  compload0tmp;
 
836
  Gnum                  commloaddlttmp;           /* Difference between old and current communication load */
 
837
  Gnum                  commloadextndlttmp;
 
838
  Gnum                  commgainextntmp;
 
839
 
 
840
  domdist            = grafptr->domdist;
 
841
  compload0tmp       = (swapval == 0) ? grafptr->compload0 : (grafptr->s.velosum - grafptr->compload0);
 
842
  commloaddlttmp     = 0;                         /* No difference yet */
 
843
  commloadextndlttmp = swapval * grafptr->commgainextn;
 
844
  commgainextntmp    = (1 - 2 * swapval) * grafptr->commgainextn;
 
845
  for (hashnum = 0; hashnum <= hashmsk; hashnum ++) { /* For all vertex slots */
 
846
    Gnum                vertnum;
 
847
    Gnum                veloval;
 
848
    Gnum                veexval;
 
849
    Gnum                edgenum;
 
850
    int                 partval;
 
851
    int                 partold;
 
852
    Gnum                commcut;
 
853
    Gnum                commgain;
 
854
    Gnum                commgainextn;
 
855
 
 
856
    vertnum = hashtab[hashnum].vertnum;
 
857
    if (vertnum == ~0)                            /* If unallocated slot */
 
858
      continue;                                   /* Skip to next slot   */
 
859
 
 
860
    veloval = (grafptr->s.velotax != NULL) ? grafptr->s.velotax[vertnum] : 1;
 
861
    partval = hashtab[hashnum].partval;
 
862
    if ((partval < 0) || (partval > 1)) {
 
863
      errorPrint ("bgraphBipartFmCheck: invalid vertex part value");
 
864
      return     (1);
 
865
    }
 
866
    if (hashtab[hashnum].compgain != (2 * partval - 1) * veloval) {
 
867
      errorPrint ("bgraphBipartFmCheck: invalid vertex computation gain");
 
868
      return     (1);
 
869
    }
 
870
    partold = grafptr->parttax[vertnum] ^ swapval;
 
871
    veexval = (grafptr->veextax != NULL) ? grafptr->veextax[vertnum] : 0;
 
872
 
 
873
    compload0tmp    += (partval ^ partold) * (1 - 2 * partval) * veloval;
 
874
    commgainextn     = (1 - 2 * partval) * veexval;
 
875
    commgainextntmp += (partval ^ partold) * commgainextn * 2;
 
876
    commloadextndlttmp -= (partval ^ partold) * commgainextn;
 
877
 
 
878
    commcut  =
 
879
    commgain = 0;
 
880
    for (edgenum = grafptr->s.verttax[vertnum];   /* For all neighbors */
 
881
         edgenum < grafptr->s.vendtax[vertnum]; edgenum ++) {
 
882
      Gnum                edloval;
 
883
      Gnum                vertend;
 
884
      Gnum                hashend;
 
885
      int                 partend;
 
886
      int                 partond;
 
887
      int                 partdlt;
 
888
 
 
889
      vertend = grafptr->s.edgetax[edgenum];
 
890
      partond = grafptr->parttax[vertend] ^ swapval;
 
891
      edloval = (grafptr->s.edlotax != NULL) ? grafptr->s.edlotax[edgenum] : 1;
 
892
 
 
893
      for (hashend = (vertend * BGRAPHBIPARTFMHASHPRIME) & hashmsk; ; hashend = (hashend + 1) & hashmsk) {
 
894
        if (hashtab[hashend].vertnum == vertend) { /* If end vertex found */
 
895
          partend = hashtab[hashend].partval;
 
896
          break;
 
897
        }
 
898
        if (hashtab[hashend].vertnum == ~0) {     /* If end vertex not present */
 
899
          partend = partond;                      /* Keep old end part         */
 
900
          break;
 
901
        }
 
902
      }
 
903
      partdlt         = partval ^ partend;
 
904
      commcut        += partdlt;
 
905
      commgain       += (1 - 2 * partdlt) * edloval;
 
906
      commloaddlttmp += (partdlt - (partold ^ partond)) * edloval; /* Will account twice for difference of edge loads */
 
907
    }
 
908
    if (commcut != hashtab[hashnum].commcut) {
 
909
      errorPrint ("bgraphBipartFmCheck: invalid vertex cut value");
 
910
      return     (1);
 
911
    }
 
912
    if ((commgain * domdist + commgainextn) != hashtab[hashnum].commgain) {
 
913
      errorPrint ("bgraphBipartFmCheck: invalid vertex communication gain value");
 
914
      return     (1);
 
915
    }
 
916
  }
 
917
  if ((compload0tmp - grafptr->compload0avg) != compload0dlt) {
 
918
    errorPrint ("bgraphBipartFmCheck: invalid computation load");
 
919
    return     (1);
 
920
  }
 
921
  if ((grafptr->commload + (commloaddlttmp / 2) * domdist) != (commload - commloadextndlttmp)) {
 
922
    errorPrint ("bgraphBipartFmCheck: invalid communication load");
 
923
    return     (1);
 
924
  }
 
925
  if (commgainextntmp != commgainextn) {
 
926
    errorPrint ("bgraphBipartFmCheck: invalid external communication gain");
 
927
    return     (1);
 
928
  }
 
929
 
 
930
  return (0);
 
931
}
 
932
#endif /* SCOTCH_DEBUG_BGRAPH3 */
 
933
#endif /* SCOTCH_DEBUG_BGRAPH2 */