source: inundation/pymetis/metis-4.0/Lib/subdomains.c @ 2051

Last change on this file since 2051 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.

File size: 38.2 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * subdomains.c
5 *
6 * This file contains functions that deal with prunning the number of
7 * adjacent subdomains in KMETIS
8 *
9 * Started 7/15/98
10 * George
11 *
12 * $Id: subdomains.c,v 1.1 1998/11/27 17:59:32 karypis Exp $
13 *
14 */
15
16#include <metis.h>
17
18
19/*************************************************************************
20* This function performs k-way refinement
21**************************************************************************/
22void Random_KWayEdgeRefineMConn(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses, int ffactor)
23{
24  int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees; 
25  int from, me, to, oldcut, vwgt, gain;
26  int maxndoms, nadd;
27  idxtype *xadj, *adjncy, *adjwgt;
28  idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
29  idxtype *phtable, *pmat, *pmatptr, *ndoms;
30  EDegreeType *myedegrees;
31  RInfoType *myrinfo;
32
33  nvtxs = graph->nvtxs;
34  xadj = graph->xadj;
35  adjncy = graph->adjncy;
36  adjwgt = graph->adjwgt;
37
38  bndptr = graph->bndptr;
39  bndind = graph->bndind;
40
41  where = graph->where;
42  pwgts = graph->pwgts;
43
44  pmat = ctrl->wspace.pmat;
45  phtable = idxwspacemalloc(ctrl, nparts);
46  ndoms = idxwspacemalloc(ctrl, nparts);
47
48  ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
49
50  /* Setup the weight intervals of the various subdomains */
51  minwgt =  idxwspacemalloc(ctrl, nparts);
52  maxwgt = idxwspacemalloc(ctrl, nparts);
53  itpwgts = idxwspacemalloc(ctrl, nparts);
54  tvwgt = idxsum(nparts, pwgts);
55  ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
56
57  for (i=0; i<nparts; i++) {
58    itpwgts[i] = tpwgts[i]*tvwgt;
59    maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
60    minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
61  }
62
63  perm = idxwspacemalloc(ctrl, nvtxs);
64
65  IFSET(ctrl->dbglvl, DBG_REFINE,
66     printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
67             pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
68             1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
69             graph->mincut));
70
71  for (pass=0; pass<npasses; pass++) {
72    ASSERT(ComputeCut(graph, where) == graph->mincut);
73
74    maxndoms = ndoms[idxamax(nparts, ndoms)];
75
76    oldcut = graph->mincut;
77    nbnd = graph->nbnd;
78
79    RandomPermute(nbnd, perm, 1);
80    for (nmoves=iii=0; iii<graph->nbnd; iii++) {
81      ii = perm[iii];
82      if (ii >= nbnd)
83        continue;
84      i = bndind[ii];
85
86      myrinfo = graph->rinfo+i;
87
88      if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */
89        from = where[i];
90        vwgt = graph->vwgt[i];
91
92        if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from]) 
93          continue;   /* This cannot be moved! */
94
95        myedegrees = myrinfo->edegrees;
96        myndegrees = myrinfo->ndegrees;
97
98        /* Determine the valid domains */
99        for (j=0; j<myndegrees; j++) {
100          to = myedegrees[j].pid;
101          phtable[to] = 1;
102          pmatptr = pmat + to*nparts;
103          for (nadd=0, k=0; k<myndegrees; k++) {
104            if (k == j)
105              continue;
106
107            l = myedegrees[k].pid;
108            if (pmatptr[l] == 0) {
109              if (ndoms[l] > maxndoms-1) {
110                phtable[to] = 0;
111                nadd = maxndoms;
112                break;
113              }
114              nadd++;
115            }
116          }
117          if (ndoms[to]+nadd > maxndoms)
118            phtable[to] = 0;
119          if (nadd == 0)
120            phtable[to] = 2;
121        }
122
123        /* Find the first valid move */
124        j = myrinfo->id;
125        for (k=0; k<myndegrees; k++) {
126          to = myedegrees[k].pid;
127          if (!phtable[to])
128            continue;
129          gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */ 
130          if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0) 
131            break;
132        }
133        if (k == myndegrees)
134          continue;  /* break out if you did not find a candidate */
135
136        for (j=k+1; j<myndegrees; j++) {
137          to = myedegrees[j].pid;
138          if (!phtable[to])
139            continue;
140          if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
141              (myedegrees[j].ed == myedegrees[k].ed && 
142               itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
143            k = j;
144        }
145
146        to = myedegrees[k].pid;
147
148        j = 0;
149        if (myedegrees[k].ed-myrinfo->id > 0)
150          j = 1;
151        else if (myedegrees[k].ed-myrinfo->id == 0) {
152          if (/*(iii&7) == 0  ||*/ phtable[myedegrees[k].pid] == 2 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
153            j = 1;
154        }
155        if (j == 0)
156          continue;
157         
158        /*=====================================================================
159        * If we got here, we can now move the vertex from 'from' to 'to'
160        *======================================================================*/
161        graph->mincut -= myedegrees[k].ed-myrinfo->id;
162
163        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));
164
165        /* Update pmat to reflect the move of 'i' */
166        pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
167        pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
168        if (pmat[from*nparts+to] == 0) {
169          ndoms[from]--;
170          if (ndoms[from]+1 == maxndoms)
171            maxndoms = ndoms[idxamax(nparts, ndoms)];
172        }
173        if (pmat[to*nparts+from] == 0) {
174          ndoms[to]--;
175          if (ndoms[to]+1 == maxndoms)
176            maxndoms = ndoms[idxamax(nparts, ndoms)];
177        }
178
179        /* Update where, weight, and ID/ED information of the vertex you moved */
180        where[i] = to;
181        INC_DEC(pwgts[to], pwgts[from], vwgt);
182        myrinfo->ed += myrinfo->id-myedegrees[k].ed;
183        SWAP(myrinfo->id, myedegrees[k].ed, j);
184        if (myedegrees[k].ed == 0) 
185          myedegrees[k] = myedegrees[--myrinfo->ndegrees];
186        else
187          myedegrees[k].pid = from;
188
189        if (myrinfo->ed-myrinfo->id < 0)
190          BNDDelete(nbnd, bndind, bndptr, i);
191
192        /* Update the degrees of adjacent vertices */
193        for (j=xadj[i]; j<xadj[i+1]; j++) {
194          ii = adjncy[j];
195          me = where[ii];
196
197          myrinfo = graph->rinfo+ii;
198          if (myrinfo->edegrees == NULL) {
199            myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
200            ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
201          }
202          myedegrees = myrinfo->edegrees;
203
204          ASSERT(CheckRInfo(myrinfo));
205
206          if (me == from) {
207            INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
208
209            if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
210              BNDInsert(nbnd, bndind, bndptr, ii);
211          }
212          else if (me == to) {
213            INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
214
215            if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
216              BNDDelete(nbnd, bndind, bndptr, ii);
217          }
218
219          /* Remove contribution from the .ed of 'from' */
220          if (me != from) {
221            for (k=0; k<myrinfo->ndegrees; k++) {
222              if (myedegrees[k].pid == from) {
223                if (myedegrees[k].ed == adjwgt[j])
224                  myedegrees[k] = myedegrees[--myrinfo->ndegrees];
225                else
226                  myedegrees[k].ed -= adjwgt[j];
227                break;
228              }
229            }
230          }
231
232          /* Add contribution to the .ed of 'to' */
233          if (me != to) {
234            for (k=0; k<myrinfo->ndegrees; k++) {
235              if (myedegrees[k].pid == to) {
236                myedegrees[k].ed += adjwgt[j];
237                break;
238              }
239            }
240            if (k == myrinfo->ndegrees) {
241              myedegrees[myrinfo->ndegrees].pid = to;
242              myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
243            }
244          }
245
246          /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
247          if (me != from && me != to) {
248            pmat[me*nparts+from] -= adjwgt[j];
249            pmat[from*nparts+me] -= adjwgt[j];
250            if (pmat[me*nparts+from] == 0) {
251              ndoms[me]--;
252              if (ndoms[me]+1 == maxndoms)
253                maxndoms = ndoms[idxamax(nparts, ndoms)];
254            }
255            if (pmat[from*nparts+me] == 0) {
256              ndoms[from]--;
257              if (ndoms[from]+1 == maxndoms)
258                maxndoms = ndoms[idxamax(nparts, ndoms)];
259            }
260
261            if (pmat[me*nparts+to] == 0) {
262              ndoms[me]++;
263              if (ndoms[me] > maxndoms) {
264                printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
265                maxndoms = ndoms[me];
266              }
267            }
268            if (pmat[to*nparts+me] == 0) {
269              ndoms[to]++;
270              if (ndoms[to] > maxndoms) {
271                printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
272                maxndoms = ndoms[to];
273              }
274            }
275            pmat[me*nparts+to] += adjwgt[j];
276            pmat[to*nparts+me] += adjwgt[j];
277          }
278
279          ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
280          ASSERT(CheckRInfo(myrinfo));
281
282        }
283        nmoves++;
284      }
285    }
286
287    graph->nbnd = nbnd;
288
289    IFSET(ctrl->dbglvl, DBG_REFINE,
290       printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %5d, Vol: %5d, %d\n",
291               pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
292               1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, 
293               graph->mincut, ComputeVolume(graph, where), idxsum(nparts, ndoms)));
294
295    if (graph->mincut == oldcut)
296      break;
297  }
298
299  idxwspacefree(ctrl, nparts);
300  idxwspacefree(ctrl, nparts);
301  idxwspacefree(ctrl, nparts);
302  idxwspacefree(ctrl, nparts);
303  idxwspacefree(ctrl, nparts);
304  idxwspacefree(ctrl, nvtxs);
305}
306
307
308
309/*************************************************************************
310* This function performs k-way refinement
311**************************************************************************/
312void Greedy_KWayEdgeBalanceMConn(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses)
313{
314  int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves; 
315  int from, me, to, oldcut, vwgt, maxndoms, nadd;
316  idxtype *xadj, *adjncy, *adjwgt;
317  idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
318  idxtype *phtable, *pmat, *pmatptr, *ndoms;
319  EDegreeType *myedegrees;
320  RInfoType *myrinfo;
321  PQueueType queue;
322
323  nvtxs = graph->nvtxs;
324  xadj = graph->xadj;
325  adjncy = graph->adjncy;
326  adjwgt = graph->adjwgt;
327
328  bndind = graph->bndind;
329  bndptr = graph->bndptr;
330
331  where = graph->where;
332  pwgts = graph->pwgts;
333 
334  pmat = ctrl->wspace.pmat;
335  phtable = idxwspacemalloc(ctrl, nparts);
336  ndoms = idxwspacemalloc(ctrl, nparts);
337
338  ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
339
340
341  /* Setup the weight intervals of the various subdomains */
342  minwgt =  idxwspacemalloc(ctrl, nparts);
343  maxwgt = idxwspacemalloc(ctrl, nparts);
344  itpwgts = idxwspacemalloc(ctrl, nparts);
345  tvwgt = idxsum(nparts, pwgts);
346  ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
347
348  for (i=0; i<nparts; i++) {
349    itpwgts[i] = tpwgts[i]*tvwgt;
350    maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
351    minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
352  }
353
354  perm = idxwspacemalloc(ctrl, nvtxs);
355  moved = idxwspacemalloc(ctrl, nvtxs);
356
357  PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
358
359  IFSET(ctrl->dbglvl, DBG_REFINE,
360     printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
361             pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
362             1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
363             graph->mincut));
364
365  for (pass=0; pass<npasses; pass++) {
366    ASSERT(ComputeCut(graph, where) == graph->mincut);
367
368    /* Check to see if things are out of balance, given the tolerance */
369    for (i=0; i<nparts; i++) {
370      if (pwgts[i] > maxwgt[i])
371        break;
372    }
373    if (i == nparts) /* Things are balanced. Return right away */
374      break;
375
376    PQueueReset(&queue);
377    idxset(nvtxs, -1, moved);
378
379    oldcut = graph->mincut;
380    nbnd = graph->nbnd;
381
382    RandomPermute(nbnd, perm, 1);
383    for (ii=0; ii<nbnd; ii++) {
384      i = bndind[perm[ii]];
385      PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
386      moved[i] = 2;
387    }
388
389    maxndoms = ndoms[idxamax(nparts, ndoms)];
390
391    for (nmoves=0;;) {
392      if ((i = PQueueGetMax(&queue)) == -1) 
393        break;
394      moved[i] = 1;
395
396      myrinfo = graph->rinfo+i;
397      from = where[i];
398      vwgt = graph->vwgt[i];
399
400      if (pwgts[from]-vwgt < minwgt[from]) 
401        continue;   /* This cannot be moved! */
402
403      myedegrees = myrinfo->edegrees;
404      myndegrees = myrinfo->ndegrees;
405
406      /* Determine the valid domains */
407      for (j=0; j<myndegrees; j++) {
408        to = myedegrees[j].pid;
409        phtable[to] = 1;
410        pmatptr = pmat + to*nparts;
411        for (nadd=0, k=0; k<myndegrees; k++) {
412          if (k == j)
413            continue;
414
415          l = myedegrees[k].pid;
416          if (pmatptr[l] == 0) {
417            if (ndoms[l] > maxndoms-1) {
418              phtable[to] = 0;
419              nadd = maxndoms;
420              break;
421            }
422            nadd++;
423          }
424        }
425        if (ndoms[to]+nadd > maxndoms)
426          phtable[to] = 0;
427      }
428
429      for (k=0; k<myndegrees; k++) {
430        to = myedegrees[k].pid;
431        if (!phtable[to])
432          continue;
433        if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from]) 
434          break;
435      }
436      if (k == myndegrees)
437        continue;  /* break out if you did not find a candidate */
438
439      for (j=k+1; j<myndegrees; j++) {
440        to = myedegrees[j].pid;
441        if (!phtable[to])
442          continue;
443        if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]) 
444          k = j;
445      }
446
447      to = myedegrees[k].pid;
448
449      if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->id < 0) 
450        continue;
451
452      /*=====================================================================
453      * If we got here, we can now move the vertex from 'from' to 'to'
454      *======================================================================*/
455      graph->mincut -= myedegrees[k].ed-myrinfo->id;
456
457      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));
458
459      /* Update pmat to reflect the move of 'i' */
460      pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
461      pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
462      if (pmat[from*nparts+to] == 0) {
463        ndoms[from]--;
464        if (ndoms[from]+1 == maxndoms)
465          maxndoms = ndoms[idxamax(nparts, ndoms)];
466      }
467      if (pmat[to*nparts+from] == 0) {
468        ndoms[to]--;
469        if (ndoms[to]+1 == maxndoms)
470          maxndoms = ndoms[idxamax(nparts, ndoms)];
471      }
472
473
474      /* Update where, weight, and ID/ED information of the vertex you moved */
475      where[i] = to;
476      INC_DEC(pwgts[to], pwgts[from], vwgt);
477      myrinfo->ed += myrinfo->id-myedegrees[k].ed;
478      SWAP(myrinfo->id, myedegrees[k].ed, j);
479      if (myedegrees[k].ed == 0) 
480        myedegrees[k] = myedegrees[--myrinfo->ndegrees];
481      else
482        myedegrees[k].pid = from;
483
484      if (myrinfo->ed == 0)
485        BNDDelete(nbnd, bndind, bndptr, i);
486
487      /* Update the degrees of adjacent vertices */
488      for (j=xadj[i]; j<xadj[i+1]; j++) {
489        ii = adjncy[j];
490        me = where[ii];
491
492        myrinfo = graph->rinfo+ii;
493        if (myrinfo->edegrees == NULL) {
494          myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
495          ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
496        }
497        myedegrees = myrinfo->edegrees;
498
499        ASSERT(CheckRInfo(myrinfo));
500
501        oldgain = (myrinfo->ed-myrinfo->id);
502
503        if (me == from) {
504          INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
505
506          if (myrinfo->ed > 0 && bndptr[ii] == -1)
507            BNDInsert(nbnd, bndind, bndptr, ii);
508        }
509        else if (me == to) {
510          INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
511
512          if (myrinfo->ed == 0 && bndptr[ii] != -1)
513            BNDDelete(nbnd, bndind, bndptr, ii);
514        }
515
516        /* Remove contribution from the .ed of 'from' */
517        if (me != from) {
518          for (k=0; k<myrinfo->ndegrees; k++) {
519            if (myedegrees[k].pid == from) {
520              if (myedegrees[k].ed == adjwgt[j])
521                myedegrees[k] = myedegrees[--myrinfo->ndegrees];
522              else
523                myedegrees[k].ed -= adjwgt[j];
524              break;
525            }
526          }
527        }
528
529        /* Add contribution to the .ed of 'to' */
530        if (me != to) {
531          for (k=0; k<myrinfo->ndegrees; k++) {
532            if (myedegrees[k].pid == to) {
533              myedegrees[k].ed += adjwgt[j];
534              break;
535            }
536          }
537          if (k == myrinfo->ndegrees) {
538            myedegrees[myrinfo->ndegrees].pid = to;
539            myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
540          }
541        }
542
543        /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
544        if (me != from && me != to) {
545          pmat[me*nparts+from] -= adjwgt[j];
546          pmat[from*nparts+me] -= adjwgt[j];
547          if (pmat[me*nparts+from] == 0) {
548            ndoms[me]--;
549            if (ndoms[me]+1 == maxndoms)
550              maxndoms = ndoms[idxamax(nparts, ndoms)];
551          }
552          if (pmat[from*nparts+me] == 0) {
553            ndoms[from]--;
554            if (ndoms[from]+1 == maxndoms)
555              maxndoms = ndoms[idxamax(nparts, ndoms)];
556          }
557
558          if (pmat[me*nparts+to] == 0) {
559            ndoms[me]++;
560            if (ndoms[me] > maxndoms) {
561              printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
562              maxndoms = ndoms[me];
563            }
564          }
565          if (pmat[to*nparts+me] == 0) {
566            ndoms[to]++;
567            if (ndoms[to] > maxndoms) {
568              printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
569              maxndoms = ndoms[to];
570            }
571          }
572          pmat[me*nparts+to] += adjwgt[j];
573          pmat[to*nparts+me] += adjwgt[j];
574        }
575
576        /* Update the queue */
577        if (me == to || me == from) { 
578          gain = myrinfo->ed-myrinfo->id;
579          if (moved[ii] == 2) {
580            if (myrinfo->ed > 0)
581              PQueueUpdate(&queue, ii, oldgain, gain);
582            else {
583              PQueueDelete(&queue, ii, oldgain);
584              moved[ii] = -1;
585            }
586          }
587          else if (moved[ii] == -1 && myrinfo->ed > 0) {
588            PQueueInsert(&queue, ii, gain);
589            moved[ii] = 2;
590          }
591        } 
592
593        ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
594        ASSERT(CheckRInfo(myrinfo));
595      }
596      nmoves++;
597    }
598
599    graph->nbnd = nbnd;
600
601    IFSET(ctrl->dbglvl, DBG_REFINE,
602       printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, %d\n",
603               pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
604               1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut,idxsum(nparts, ndoms)));
605  }
606
607  PQueueFree(ctrl, &queue);
608
609  idxwspacefree(ctrl, nparts);
610  idxwspacefree(ctrl, nparts);
611  idxwspacefree(ctrl, nparts);
612  idxwspacefree(ctrl, nparts);
613  idxwspacefree(ctrl, nparts);
614  idxwspacefree(ctrl, nvtxs);
615  idxwspacefree(ctrl, nvtxs);
616
617}
618
619
620
621
622/*************************************************************************
623* This function computes the subdomain graph
624**************************************************************************/
625void PrintSubDomainGraph(GraphType *graph, int nparts, idxtype *where)
626{
627  int i, j, k, me, nvtxs, total, max;
628  idxtype *xadj, *adjncy, *adjwgt, *pmat;
629
630  nvtxs = graph->nvtxs;
631  xadj = graph->xadj;
632  adjncy = graph->adjncy;
633  adjwgt = graph->adjwgt;
634
635  pmat = idxsmalloc(nparts*nparts, 0, "ComputeSubDomainGraph: pmat");
636
637  for (i=0; i<nvtxs; i++) {
638    me = where[i];
639    for (j=xadj[i]; j<xadj[i+1]; j++) {
640      k = adjncy[j];
641      if (where[k] != me) 
642        pmat[me*nparts+where[k]] += adjwgt[j];
643    }
644  }
645
646  /* printf("Subdomain Info\n"); */
647  total = max = 0;
648  for (i=0; i<nparts; i++) {
649    for (k=0, j=0; j<nparts; j++) {
650      if (pmat[i*nparts+j] > 0)
651        k++;
652    }
653    total += k;
654
655    if (k > max)
656      max = k;
657/*
658    printf("%2d -> %2d  ", i, k);
659    for (j=0; j<nparts; j++) {
660      if (pmat[i*nparts+j] > 0)
661        printf("[%2d %4d] ", j, pmat[i*nparts+j]);
662    }
663    printf("\n");
664*/
665  }
666  printf("Total adjacent subdomains: %d, Max: %d\n", total, max);
667
668  free(pmat);
669}
670
671
672
673/*************************************************************************
674* This function computes the subdomain graph
675**************************************************************************/
676void ComputeSubDomainGraph(GraphType *graph, int nparts, idxtype *pmat, idxtype *ndoms)
677{
678  int i, j, k, me, nvtxs, ndegrees;
679  idxtype *xadj, *adjncy, *adjwgt, *where;
680  RInfoType *rinfo;
681  EDegreeType *edegrees;
682
683  nvtxs = graph->nvtxs;
684  xadj = graph->xadj;
685  adjncy = graph->adjncy;
686  adjwgt = graph->adjwgt;
687  where = graph->where;
688  rinfo = graph->rinfo;
689
690  idxset(nparts*nparts, 0, pmat);
691
692  for (i=0; i<nvtxs; i++) {
693    if (rinfo[i].ed > 0) {
694      me = where[i];
695      ndegrees = rinfo[i].ndegrees;
696      edegrees = rinfo[i].edegrees;
697
698      k = me*nparts;
699      for (j=0; j<ndegrees; j++) 
700        pmat[k+edegrees[j].pid] += edegrees[j].ed;
701    }
702  }
703
704  for (i=0; i<nparts; i++) {
705    ndoms[i] = 0;
706    for (j=0; j<nparts; j++) {
707      if (pmat[i*nparts+j] > 0)
708        ndoms[i]++;
709    }
710  }
711
712}
713
714
715
716
717
718/*************************************************************************
719* This function computes the subdomain graph
720**************************************************************************/
721void EliminateSubDomainEdges(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts)
722{
723  int i, ii, j, k, me, other, nvtxs, total, max, avg, totalout, nind, ncand, ncand2, target, target2, nadd;
724  int min, move, cpwgt, tvwgt;
725  idxtype *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt, *pmat, *ndoms, *mypmat, *otherpmat, *ind;
726  KeyValueType *cand, *cand2;
727
728  nvtxs = graph->nvtxs;
729  xadj = graph->xadj;
730  adjncy = graph->adjncy;
731  vwgt = graph->vwgt;
732  adjwgt = graph->adjwgt;
733
734  where = graph->where;
735  pwgts = graph->pwgts;  /* We assume that this is properly initialized */
736
737  maxpwgt = idxwspacemalloc(ctrl, nparts);
738  ndoms = idxwspacemalloc(ctrl, nparts);
739  otherpmat = idxwspacemalloc(ctrl, nparts);
740  ind = idxwspacemalloc(ctrl, nvtxs);
741  pmat = ctrl->wspace.pmat;
742
743  cand = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
744  cand2 = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
745
746  /* Compute the pmat matrix and ndoms */
747  ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
748
749
750  /* Compute the maximum allowed weight for each domain */
751  tvwgt = idxsum(nparts, pwgts);
752  for (i=0; i<nparts; i++)
753    maxpwgt[i] = 1.25*tpwgts[i]*tvwgt;
754
755
756  /* Get into the loop eliminating subdomain connections */
757  for (;;) {
758    total = idxsum(nparts, ndoms);
759    avg = total/nparts;
760    max = ndoms[idxamax(nparts, ndoms)];
761
762    /* printf("Adjacent Subdomain Stats: Total: %3d, Max: %3d, Avg: %3d [%5d]\n", total, max, avg, idxsum(nparts*nparts, pmat)); */
763
764    if (max < 1.4*avg)
765      break;
766
767    me = idxamax(nparts, ndoms);
768    mypmat = pmat + me*nparts;
769    totalout = idxsum(nparts, mypmat);
770
771    /*printf("Me: %d, TotalOut: %d,\n", me, totalout);*/
772
773    /* Sort the connections according to their cut */
774    for (ncand2=0, i=0; i<nparts; i++) {
775      if (mypmat[i] > 0) {
776        cand2[ncand2].key = mypmat[i];
777        cand2[ncand2++].val = i;
778      }
779    }
780    ikeysort(ncand2, cand2);
781
782    move = 0;
783    for (min=0; min<ncand2; min++) {
784      if (cand2[min].key > totalout/(2*ndoms[me])) 
785        break;
786
787      other = cand2[min].val;
788
789      /*printf("\tMinOut: %d to %d\n", mypmat[other], other);*/
790
791      idxset(nparts, 0, otherpmat);
792
793      /* Go and find the vertices in 'other' that are connected in 'me' */
794      for (nind=0, i=0; i<nvtxs; i++) {
795        if (where[i] == other) {
796          for (j=xadj[i]; j<xadj[i+1]; j++) {
797            if (where[adjncy[j]] == me) {
798              ind[nind++] = i;
799              break;
800            }
801          }
802        }
803      }
804
805      /* Go and construct the otherpmat to see where these nind vertices are connected to */
806      for (cpwgt=0, ii=0; ii<nind; ii++) {
807        i = ind[ii];
808        cpwgt += vwgt[i];
809
810        for (j=xadj[i]; j<xadj[i+1]; j++) 
811          otherpmat[where[adjncy[j]]] += adjwgt[j];
812      }
813      otherpmat[other] = 0;
814
815      for (ncand=0, i=0; i<nparts; i++) {
816        if (otherpmat[i] > 0) {
817          cand[ncand].key = -otherpmat[i];
818          cand[ncand++].val = i;
819        }
820      }
821      ikeysort(ncand, cand);
822
823      /*
824       * Go through and the select the first domain that is common with 'me', and
825       * does not increase the ndoms[target] higher than my ndoms, subject to the
826       * maxpwgt constraint. Traversal is done from the mostly connected to the least.
827       */
828      target = target2 = -1;
829      for (i=0; i<ncand; i++) {
830        k = cand[i].val;
831
832        if (mypmat[k] > 0) {
833          if (pwgts[k] + cpwgt > maxpwgt[k])  /* Check if balance will go off */
834            continue;
835
836          for (j=0; j<nparts; j++) {
837            if (otherpmat[j] > 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0)
838              break;
839          }
840          if (j == nparts) { /* No bad second level effects */
841            for (nadd=0, j=0; j<nparts; j++) {
842              if (otherpmat[j] > 0 && pmat[nparts*k+j] == 0)
843                nadd++;
844            }
845
846            /*printf("\t\tto=%d, nadd=%d, %d\n", k, nadd, ndoms[k]);*/
847            if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) {
848              target2 = k;
849            }
850            if (nadd == 0) {
851              target = k;
852              break;
853            }
854          }
855        }
856      }
857      if (target == -1 && target2 != -1)
858        target = target2;
859
860      if (target == -1) {
861        /* printf("\t\tCould not make the move\n");*/
862        continue;
863      }
864
865      /*printf("\t\tMoving to %d\n", target);*/
866
867      /* Update the partition weights */
868      INC_DEC(pwgts[target], pwgts[other], cpwgt);
869
870      MoveGroupMConn(ctrl, graph, ndoms, pmat, nparts, target, nind, ind);
871
872      move = 1;
873      break;
874    }
875
876    if (move == 0)
877      break;
878  }
879
880  idxwspacefree(ctrl, nparts);
881  idxwspacefree(ctrl, nparts);
882  idxwspacefree(ctrl, nparts);
883  idxwspacefree(ctrl, nvtxs);
884
885  GKfree(&cand, &cand2, LTERM);
886}
887
888
889/*************************************************************************
890* This function moves a collection of vertices and updates their rinfo
891**************************************************************************/
892void MoveGroupMConn(CtrlType *ctrl, GraphType *graph, idxtype *ndoms, idxtype *pmat,
893                    int nparts, int to, int nind, idxtype *ind)
894{
895  int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees; 
896  int from, me;
897  idxtype *xadj, *adjncy, *adjwgt;
898  idxtype *where, *bndptr, *bndind;
899  EDegreeType *myedegrees;
900  RInfoType *myrinfo;
901
902  nvtxs = graph->nvtxs;
903  xadj = graph->xadj;
904  adjncy = graph->adjncy;
905  adjwgt = graph->adjwgt;
906
907  where = graph->where;
908  bndptr = graph->bndptr;
909  bndind = graph->bndind;
910
911  nbnd = graph->nbnd;
912
913  for (iii=0; iii<nind; iii++) {
914    i = ind[iii];
915    from = where[i];
916
917    myrinfo = graph->rinfo+i;
918    if (myrinfo->edegrees == NULL) {
919      myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
920      ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
921      myrinfo->ndegrees = 0;
922    }
923    myedegrees = myrinfo->edegrees;
924
925    /* find the location of 'to' in myrinfo or create it if it is not there */
926    for (k=0; k<myrinfo->ndegrees; k++) {
927      if (myedegrees[k].pid == to)
928        break;
929    }
930    if (k == myrinfo->ndegrees) {
931      myedegrees[k].pid = to;
932      myedegrees[k].ed = 0;
933      myrinfo->ndegrees++;
934    }
935
936    graph->mincut -= myedegrees[k].ed-myrinfo->id;
937
938    /* Update pmat to reflect the move of 'i' */
939    pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
940    pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
941    if (pmat[from*nparts+to] == 0) 
942      ndoms[from]--;
943    if (pmat[to*nparts+from] == 0) 
944      ndoms[to]--;
945
946    /* Update where, weight, and ID/ED information of the vertex you moved */
947    where[i] = to;
948    myrinfo->ed += myrinfo->id-myedegrees[k].ed;
949    SWAP(myrinfo->id, myedegrees[k].ed, j);
950    if (myedegrees[k].ed == 0) 
951      myedegrees[k] = myedegrees[--myrinfo->ndegrees];
952    else
953      myedegrees[k].pid = from;
954
955    if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1)
956      BNDDelete(nbnd, bndind, bndptr, i);
957
958    /* Update the degrees of adjacent vertices */
959    for (j=xadj[i]; j<xadj[i+1]; j++) {
960      ii = adjncy[j];
961      me = where[ii];
962
963      myrinfo = graph->rinfo+ii;
964      if (myrinfo->edegrees == NULL) {
965        myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
966        ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
967      }
968      myedegrees = myrinfo->edegrees;
969
970      ASSERT(CheckRInfo(myrinfo));
971
972      if (me == from) {
973        INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
974
975        if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
976          BNDInsert(nbnd, bndind, bndptr, ii);
977      }
978      else if (me == to) {
979        INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
980
981        if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
982          BNDDelete(nbnd, bndind, bndptr, ii);
983      }
984
985      /* Remove contribution from the .ed of 'from' */
986      if (me != from) {
987        for (k=0; k<myrinfo->ndegrees; k++) {
988          if (myedegrees[k].pid == from) {
989            if (myedegrees[k].ed == adjwgt[j])
990              myedegrees[k] = myedegrees[--myrinfo->ndegrees];
991            else
992              myedegrees[k].ed -= adjwgt[j];
993            break;
994          }
995        }
996      }
997
998      /* Add contribution to the .ed of 'to' */
999      if (me != to) {
1000        for (k=0; k<myrinfo->ndegrees; k++) {
1001          if (myedegrees[k].pid == to) {
1002            myedegrees[k].ed += adjwgt[j];
1003            break;
1004          }
1005        }
1006        if (k == myrinfo->ndegrees) {
1007          myedegrees[myrinfo->ndegrees].pid = to;
1008          myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
1009        }
1010      }
1011
1012      /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
1013      if (me != from && me != to) {
1014        pmat[me*nparts+from] -= adjwgt[j];
1015        pmat[from*nparts+me] -= adjwgt[j];
1016        if (pmat[me*nparts+from] == 0) 
1017          ndoms[me]--;
1018        if (pmat[from*nparts+me] == 0) 
1019          ndoms[from]--;
1020
1021        if (pmat[me*nparts+to] == 0) 
1022          ndoms[me]++;
1023        if (pmat[to*nparts+me] == 0) 
1024          ndoms[to]++;
1025
1026        pmat[me*nparts+to] += adjwgt[j];
1027        pmat[to*nparts+me] += adjwgt[j];
1028      }
1029
1030      ASSERT(CheckRInfo(myrinfo));
1031    }
1032
1033    ASSERT(CheckRInfo(graph->rinfo+i));
1034  }
1035
1036  graph->nbnd = nbnd;
1037
1038}
1039
1040
1041
1042
1043/*************************************************************************
1044* This function finds all the connected components induced by the
1045* partitioning vector in wgraph->where and tries to push them around to
1046* remove some of them
1047**************************************************************************/
1048void EliminateComponents(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
1049{
1050  int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, other, target, deltawgt;
1051  idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt;
1052  idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps;
1053
1054  nvtxs = graph->nvtxs;
1055  xadj = graph->xadj;
1056  adjncy = graph->adjncy;
1057  vwgt = graph->vwgt;
1058  adjwgt = graph->adjwgt;
1059
1060  where = graph->where;
1061  pwgts = graph->pwgts;
1062
1063  touched = idxset(nvtxs, 0, idxwspacemalloc(ctrl, nvtxs));
1064  cptr = idxwspacemalloc(ctrl, nvtxs);
1065  cind = idxwspacemalloc(ctrl, nvtxs);
1066  perm = idxwspacemalloc(ctrl, nvtxs);
1067  todo = idxwspacemalloc(ctrl, nvtxs);
1068  maxpwgt = idxwspacemalloc(ctrl, nparts);
1069  cpvec = idxwspacemalloc(ctrl, nparts);
1070  npcmps = idxset(nparts, 0, idxwspacemalloc(ctrl, nparts));
1071
1072  for (i=0; i<nvtxs; i++) 
1073    perm[i] = todo[i] = i;
1074
1075  /* Find the connected componends induced by the partition */
1076  ncmps = -1;
1077  first = last = 0;
1078  nleft = nvtxs;
1079  while (nleft > 0) {
1080    if (first == last) { /* Find another starting vertex */
1081      cptr[++ncmps] = first;
1082      ASSERT(touched[todo[0]] == 0);
1083      i = todo[0];
1084      cind[last++] = i;
1085      touched[i] = 1;
1086      me = where[i];
1087      npcmps[me]++;
1088    }
1089
1090    i = cind[first++];
1091    k = perm[i];
1092    j = todo[k] = todo[--nleft];
1093    perm[j] = k;
1094
1095    for (j=xadj[i]; j<xadj[i+1]; j++) {
1096      k = adjncy[j];
1097      if (where[k] == me && !touched[k]) {
1098        cind[last++] = k;
1099        touched[k] = 1;
1100      }
1101    }
1102  }
1103  cptr[++ncmps] = first;
1104
1105  /* printf("I found %d components, for this %d-way partition\n", ncmps, nparts); */
1106
1107  if (ncmps > nparts) { /* There are more components than processors */
1108    /* First determine the max allowed load imbalance */
1109    tvwgt = idxsum(nparts, pwgts);
1110    for (i=0; i<nparts; i++)
1111      maxpwgt[i] = ubfactor*tpwgts[i]*tvwgt;
1112
1113    deltawgt = 5;
1114
1115    for (i=0; i<ncmps; i++) {
1116      me = where[cind[cptr[i]]];  /* Get the domain of this component */
1117      if (npcmps[me] == 1)
1118        continue;  /* Skip it because it is contigous */
1119
1120      /*printf("Trying to move %d from %d\n", i, me); */
1121
1122      /* Determine the weight of the block to be moved and abort if too high */
1123      for (cwgt=0, j=cptr[i]; j<cptr[i+1]; j++) 
1124        cwgt += vwgt[cind[j]];
1125
1126      if (cwgt > .30*pwgts[me])
1127        continue;  /* Skip the component if it is over 30% of the weight */
1128
1129      /* Determine the connectivity */
1130      idxset(nparts, 0, cpvec);
1131      for (j=cptr[i]; j<cptr[i+1]; j++) {
1132        ii = cind[j];
1133        for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) 
1134          cpvec[where[adjncy[jj]]] += adjwgt[jj];
1135      }
1136      cpvec[me] = 0;
1137
1138      target = -1;
1139      for (j=0; j<nparts; j++) {
1140        if (cpvec[j] > 0 && (cwgt < deltawgt || pwgts[j] + cwgt < maxpwgt[j])) {
1141          if (target == -1 || cpvec[target] < cpvec[j])
1142            target = j;
1143        }
1144      }
1145
1146      /* printf("\tMoving it to %d [%d]\n", target, cpvec[target]);*/
1147
1148      if (target != -1) {
1149        /* Assign all the vertices of 'me' to 'target' and update data structures */
1150        INC_DEC(pwgts[target], pwgts[me], cwgt);
1151        npcmps[me]--;
1152
1153        MoveGroup(ctrl, graph, nparts, target, i, cptr, cind);
1154      }
1155    }
1156
1157  }
1158
1159  idxwspacefree(ctrl, nparts);
1160  idxwspacefree(ctrl, nparts);
1161  idxwspacefree(ctrl, nparts);
1162  idxwspacefree(ctrl, nvtxs);
1163  idxwspacefree(ctrl, nvtxs);
1164  idxwspacefree(ctrl, nvtxs);
1165  idxwspacefree(ctrl, nvtxs);
1166  idxwspacefree(ctrl, nvtxs);
1167
1168}
1169
1170
1171/*************************************************************************
1172* This function moves a collection of vertices and updates their rinfo
1173**************************************************************************/
1174void MoveGroup(CtrlType *ctrl, GraphType *graph, int nparts, int to, int gid, idxtype *ptr, idxtype *ind)
1175{
1176  int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees; 
1177  int from, me;
1178  idxtype *xadj, *adjncy, *adjwgt;
1179  idxtype *where, *bndptr, *bndind;
1180  EDegreeType *myedegrees;
1181  RInfoType *myrinfo;
1182
1183  nvtxs = graph->nvtxs;
1184  xadj = graph->xadj;
1185  adjncy = graph->adjncy;
1186  adjwgt = graph->adjwgt;
1187
1188  where = graph->where;
1189  bndptr = graph->bndptr;
1190  bndind = graph->bndind;
1191
1192  nbnd = graph->nbnd;
1193
1194  for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
1195    i = ind[iii];
1196    from = where[i];
1197
1198    myrinfo = graph->rinfo+i;
1199    if (myrinfo->edegrees == NULL) {
1200      myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
1201      ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
1202      myrinfo->ndegrees = 0;
1203    }
1204    myedegrees = myrinfo->edegrees;
1205
1206    /* find the location of 'to' in myrinfo or create it if it is not there */
1207    for (k=0; k<myrinfo->ndegrees; k++) {
1208      if (myedegrees[k].pid == to)
1209        break;
1210    }
1211    if (k == myrinfo->ndegrees) {
1212      myedegrees[k].pid = to;
1213      myedegrees[k].ed = 0;
1214      myrinfo->ndegrees++;
1215    }
1216
1217    graph->mincut -= myedegrees[k].ed-myrinfo->id;
1218
1219
1220    /* Update where, weight, and ID/ED information of the vertex you moved */
1221    where[i] = to;
1222    myrinfo->ed += myrinfo->id-myedegrees[k].ed;
1223    SWAP(myrinfo->id, myedegrees[k].ed, j);
1224    if (myedegrees[k].ed == 0) 
1225      myedegrees[k] = myedegrees[--myrinfo->ndegrees];
1226    else
1227      myedegrees[k].pid = from;
1228
1229    if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1)
1230      BNDDelete(nbnd, bndind, bndptr, i);
1231
1232    /* Update the degrees of adjacent vertices */
1233    for (j=xadj[i]; j<xadj[i+1]; j++) {
1234      ii = adjncy[j];
1235      me = where[ii];
1236
1237      myrinfo = graph->rinfo+ii;
1238      if (myrinfo->edegrees == NULL) {
1239        myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
1240        ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
1241      }
1242      myedegrees = myrinfo->edegrees;
1243
1244      ASSERT(CheckRInfo(myrinfo));
1245
1246      if (me == from) {
1247        INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
1248
1249        if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
1250          BNDInsert(nbnd, bndind, bndptr, ii);
1251      }
1252      else if (me == to) {
1253        INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
1254
1255        if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
1256          BNDDelete(nbnd, bndind, bndptr, ii);
1257      }
1258
1259      /* Remove contribution from the .ed of 'from' */
1260      if (me != from) {
1261        for (k=0; k<myrinfo->ndegrees; k++) {
1262          if (myedegrees[k].pid == from) {
1263            if (myedegrees[k].ed == adjwgt[j])
1264              myedegrees[k] = myedegrees[--myrinfo->ndegrees];
1265            else
1266              myedegrees[k].ed -= adjwgt[j];
1267            break;
1268          }
1269        }
1270      }
1271
1272      /* Add contribution to the .ed of 'to' */
1273      if (me != to) {
1274        for (k=0; k<myrinfo->ndegrees; k++) {
1275          if (myedegrees[k].pid == to) {
1276            myedegrees[k].ed += adjwgt[j];
1277            break;
1278          }
1279        }
1280        if (k == myrinfo->ndegrees) {
1281          myedegrees[myrinfo->ndegrees].pid = to;
1282          myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
1283        }
1284      }
1285
1286      ASSERT(CheckRInfo(myrinfo));
1287    }
1288
1289    ASSERT(CheckRInfo(graph->rinfo+i));
1290  }
1291
1292  graph->nbnd = nbnd;
1293
1294}
1295
Note: See TracBrowser for help on using the repository browser.