Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
mkwayfmh.c
Go to the documentation of this file.
1 /*
2  * mkwayfmh.c
3  *
4  * This file contains code that implements the multilevel k-way refinement
5  *
6  * Started 7/28/97
7  * George
8  *
9  * $Id: mkwayfmh.c,v 1.1 1998/11/27 17:59:24 karypis Exp $
10  *
11  */
12 
13 #include <metis.h>
14 
15 
16 
17 /*************************************************************************
18 * This function performs k-way refinement
19 **************************************************************************/
21  float *orgubvec, int npasses)
22 {
23  int i, ii, iii, j, jj, k, l, pass, nvtxs, ncon, nmoves, nbnd, myndegrees, same;
24  int from, me, to, oldcut, gain;
25  idxtype *xadj, *adjncy, *adjwgt;
26  idxtype *where, *perm, *bndptr, *bndind;
27  EDegreeType *myedegrees;
28  RInfoType *myrinfo;
29  float *npwgts, *nvwgt, *minwgt, *maxwgt, maxlb, minlb, ubvec[MAXNCON], tvec[MAXNCON];
30 
31  nvtxs = graph->nvtxs;
32  ncon = graph->ncon;
33  xadj = graph->xadj;
34  adjncy = graph->adjncy;
35  adjwgt = graph->adjwgt;
36 
37  bndptr = graph->bndptr;
38  bndind = graph->bndind;
39 
40  where = graph->where;
41  npwgts = graph->npwgts;
42 
43  /* Setup the weight intervals of the various subdomains */
44  minwgt = fwspacemalloc(ctrl, nparts*ncon);
45  maxwgt = fwspacemalloc(ctrl, nparts*ncon);
46 
47  /* See if the orgubvec consists of identical constraints */
48  maxlb = minlb = orgubvec[0];
49  for (i=1; i<ncon; i++) {
50  minlb = (orgubvec[i] < minlb ? orgubvec[i] : minlb);
51  maxlb = (orgubvec[i] > maxlb ? orgubvec[i] : maxlb);
52  }
53  same = (fabs(maxlb-minlb) < .01 ? 1 : 0);
54 
55 
56  /* Let's not get very optimistic. Let Balancing do the work */
57  ComputeHKWayLoadImbalance(ncon, nparts, npwgts, ubvec);
58  for (i=0; i<ncon; i++)
59  ubvec[i] = amax(ubvec[i], orgubvec[i]);
60 
61  if (!same) {
62  for (i=0; i<nparts; i++) {
63  for (j=0; j<ncon; j++) {
64  maxwgt[i*ncon+j] = ubvec[j]/nparts;
65  minwgt[i*ncon+j] = 1.0/(ubvec[j]*nparts);
66  }
67  }
68  }
69  else {
70  maxlb = ubvec[0];
71  for (i=1; i<ncon; i++)
72  maxlb = (ubvec[i] > maxlb ? ubvec[i] : maxlb);
73 
74  for (i=0; i<nparts; i++) {
75  for (j=0; j<ncon; j++) {
76  maxwgt[i*ncon+j] = maxlb/nparts;
77  minwgt[i*ncon+j] = 1.0/(maxlb*nparts);
78  }
79  }
80  }
81 
82 
83  perm = idxwspacemalloc(ctrl, nvtxs);
84 
85  if (ctrl->dbglvl&DBG_REFINE) {
86  printf("Partitions: [%5.4f %5.4f], Nv-Nb[%6d %6d]. Cut: %6d, LB: ",
87  npwgts[samin(ncon*nparts, npwgts)], npwgts[samax(ncon*nparts, npwgts)],
88  graph->nvtxs, graph->nbnd, graph->mincut);
89  ComputeHKWayLoadImbalance(ncon, nparts, npwgts, tvec);
90  for (i=0; i<ncon; i++)
91  printf("%.3f ", tvec[i]);
92  printf("\n");
93  }
94 
95  for (pass=0; pass<npasses; pass++) {
96  ASSERT(ComputeCut(graph, where) == graph->mincut);
97 
98  oldcut = graph->mincut;
99  nbnd = graph->nbnd;
100 
101  RandomPermute(nbnd, perm, 1);
102  for (nmoves=iii=0; iii<graph->nbnd; iii++) {
103  ii = perm[iii];
104  if (ii >= nbnd)
105  continue;
106  i = bndind[ii];
107 
108  myrinfo = graph->rinfo+i;
109 
110  if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */
111  from = where[i];
112  nvwgt = graph->nvwgt+i*ncon;
113 
114  if (myrinfo->id > 0 && AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, -1.0, nvwgt, minwgt+from*ncon))
115  continue; /* This cannot be moved! */
116 
117  myedegrees = myrinfo->edegrees;
118  myndegrees = myrinfo->ndegrees;
119 
120  for (k=0; k<myndegrees; k++) {
121  to = myedegrees[k].pid;
122  gain = myedegrees[k].ed - myrinfo->id;
123  if (gain >= 0 &&
124  (AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon) ||
125  IsHBalanceBetterFT(ncon, nparts, npwgts+from*ncon, npwgts+to*ncon, nvwgt, ubvec)))
126  break;
127  }
128  if (k == myndegrees)
129  continue; /* break out if you did not find a candidate */
130 
131  for (j=k+1; j<myndegrees; j++) {
132  to = myedegrees[j].pid;
133  if ((myedegrees[j].ed > myedegrees[k].ed &&
134  (AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon) ||
135  IsHBalanceBetterFT(ncon, nparts, npwgts+from*ncon, npwgts+to*ncon, nvwgt, ubvec))) ||
136  (myedegrees[j].ed == myedegrees[k].ed &&
137  IsHBalanceBetterTT(ncon, nparts, npwgts+myedegrees[k].pid*ncon, npwgts+to*ncon, nvwgt, ubvec)))
138  k = j;
139  }
140 
141  to = myedegrees[k].pid;
142 
143  if (myedegrees[k].ed-myrinfo->id == 0
144  && !IsHBalanceBetterFT(ncon, nparts, npwgts+from*ncon, npwgts+to*ncon, nvwgt, ubvec)
145  && AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, npwgts+from*ncon, maxwgt+from*ncon))
146  continue;
147 
148  /*=====================================================================
149  * If we got here, we can now move the vertex from 'from' to 'to'
150  *======================================================================*/
151  graph->mincut -= myedegrees[k].ed-myrinfo->id;
152 
153  IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
154 
155  /* Update where, weight, and ID/ED information of the vertex you moved */
156  saxpy(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);
157  saxpy(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);
158  where[i] = to;
159  myrinfo->ed += myrinfo->id-myedegrees[k].ed;
160  SWAP(myrinfo->id, myedegrees[k].ed, j);
161  if (myedegrees[k].ed == 0)
162  myedegrees[k] = myedegrees[--myrinfo->ndegrees];
163  else
164  myedegrees[k].pid = from;
165 
166  if (myrinfo->ed-myrinfo->id < 0)
167  BNDDelete(nbnd, bndind, bndptr, i);
168 
169  /* Update the degrees of adjacent vertices */
170  for (j=xadj[i]; j<xadj[i+1]; j++) {
171  ii = adjncy[j];
172  me = where[ii];
173 
174  myrinfo = graph->rinfo+ii;
175  if (myrinfo->edegrees == NULL) {
176  myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
177  ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
178  }
179  myedegrees = myrinfo->edegrees;
180 
181  ASSERT(CheckRInfo(myrinfo));
182 
183  if (me == from) {
184  INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
185 
186  if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
187  BNDInsert(nbnd, bndind, bndptr, ii);
188  }
189  else if (me == to) {
190  INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
191 
192  if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
193  BNDDelete(nbnd, bndind, bndptr, ii);
194  }
195 
196  /* Remove contribution from the .ed of 'from' */
197  if (me != from) {
198  for (k=0; k<myrinfo->ndegrees; k++) {
199  if (myedegrees[k].pid == from) {
200  if (myedegrees[k].ed == adjwgt[j])
201  myedegrees[k] = myedegrees[--myrinfo->ndegrees];
202  else
203  myedegrees[k].ed -= adjwgt[j];
204  break;
205  }
206  }
207  }
208 
209  /* Add contribution to the .ed of 'to' */
210  if (me != to) {
211  for (k=0; k<myrinfo->ndegrees; k++) {
212  if (myedegrees[k].pid == to) {
213  myedegrees[k].ed += adjwgt[j];
214  break;
215  }
216  }
217  if (k == myrinfo->ndegrees) {
218  myedegrees[myrinfo->ndegrees].pid = to;
219  myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
220  }
221  }
222 
223  ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
224  ASSERT(CheckRInfo(myrinfo));
225 
226  }
227  nmoves++;
228  }
229  }
230 
231  graph->nbnd = nbnd;
232 
233  if (ctrl->dbglvl&DBG_REFINE) {
234  printf("\t [%5.4f %5.4f], Nb: %6d, Nmoves: %5d, Cut: %6d, LB: ",
235  npwgts[samin(ncon*nparts, npwgts)], npwgts[samax(ncon*nparts, npwgts)],
236  nbnd, nmoves, graph->mincut);
237  ComputeHKWayLoadImbalance(ncon, nparts, npwgts, tvec);
238  for (i=0; i<ncon; i++)
239  printf("%.3f ", tvec[i]);
240  printf("\n");
241  }
242 
243  if (graph->mincut == oldcut)
244  break;
245  }
246 
247  fwspacefree(ctrl, ncon*nparts);
248  fwspacefree(ctrl, ncon*nparts);
249  idxwspacefree(ctrl, nvtxs);
250 }
251 
252 
253 
254 /*************************************************************************
255 * This function performs k-way refinement
256 **************************************************************************/
258  float *ubvec, int npasses)
259 {
260  int i, ii, iii, j, jj, k, l, pass, nvtxs, ncon, nbnd, myndegrees, oldgain, gain, nmoves;
261  int from, me, to, oldcut;
262  idxtype *xadj, *adjncy, *adjwgt;
263  idxtype *where, *perm, *bndptr, *bndind, *moved;
264  EDegreeType *myedegrees;
265  RInfoType *myrinfo;
266  PQueueType queue;
267  float *npwgts, *nvwgt, *minwgt, *maxwgt, tvec[MAXNCON];
268 
269  nvtxs = graph->nvtxs;
270  ncon = graph->ncon;
271  xadj = graph->xadj;
272  adjncy = graph->adjncy;
273  adjwgt = graph->adjwgt;
274 
275  bndind = graph->bndind;
276  bndptr = graph->bndptr;
277 
278  where = graph->where;
279  npwgts = graph->npwgts;
280 
281  /* Setup the weight intervals of the various subdomains */
282  minwgt = fwspacemalloc(ctrl, ncon*nparts);
283  maxwgt = fwspacemalloc(ctrl, ncon*nparts);
284 
285  for (i=0; i<nparts; i++) {
286  for (j=0; j<ncon; j++) {
287  maxwgt[i*ncon+j] = ubvec[j]/nparts;
288  minwgt[i*ncon+j] = 1.0/(ubvec[j]*nparts);
289  }
290  }
291 
292  perm = idxwspacemalloc(ctrl, nvtxs);
293  moved = idxwspacemalloc(ctrl, nvtxs);
294 
295  PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
296 
297  if (ctrl->dbglvl&DBG_REFINE) {
298  printf("Partitions: [%5.4f %5.4f], Nv-Nb[%6d %6d]. Cut: %6d, LB: ",
299  npwgts[samin(ncon*nparts, npwgts)], npwgts[samax(ncon*nparts, npwgts)],
300  graph->nvtxs, graph->nbnd, graph->mincut);
301  ComputeHKWayLoadImbalance(ncon, nparts, npwgts, tvec);
302  for (i=0; i<ncon; i++)
303  printf("%.3f ", tvec[i]);
304  printf("[B]\n");
305  }
306 
307 
308  for (pass=0; pass<npasses; pass++) {
309  ASSERT(ComputeCut(graph, where) == graph->mincut);
310 
311  /* Check to see if things are out of balance, given the tolerance */
312  if (MocIsHBalanced(ncon, nparts, npwgts, ubvec))
313  break;
314 
315  PQueueReset(&queue);
316  idxset(nvtxs, -1, moved);
317 
318  oldcut = graph->mincut;
319  nbnd = graph->nbnd;
320 
321  RandomPermute(nbnd, perm, 1);
322  for (ii=0; ii<nbnd; ii++) {
323  i = bndind[perm[ii]];
324  PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
325  moved[i] = 2;
326  }
327 
328  nmoves = 0;
329  for (;;) {
330  if ((i = PQueueGetMax(&queue)) == -1)
331  break;
332  moved[i] = 1;
333 
334  myrinfo = graph->rinfo+i;
335  from = where[i];
336  nvwgt = graph->nvwgt+i*ncon;
337 
338  if (AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, -1.0, nvwgt, minwgt+from*ncon))
339  continue; /* This cannot be moved! */
340 
341  myedegrees = myrinfo->edegrees;
342  myndegrees = myrinfo->ndegrees;
343 
344  for (k=0; k<myndegrees; k++) {
345  to = myedegrees[k].pid;
346  if (IsHBalanceBetterFT(ncon, nparts, npwgts+from*ncon, npwgts+to*ncon, nvwgt, ubvec))
347  break;
348  }
349  if (k == myndegrees)
350  continue; /* break out if you did not find a candidate */
351 
352  for (j=k+1; j<myndegrees; j++) {
353  to = myedegrees[j].pid;
354  if (IsHBalanceBetterTT(ncon, nparts, npwgts+myedegrees[k].pid*ncon, npwgts+to*ncon, nvwgt, ubvec))
355  k = j;
356  }
357 
358  to = myedegrees[k].pid;
359 
360  j = 0;
361  if (!AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, maxwgt+from*ncon))
362  j++;
363  if (myedegrees[k].ed-myrinfo->id >= 0)
364  j++;
365  if (!AreAllHVwgtsAbove(ncon, 1.0, npwgts+to*ncon, 0.0, nvwgt, minwgt+to*ncon) &&
366  AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon))
367  j++;
368  if (j == 0)
369  continue;
370 
371 /* DELETE
372  if (myedegrees[k].ed-myrinfo->id < 0 &&
373  AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, maxwgt+from*ncon) &&
374  AreAllHVwgtsAbove(ncon, 1.0, npwgts+to*ncon, 0.0, nvwgt, minwgt+to*ncon) &&
375  AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon))
376  continue;
377 */
378  /*=====================================================================
379  * If we got here, we can now move the vertex from 'from' to 'to'
380  *======================================================================*/
381  graph->mincut -= myedegrees[k].ed-myrinfo->id;
382 
383  IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
384 
385  /* Update where, weight, and ID/ED information of the vertex you moved */
386  saxpy(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);
387  saxpy(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);
388  where[i] = to;
389  myrinfo->ed += myrinfo->id-myedegrees[k].ed;
390  SWAP(myrinfo->id, myedegrees[k].ed, j);
391  if (myedegrees[k].ed == 0)
392  myedegrees[k] = myedegrees[--myrinfo->ndegrees];
393  else
394  myedegrees[k].pid = from;
395 
396  if (myrinfo->ed == 0)
397  BNDDelete(nbnd, bndind, bndptr, i);
398 
399  /* Update the degrees of adjacent vertices */
400  for (j=xadj[i]; j<xadj[i+1]; j++) {
401  ii = adjncy[j];
402  me = where[ii];
403 
404  myrinfo = graph->rinfo+ii;
405  if (myrinfo->edegrees == NULL) {
406  myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
407  ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
408  }
409  myedegrees = myrinfo->edegrees;
410 
411  ASSERT(CheckRInfo(myrinfo));
412 
413  oldgain = (myrinfo->ed-myrinfo->id);
414 
415  if (me == from) {
416  INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
417 
418  if (myrinfo->ed > 0 && bndptr[ii] == -1)
419  BNDInsert(nbnd, bndind, bndptr, ii);
420  }
421  else if (me == to) {
422  INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
423 
424  if (myrinfo->ed == 0 && bndptr[ii] != -1)
425  BNDDelete(nbnd, bndind, bndptr, ii);
426  }
427 
428  /* Remove contribution from the .ed of 'from' */
429  if (me != from) {
430  for (k=0; k<myrinfo->ndegrees; k++) {
431  if (myedegrees[k].pid == from) {
432  if (myedegrees[k].ed == adjwgt[j])
433  myedegrees[k] = myedegrees[--myrinfo->ndegrees];
434  else
435  myedegrees[k].ed -= adjwgt[j];
436  break;
437  }
438  }
439  }
440 
441  /* Add contribution to the .ed of 'to' */
442  if (me != to) {
443  for (k=0; k<myrinfo->ndegrees; k++) {
444  if (myedegrees[k].pid == to) {
445  myedegrees[k].ed += adjwgt[j];
446  break;
447  }
448  }
449  if (k == myrinfo->ndegrees) {
450  myedegrees[myrinfo->ndegrees].pid = to;
451  myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
452  }
453  }
454 
455 
456  /* Update the queue */
457  if (me == to || me == from) {
458  gain = myrinfo->ed-myrinfo->id;
459  if (moved[ii] == 2) {
460  if (myrinfo->ed > 0)
461  PQueueUpdate(&queue, ii, oldgain, gain);
462  else {
463  PQueueDelete(&queue, ii, oldgain);
464  moved[ii] = -1;
465  }
466  }
467  else if (moved[ii] == -1 && myrinfo->ed > 0) {
468  PQueueInsert(&queue, ii, gain);
469  moved[ii] = 2;
470  }
471  }
472 
473  ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
474  ASSERT(CheckRInfo(myrinfo));
475  }
476  nmoves++;
477  }
478 
479  graph->nbnd = nbnd;
480 
481  if (ctrl->dbglvl&DBG_REFINE) {
482  printf("\t [%5.4f %5.4f], Nb: %6d, Nmoves: %5d, Cut: %6d, LB: ",
483  npwgts[samin(ncon*nparts, npwgts)], npwgts[samax(ncon*nparts, npwgts)],
484  nbnd, nmoves, graph->mincut);
485  ComputeHKWayLoadImbalance(ncon, nparts, npwgts, tvec);
486  for (i=0; i<ncon; i++)
487  printf("%.3f ", tvec[i]);
488  printf("\n");
489  }
490 
491  if (nmoves == 0)
492  break;
493  }
494 
495  PQueueFree(ctrl, &queue);
496 
497  fwspacefree(ctrl, ncon*nparts);
498  fwspacefree(ctrl, ncon*nparts);
499  idxwspacefree(ctrl, nvtxs);
500  idxwspacefree(ctrl, nvtxs);
501 
502 }
503 
504 
505 
506 
507 
508 /*************************************************************************
509 * This function checks if the vertex weights of two vertices are below
510 * a given set of values
511 **************************************************************************/
512 int AreAllHVwgtsBelow(int ncon, float alpha, float *vwgt1, float beta, float *vwgt2, float *limit)
513 {
514  int i;
515 
516  for (i=0; i<ncon; i++)
517  if (alpha*vwgt1[i] + beta*vwgt2[i] > limit[i])
518  return 0;
519 
520  return 1;
521 }
522 
523 
524 
525 /*************************************************************************
526 * This function checks if the vertex weights of two vertices are above
527 * a given set of values
528 **************************************************************************/
529 int AreAllHVwgtsAbove(int ncon, float alpha, float *vwgt1, float beta, float *vwgt2, float *limit)
530 {
531  int i;
532 
533  for (i=0; i<ncon; i++)
534  if (alpha*vwgt1[i] + beta*vwgt2[i] < limit[i])
535  return 0;
536 
537  return 1;
538 }
539 
540 
541 /*************************************************************************
542 * This function computes the load imbalance over all the constrains
543 * For now assume that we just want balanced partitionings
544 **************************************************************************/
545 void ComputeHKWayLoadImbalance(int ncon, int nparts, float *npwgts, float *lbvec)
546 {
547  int i, j;
548  float max;
549 
550  for (i=0; i<ncon; i++) {
551  max = 0.0;
552  for (j=0; j<nparts; j++) {
553  if (npwgts[j*ncon+i] > max)
554  max = npwgts[j*ncon+i];
555  }
556 
557  lbvec[i] = max*nparts;
558  }
559 }
560 
561 
562 /*************************************************************************
563 * This function determines if a partitioning is horizontally balanced
564 **************************************************************************/
565 int MocIsHBalanced(int ncon, int nparts, float *npwgts, float *ubvec)
566 {
567  int i, j;
568  float max;
569 
570  for (i=0; i<ncon; i++) {
571  max = 0.0;
572  for (j=0; j<nparts; j++) {
573  if (npwgts[j*ncon+i] > max)
574  max = npwgts[j*ncon+i];
575  }
576 
577  if (ubvec[i] < max*nparts)
578  return 0;
579  }
580 
581  return 1;
582 }
583 
584 
585 
586 
587 
588 /*************************************************************************
589 * This function checks if the pairwise balance of the between the two
590 * partitions will improve by moving the vertex v from pfrom to pto,
591 * subject to the target partition weights of tfrom, and tto respectively
592 **************************************************************************/
593 int IsHBalanceBetterFT(int ncon, int nparts, float *pfrom, float *pto, float *vwgt, float *ubvec)
594 {
595  int i, j, k;
596  float blb1=0.0, alb1=0.0, sblb=0.0, salb=0.0;
597  float blb2=0.0, alb2=0.0;
598  float temp;
599 
600  for (i=0; i<ncon; i++) {
601  temp = amax(pfrom[i], pto[i])*nparts/ubvec[i];
602  if (blb1 < temp) {
603  blb2 = blb1;
604  blb1 = temp;
605  }
606  else if (blb2 < temp)
607  blb2 = temp;
608  sblb += temp;
609 
610  temp = amax(pfrom[i]-vwgt[i], pto[i]+vwgt[i])*nparts/ubvec[i];
611  if (alb1 < temp) {
612  alb2 = alb1;
613  alb1 = temp;
614  }
615  else if (alb2 < temp)
616  alb2 = temp;
617  salb += temp;
618  }
619 
620  if (alb1 < blb1)
621  return 1;
622  if (blb1 < alb1)
623  return 0;
624  if (alb2 < blb2)
625  return 1;
626  if (blb2 < alb2)
627  return 0;
628 
629  return salb < sblb;
630 
631 }
632 
633 
634 
635 
636 /*************************************************************************
637 * This function checks if it will be better to move a vertex to pt2 than
638 * to pt1 subject to their target weights of tt1 and tt2, respectively
639 * This routine takes into account the weight of the vertex in question
640 **************************************************************************/
641 int IsHBalanceBetterTT(int ncon, int nparts, float *pt1, float *pt2, float *vwgt, float *ubvec)
642 {
643  int i;
644  float m11=0.0, m12=0.0, m21=0.0, m22=0.0, sm1=0.0, sm2=0.0, temp;
645 
646  for (i=0; i<ncon; i++) {
647  temp = (pt1[i]+vwgt[i])*nparts/ubvec[i];
648  if (m11 < temp) {
649  m12 = m11;
650  m11 = temp;
651  }
652  else if (m12 < temp)
653  m12 = temp;
654  sm1 += temp;
655 
656  temp = (pt2[i]+vwgt[i])*nparts/ubvec[i];
657  if (m21 < temp) {
658  m22 = m21;
659  m21 = temp;
660  }
661  else if (m22 < temp)
662  m22 = temp;
663  sm2 += temp;
664  }
665 
666  if (m21 < m11)
667  return 1;
668  if (m21 > m11)
669  return 0;
670  if (m22 < m12)
671  return 1;
672  if (m22 > m12)
673  return 0;
674 
675  return sm2 < sm1;
676 }
677 
EDegreeType * edegrees
Definition: struct.h:102
#define idxwspacefree
Definition: rename.h:165
#define PQueueUpdate
Definition: rename.h:320
int ndegrees
Definition: struct.h:121
#define ComputeHKWayLoadImbalance
Definition: rename.h:228
#define MCGreedy_KWayEdgeBalanceHorizontal
Definition: rename.h:225
#define saxpy
Definition: rename.h:409
idxtype * adjwgtsum
Definition: struct.h:168
#define DBG_REFINE
Definition: defs.h:157
int nbnd
Definition: struct.h:177
idxtype ed
Definition: struct.h:79
idxtype pid
Definition: struct.h:78
#define IsHBalanceBetterFT
Definition: rename.h:230
void fwspacefree(CtrlType *ctrl, int n)
Definition: memory.c:140
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int mincut
Definition: struct.h:175
#define DBG_MOVEINFO
Definition: defs.h:159
idxtype * bndptr
Definition: struct.h:178
#define idxwspacemalloc
Definition: rename.h:164
#define AreAllHVwgtsBelow
Definition: rename.h:226
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
float * npwgts
Definition: struct.h:196
int idxtype
Definition: struct.h:19
#define PQueueReset
Definition: rename.h:316
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define fwspacemalloc
Definition: rename.h:166
int ed
Definition: struct.h:120
#define AreAllHVwgtsAbove
Definition: rename.h:227
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
RInfoType * rinfo
Definition: struct.h:184
int cdegree
Definition: struct.h:104
#define MCRandom_KWayEdgeRefineHorizontal
Definition: rename.h:224
#define CheckRInfo
Definition: rename.h:47
int ncon
Definition: struct.h:194
#define BNDDelete(nbnd, bndind, bndptr, vtx)
Definition: macros.h:109
#define MAXNCON
Definition: defs.h:20
#define amax(a, b)
Definition: macros.h:29
idxtype * bndind
Definition: struct.h:178
#define idxamax
Definition: rename.h:393
#define IsHBalanceBetterTT
Definition: rename.h:231
#define MocIsHBalanced
Definition: rename.h:229
#define INC_DEC(a, b, val)
Definition: macros.h:39
#define samax
Definition: rename.h:395
#define samin
Definition: rename.h:398
#define PQueueGetMax
Definition: rename.h:322
EDegreeType * edegrees
Definition: struct.h:122
#define PQueueInsert
Definition: rename.h:318
int nvtxs
Definition: struct.h:161
#define RandomPermute
Definition: rename.h:410
WorkSpaceType wspace
Definition: struct.h:227
#define ASSERT(expr)
Definition: macros.h:130
#define SWAP(a, b, tmp)
Definition: macros.h:36
float * nvwgt
Definition: struct.h:195
#define ComputeCut
Definition: rename.h:43
#define max(a, b)
Definition: cannonAsync.c:47
#define PQueueDelete
Definition: rename.h:319
#define PQueueFree
Definition: rename.h:317
int id
Definition: struct.h:120
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define PQueueInit
Definition: rename.h:315