Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
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  * $Id: debug.c,v 1.1 1998/11/27 17:59:13 karypis Exp $
12  *
13  */
14 
15 #include <metis.h>
16 
17 /*************************************************************************
18 * This function computes the cut given the graph and a where vector
19 **************************************************************************/
21 {
22  int i, j, cut;
23 
24  if (graph->adjwgt == NULL) {
25  for (cut=0, i=0; i<graph->nvtxs; i++) {
26  for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
27  if (where[i] != where[graph->adjncy[j]])
28  cut++;
29  }
30  }
31  else {
32  for (cut=0, i=0; i<graph->nvtxs; i++) {
33  for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
34  if (where[i] != where[graph->adjncy[j]])
35  cut += graph->adjwgt[j];
36  }
37  }
38 
39  return cut/2;
40 }
41 
42 
43 /*************************************************************************
44 * This function checks whether or not the boundary information is correct
45 **************************************************************************/
47 {
48  int i, j, nvtxs, nbnd;
49  idxtype *xadj, *adjncy, *where, *bndptr, *bndind;
50 
51  nvtxs = graph->nvtxs;
52  xadj = graph->xadj;
53  adjncy = graph->adjncy;
54  where = graph->where;
55  bndptr = graph->bndptr;
56  bndind = graph->bndind;
57 
58  for (nbnd=0, i=0; i<nvtxs; i++) {
59  if (xadj[i+1]-xadj[i] == 0)
60  nbnd++; /* Islands are considered to be boundary vertices */
61 
62  for (j=xadj[i]; j<xadj[i+1]; j++) {
63  if (where[i] != where[adjncy[j]]) {
64  nbnd++;
65  ASSERT(bndptr[i] != -1);
66  ASSERT(bndind[bndptr[i]] == i);
67  break;
68  }
69  }
70  }
71 
72  ASSERTP(nbnd == graph->nbnd, ("%d %d\n", nbnd, graph->nbnd));
73 
74  return 1;
75 }
76 
77 
78 
79 /*************************************************************************
80 * This function checks whether or not the boundary information is correct
81 **************************************************************************/
83 {
84  int i, j, nvtxs, nbnd, id, ed;
85  idxtype *xadj, *adjncy, *where, *bndptr, *bndind;
86 
87  nvtxs = graph->nvtxs;
88  xadj = graph->xadj;
89  adjncy = graph->adjncy;
90  where = graph->where;
91  bndptr = graph->bndptr;
92  bndind = graph->bndind;
93 
94  for (nbnd=0, i=0; i<nvtxs; i++) {
95  id = ed = 0;
96  for (j=xadj[i]; j<xadj[i+1]; j++) {
97  if (where[i] != where[adjncy[j]])
98  ed += graph->adjwgt[j];
99  else
100  id += graph->adjwgt[j];
101  }
102  if (ed - id >= 0 && xadj[i] < xadj[i+1]) {
103  nbnd++;
104  ASSERTP(bndptr[i] != -1, ("%d %d %d\n", i, id, ed));
105  ASSERT(bndind[bndptr[i]] == i);
106  }
107  }
108 
109  ASSERTP(nbnd == graph->nbnd, ("%d %d\n", nbnd, graph->nbnd));
110 
111  return 1;
112 }
113 
114 /*************************************************************************
115 * This function checks whether or not the boundary information is correct
116 **************************************************************************/
117 int CheckNodeBnd(GraphType *graph, int onbnd)
118 {
119  int i, j, nvtxs, nbnd;
120  idxtype *xadj, *adjncy, *where, *bndptr, *bndind;
121 
122  nvtxs = graph->nvtxs;
123  xadj = graph->xadj;
124  adjncy = graph->adjncy;
125  where = graph->where;
126  bndptr = graph->bndptr;
127  bndind = graph->bndind;
128 
129  for (nbnd=0, i=0; i<nvtxs; i++) {
130  if (where[i] == 2)
131  nbnd++;
132  }
133 
134  ASSERTP(nbnd == onbnd, ("%d %d\n", nbnd, onbnd));
135 
136  for (i=0; i<nvtxs; i++) {
137  if (where[i] != 2) {
138  ASSERTP(bndptr[i] == -1, ("%d %d\n", i, bndptr[i]));
139  }
140  else {
141  ASSERTP(bndptr[i] != -1, ("%d %d\n", i, bndptr[i]));
142  }
143  }
144 
145  return 1;
146 }
147 
148 
149 
150 /*************************************************************************
151 * This function checks whether or not the rinfo of a vertex is consistent
152 **************************************************************************/
154 {
155  int i, j;
156 
157  for (i=0; i<rinfo->ndegrees; i++) {
158  for (j=i+1; j<rinfo->ndegrees; j++)
159  ASSERTP(rinfo->edegrees[i].pid != rinfo->edegrees[j].pid, ("%d %d %d %d\n", i, j, rinfo->edegrees[i].pid, rinfo->edegrees[j].pid));
160  }
161 
162  return 1;
163 }
164 
165 
166 
167 /*************************************************************************
168 * This function checks the correctness of the NodeFM data structures
169 **************************************************************************/
171 {
172  int i, j, k, l, nvtxs, me, other;
173  idxtype *xadj, *adjncy, *adjwgt, *vwgt, *where;
174  idxtype edegrees[2], pwgts[3];
175 
176  nvtxs = graph->nvtxs;
177  xadj = graph->xadj;
178  vwgt = graph->vwgt;
179  adjncy = graph->adjncy;
180  adjwgt = graph->adjwgt;
181 
182  where = graph->where;
183 
184  /*------------------------------------------------------------
185  / Compute now the separator external degrees
186  /------------------------------------------------------------*/
187  pwgts[0] = pwgts[1] = pwgts[2] = 0;
188  for (i=0; i<nvtxs; i++) {
189  me = where[i];
190  pwgts[me] += vwgt[i];
191 
192  if (me == 2) { /* If it is on the separator do some computations */
193  edegrees[0] = edegrees[1] = 0;
194 
195  for (j=xadj[i]; j<xadj[i+1]; j++) {
196  other = where[adjncy[j]];
197  if (other != 2)
198  edegrees[other] += vwgt[adjncy[j]];
199  }
200  if (edegrees[0] != graph->nrinfo[i].edegrees[0] || edegrees[1] != graph->nrinfo[i].edegrees[1]) {
201  printf("Something wrong with edegrees: %d %d %d %d %d\n", i, edegrees[0], edegrees[1], graph->nrinfo[i].edegrees[0], graph->nrinfo[i].edegrees[1]);
202  return 0;
203  }
204  }
205  }
206 
207  if (pwgts[0] != graph->pwgts[0] || pwgts[1] != graph->pwgts[1] || pwgts[2] != graph->pwgts[2])
208  printf("Something wrong with part-weights: %d %d %d %d %d %d\n", pwgts[0], pwgts[1], pwgts[2], graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]);
209 
210  return 1;
211 }
212 
213 
214 /*************************************************************************
215 * This function checks if the separator is indeed a separator
216 **************************************************************************/
218 {
219  int i, j, nvtxs, other;
220  idxtype *xadj, *adjncy, *where;
221 
222  nvtxs = graph->nvtxs;
223  xadj = graph->xadj;
224  adjncy = graph->adjncy;
225  where = graph->where;
226 
227  for (i=0; i<nvtxs; i++) {
228  if (where[i] == 2)
229  continue;
230  other = (where[i]+1)%2;
231  for (j=xadj[i]; j<xadj[i+1]; j++) {
232  ASSERTP(where[adjncy[j]] != other, ("%d %d %d %d %d %d\n", i, where[i], adjncy[j], where[adjncy[j]], xadj[i+1]-xadj[i], xadj[adjncy[j]+1]-xadj[adjncy[j]]));
233  }
234  }
235 
236  return 1;
237 }
238 
239 
NRInfoType * nrinfo
Definition: struct.h:190
int ndegrees
Definition: struct.h:121
idxtype * pwgts
Definition: struct.h:176
#define CheckNodeBnd
Definition: rename.h:46
int nbnd
Definition: struct.h:177
idxtype pid
Definition: struct.h:78
idxtype * bndptr
Definition: struct.h:178
#define CheckNodePartitionParams
Definition: rename.h:48
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
int idxtype
Definition: struct.h:19
#define IsSeparable
Definition: rename.h:49
#define CheckBnd
Definition: rename.h:44
idxtype * adjwgt
Definition: struct.h:166
#define CheckRInfo
Definition: rename.h:47
#define ASSERTP(expr, msg)
Definition: macros.h:142
#define CheckBnd2
Definition: rename.h:45
idxtype * bndind
Definition: struct.h:178
idxtype * vwgt
Definition: struct.h:163
EDegreeType * edegrees
Definition: struct.h:122
idxtype edegrees[2]
Definition: struct.h:147
int nvtxs
Definition: struct.h:161
#define ASSERT(expr)
Definition: macros.h:130
#define ComputeCut
Definition: rename.h:43
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162