source: branches/numpy/pymetis/metis-4.0/Lib/debug.c @ 6971

Last change on this file since 6971 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.

File size: 6.4 KB
Line 
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**************************************************************************/
20int 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**************************************************************************/
46int 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**************************************************************************/
82int 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**************************************************************************/
117int 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**************************************************************************/
153int 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**************************************************************************/
170int 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**************************************************************************/
217int 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
Note: See TracBrowser for help on using the repository browser.