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