SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/debug.c
ViewVC logotype

Annotation of /pkg/src/Metis/debug.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (view) (download) (as text)

1 : bates 10 /*
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 2003/12/31 21:32:30 bates 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 :    

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge