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 | } |
---|