debug.c
Go to the documentation of this file.
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 /*************************************************************************/
20 /*************************************************************************/
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 /*************************************************************************/
47 /*************************************************************************/
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 /*************************************************************************/
84 /*************************************************************************/
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 /*************************************************************************/
120 /*************************************************************************/
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 /*************************************************************************/
157 /*************************************************************************/
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 /*************************************************************************/
194 /*************************************************************************/
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 /*************************************************************************/
231 /*************************************************************************/
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 /*************************************************************************/
254 /*************************************************************************/
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 /*************************************************************************/
308 /*************************************************************************/
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 /*************************************************************************/
338 /*************************************************************************/
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 
idx_t CheckNodeBnd(graph_t *graph, idx_t onbnd)
Definition: debug.c:195
idx_t idx_t idx_t idx_t * vwgt
idx_t * bndind
idx_t * xadj
vnbr_t * vnbrpool
idx_t * pwgts
idx_t * adjwgt
#define ismalloc
Definition: gklib_rename.h:68
idx_t * bndptr
idx_t IsSeparable(graph_t *graph)
Definition: debug.c:309
#define ASSERTP(expr, msg)
Definition: gk_macros.h:131
idx_t idx_t * xadj
idx_t * where
idx_t pid
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
#define WCOREPUSH
idx_t nvtxs
#define iargmax
Definition: gklib_rename.h:23
idx_t * vsize
NonlinearFactorGraph graph
nrinfo_t * nrinfo
static const Similarity3 id
idx_t idx_t idx_t idx_t idx_t * vsize
#define PRIDX
#define ASSERT(expression)
Definition: ccolamd.c:872
idx_t CheckNodePartitionParams(graph_t *graph)
Definition: debug.c:255
static const Line3 l(Rot3(), 1, 1)
idx_t edegrees[2]
idx_t ComputeCut(graph_t *graph, idx_t *where)
Definition: debug.c:21
int32_t idx_t
cnbr_t * cnbrpool
idx_t nparts
idx_t CheckBnd2(graph_t *graph)
Definition: debug.c:158
#define NULL
Definition: ccolamd.c:609
idx_t gv
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
void gk_free(void **ptr1,...)
Definition: memory.c:202
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
idx_t CheckBnd(graph_t *graph)
Definition: debug.c:121
idx_t idx_t idx_t * adjncy
idx_t ComputeVolume(graph_t *graph, idx_t *where)
Definition: debug.c:48
#define WCOREPOP
idx_t ComputeMaxCut(graph_t *graph, idx_t nparts, idx_t *where)
Definition: debug.c:85
void CheckKWayVolPartitionParams(ctrl_t *ctrl, graph_t *graph)
Definition: debug.c:339
std::ptrdiff_t j
vkrinfo_t * vkrinfo
#define wspacemalloc
Definition: rename.h:253
#define LTERM
Definition: gk_defs.h:14
idx_t CheckRInfo(ctrl_t *ctrl, ckrinfo_t *rinfo)
Definition: debug.c:232
idx_t * vwgt


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:09