1 /*
2 * mutil.c
3 *
4 * This file contains various utility functions for the MOC portion of the
5 * code
6 *
7 * Started 2/15/98
8 * George
9 *
10 * $Id: mcutil.c 13901 2013-03-24 16:17:03Z karypis $
11 *
12 */
13
14 #include "metislib.h"
15
16
17 /*************************************************************************/
18 /*! This function compares two vectors x & y and returns true
19 if \forall i, x[i] <= y[i].
20 */
21 /**************************************************************************/
rvecle(idx_t n,real_t * x,real_t * y)22 int rvecle(idx_t n, real_t *x, real_t *y)
23 {
24 for (n--; n>=0; n--) {
25 if (x[n] > y[n])
26 return 0;
27 }
28
29 return 1;
30 }
31
32
33 /*************************************************************************/
34 /*! This function compares two vectors x & y and returns true
35 if \forall i, x[i] >= y[i].
36 */
37 /**************************************************************************/
rvecge(idx_t n,real_t * x,real_t * y)38 int rvecge(idx_t n, real_t *x, real_t *y)
39 {
40 for (n--; n>=0; n--) {
41 if (x[n] < y[n])
42 return 0;
43 }
44
45 return 1;
46 }
47
48
49 /*************************************************************************/
50 /*! This function compares vectors x1+x2 against y and returns true
51 if \forall i, x1[i]+x2[i] <= y[i].
52 */
53 /**************************************************************************/
rvecsumle(idx_t n,real_t * x1,real_t * x2,real_t * y)54 int rvecsumle(idx_t n, real_t *x1, real_t *x2, real_t *y)
55 {
56 for (n--; n>=0; n--) {
57 if (x1[n]+x2[n] > y[n])
58 return 0;
59 }
60
61 return 1;
62 }
63
64
65 /*************************************************************************/
66 /*! This function returns max_i(x[i]-y[i]) */
67 /**************************************************************************/
rvecmaxdiff(idx_t n,real_t * x,real_t * y)68 real_t rvecmaxdiff(idx_t n, real_t *x, real_t *y)
69 {
70 real_t max;
71
72 max = x[0]-y[0];
73
74 for (n--; n>0; n--) {
75 if (max < x[n]-y[n])
76 max = x[n]-y[n];
77 }
78
79 return max;
80 }
81
82
83 /*************************************************************************/
84 /*! This function returns true if \forall i, x[i] <= z[i]. */
85 /**************************************************************************/
ivecle(idx_t n,idx_t * x,idx_t * z)86 int ivecle(idx_t n, idx_t *x, idx_t *z)
87 {
88 for (n--; n>=0; n--) {
89 if (x[n] > z[n])
90 return 0;
91 }
92
93 return 1;
94 }
95
96
97 /*************************************************************************/
98 /*! This function returns true if \forall i, x[i] >= z[i]. */
99 /**************************************************************************/
ivecge(idx_t n,idx_t * x,idx_t * z)100 int ivecge(idx_t n, idx_t *x, idx_t *z)
101 {
102 for (n--; n>=0; n--) {
103 if (x[n] < z[n])
104 return 0;
105 }
106
107 return 1;
108 }
109
110
111 /*************************************************************************/
112 /*! This function returns true if \forall i, a*x[i]+y[i] <= z[i]. */
113 /**************************************************************************/
ivecaxpylez(idx_t n,idx_t a,idx_t * x,idx_t * y,idx_t * z)114 int ivecaxpylez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
115 {
116 for (n--; n>=0; n--) {
117 if (a*x[n]+y[n] > z[n])
118 return 0;
119 }
120
121 return 1;
122 }
123
124
125 /*************************************************************************/
126 /*! This function returns true if \forall i, a*x[i]+y[i] >= z[i]. */
127 /**************************************************************************/
ivecaxpygez(idx_t n,idx_t a,idx_t * x,idx_t * y,idx_t * z)128 int ivecaxpygez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
129 {
130 for (n--; n>=0; n--) {
131 if (a*x[n]+y[n] < z[n])
132 return 0;
133 }
134
135 return 1;
136 }
137
138
139 /*************************************************************************/
140 /*! This function checks if v+u2 provides a better balance in the weight
141 vector that v+u1 */
142 /*************************************************************************/
BetterVBalance(idx_t ncon,real_t * invtvwgt,idx_t * v_vwgt,idx_t * u1_vwgt,idx_t * u2_vwgt)143 int BetterVBalance(idx_t ncon, real_t *invtvwgt, idx_t *v_vwgt, idx_t *u1_vwgt,
144 idx_t *u2_vwgt)
145 {
146 idx_t i;
147 real_t sum1=0.0, sum2=0.0, diff1=0.0, diff2=0.0;
148
149 for (i=0; i<ncon; i++) {
150 sum1 += (v_vwgt[i]+u1_vwgt[i])*invtvwgt[i];
151 sum2 += (v_vwgt[i]+u2_vwgt[i])*invtvwgt[i];
152 }
153 sum1 = sum1/ncon;
154 sum2 = sum2/ncon;
155
156 for (i=0; i<ncon; i++) {
157 diff1 += rabs(sum1 - (v_vwgt[i]+u1_vwgt[i])*invtvwgt[i]);
158 diff2 += rabs(sum2 - (v_vwgt[i]+u2_vwgt[i])*invtvwgt[i]);
159 }
160
161 return (diff1 - diff2 >= 0);
162 }
163
164
165 /*************************************************************************/
166 /*! This function takes two ubfactor-centered load imbalance vectors x & y,
167 and returns true if y is better balanced than x. */
168 /*************************************************************************/
BetterBalance2Way(idx_t n,real_t * x,real_t * y)169 int BetterBalance2Way(idx_t n, real_t *x, real_t *y)
170 {
171 real_t nrm1=0.0, nrm2=0.0;
172
173 for (--n; n>=0; n--) {
174 if (x[n] > 0) nrm1 += x[n]*x[n];
175 if (y[n] > 0) nrm2 += y[n]*y[n];
176 }
177 return nrm2 < nrm1;
178 }
179
180
181 /*************************************************************************/
182 /*! Given a vertex and two weights, this function returns 1, if the second
183 partition will be more balanced than the first after the weighted
184 additional of that vertex.
185 The balance determination takes into account the ideal target weights
186 of the two partitions.
187 */
188 /*************************************************************************/
BetterBalanceKWay(idx_t ncon,idx_t * vwgt,real_t * ubvec,idx_t a1,idx_t * pt1,real_t * bm1,idx_t a2,idx_t * pt2,real_t * bm2)189 int BetterBalanceKWay(idx_t ncon, idx_t *vwgt, real_t *ubvec,
190 idx_t a1, idx_t *pt1, real_t *bm1,
191 idx_t a2, idx_t *pt2, real_t *bm2)
192 {
193 idx_t i;
194 real_t tmp, nrm1=0.0, nrm2=0.0, max1=0.0, max2=0.0;
195
196 for (i=0; i<ncon; i++) {
197 tmp = bm1[i]*(pt1[i]+a1*vwgt[i]) - ubvec[i];
198 //printf("BB: %d %+.4f ", (int)i, (float)tmp);
199 nrm1 += tmp*tmp;
200 max1 = (tmp > max1 ? tmp : max1);
201
202 tmp = bm2[i]*(pt2[i]+a2*vwgt[i]) - ubvec[i];
203 //printf("%+.4f ", (float)tmp);
204 nrm2 += tmp*tmp;
205 max2 = (tmp > max2 ? tmp : max2);
206
207 //printf("%4d %4d %4d %4d %4d %4d %4d %.2f\n",
208 // (int)vwgt[i],
209 // (int)a1, (int)pt1[i], (int)tpt1[i],
210 // (int)a2, (int)pt2[i], (int)tpt2[i], ubvec[i]);
211 }
212 //printf(" %.3f %.3f %.3f %.3f\n", (float)max1, (float)nrm1, (float)max2, (float)nrm2);
213
214 if (max2 < max1)
215 return 1;
216
217 if (max2 == max1 && nrm2 < nrm1)
218 return 1;
219
220 return 0;
221 }
222
223
224 /*************************************************************************/
225 /*! Computes the maximum load imbalance of a partitioning solution over
226 all the constraints. */
227 /**************************************************************************/
ComputeLoadImbalance(graph_t * graph,idx_t nparts,real_t * pijbm)228 real_t ComputeLoadImbalance(graph_t *graph, idx_t nparts, real_t *pijbm)
229 {
230 idx_t i, j, ncon, *pwgts;
231 real_t max, cur;
232
233 ncon = graph->ncon;
234 pwgts = graph->pwgts;
235
236 max = 1.0;
237 for (i=0; i<ncon; i++) {
238 for (j=0; j<nparts; j++) {
239 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i];
240 if (cur > max)
241 max = cur;
242 }
243 }
244
245 return max;
246 }
247
248
249 /*************************************************************************/
250 /*! Computes the maximum load imbalance difference of a partitioning
251 solution over all the constraints.
252 The difference is defined with respect to the allowed maximum
253 unbalance for the respective constraint.
254 */
255 /**************************************************************************/
ComputeLoadImbalanceDiff(graph_t * graph,idx_t nparts,real_t * pijbm,real_t * ubvec)256 real_t ComputeLoadImbalanceDiff(graph_t *graph, idx_t nparts, real_t *pijbm,
257 real_t *ubvec)
258 {
259 idx_t i, j, ncon, *pwgts;
260 real_t max, cur;
261
262 ncon = graph->ncon;
263 pwgts = graph->pwgts;
264
265 max = -1.0;
266 for (i=0; i<ncon; i++) {
267 for (j=0; j<nparts; j++) {
268 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i] - ubvec[i];
269 if (cur > max)
270 max = cur;
271 }
272 }
273
274 return max;
275 }
276
277
278 /*************************************************************************/
279 /*! Computes the difference between load imbalance of each constraint across
280 the partitions minus the desired upper bound on the load imabalnce.
281 It also returns the maximum load imbalance across the partitions &
282 constraints. */
283 /**************************************************************************/
ComputeLoadImbalanceDiffVec(graph_t * graph,idx_t nparts,real_t * pijbm,real_t * ubfactors,real_t * diffvec)284 real_t ComputeLoadImbalanceDiffVec(graph_t *graph, idx_t nparts, real_t *pijbm,
285 real_t *ubfactors, real_t *diffvec)
286 {
287 idx_t i, j, ncon, *pwgts;
288 real_t cur, max;
289
290 ncon = graph->ncon;
291 pwgts = graph->pwgts;
292
293 for (max=-1.0, i=0; i<ncon; i++) {
294 diffvec[i] = pwgts[i]*pijbm[i] - ubfactors[i];
295 for (j=1; j<nparts; j++) {
296 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i] - ubfactors[i];
297 if (cur > diffvec[i])
298 diffvec[i] = cur;
299 }
300 if (max < diffvec[i])
301 max = diffvec[i];
302 }
303
304 return max;
305 }
306
307
308 /*************************************************************************/
309 /*! Computes the load imbalance of each constraint across the partitions. */
310 /**************************************************************************/
ComputeLoadImbalanceVec(graph_t * graph,idx_t nparts,real_t * pijbm,real_t * lbvec)311 void ComputeLoadImbalanceVec(graph_t *graph, idx_t nparts, real_t *pijbm,
312 real_t *lbvec)
313 {
314 idx_t i, j, ncon, *pwgts;
315 real_t cur;
316
317 ncon = graph->ncon;
318 pwgts = graph->pwgts;
319
320 for (i=0; i<ncon; i++) {
321 lbvec[i] = pwgts[i]*pijbm[i];
322 for (j=1; j<nparts; j++) {
323 cur = pwgts[j*ncon+i]*pijbm[j*ncon+i];
324 if (cur > lbvec[i])
325 lbvec[i] = cur;
326 }
327 }
328 }
329
330
331