← Back to branch summary

~ubuntu-branches/ubuntu/precise/scotch/precise

« back to all changes in this revision

Viewing changes to src/libscotch/bdgraph_bipart_st.c

  • Committer: Package Import Robot
  • Author(s): "Adam C. Powell, IV"
  • Date: 2011-12-21 13:40:52 UTC
  • mfrom: (14.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20111221134052-1yw353l7p7zoo51d
Tags: 5.1.12b.dfsg-1
http://bugs.debian.org/652900
http://bugs.debian.org/652311
* New upstream (closes: #652900).
* Rebuild with new mpi-defaults (closes: #652311).
* Forward-ported build-fixes.patch (just shifted one hunk two lines).
* New build-arch and build-indep targets in rules.
* Updated VCS URLs.
* Bumped Standards-Version.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libscotch/bdgraph_bipart_st.c
1
 
/* Copyright 2007-2010 ENSEIRB, INRIA & CNRS
 
1
/* Copyright 2007-2011 ENSEIRB, INRIA & CNRS
2
2
**
3
3
** This file is part of the Scotch software package for static mapping,
4
4
** graph partitioning and sparse matrix ordering.
41
41
/**                bipartitioning methods.                 **/
42
42
/**                                                        **/
43
43
/**   DATES      : # Version 5.1  : from : 10 sep 2007     **/
44
 
/**                                 to   : 14 aug 2010     **/
 
44
/**                                 to   : 15 apr 2011     **/
45
45
/**                                                        **/
46
46
/************************************************************/
47
47
 
84
84
static union {
85
85
  BdgraphBipartDfParam      param;
86
86
  StratNodeMethodData       padding;
87
 
} bdgraphbipartstdefaultdf = { { 500, 1.0, 0.0, 0.0 } };
 
87
} bdgraphbipartstdefaultdf = { { 500, 1.0, 0.0, BDGRAPHBIPARTDFTYPEBAL } };
88
88
 
89
89
static union {
90
90
  BdgraphBipartExParam      param;
135
135
                                (byte *) &bdgraphbipartstdefaultdf.param,
136
136
                                (byte *) &bdgraphbipartstdefaultdf.param.cremval,
137
137
                                NULL },
 
138
                              { BDGRAPHBIPARTSTMETHDF,  STRATPARAMCASE,   "type",
 
139
                                (byte *) &bdgraphbipartstdefaultdf.param,
 
140
                                (byte *) &bdgraphbipartstdefaultdf.param.typeval,
 
141
                                (void *) "bk" },
138
142
                              { BDGRAPHBIPARTSTMETHEX,  STRATPARAMINT,    "sbbt",
139
143
                                (byte *) &bdgraphbipartstdefaultex.param,
140
144
                                (byte *) &bdgraphbipartstdefaultex.param.sbbtnbr,
183
187
                                (byte *) &bdgraphdummy,
184
188
                                (byte *) &bdgraphdummy.compglbload0,
185
189
                                NULL },
 
190
                              { STRATNODECOND,       STRATPARAMINT,    "lmin0",
 
191
                                (byte *) &bdgraphdummy,
 
192
                                (byte *) &bdgraphdummy.compglbload0min,
 
193
                                NULL },
 
194
                              { STRATNODECOND,       STRATPARAMINT,    "lmax0",
 
195
                                (byte *) &bdgraphdummy,
 
196
                                (byte *) &bdgraphdummy.compglbload0max,
 
197
                                NULL },
186
198
                              { STRATNODECOND,       STRATPARAMINT,    "edge",
187
199
                                (byte *) &bdgraphdummy,
188
200
                                (byte *) &bdgraphdummy.s.edgeglbnbr,
300
312
      bdgraphStoreUpdt     (grafptr, &savetab[1]); /* Restore initial bipartition           */
301
313
      o2 = bdgraphBipartSt (grafptr, strat->data.select.strat[1]); /* Apply second strategy */
302
314
 
303
 
      if ((o == 0) || (o2 == 0)) {                /* If at least one method did bipartition     */
304
 
        if ( (savetab[0].commglbload <  grafptr->commglbload) || /* If first strategy is better */
305
 
            ((savetab[0].commglbload == grafptr->commglbload) &&
306
 
             (abs (savetab[0].compglbload0dlt) < abs (grafptr->compglbload0dlt))))
 
315
      if ((o == 0) || (o2 == 0)) {                /* If at least one method did bipartition */
 
316
        Gnum                compglbload0;
 
317
        int                 b0;
 
318
        int                 b1;
 
319
 
 
320
        compglbload0 = grafptr->compglbload0avg + savetab[0].compglbload0dlt;
 
321
        b0 = ((compglbload0 < grafptr->compglbload0min) ||
 
322
              (compglbload0 > grafptr->compglbload0max)) ? 1 : o;
 
323
        compglbload0 = grafptr->compglbload0avg + savetab[1].compglbload0dlt;
 
324
        b1 = ((compglbload0 < grafptr->compglbload0min) ||
 
325
              (compglbload0 > grafptr->compglbload0max)) ? 1 : o2;
 
326
 
 
327
        do {                                      /* Do we want to restore partition 0 ? */
 
328
          if (b0 > b1)
 
329
            break;
 
330
          if (b0 == b1) {                         /* If both are valid or invalid        */
 
331
            if (b0 == 0) {                        /* If both are valid                   */
 
332
              if ( (savetab[0].commglbload >  grafptr->commglbload) || /* Compare on cut */
 
333
                  ((savetab[0].commglbload == grafptr->commglbload) &&
 
334
                   (abs (savetab[0].compglbload0dlt) > abs (grafptr->compglbload0dlt))))
 
335
                break;
 
336
            }
 
337
            else {                                /* If both are invalid */
 
338
              if ( (abs (savetab[0].compglbload0dlt) >  abs (grafptr->compglbload0dlt)) || /* Compare on imbalance */
 
339
                  ((abs (savetab[0].compglbload0dlt) == abs (grafptr->compglbload0dlt)) &&
 
340
                   (savetab[0].commglbload > grafptr->commglbload)))
 
341
                break;
 
342
            }
 
343
          }
 
344
 
307
345
          bdgraphStoreUpdt (grafptr, &savetab[0]); /* Restore its result */
 
346
        }  while (0);
308
347
      }
309
348
      if (o2 < o)                                 /* o = min(o,o2): if one biparts, then bipart */
310
349
        o = o2;                                   /* Else if one stops, then stop, else error   */