source: inundation/pymetis/metis-4.0/Lib/balance.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: 9.0 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * balance.c
5 *
6 * This file contains code that is used to forcefully balance either
7 * bisections or k-sections
8 *
9 * Started 7/29/97
10 * George
11 *
12 * $Id: balance.c,v 1.1 1998/11/27 17:59:10 karypis Exp $
13 *
14 */
15
16#include <metis.h>
17
18/*************************************************************************
19* This function is the entry point of the bisection balancing algorithms.
20**************************************************************************/
21void Balance2Way(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
22{
23  int i, j, nvtxs, from, imax, gain, mindiff;
24  idxtype *id, *ed;
25
26  /* Return right away if the balance is OK */
27  mindiff = abs(tpwgts[0]-graph->pwgts[0]);
28  if (mindiff < 3*(graph->pwgts[0]+graph->pwgts[1])/graph->nvtxs)
29    return;
30  if (graph->pwgts[0] > tpwgts[0] && graph->pwgts[0] < (int)(ubfactor*tpwgts[0]))
31    return;
32  if (graph->pwgts[1] > tpwgts[1] && graph->pwgts[1] < (int)(ubfactor*tpwgts[1]))
33    return;
34
35  if (graph->nbnd > 0)
36    Bnd2WayBalance(ctrl, graph, tpwgts);
37  else
38    General2WayBalance(ctrl, graph, tpwgts);
39
40}
41
42
43
44/*************************************************************************
45* This function balances two partitions by moving boundary nodes
46* from the domain that is overweight to the one that is underweight.
47**************************************************************************/
48void Bnd2WayBalance(CtrlType *ctrl, GraphType *graph, int *tpwgts)
49{
50  int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
51  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
52  idxtype *moved, *perm;
53  PQueueType parts;
54  int higain, oldgain, mincut, mindiff;
55
56  nvtxs = graph->nvtxs;
57  xadj = graph->xadj;
58  vwgt = graph->vwgt;
59  adjncy = graph->adjncy;
60  adjwgt = graph->adjwgt;
61  where = graph->where;
62  id = graph->id;
63  ed = graph->ed;
64  pwgts = graph->pwgts;
65  bndptr = graph->bndptr;
66  bndind = graph->bndind;
67
68  moved = idxwspacemalloc(ctrl, nvtxs);
69  perm = idxwspacemalloc(ctrl, nvtxs);
70
71  /* Determine from which domain you will be moving data */
72  mindiff = abs(tpwgts[0]-pwgts[0]);
73  from = (pwgts[0] < tpwgts[0] ? 1 : 0);
74  to = (from+1)%2;
75
76  IFSET(ctrl->dbglvl, DBG_REFINE, 
77     printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d [B]\n",
78             pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
79
80  tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];
81  PQueueInit(ctrl, &parts, nvtxs, tmp);
82
83  idxset(nvtxs, -1, moved);
84
85  ASSERT(ComputeCut(graph, where) == graph->mincut);
86  ASSERT(CheckBnd(graph));
87
88  /* Insert the boundary nodes of the proper partition whose size is OK in the priority queue */
89  nbnd = graph->nbnd;
90  RandomPermute(nbnd, perm, 1);
91  for (ii=0; ii<nbnd; ii++) {
92    i = perm[ii];
93    ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
94    ASSERT(bndptr[bndind[i]] != -1);
95    if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)
96      PQueueInsert(&parts, bndind[i], ed[bndind[i]]-id[bndind[i]]);
97  }
98
99  mincut = graph->mincut;
100  for (nswaps=0; nswaps<nvtxs; nswaps++) {
101    if ((higain = PQueueGetMax(&parts)) == -1)
102      break;
103    ASSERT(bndptr[higain] != -1);
104
105    if (pwgts[to]+vwgt[higain] > tpwgts[to])
106      break;
107
108    mincut -= (ed[higain]-id[higain]);
109    INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
110
111    where[higain] = to;
112    moved[higain] = nswaps;
113
114    IFSET(ctrl->dbglvl, DBG_MOVEINFO, 
115      printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
116
117    /**************************************************************
118    * Update the id[i]/ed[i] values of the affected nodes
119    ***************************************************************/
120    SWAP(id[higain], ed[higain], tmp);
121    if (ed[higain] == 0 && xadj[higain] < xadj[higain+1]) 
122      BNDDelete(nbnd, bndind,  bndptr, higain);
123
124    for (j=xadj[higain]; j<xadj[higain+1]; j++) {
125      k = adjncy[j];
126      oldgain = ed[k]-id[k];
127
128      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
129      INC_DEC(id[k], ed[k], kwgt);
130
131      /* Update its boundary information and queue position */
132      if (bndptr[k] != -1) { /* If k was a boundary vertex */
133        if (ed[k] == 0) { /* Not a boundary vertex any more */
134          BNDDelete(nbnd, bndind, bndptr, k);
135          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)  /* Remove it if in the queues */
136            PQueueDelete(&parts, k, oldgain);
137        }
138        else { /* If it has not been moved, update its position in the queue */
139          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
140            PQueueUpdate(&parts, k, oldgain, ed[k]-id[k]);
141        }
142      }
143      else {
144        if (ed[k] > 0) {  /* It will now become a boundary vertex */
145          BNDInsert(nbnd, bndind, bndptr, k);
146          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff) 
147            PQueueInsert(&parts, k, ed[k]-id[k]);
148        }
149      }
150    }
151  }
152
153  IFSET(ctrl->dbglvl, DBG_REFINE, 
154    printf("\tMinimum cut: %6d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, pwgts[0], pwgts[1], nbnd));
155
156  graph->mincut = mincut;
157  graph->nbnd = nbnd;
158
159  PQueueFree(ctrl, &parts);
160
161  idxwspacefree(ctrl, nvtxs);
162  idxwspacefree(ctrl, nvtxs);
163}
164
165
166/*************************************************************************
167* This function balances two partitions by moving the highest gain
168* (including negative gain) vertices to the other domain.
169* It is used only when tha unbalance is due to non contigous
170* subdomains. That is, the are no boundary vertices.
171* It moves vertices from the domain that is overweight to the one that
172* is underweight.
173**************************************************************************/
174void General2WayBalance(CtrlType *ctrl, GraphType *graph, int *tpwgts)
175{
176  int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
177  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
178  idxtype *moved, *perm;
179  PQueueType parts;
180  int higain, oldgain, mincut, mindiff;
181
182  nvtxs = graph->nvtxs;
183  xadj = graph->xadj;
184  vwgt = graph->vwgt;
185  adjncy = graph->adjncy;
186  adjwgt = graph->adjwgt;
187  where = graph->where;
188  id = graph->id;
189  ed = graph->ed;
190  pwgts = graph->pwgts;
191  bndptr = graph->bndptr;
192  bndind = graph->bndind;
193
194  moved = idxwspacemalloc(ctrl, nvtxs);
195  perm = idxwspacemalloc(ctrl, nvtxs);
196
197  /* Determine from which domain you will be moving data */
198  mindiff = abs(tpwgts[0]-pwgts[0]);
199  from = (pwgts[0] < tpwgts[0] ? 1 : 0);
200  to = (from+1)%2;
201
202  IFSET(ctrl->dbglvl, DBG_REFINE, 
203     printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d [B]\n",
204             pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
205
206  tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];
207  PQueueInit(ctrl, &parts, nvtxs, tmp);
208
209  idxset(nvtxs, -1, moved);
210
211  ASSERT(ComputeCut(graph, where) == graph->mincut);
212  ASSERT(CheckBnd(graph));
213
214  /* Insert the nodes of the proper partition whose size is OK in the priority queue */
215  RandomPermute(nvtxs, perm, 1);
216  for (ii=0; ii<nvtxs; ii++) {
217    i = perm[ii];
218    if (where[i] == from && vwgt[i] <= mindiff)
219      PQueueInsert(&parts, i, ed[i]-id[i]);
220  }
221
222  mincut = graph->mincut;
223  nbnd = graph->nbnd;
224  for (nswaps=0; nswaps<nvtxs; nswaps++) {
225    if ((higain = PQueueGetMax(&parts)) == -1)
226      break;
227
228    if (pwgts[to]+vwgt[higain] > tpwgts[to])
229      break;
230
231    mincut -= (ed[higain]-id[higain]);
232    INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
233
234    where[higain] = to;
235    moved[higain] = nswaps;
236
237    IFSET(ctrl->dbglvl, DBG_MOVEINFO, 
238      printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
239
240    /**************************************************************
241    * Update the id[i]/ed[i] values of the affected nodes
242    ***************************************************************/
243    SWAP(id[higain], ed[higain], tmp);
244    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1]) 
245      BNDDelete(nbnd, bndind,  bndptr, higain);
246    if (ed[higain] > 0 && bndptr[higain] == -1)
247      BNDInsert(nbnd, bndind,  bndptr, higain);
248
249    for (j=xadj[higain]; j<xadj[higain+1]; j++) {
250      k = adjncy[j];
251      oldgain = ed[k]-id[k];
252
253      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
254      INC_DEC(id[k], ed[k], kwgt);
255
256      /* Update the queue position */
257      if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
258        PQueueUpdate(&parts, k, oldgain, ed[k]-id[k]);
259
260      /* Update its boundary information */
261      if (ed[k] == 0 && bndptr[k] != -1) 
262        BNDDelete(nbnd, bndind, bndptr, k);
263      else if (ed[k] > 0 && bndptr[k] == -1) 
264        BNDInsert(nbnd, bndind, bndptr, k);
265    }
266  }
267
268  IFSET(ctrl->dbglvl, DBG_REFINE, 
269    printf("\tMinimum cut: %6d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, pwgts[0], pwgts[1], nbnd));
270
271  graph->mincut = mincut;
272  graph->nbnd = nbnd;
273
274  PQueueFree(ctrl, &parts);
275
276  idxwspacefree(ctrl, nvtxs);
277  idxwspacefree(ctrl, nvtxs);
278}
Note: See TracBrowser for help on using the repository browser.