1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * debug.c
5 *
6 * This file contains code that performs self debuging
7 *
8 * Started 7/24/97
9 * George
10 *
11 */
12
13 #include "metislib.h"
14
15
16
17 /*************************************************************************/
18 /*! This function computes the total edgecut
19 */
20 /*************************************************************************/
ComputeCut(graph_t * graph,idx_t * where)21 idx_t ComputeCut(graph_t *graph, idx_t *where)
22 {
23 idx_t i, j, cut;
24
25 if (graph->adjwgt == NULL) {
26 for (cut=0, i=0; i<graph->nvtxs; i++) {
27 for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
28 if (where[i] != where[graph->adjncy[j]])
29 cut++;
30 }
31 }
32 else {
33 for (cut=0, i=0; i<graph->nvtxs; i++) {
34 for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
35 if (where[i] != where[graph->adjncy[j]])
36 cut += graph->adjwgt[j];
37 }
38 }
39
40 return cut/2;
41 }
42
43
44 /*************************************************************************/
45 /*! This function computes the total volume
46 */
47 /*************************************************************************/
ComputeVolume(graph_t * graph,idx_t * where)48 idx_t ComputeVolume(graph_t *graph, idx_t *where)
49 {
50 idx_t i, j, k, me, nvtxs, nparts, totalv;
51 idx_t *xadj, *adjncy, *vsize, *marker;
52
53
54 nvtxs = graph->nvtxs;
55 xadj = graph->xadj;
56 adjncy = graph->adjncy;
57 vsize = graph->vsize;
58
59 nparts = where[iargmax(nvtxs, where)]+1;
60 marker = ismalloc(nparts, -1, "ComputeVolume: marker");
61
62 totalv = 0;
63
64 for (i=0; i<nvtxs; i++) {
65 marker[where[i]] = i;
66 for (j=xadj[i]; j<xadj[i+1]; j++) {
67 k = where[adjncy[j]];
68 if (marker[k] != i) {
69 marker[k] = i;
70 totalv += (vsize ? vsize[i] : 1);
71 }
72 }
73 }
74
75 gk_free((void **)&marker, LTERM);
76
77 return totalv;
78 }
79
80
81 /*************************************************************************/
82 /*! This function computes the cut given the graph and a where vector
83 */
84 /*************************************************************************/
ComputeMaxCut(graph_t * graph,idx_t nparts,idx_t * where)85 idx_t ComputeMaxCut(graph_t *graph, idx_t nparts, idx_t *where)
86 {
87 idx_t i, j, maxcut;
88 idx_t *cuts;
89
90 cuts = ismalloc(nparts, 0, "ComputeMaxCut: cuts");
91
92 if (graph->adjwgt == NULL) {
93 for (i=0; i<graph->nvtxs; i++) {
94 for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
95 if (where[i] != where[graph->adjncy[j]])
96 cuts[where[i]]++;
97 }
98 }
99 else {
100 for (i=0; i<graph->nvtxs; i++) {
101 for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
102 if (where[i] != where[graph->adjncy[j]])
103 cuts[where[i]] += graph->adjwgt[j];
104 }
105 }
106
107 maxcut = cuts[iargmax(nparts, cuts)];
108
109 printf("%zu => %"PRIDX"\n", iargmax(nparts, cuts), maxcut);
110
111 gk_free((void **)&cuts, LTERM);
112
113 return maxcut;
114 }
115
116
117 /*************************************************************************/
118 /*! This function checks whether or not the boundary information is correct
119 */
120 /*************************************************************************/
CheckBnd(graph_t * graph)121 idx_t CheckBnd(graph_t *graph)
122 {
123 idx_t i, j, nvtxs, nbnd;
124 idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
125
126 nvtxs = graph->nvtxs;
127 xadj = graph->xadj;
128 adjncy = graph->adjncy;
129 where = graph->where;
130 bndptr = graph->bndptr;
131 bndind = graph->bndind;
132
133 for (nbnd=0, i=0; i<nvtxs; i++) {
134 if (xadj[i+1]-xadj[i] == 0)
135 nbnd++; /* Islands are considered to be boundary vertices */
136
137 for (j=xadj[i]; j<xadj[i+1]; j++) {
138 if (where[i] != where[adjncy[j]]) {
139 nbnd++;
140 ASSERT(bndptr[i] != -1);
141 ASSERT(bndind[bndptr[i]] == i);
142 break;
143 }
144 }
145 }
146
147 ASSERTP(nbnd == graph->nbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, graph->nbnd));
148
149 return 1;
150 }
151
152
153
154 /*************************************************************************/
155 /*! This function checks whether or not the boundary information is correct
156 */
157 /*************************************************************************/
CheckBnd2(graph_t * graph)158 idx_t CheckBnd2(graph_t *graph)
159 {
160 idx_t i, j, nvtxs, nbnd, id, ed;
161 idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
162
163 nvtxs = graph->nvtxs;
164 xadj = graph->xadj;
165 adjncy = graph->adjncy;
166 where = graph->where;
167 bndptr = graph->bndptr;
168 bndind = graph->bndind;
169
170 for (nbnd=0, i=0; i<nvtxs; i++) {
171 id = ed = 0;
172 for (j=xadj[i]; j<xadj[i+1]; j++) {
173 if (where[i] != where[adjncy[j]])
174 ed += graph->adjwgt[j];
175 else
176 id += graph->adjwgt[j];
177 }
178 if (ed - id >= 0 && xadj[i] < xadj[i+1]) {
179 nbnd++;
180 ASSERTP(bndptr[i] != -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", i, id, ed));
181 ASSERT(bndind[bndptr[i]] == i);
182 }
183 }
184
185 ASSERTP(nbnd == graph->nbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, graph->nbnd));
186
187 return 1;
188 }
189
190
191 /*************************************************************************/
192 /*! This function checks whether or not the boundary information is correct
193 */
194 /*************************************************************************/
CheckNodeBnd(graph_t * graph,idx_t onbnd)195 idx_t CheckNodeBnd(graph_t *graph, idx_t onbnd)
196 {
197 idx_t i, j, nvtxs, nbnd;
198 idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
199
200 nvtxs = graph->nvtxs;
201 xadj = graph->xadj;
202 adjncy = graph->adjncy;
203 where = graph->where;
204 bndptr = graph->bndptr;
205 bndind = graph->bndind;
206
207 for (nbnd=0, i=0; i<nvtxs; i++) {
208 if (where[i] == 2)
209 nbnd++;
210 }
211
212 ASSERTP(nbnd == onbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, onbnd));
213
214 for (i=0; i<nvtxs; i++) {
215 if (where[i] != 2) {
216 ASSERTP(bndptr[i] == -1, ("%"PRIDX" %"PRIDX"\n", i, bndptr[i]));
217 }
218 else {
219 ASSERTP(bndptr[i] != -1, ("%"PRIDX" %"PRIDX"\n", i, bndptr[i]));
220 }
221 }
222
223 return 1;
224 }
225
226
227
228 /*************************************************************************/
229 /*! This function checks whether or not the rinfo of a vertex is consistent
230 */
231 /*************************************************************************/
CheckRInfo(ctrl_t * ctrl,ckrinfo_t * rinfo)232 idx_t CheckRInfo(ctrl_t *ctrl, ckrinfo_t *rinfo)
233 {
234 idx_t i, j;
235 cnbr_t *nbrs;
236
237 nbrs = ctrl->cnbrpool + rinfo->inbr;
238
239 for (i=0; i<rinfo->nnbrs; i++) {
240 for (j=i+1; j<rinfo->nnbrs; j++)
241 ASSERTP(nbrs[i].pid != nbrs[j].pid,
242 ("%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n",
243 i, j, nbrs[i].pid, nbrs[j].pid));
244 }
245
246 return 1;
247 }
248
249
250
251 /*************************************************************************/
252 /*! This function checks the correctness of the NodeFM data structures
253 */
254 /*************************************************************************/
CheckNodePartitionParams(graph_t * graph)255 idx_t CheckNodePartitionParams(graph_t *graph)
256 {
257 idx_t i, j, k, l, nvtxs, me, other;
258 idx_t *xadj, *adjncy, *adjwgt, *vwgt, *where;
259 idx_t edegrees[2], pwgts[3];
260
261 nvtxs = graph->nvtxs;
262 xadj = graph->xadj;
263 vwgt = graph->vwgt;
264 adjncy = graph->adjncy;
265 adjwgt = graph->adjwgt;
266 where = graph->where;
267
268 /*------------------------------------------------------------
269 / Compute now the separator external degrees
270 /------------------------------------------------------------*/
271 pwgts[0] = pwgts[1] = pwgts[2] = 0;
272 for (i=0; i<nvtxs; i++) {
273 me = where[i];
274 pwgts[me] += vwgt[i];
275
276 if (me == 2) { /* If it is on the separator do some computations */
277 edegrees[0] = edegrees[1] = 0;
278
279 for (j=xadj[i]; j<xadj[i+1]; j++) {
280 other = where[adjncy[j]];
281 if (other != 2)
282 edegrees[other] += vwgt[adjncy[j]];
283 }
284 if (edegrees[0] != graph->nrinfo[i].edegrees[0] ||
285 edegrees[1] != graph->nrinfo[i].edegrees[1]) {
286 printf("Something wrong with edegrees: %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n",
287 i, edegrees[0], edegrees[1],
288 graph->nrinfo[i].edegrees[0], graph->nrinfo[i].edegrees[1]);
289 return 0;
290 }
291 }
292 }
293
294 if (pwgts[0] != graph->pwgts[0] ||
295 pwgts[1] != graph->pwgts[1] ||
296 pwgts[2] != graph->pwgts[2]) {
297 printf("Something wrong with part-weights: %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n", pwgts[0], pwgts[1], pwgts[2], graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]);
298 return 0;
299 }
300
301 return 1;
302 }
303
304
305 /*************************************************************************/
306 /*! This function checks if the separator is indeed a separator
307 */
308 /*************************************************************************/
IsSeparable(graph_t * graph)309 idx_t IsSeparable(graph_t *graph)
310 {
311 idx_t i, j, nvtxs, other;
312 idx_t *xadj, *adjncy, *where;
313
314 nvtxs = graph->nvtxs;
315 xadj = graph->xadj;
316 adjncy = graph->adjncy;
317 where = graph->where;
318
319 for (i=0; i<nvtxs; i++) {
320 if (where[i] == 2)
321 continue;
322 other = (where[i]+1)%2;
323 for (j=xadj[i]; j<xadj[i+1]; j++) {
324 ASSERTP(where[adjncy[j]] != other,
325 ("%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n",
326 i, where[i], adjncy[j], where[adjncy[j]], xadj[i+1]-xadj[i],
327 xadj[adjncy[j]+1]-xadj[adjncy[j]]));
328 }
329 }
330
331 return 1;
332 }
333
334
335 /*************************************************************************/
336 /*! This function recomputes the vrinfo fields and checks them against
337 those in the graph->vrinfo structure */
338 /*************************************************************************/
CheckKWayVolPartitionParams(ctrl_t * ctrl,graph_t * graph)339 void CheckKWayVolPartitionParams(ctrl_t *ctrl, graph_t *graph)
340 {
341 idx_t i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
342 idx_t *xadj, *vsize, *adjncy, *pwgts, *where, *bndind, *bndptr;
343 vkrinfo_t *rinfo, *myrinfo, *orinfo, tmprinfo;
344 vnbr_t *mynbrs, *onbrs, *tmpnbrs;
345
346 WCOREPUSH;
347
348 nvtxs = graph->nvtxs;
349 xadj = graph->xadj;
350 vsize = graph->vsize;
351 adjncy = graph->adjncy;
352 where = graph->where;
353 rinfo = graph->vkrinfo;
354
355 tmpnbrs = (vnbr_t *)wspacemalloc(ctrl, ctrl->nparts*sizeof(vnbr_t));
356
357 /*------------------------------------------------------------
358 / Compute now the iv/ev degrees
359 /------------------------------------------------------------*/
360 for (i=0; i<nvtxs; i++) {
361 me = where[i];
362
363 myrinfo = rinfo+i;
364 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
365
366 for (k=0; k<myrinfo->nnbrs; k++)
367 tmpnbrs[k] = mynbrs[k];
368
369 tmprinfo.nnbrs = myrinfo->nnbrs;
370 tmprinfo.nid = myrinfo->nid;
371 tmprinfo.ned = myrinfo->ned;
372
373 myrinfo = &tmprinfo;
374 mynbrs = tmpnbrs;
375
376 for (k=0; k<myrinfo->nnbrs; k++)
377 mynbrs[k].gv = 0;
378
379 for (j=xadj[i]; j<xadj[i+1]; j++) {
380 ii = adjncy[j];
381 other = where[ii];
382 orinfo = rinfo+ii;
383 onbrs = ctrl->vnbrpool + orinfo->inbr;
384
385 if (me == other) {
386 /* Find which domains 'i' is connected and 'ii' is not and update their gain */
387 for (k=0; k<myrinfo->nnbrs; k++) {
388 pid = mynbrs[k].pid;
389 for (kk=0; kk<orinfo->nnbrs; kk++) {
390 if (onbrs[kk].pid == pid)
391 break;
392 }
393 if (kk == orinfo->nnbrs)
394 mynbrs[k].gv -= vsize[ii];
395 }
396 }
397 else {
398 /* Find the orinfo[me].ed and see if I'm the only connection */
399 for (k=0; k<orinfo->nnbrs; k++) {
400 if (onbrs[k].pid == me)
401 break;
402 }
403
404 if (onbrs[k].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
405 for (k=0; k<myrinfo->nnbrs; k++) {
406 if (mynbrs[k].pid == other) {
407 mynbrs[k].gv += vsize[ii];
408 break;
409 }
410 }
411
412 /* Increase the gains for all the common domains between 'i' and 'ii' */
413 for (k=0; k<myrinfo->nnbrs; k++) {
414 if ((pid = mynbrs[k].pid) == other)
415 continue;
416 for (kk=0; kk<orinfo->nnbrs; kk++) {
417 if (onbrs[kk].pid == pid) {
418 mynbrs[k].gv += vsize[ii];
419 break;
420 }
421 }
422 }
423
424 }
425 else {
426 /* Find which domains 'i' is connected and 'ii' is not and update their gain */
427 for (k=0; k<myrinfo->nnbrs; k++) {
428 if ((pid = mynbrs[k].pid) == other)
429 continue;
430 for (kk=0; kk<orinfo->nnbrs; kk++) {
431 if (onbrs[kk].pid == pid)
432 break;
433 }
434 if (kk == orinfo->nnbrs)
435 mynbrs[k].gv -= vsize[ii];
436 }
437 }
438 }
439 }
440
441 myrinfo = rinfo+i;
442 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
443
444 for (k=0; k<myrinfo->nnbrs; k++) {
445 pid = mynbrs[k].pid;
446 for (kk=0; kk<tmprinfo.nnbrs; kk++) {
447 if (tmpnbrs[kk].pid == pid) {
448 if (tmpnbrs[kk].gv != mynbrs[k].gv)
449 printf("[%8"PRIDX" %8"PRIDX" %8"PRIDX" %+8"PRIDX" %+8"PRIDX"]\n",
450 i, where[i], pid, mynbrs[k].gv, tmpnbrs[kk].gv);
451 break;
452 }
453 }
454 }
455
456 }
457
458 WCOREPOP;
459 }
460
461
462