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 | **************************************************************************/ |
---|
20 | int ComputeCut(GraphType *graph, idxtype *where) |
---|
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 | **************************************************************************/ |
---|
46 | int CheckBnd(GraphType *graph) |
---|
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 | **************************************************************************/ |
---|
82 | int CheckBnd2(GraphType *graph) |
---|
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 | **************************************************************************/ |
---|
153 | int CheckRInfo(RInfoType *rinfo) |
---|
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 | **************************************************************************/ |
---|
170 | int CheckNodePartitionParams(GraphType *graph) |
---|
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 | **************************************************************************/ |
---|
217 | int IsSeparable(GraphType *graph) |
---|
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 | |
---|