Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
balance.c
Go to the documentation of this file.
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 **************************************************************************/
21 void 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 **************************************************************************/
48 void 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 **************************************************************************/
174 void 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 }
#define idxwspacefree
Definition: rename.h:165
#define PQueueUpdate
Definition: rename.h:320
#define Bnd2WayBalance
Definition: rename.h:17
#define Balance2Way
Definition: rename.h:16
idxtype * pwgts
Definition: struct.h:176
idxtype * adjwgtsum
Definition: struct.h:168
#define DBG_REFINE
Definition: defs.h:157
int nbnd
Definition: struct.h:177
idxtype * ed
Definition: struct.h:181
idxtype * id
Definition: struct.h:181
#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
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
int idxtype
Definition: struct.h:19
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define General2WayBalance
Definition: rename.h:18
#define CheckBnd
Definition: rename.h:44
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define BNDDelete(nbnd, bndind, bndptr, vtx)
Definition: macros.h:109
idxtype * bndind
Definition: struct.h:178
#define idxamax
Definition: rename.h:393
idxtype * vwgt
Definition: struct.h:163
#define INC_DEC(a, b, val)
Definition: macros.h:39
#define PQueueGetMax
Definition: rename.h:322
#define PQueueInsert
Definition: rename.h:318
int nvtxs
Definition: struct.h:161
#define RandomPermute
Definition: rename.h:410
#define ASSERT(expr)
Definition: macros.h:130
#define SWAP(a, b, tmp)
Definition: macros.h:36
#define ComputeCut
Definition: rename.h:43
#define PQueueDelete
Definition: rename.h:319
#define PQueueFree
Definition: rename.h:317
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define PQueueInit
Definition: rename.h:315