source: branches/inundation-numpy-branch/pymetis/metis-4.0/Test/mtest.c @ 7256

Last change on this file since 7256 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: 53.5 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * mtest.c
5 *
6 * This file is a comprehensive tester for all the graph partitioning/ordering
7 * routines of METIS
8 *
9 * Started 9/18/98
10 * George
11 *
12 * $Id: mtest.c,v 1.8 1998/09/20 17:36:14 karypis Exp $
13 *
14 */
15
16#include <metis.h>
17
18
19
20/*************************************************************************
21* Let the game begin
22**************************************************************************/
23main(int argc, char *argv[])
24{
25  int i, nparts, options[10];
26  idxtype *part;
27  float lbvec[MAXNCON], rubvec[MAXNCON];
28  GraphType graph;
29  int numflag = 0, wgtflag = 0, edgecut;
30
31
32  if (argc != 2) {
33    printf("Usage: %s <GraphFile>\n",argv[0]);
34    exit(0);
35  }
36   
37  ReadGraph(&graph, argv[1], &wgtflag);
38
39  printf("**********************************************************************\n");
40  printf("%s", METISTITLE);
41  printf("Graph Information ---------------------------------------------------\n");
42  printf("  Name: %s, #Vertices: %d, #Edges: %d\n", argv[1], graph.nvtxs, graph.nedges/2);
43
44  Test_PartGraph(graph.nvtxs, graph.xadj, graph.adjncy);
45
46  Test_PartGraphV(graph.nvtxs, graph.xadj, graph.adjncy);
47
48  Test_PartGraphmC(graph.nvtxs, graph.xadj, graph.adjncy);
49
50  Test_ND(graph.nvtxs, graph.xadj, graph.adjncy);
51
52  printf("\n---------------------------------------------------------------------\n");
53  printf(" Testing completed.\n");
54  printf("**********************************************************************\n");
55
56  GKfree(&graph.xadj, &graph.adjncy, &graph.vwgt, &graph.adjwgt, LTERM);
57} 
58
59
60
61/*************************************************************************
62* This function tests the regular graph partitioning routines
63**************************************************************************/
64void Test_PartGraph(int nvtxs, idxtype *xadj, idxtype *adjncy)
65{
66  int i, j, jj, k, tstnum, rcode;
67  int nparts, numflag, wgtflag, edgecut, options[10];
68  idxtype *part, *vwgt, *adjwgt;
69  float tpwgts[256];
70
71  vwgt = idxmalloc(nvtxs, "vwgt");
72  for (i=0; i<nvtxs; i++)
73    vwgt[i] = RandomInRange(10);
74
75  adjwgt = idxmalloc(xadj[nvtxs], "adjwgt");
76  for (i=0; i<nvtxs; i++) {
77    for (j=xadj[i]; j<xadj[i+1]; j++) {
78      k = adjncy[j];
79      if (i < k) {
80        adjwgt[j] = 1+RandomInRange(5);
81        for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
82          if (adjncy[jj] == i) {
83            adjwgt[jj] = adjwgt[j];
84            break;
85          }
86        }
87      }
88    }
89  }
90
91
92  part = idxmalloc(nvtxs, "part");
93
94  tpwgts[0] = .1;
95  tpwgts[1] = .2;
96  tpwgts[2] = .3;
97  tpwgts[3] = .1;
98  tpwgts[4] = .05;
99  tpwgts[5] = .25;
100
101
102  /*===========================================================================*/
103  printf("\nTesting METIS_PartGraphRecursive ------------------------------------\n  ");
104  tstnum = 1;
105
106/**/
107  numflag = 0; wgtflag = 0; nparts = 20;
108  options[0] = 0;
109  METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
110                           &nparts, options, &edgecut, part);
111
112  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, edgecut, part)) == 0)
113    printf("[%d:ok]", tstnum++);
114  else
115    printf("[%d:err-%d]", tstnum++, rcode);
116  fflush(stdout);
117
118
119/**/
120  numflag = 0; wgtflag = 1; nparts = 20;
121  options[0] = 0;
122  METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
123                           &nparts, options, &edgecut, part);
124
125  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, edgecut, part)) == 0)
126    printf("[%d:ok]", tstnum++);
127  else
128    printf("[%d:err-%d]", tstnum++, rcode);
129  fflush(stdout);
130
131
132/**/
133  numflag = 0; wgtflag = 2; nparts = 20;
134  options[0] = 0;
135  METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
136                           &nparts, options, &edgecut, part);
137
138  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, edgecut, part)) == 0)
139    printf("[%d:ok]", tstnum++);
140  else
141    printf("[%d:err-%d]", tstnum++, rcode);
142  fflush(stdout);
143
144
145/**/
146  numflag = 0; wgtflag = 3; nparts = 20;
147  options[0] = 0;
148  METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
149                           &nparts, options, &edgecut, part);
150
151  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
152    printf("[%d:ok]", tstnum++);
153  else
154    printf("[%d:err-%d]", tstnum++, rcode);
155  fflush(stdout);
156
157
158/**/
159  numflag = 0; wgtflag = 3; nparts = 20;
160  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
161  METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
162                           &nparts, options, &edgecut, part);
163
164  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
165    printf("[%d:ok]", tstnum++);
166  else
167    printf("[%d:err-%d]", tstnum++, rcode);
168  fflush(stdout);
169
170
171/**/
172  numflag = 0; wgtflag = 3; nparts = 20;
173  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
174  METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
175                           &nparts, options, &edgecut, part);
176
177  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
178    printf("[%d:ok]", tstnum++);
179  else
180    printf("[%d:err-%d]", tstnum++, rcode);
181  fflush(stdout);
182
183  printf("\n");
184
185
186 
187  /*===========================================================================*/
188  printf("\nTesting METIS_WPartGraphRecursive -----------------------------------\n  ");
189  tstnum = 1;
190
191
192/**/
193  numflag = 0; wgtflag = 0; nparts = 6;
194  options[0] = 0;
195  METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
196                           &nparts, tpwgts, options, &edgecut, part);
197
198  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, tpwgts, edgecut, part)) == 0)
199    printf("[%d:ok]", tstnum++);
200  else
201    printf("[%d:err-%d]", tstnum++, rcode);
202  fflush(stdout);
203
204
205/**/
206  numflag = 0; wgtflag = 1; nparts = 6;
207  options[0] = 0;
208  METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
209                           &nparts, tpwgts, options, &edgecut, part);
210
211  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
212    printf("[%d:ok]", tstnum++);
213  else
214    printf("[%d:err-%d]", tstnum++, rcode);
215  fflush(stdout);
216
217
218/**/
219  numflag = 0; wgtflag = 2; nparts = 6;
220  options[0] = 0;
221  METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
222                           &nparts, tpwgts, options, &edgecut, part);
223
224  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, tpwgts, edgecut, part)) == 0)
225    printf("[%d:ok]", tstnum++);
226  else
227    printf("[%d:err-%d]", tstnum++, rcode);
228  fflush(stdout);
229
230
231/**/
232  numflag = 0; wgtflag = 3; nparts = 6;
233  options[0] = 0;
234  METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
235                           &nparts, tpwgts, options, &edgecut, part);
236
237  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
238    printf("[%d:ok]", tstnum++);
239  else
240    printf("[%d:err-%d]", tstnum++, rcode);
241  fflush(stdout);
242
243
244/**/
245  numflag = 0; wgtflag = 3; nparts = 6;
246  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
247  METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
248                           &nparts, tpwgts, options, &edgecut, part);
249
250  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
251    printf("[%d:ok]", tstnum++);
252  else
253    printf("[%d:err-%d]", tstnum++, rcode);
254  fflush(stdout);
255
256
257/**/
258  numflag = 0; wgtflag = 3; nparts = 6;
259  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
260  METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
261                           &nparts, tpwgts, options, &edgecut, part);
262
263  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
264    printf("[%d:ok]", tstnum++);
265  else
266    printf("[%d:err-%d]", tstnum++, rcode);
267  fflush(stdout);
268
269  printf("\n");
270
271
272
273  /*===========================================================================*/
274  printf("\nTesting METIS_PartGraphKway -----------------------------------------\n  ");
275  tstnum = 1;
276
277/**/
278  numflag = 0; wgtflag = 0; nparts = 20;
279  options[0] = 0;
280  METIS_PartGraphKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
281                      &nparts, options, &edgecut, part);
282
283  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, edgecut, part)) == 0)
284    printf("[%d:ok]", tstnum++);
285  else
286    printf("[%d:err-%d]", tstnum++, rcode);
287  fflush(stdout);
288
289
290/**/
291  numflag = 0; wgtflag = 1; nparts = 20;
292  options[0] = 0;
293  METIS_PartGraphKway(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
294                      &nparts, options, &edgecut, part);
295
296  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, edgecut, part)) == 0)
297    printf("[%d:ok]", tstnum++);
298  else
299    printf("[%d:err-%d]", tstnum++, rcode);
300  fflush(stdout);
301
302
303/**/
304  numflag = 0; wgtflag = 2; nparts = 20;
305  options[0] = 0;
306  METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
307                      &nparts, options, &edgecut, part);
308
309  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, edgecut, part)) == 0)
310    printf("[%d:ok]", tstnum++);
311  else
312    printf("[%d:err-%d]", tstnum++, rcode);
313  fflush(stdout);
314
315
316/**/
317  numflag = 0; wgtflag = 3; nparts = 20;
318  options[0] = 0;
319  METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
320                      &nparts, options, &edgecut, part);
321
322  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
323    printf("[%d:ok]", tstnum++);
324  else
325    printf("[%d:err-%d]", tstnum++, rcode);
326  fflush(stdout);
327
328
329/**/
330  numflag = 0; wgtflag = 3; nparts = 20;
331  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
332  METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
333                      &nparts, options, &edgecut, part);
334
335  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
336    printf("[%d:ok]", tstnum++);
337  else
338    printf("[%d:err-%d]", tstnum++, rcode);
339  fflush(stdout);
340
341
342/**/
343  numflag = 0; wgtflag = 3; nparts = 20;
344  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
345  METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
346                      &nparts, options, &edgecut, part);
347
348  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
349    printf("[%d:ok]", tstnum++);
350  else
351    printf("[%d:err-%d]", tstnum++, rcode);
352  fflush(stdout);
353
354
355/**/
356  numflag = 0; wgtflag = 3; nparts = 20;
357  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 2; options[4] = 0;
358  METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
359                      &nparts, options, &edgecut, part);
360
361  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
362    printf("[%d:ok]", tstnum++);
363  else
364    printf("[%d:err-%d]", tstnum++, rcode);
365  fflush(stdout);
366
367
368/**/
369  numflag = 0; wgtflag = 3; nparts = 20;
370  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 3; options[4] = 0;
371  METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
372                      &nparts, options, &edgecut, part);
373
374  if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
375    printf("[%d:ok]", tstnum++);
376  else
377    printf("[%d:err-%d]", tstnum++, rcode);
378  fflush(stdout);
379
380  printf("\n");
381
382
383 
384  /*===========================================================================*/
385  printf("\nTesting METIS_WPartGraphKway ----------------------------------------\n  ");
386  tstnum = 1;
387
388
389/**/
390  numflag = 0; wgtflag = 0; nparts = 6;
391  options[0] = 0;
392  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
393                       &nparts, tpwgts, options, &edgecut, part);
394
395  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, tpwgts, edgecut, part)) == 0)
396    printf("[%d:ok]", tstnum++);
397  else
398    printf("[%d:err-%d]", tstnum++, rcode);
399  fflush(stdout);
400
401
402/**/
403  numflag = 0; wgtflag = 1; nparts = 6;
404  options[0] = 0;
405  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
406                       &nparts, tpwgts, options, &edgecut, part);
407
408  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
409    printf("[%d:ok]", tstnum++);
410  else
411    printf("[%d:err-%d]", tstnum++, rcode);
412  fflush(stdout);
413
414
415/**/
416  numflag = 0; wgtflag = 2; nparts = 6;
417  options[0] = 0;
418  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
419                       &nparts, tpwgts, options, &edgecut, part);
420
421  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, tpwgts, edgecut, part)) == 0)
422    printf("[%d:ok]", tstnum++);
423  else
424    printf("[%d:err-%d]", tstnum++, rcode);
425  fflush(stdout);
426
427
428/**/
429  numflag = 0; wgtflag = 3; nparts = 6;
430  options[0] = 0;
431  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
432                       &nparts, tpwgts, options, &edgecut, part);
433
434  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
435    printf("[%d:ok]", tstnum++);
436  else
437    printf("[%d:err-%d]", tstnum++, rcode);
438  fflush(stdout);
439
440
441/**/
442  numflag = 0; wgtflag = 3; nparts = 6;
443  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
444  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
445                       &nparts, tpwgts, options, &edgecut, part);
446
447  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
448    printf("[%d:ok]", tstnum++);
449  else
450    printf("[%d:err-%d]", tstnum++, rcode);
451  fflush(stdout);
452
453
454/**/
455  numflag = 0; wgtflag = 3; nparts = 6;
456  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
457  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
458                       &nparts, tpwgts, options, &edgecut, part);
459
460  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
461    printf("[%d:ok]", tstnum++);
462  else
463    printf("[%d:err-%d]", tstnum++, rcode);
464  fflush(stdout);
465
466
467/**/
468  numflag = 0; wgtflag = 3; nparts = 6;
469  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 2; options[4] = 0;
470  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
471                       &nparts, tpwgts, options, &edgecut, part);
472
473  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
474    printf("[%d:ok]", tstnum++);
475  else
476    printf("[%d:err-%d]", tstnum++, rcode);
477  fflush(stdout);
478
479
480/**/
481  numflag = 0; wgtflag = 3; nparts = 6;
482  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 3; options[4] = 0;
483  METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
484                       &nparts, tpwgts, options, &edgecut, part);
485
486  if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
487    printf("[%d:ok]", tstnum++);
488  else
489    printf("[%d:err-%d]", tstnum++, rcode);
490  fflush(stdout);
491
492  printf("\n");
493
494  GKfree(&vwgt, &adjwgt, &part, LTERM);
495}
496
497
498
499/*************************************************************************
500* This function verifies that the partitioning was computed correctly
501**************************************************************************/
502int VerifyPart(int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
503               idxtype *adjwgt, int nparts, int edgecut, idxtype *part)
504{
505  int i, j, k, cut, vfree=0, efree=0, rcode=0;
506  idxtype *pwgts;
507
508  if (part[idxamax(nvtxs, part)] != nparts-1)
509    return 1;  /* the total number of partitions is different than nparts */
510
511  /* compute the cut and the pwgts */
512  if (vwgt == NULL) {
513    vfree = 1;
514    vwgt = idxsmalloc(nvtxs, 1, "vwgt");
515  }
516  if (adjwgt == NULL) {
517    efree = 1;
518    adjwgt = idxsmalloc(xadj[nvtxs], 1, "adjwgt");
519  }
520  pwgts = idxsmalloc(nparts, 0, "pwgts");
521
522  for (cut=0, i=0; i<nvtxs; i++) {
523    pwgts[part[i]] += vwgt[i];
524    for (j=xadj[i]; j<xadj[i+1]; j++) 
525      cut += (part[i] != part[adjncy[j]] ? adjwgt[j] : 0);
526  }
527
528  if (cut != 2*edgecut)
529    rcode = 2;
530
531  if (nparts*pwgts[idxamax(nparts, pwgts)] > 1.10*idxsum(nparts, pwgts))
532    rcode = 3;
533
534  if (vfree)
535    free(vwgt);
536
537  if (efree)
538    free(adjwgt);
539
540  free(pwgts);
541
542  MALLOC_CHECK(NULL);
543
544  return rcode;
545}
546
547
548/*************************************************************************
549* This function verifies that the partitioning was computed correctly
550**************************************************************************/
551int VerifyWPart(int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
552                idxtype *adjwgt, int nparts, float *tpwgts, int edgecut, idxtype *part)
553{
554  int i, j, k, tvwgt, cut, vfree=0, efree=0, rcode=0;
555  idxtype *pwgts;
556
557  if (part[idxamax(nvtxs, part)] != nparts-1) 
558    return 1;  /* the total number of partitions is different than nparts */
559
560  /* compute the cut and the pwgts */
561  if (vwgt == NULL) {
562    vfree = 1;
563    vwgt = idxsmalloc(nvtxs, 1, "vwgt");
564  }
565  if (adjwgt == NULL) {
566    efree = 1;
567    adjwgt = idxsmalloc(xadj[nvtxs], 1, "adjwgt");
568  }
569  pwgts = idxsmalloc(nparts, 0, "pwgts");
570
571  for (cut=0, i=0; i<nvtxs; i++) {
572    pwgts[part[i]] += vwgt[i];
573    for (j=xadj[i]; j<xadj[i+1]; j++) 
574      cut += (part[i] != part[adjncy[j]] ? adjwgt[j] : 0);
575  }
576
577  if (cut != 2*edgecut)
578    rcode = 2;
579
580  tvwgt = idxsum(nparts, pwgts);
581  for (i=0; i<nparts; i++) {
582    if (pwgts[i] > 1.10*tpwgts[i]*tvwgt) {
583      rcode = 3;
584      break;
585    }
586  }
587
588  if (vfree)
589    free(vwgt);
590
591  if (efree)
592    free(adjwgt);
593
594  free(pwgts);
595
596  MALLOC_CHECK(NULL);
597
598  return rcode;
599}
600
601
602
603/*************************************************************************
604* This function tests the regular graph partitioning routines
605**************************************************************************/
606void Test_PartGraphV(int nvtxs, idxtype *xadj, idxtype *adjncy)
607{
608  int i, j, jj, k, tstnum, rcode;
609  int nparts, numflag, wgtflag, totalv, options[10];
610  idxtype *part, *vwgt, *vsize;
611  float tpwgts[256];
612
613  vwgt = idxmalloc(nvtxs, "vwgt");
614  for (i=0; i<nvtxs; i++)
615    vwgt[i] = RandomInRange(10);
616
617  vsize = idxmalloc(nvtxs, "vsize");
618  for (i=0; i<nvtxs; i++)
619    vsize[i] = RandomInRange(10);
620
621  part = idxmalloc(nvtxs, "part");
622
623  tpwgts[0] = .1;
624  tpwgts[1] = .2;
625  tpwgts[2] = .3;
626  tpwgts[3] = .1;
627  tpwgts[4] = .05;
628  tpwgts[5] = .25;
629
630
631  /*===========================================================================*/
632  printf("\nTesting METIS_PartGraphVKway ----------------------------------------\n  ");
633  tstnum = 1;
634
635/**/
636  numflag = 0; wgtflag = 0; nparts = 20;
637  options[0] = 0;
638  METIS_PartGraphVKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
639                       &nparts, options, &totalv, part);
640
641  if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, NULL, NULL, nparts, totalv, part)) == 0)
642    printf("[%d:ok]", tstnum++);
643  else
644    printf("[%d:err-%d]", tstnum++, rcode);
645  fflush(stdout);
646
647
648/**/
649  numflag = 0; wgtflag = 1; nparts = 20;
650  options[0] = 0;
651  METIS_PartGraphVKway(&nvtxs, xadj, adjncy, NULL, vsize, &wgtflag, &numflag,
652                       &nparts, options, &totalv, part);
653
654  if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, NULL, vsize, nparts, totalv, part)) == 0)
655    printf("[%d:ok]", tstnum++);
656  else
657    printf("[%d:err-%d]", tstnum++, rcode);
658  fflush(stdout);
659
660
661/**/
662  numflag = 0; wgtflag = 2; nparts = 20;
663  options[0] = 0;
664  METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
665                       &nparts, options, &totalv, part);
666
667  if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, NULL, nparts, totalv, part)) == 0)
668    printf("[%d:ok]", tstnum++);
669  else
670    printf("[%d:err-%d]", tstnum++, rcode);
671  fflush(stdout);
672
673
674/**/
675  numflag = 0; wgtflag = 3; nparts = 20;
676  options[0] = 0;
677  METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
678                       &nparts, options, &totalv, part);
679
680  if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
681    printf("[%d:ok]", tstnum++);
682  else
683    printf("[%d:err-%d]", tstnum++, rcode);
684  fflush(stdout);
685
686
687/**/
688  numflag = 0; wgtflag = 3; nparts = 20;
689  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
690  METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
691                       &nparts, options, &totalv, part);
692
693  if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
694    printf("[%d:ok]", tstnum++);
695  else
696    printf("[%d:err-%d]", tstnum++, rcode);
697  fflush(stdout);
698
699
700/**/
701  numflag = 0; wgtflag = 3; nparts = 20;
702  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
703  METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
704                       &nparts, options, &totalv, part);
705
706  if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
707    printf("[%d:ok]", tstnum++);
708  else
709    printf("[%d:err-%d]", tstnum++, rcode);
710  fflush(stdout);
711
712
713/**/
714  numflag = 0; wgtflag = 3; nparts = 20;
715  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 3; options[4] = 0;
716  METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
717                       &nparts, options, &totalv, part);
718
719  if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
720    printf("[%d:ok]", tstnum++);
721  else
722    printf("[%d:err-%d]", tstnum++, rcode);
723  fflush(stdout);
724
725  printf("\n");
726
727
728 
729  /*===========================================================================*/
730  printf("\nTesting METIS_WPartGraphVKway ---------------------------------------\n  ");
731  tstnum = 1;
732
733
734/**/
735  numflag = 0; wgtflag = 0; nparts = 6;
736  options[0] = 0;
737  METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
738                        &nparts, tpwgts, options, &totalv, part);
739
740  if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, NULL, NULL, nparts, tpwgts, totalv, part)) == 0)
741    printf("[%d:ok]", tstnum++);
742  else
743    printf("[%d:err-%d]", tstnum++, rcode);
744  fflush(stdout);
745
746
747/**/
748  numflag = 0; wgtflag = 1; nparts = 6;
749  options[0] = 0;
750  METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, NULL, vsize, &wgtflag, &numflag,
751                        &nparts, tpwgts, options, &totalv, part);
752
753  if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, NULL, vsize, nparts, tpwgts, totalv, part)) == 0)
754    printf("[%d:ok]", tstnum++);
755  else
756    printf("[%d:err-%d]", tstnum++, rcode);
757  fflush(stdout);
758
759
760/**/
761  numflag = 0; wgtflag = 2; nparts = 6;
762  options[0] = 0;
763  METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
764                        &nparts, tpwgts, options, &totalv, part);
765
766  if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, NULL, nparts, tpwgts, totalv, part)) == 0)
767    printf("[%d:ok]", tstnum++);
768  else
769    printf("[%d:err-%d]", tstnum++, rcode);
770  fflush(stdout);
771
772
773/**/
774  numflag = 0; wgtflag = 3; nparts = 6;
775  options[0] = 0;
776  METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
777                        &nparts, tpwgts, options, &totalv, part);
778
779  if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
780    printf("[%d:ok]", tstnum++);
781  else
782    printf("[%d:err-%d]", tstnum++, rcode);
783  fflush(stdout);
784
785
786/**/
787  numflag = 0; wgtflag = 3; nparts = 6;
788  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
789  METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
790                        &nparts, tpwgts, options, &totalv, part);
791
792  if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
793    printf("[%d:ok]", tstnum++);
794  else
795    printf("[%d:err-%d]", tstnum++, rcode);
796  fflush(stdout);
797
798
799/**/
800  numflag = 0; wgtflag = 3; nparts = 6;
801  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
802  METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
803                        &nparts, tpwgts, options, &totalv, part);
804
805  if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
806    printf("[%d:ok]", tstnum++);
807  else
808    printf("[%d:err-%d]", tstnum++, rcode);
809  fflush(stdout);
810
811
812/**/
813  numflag = 0; wgtflag = 3; nparts = 6;
814  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 3; options[4] = 0;
815  METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
816                        &nparts, tpwgts, options, &totalv, part);
817
818  if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
819    printf("[%d:ok]", tstnum++);
820  else
821    printf("[%d:err-%d]", tstnum++, rcode);
822  fflush(stdout);
823
824  printf("\n");
825
826
827  GKfree(&vwgt, &vsize, &part, LTERM);
828}
829
830
831/*************************************************************************
832* This function verifies that the partitioning was computed correctly
833**************************************************************************/
834int VerifyPartV(int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
835               idxtype *vsize, int nparts, int totalv, idxtype *part)
836{
837  int i, j, k, ttlv, vfree=0, efree=0, rcode=0;
838  idxtype *pwgts, *marker;
839
840  if (part[idxamax(nvtxs, part)] != nparts-1)
841    return 1;  /* the total number of partitions is different than nparts */
842
843  /* compute the cut and the pwgts */
844  if (vwgt == NULL) {
845    vfree = 1;
846    vwgt = idxsmalloc(nvtxs, 1, "vwgt");
847  }
848  if (vsize == NULL) {
849    efree = 1;
850    vsize = idxsmalloc(nvtxs, 1, "vsize");
851  }
852  pwgts = idxsmalloc(nparts, 0, "pwgts");
853
854  marker = idxsmalloc(nparts, -1, "htable");
855  for (ttlv=0, i=0; i<nvtxs; i++) {
856    pwgts[part[i]] += vwgt[i];
857    marker[part[i]] = i;
858    for (j=xadj[i]; j<xadj[i+1]; j++) {
859      if (marker[part[adjncy[j]]] != i) {
860        ttlv += vsize[i];
861        marker[part[adjncy[j]]] = i;
862      }
863    }
864  }
865
866  if (ttlv != totalv)
867    rcode = 2;
868
869  if (nparts*pwgts[idxamax(nparts, pwgts)] > 1.05*idxsum(nparts, pwgts))
870    rcode = 3;
871
872  if (vfree)
873    free(vwgt);
874
875  if (efree)
876    free(vsize);
877
878  free(pwgts);
879  free(marker);
880
881  MALLOC_CHECK(NULL);
882
883  return rcode;
884}
885
886
887/*************************************************************************
888* This function verifies that the partitioning was computed correctly
889**************************************************************************/
890int VerifyWPartV(int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
891                idxtype *vsize, int nparts, float *tpwgts, int totalv, idxtype *part)
892{
893  int i, j, k, tvwgt, ttlv, vfree=0, efree=0, rcode=0;
894  idxtype *pwgts, *marker;
895
896  if (part[idxamax(nvtxs, part)] != nparts-1) 
897    return 1;  /* the total number of partitions is different than nparts */
898
899  /* compute the cut and the pwgts */
900  if (vwgt == NULL) {
901    vfree = 1;
902    vwgt = idxsmalloc(nvtxs, 1, "vwgt");
903  }
904  if (vsize == NULL) {
905    efree = 1;
906    vsize = idxsmalloc(nvtxs, 1, "vsize");
907  }
908  pwgts = idxsmalloc(nparts, 0, "pwgts");
909
910  marker = idxsmalloc(nparts, -1, "htable");
911  for (ttlv=0, i=0; i<nvtxs; i++) {
912    pwgts[part[i]] += vwgt[i];
913    marker[part[i]] = i;
914    for (j=xadj[i]; j<xadj[i+1]; j++) {
915      if (marker[part[adjncy[j]]] != i) {
916        ttlv += vsize[i];
917        marker[part[adjncy[j]]] = i;
918      }
919    }
920  }
921
922  if (ttlv != totalv)
923    rcode = 2;
924
925  tvwgt = idxsum(nparts, pwgts);
926  for (i=0; i<nparts; i++) {
927    if (pwgts[i] > 1.05*tpwgts[i]*tvwgt) {
928      rcode = 3;
929      break;
930    }
931  }
932
933  if (vfree)
934    free(vwgt);
935
936  if (efree)
937    free(vsize);
938
939  free(pwgts);
940  free(marker);
941
942  MALLOC_CHECK(NULL);
943
944  return rcode;
945}
946
947
948
949/*************************************************************************
950* This function tests the regular graph partitioning routines
951**************************************************************************/
952void Test_PartGraphmC(int nvtxs, idxtype *xadj, idxtype *adjncy)
953{
954  int i, j, jj, k, tstnum, rcode;
955  int nparts, ncon, numflag, wgtflag, edgecut, options[10];
956  idxtype *part, *vwgt, *adjwgt;
957  float ubvec[MAXNCON];
958
959  ncon = 3;
960
961  vwgt = idxmalloc(nvtxs*ncon, "vwgt");
962  for (i=0; i<ncon*nvtxs; i++)
963    vwgt[i] = RandomInRange(10);
964
965  adjwgt = idxmalloc(xadj[nvtxs], "adjwgt");
966  for (i=0; i<nvtxs; i++) {
967    for (j=xadj[i]; j<xadj[i+1]; j++) {
968      k = adjncy[j];
969      if (i < k) {
970        adjwgt[j] = 1+RandomInRange(5);
971        for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
972          if (adjncy[jj] == i) {
973            adjwgt[jj] = adjwgt[j];
974            break;
975          }
976        }
977      }
978    }
979  }
980
981
982  part = idxmalloc(nvtxs, "part");
983
984
985
986  /*===========================================================================*/
987  printf("\nTesting METIS_mCPartGraphRecursive ----------------------------------\n  ");
988  tstnum = 1;
989
990/**/
991  numflag = 0; wgtflag = 0; nparts = 10;
992  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
993  options[0] = 0;
994  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
995                             &nparts, options, &edgecut, part);
996
997  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, NULL, nparts, ubvec, edgecut, part)) == 0)
998    printf("[%d:ok]", tstnum++);
999  else
1000    printf("[%d:err-%d]", tstnum++, rcode);
1001  fflush(stdout);
1002
1003
1004/**/
1005  numflag = 0; wgtflag = 1; nparts = 10;
1006  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1007  options[0] = 0;
1008  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1009                             &nparts, options, &edgecut, part);
1010
1011  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1012    printf("[%d:ok]", tstnum++);
1013  else
1014    printf("[%d:err-%d]", tstnum++, rcode);
1015  fflush(stdout);
1016
1017
1018/**/
1019  numflag = 0; wgtflag = 1; nparts = 10;
1020  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1021  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
1022  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1023                             &nparts, options, &edgecut, part);
1024
1025  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1026    printf("[%d:ok]", tstnum++);
1027  else
1028    printf("[%d:err-%d]", tstnum++, rcode);
1029  fflush(stdout);
1030
1031
1032/**/
1033  numflag = 0; wgtflag = 1; nparts = 10;
1034  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1035  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
1036  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1037                             &nparts, options, &edgecut, part);
1038
1039  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1040    printf("[%d:ok]", tstnum++);
1041  else
1042    printf("[%d:err-%d]", tstnum++, rcode);
1043  fflush(stdout);
1044
1045
1046/**/
1047  numflag = 0; wgtflag = 1; nparts = 10;
1048  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1049  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
1050  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1051                             &nparts, options, &edgecut, part);
1052
1053  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1054    printf("[%d:ok]", tstnum++);
1055  else
1056    printf("[%d:err-%d]", tstnum++, rcode);
1057  fflush(stdout);
1058
1059
1060/**/
1061  numflag = 0; wgtflag = 1; nparts = 10;
1062  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1063  options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
1064  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1065                             &nparts, options, &edgecut, part);
1066
1067  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1068    printf("[%d:ok]", tstnum++);
1069  else
1070    printf("[%d:err-%d]", tstnum++, rcode);
1071  fflush(stdout);
1072
1073
1074/**/
1075  numflag = 0; wgtflag = 1; nparts = 10;
1076  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1077  options[0] = 1; options[1] = 5; options[2] = 1; options[3] = 1; options[4] = 0;
1078  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1079                             &nparts, options, &edgecut, part);
1080
1081  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1082    printf("[%d:ok]", tstnum++);
1083  else
1084    printf("[%d:err-%d]", tstnum++, rcode);
1085  fflush(stdout);
1086
1087
1088/**/
1089  numflag = 0; wgtflag = 1; nparts = 10;
1090  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1091  options[0] = 1; options[1] = 6; options[2] = 1; options[3] = 1; options[4] = 0;
1092  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1093                             &nparts, options, &edgecut, part);
1094
1095  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1096    printf("[%d:ok]", tstnum++);
1097  else
1098    printf("[%d:err-%d]", tstnum++, rcode);
1099  fflush(stdout);
1100
1101
1102/**/
1103  numflag = 0; wgtflag = 1; nparts = 10;
1104  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1105  options[0] = 1; options[1] = 7; options[2] = 1; options[3] = 1; options[4] = 0;
1106  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1107                             &nparts, options, &edgecut, part);
1108
1109  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1110    printf("[%d:ok]", tstnum++);
1111  else
1112    printf("[%d:err-%d]", tstnum++, rcode);
1113  fflush(stdout);
1114
1115
1116/**/
1117  numflag = 0; wgtflag = 1; nparts = 10;
1118  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1119  options[0] = 1; options[1] = 8; options[2] = 1; options[3] = 1; options[4] = 0;
1120  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1121                             &nparts, options, &edgecut, part);
1122
1123  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1124    printf("[%d:ok]", tstnum++);
1125  else
1126    printf("[%d:err-%d]", tstnum++, rcode);
1127  fflush(stdout);
1128
1129  printf("\n  ");
1130
1131/**/
1132  numflag = 0; wgtflag = 1; nparts = 10;
1133  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1134  options[0] = 1; options[1] = 4; options[2] = 2; options[3] = 1; options[4] = 0;
1135  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1136                             &nparts, options, &edgecut, part);
1137
1138  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1139    printf("[%d:ok]", tstnum++);
1140  else
1141    printf("[%d:err-%d]", tstnum++, rcode);
1142  fflush(stdout);
1143
1144
1145/**/
1146  numflag = 0; wgtflag = 1; nparts = 10;
1147  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1148  options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
1149  METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1150                             &nparts, options, &edgecut, part);
1151
1152  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1153    printf("[%d:ok]", tstnum++);
1154  else
1155    printf("[%d:err-%d]", tstnum++, rcode);
1156  fflush(stdout);
1157
1158  printf("\n");
1159
1160
1161
1162  printf("\nTesting METIS_mCPartGraphKway ---------------------------------------\n  ");
1163  tstnum = 1;
1164
1165/**/
1166  numflag = 0; wgtflag = 0; nparts = 10;
1167  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1168  options[0] = 0;
1169  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
1170                        &nparts, ubvec, options, &edgecut, part);
1171
1172  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, NULL, nparts, ubvec, edgecut, part)) == 0)
1173    printf("[%d:ok]", tstnum++);
1174  else
1175    printf("[%d:err-%d]", tstnum++, rcode);
1176  fflush(stdout);
1177
1178
1179/**/
1180  numflag = 0; wgtflag = 1; nparts = 10;
1181  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1182  options[0] = 0;
1183  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1184                        &nparts, ubvec, options, &edgecut, part);
1185
1186  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1187    printf("[%d:ok]", tstnum++);
1188  else
1189    printf("[%d:err-%d]", tstnum++, rcode);
1190  fflush(stdout);
1191
1192
1193/**/
1194  numflag = 0; wgtflag = 1; nparts = 10;
1195  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1196  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
1197  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1198                        &nparts, ubvec, options, &edgecut, part);
1199
1200  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1201    printf("[%d:ok]", tstnum++);
1202  else
1203    printf("[%d:err-%d]", tstnum++, rcode);
1204  fflush(stdout);
1205
1206
1207/**/
1208  numflag = 0; wgtflag = 1; nparts = 10;
1209  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1210  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
1211  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1212                        &nparts, ubvec, options, &edgecut, part);
1213
1214  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1215    printf("[%d:ok]", tstnum++);
1216  else
1217    printf("[%d:err-%d]", tstnum++, rcode);
1218  fflush(stdout);
1219
1220
1221/**/
1222  numflag = 0; wgtflag = 1; nparts = 10;
1223  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1224  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
1225  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1226                        &nparts, ubvec, options, &edgecut, part);
1227
1228  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1229    printf("[%d:ok]", tstnum++);
1230  else
1231    printf("[%d:err-%d]", tstnum++, rcode);
1232  fflush(stdout);
1233
1234
1235/**/
1236  numflag = 0; wgtflag = 1; nparts = 10;
1237  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1238  options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
1239  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1240                        &nparts, ubvec, options, &edgecut, part);
1241
1242  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1243    printf("[%d:ok]", tstnum++);
1244  else
1245    printf("[%d:err-%d]", tstnum++, rcode);
1246  fflush(stdout);
1247
1248
1249/**/
1250  numflag = 0; wgtflag = 1; nparts = 10;
1251  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1252  options[0] = 1; options[1] = 5; options[2] = 1; options[3] = 1; options[4] = 0;
1253  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1254                        &nparts, ubvec, options, &edgecut, part);
1255
1256  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1257    printf("[%d:ok]", tstnum++);
1258  else
1259    printf("[%d:err-%d]", tstnum++, rcode);
1260  fflush(stdout);
1261
1262
1263/**/
1264  numflag = 0; wgtflag = 1; nparts = 10;
1265  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1266  options[0] = 1; options[1] = 6; options[2] = 1; options[3] = 1; options[4] = 0;
1267  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1268                        &nparts, ubvec, options, &edgecut, part);
1269
1270  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1271    printf("[%d:ok]", tstnum++);
1272  else
1273    printf("[%d:err-%d]", tstnum++, rcode);
1274  fflush(stdout);
1275
1276
1277/**/
1278  numflag = 0; wgtflag = 1; nparts = 10;
1279  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1280  options[0] = 1; options[1] = 7; options[2] = 1; options[3] = 1; options[4] = 0;
1281  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1282                        &nparts, ubvec, options, &edgecut, part);
1283
1284  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1285    printf("[%d:ok]", tstnum++);
1286  else
1287    printf("[%d:err-%d]", tstnum++, rcode);
1288  fflush(stdout);
1289
1290
1291/**/
1292  numflag = 0; wgtflag = 1; nparts = 10;
1293  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1294  options[0] = 1; options[1] = 8; options[2] = 1; options[3] = 1; options[4] = 0;
1295  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1296                        &nparts, ubvec, options, &edgecut, part);
1297
1298  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1299    printf("[%d:ok]", tstnum++);
1300  else
1301    printf("[%d:err-%d]", tstnum++, rcode);
1302  fflush(stdout);
1303
1304  printf("\n  ");
1305
1306/**/
1307  numflag = 0; wgtflag = 1; nparts = 10;
1308  ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1309  options[0] = 1; options[1] = 6; options[2] = 2; options[3] = 1; options[4] = 0;
1310  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1311                        &nparts, ubvec, options, &edgecut, part);
1312
1313  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1314    printf("[%d:ok]", tstnum++);
1315  else
1316    printf("[%d:err-%d]", tstnum++, rcode);
1317  fflush(stdout);
1318
1319
1320/**/
1321  numflag = 0; wgtflag = 1; nparts = 10;
1322  ubvec[0] = 1.05; ubvec[1] = 1.5; ubvec[2] = 1.05;
1323  options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
1324  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1325                        &nparts, ubvec, options, &edgecut, part);
1326
1327  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1328    printf("[%d:ok]", tstnum++);
1329  else
1330    printf("[%d:err-%d]", tstnum++, rcode);
1331  fflush(stdout);
1332
1333
1334/**/
1335  numflag = 0; wgtflag = 1; nparts = 10;
1336  ubvec[0] = 1.05; ubvec[1] = 1.5; ubvec[2] = 1.5;
1337  options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
1338  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1339                        &nparts, ubvec, options, &edgecut, part);
1340
1341  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1342    printf("[%d:ok]", tstnum++);
1343  else
1344    printf("[%d:err-%d]", tstnum++, rcode);
1345  fflush(stdout);
1346
1347
1348/**/
1349  numflag = 0; wgtflag = 1; nparts = 10;
1350  ubvec[0] = 2.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
1351  options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
1352  METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
1353                        &nparts, ubvec, options, &edgecut, part);
1354
1355  if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
1356    printf("[%d:ok]", tstnum++);
1357  else
1358    printf("[%d:err-%d]", tstnum++, rcode);
1359  fflush(stdout);
1360
1361
1362  printf("\n");
1363
1364  GKfree(&vwgt, &adjwgt, &part, LTERM);
1365}
1366
1367
1368
1369/*************************************************************************
1370* This function verifies that the partitioning was computed correctly
1371**************************************************************************/
1372int VerifyPartmC(int nvtxs, int ncon, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
1373               idxtype *adjwgt, int nparts, float *ubvec, int edgecut, idxtype *part)
1374{
1375  int i, j, k, cut, efree=0, rcode=0;
1376  idxtype *pwgts;
1377  float lb;
1378
1379  if (part[idxamax(nvtxs, part)] != nparts-1)
1380    return 1;  /* the total number of partitions is different than nparts */
1381
1382  if (adjwgt == NULL) {
1383    efree = 1;
1384    adjwgt = idxsmalloc(xadj[nvtxs], 1, "adjwgt");
1385  }
1386  pwgts = idxsmalloc(ncon*nparts, 0, "pwgts");
1387
1388  for (cut=0, i=0; i<nvtxs; i++) {
1389    for (j=0; j<ncon; j++)
1390      pwgts[part[i]*ncon+j] += vwgt[i*ncon+j];
1391    for (j=xadj[i]; j<xadj[i+1]; j++) 
1392      cut += (part[i] != part[adjncy[j]] ? adjwgt[j] : 0);
1393  }
1394
1395  if (cut != 2*edgecut)
1396    rcode = 2;
1397
1398/*
1399printf("\n");
1400for (i=0; i<nparts; i++) {
1401  for (j=0; j<ncon; j++)
1402    printf("%5d ", pwgts[i*ncon+j]);
1403  printf("\n");
1404}
1405printf("---------------------------------\n");
1406for (j=0; j<ncon; j++)
1407  printf("%5d ", idxsum_strd(nparts, pwgts+j, ncon));
1408printf("\n---------------------------------\n");
1409for (j=0; j<ncon; j++)
1410  printf("%5d ", pwgts[ncon*idxamax_strd(nparts, pwgts+j, ncon)+j]);
1411printf("\n%d %d\n", idxsum(ncon*nvtxs, vwgt), idxsum(ncon*nparts, pwgts));
1412*/
1413
1414  for (i=0; i<ncon; i++) {
1415    lb = 1.0*nparts*pwgts[ncon*idxamax_strd(nparts, pwgts+i, ncon)+i]/(1.0*idxsum_strd(nparts, pwgts+i, ncon));
1416    /*printf("[%3.2f]", lb);*/
1417    if (lb > ubvec[i])
1418      rcode = 3;
1419  }
1420
1421
1422  if (efree)
1423    free(adjwgt);
1424
1425  free(pwgts);
1426
1427  MALLOC_CHECK(NULL);
1428
1429  return rcode;
1430}
1431
1432
1433/*************************************************************************
1434* This function tests the regular graph partitioning routines
1435**************************************************************************/
1436void Test_ND(int nvtxs, idxtype *xadj, idxtype *adjncy)
1437{
1438  int i, j, jj, k, tstnum, rcode;
1439  int numflag, wgtflag, options[10];
1440  idxtype *perm, *iperm, *vwgt;
1441
1442  vwgt = idxmalloc(nvtxs, "vwgt");
1443  for (i=0; i<nvtxs; i++)
1444    vwgt[i] = 1+RandomInRange(10);
1445
1446
1447  perm = idxmalloc(nvtxs, "perm");
1448  iperm = idxmalloc(nvtxs, "iperm");
1449
1450
1451
1452  /*===========================================================================*/
1453  printf("\nTesting METIS_EdgeND ------------------------------------------------\n  ");
1454  tstnum = 1;
1455
1456/**/
1457  numflag = 0; 
1458  options[0] = 0;
1459  METIS_EdgeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1460
1461  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1462    printf("[%d:ok]", tstnum++);
1463  else
1464    printf("[%d:err-%d]", tstnum++, rcode);
1465  fflush(stdout);
1466
1467
1468/**/
1469  numflag = 0; 
1470  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
1471  METIS_EdgeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1472
1473  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1474    printf("[%d:ok]", tstnum++);
1475  else
1476    printf("[%d:err-%d]", tstnum++, rcode);
1477  fflush(stdout);
1478
1479
1480/**/
1481  numflag = 0; 
1482  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
1483  METIS_EdgeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1484
1485  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1486    printf("[%d:ok]", tstnum++);
1487  else
1488    printf("[%d:err-%d]", tstnum++, rcode);
1489  fflush(stdout);
1490
1491  printf("\n");
1492
1493
1494
1495  /*===========================================================================*/
1496  printf("\nTesting METIS_NodeND ------------------------------------------------\n  ");
1497  tstnum = 1;
1498
1499/**/
1500  numflag = 0; 
1501  options[0] = 0;
1502  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1503
1504  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1505    printf("[%d:ok]", tstnum++);
1506  else
1507    printf("[%d:err-%d]", tstnum++, rcode);
1508  fflush(stdout);
1509
1510
1511/**/
1512  numflag = 0; 
1513  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
1514  options[5] = 0; options[6] = 0; options[7] = 1;
1515  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1516
1517  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1518    printf("[%d:ok]", tstnum++);
1519  else
1520    printf("[%d:err-%d]", tstnum++, rcode);
1521  fflush(stdout);
1522
1523
1524/**/
1525  numflag = 0; 
1526  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0; 
1527  options[5] = 0; options[6] = 0; options[7] = 1;
1528  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1529
1530  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1531    printf("[%d:ok]", tstnum++);
1532  else
1533    printf("[%d:err-%d]", tstnum++, rcode);
1534  fflush(stdout);
1535
1536
1537/**/
1538  numflag = 0; 
1539  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
1540  options[5] = 0; options[6] = 0; options[7] = 1;
1541  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1542
1543  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1544    printf("[%d:ok]", tstnum++);
1545  else
1546    printf("[%d:err-%d]", tstnum++, rcode);
1547  fflush(stdout);
1548
1549
1550/**/
1551  numflag = 0; 
1552  options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
1553  options[5] = 0; options[6] = 0; options[7] = 1;
1554  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1555
1556  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1557    printf("[%d:ok]", tstnum++);
1558  else
1559    printf("[%d:err-%d]", tstnum++, rcode);
1560  fflush(stdout);
1561
1562
1563/**/
1564  numflag = 0; 
1565  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1566  options[5] = 0; options[6] = 0; options[7] = 1;
1567  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1568
1569  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1570    printf("[%d:ok]", tstnum++);
1571  else
1572    printf("[%d:err-%d]", tstnum++, rcode);
1573  fflush(stdout);
1574
1575
1576/**/
1577  numflag = 0; 
1578  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1579  options[5] = 1; options[6] = 0; options[7] = 1;
1580  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1581
1582  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1583    printf("[%d:ok]", tstnum++);
1584  else
1585    printf("[%d:err-%d]", tstnum++, rcode);
1586  fflush(stdout);
1587
1588
1589/**/
1590  numflag = 0; 
1591  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1592  options[5] = 2; options[6] = 0; options[7] = 1;
1593  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1594
1595  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1596    printf("[%d:ok]", tstnum++);
1597  else
1598    printf("[%d:err-%d]", tstnum++, rcode);
1599  fflush(stdout);
1600
1601
1602/**/
1603  numflag = 0; 
1604  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1605  options[5] = 3; options[6] = 0; options[7] = 1;
1606  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1607
1608  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1609    printf("[%d:ok]", tstnum++);
1610  else
1611    printf("[%d:err-%d]", tstnum++, rcode);
1612  fflush(stdout);
1613
1614
1615/**/
1616  numflag = 0; 
1617  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1618  options[5] = 3; options[6] = 40; options[7] = 1;
1619  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1620
1621  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1622    printf("[%d:ok]", tstnum++);
1623  else
1624    printf("[%d:err-%d]", tstnum++, rcode);
1625  fflush(stdout);
1626
1627  printf("\n  ");
1628
1629/**/
1630  numflag = 0; 
1631  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1632  options[5] = 3; options[6] = 20; options[7] = 1;
1633  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1634
1635  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1636    printf("[%d:ok]", tstnum++);
1637  else
1638    printf("[%d:err-%d]", tstnum++, rcode);
1639  fflush(stdout);
1640
1641
1642/**/
1643  numflag = 0; 
1644  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1645  options[5] = 3; options[6] = 20; options[7] = 2;
1646  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1647
1648  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1649    printf("[%d:ok]", tstnum++);
1650  else
1651    printf("[%d:err-%d]", tstnum++, rcode);
1652  fflush(stdout);
1653
1654
1655/**/
1656  numflag = 0; 
1657  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1658  options[5] = 0; options[6] = 0; options[7] = 2;
1659  METIS_NodeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
1660
1661  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1662    printf("[%d:ok]", tstnum++);
1663  else
1664    printf("[%d:err-%d]", tstnum++, rcode);
1665  fflush(stdout);
1666
1667  printf("\n");
1668
1669
1670
1671  /*===========================================================================*/
1672  printf("\nTesting METIS_NodeWND -----------------------------------------------\n  ");
1673  tstnum = 1;
1674
1675/**/
1676  numflag = 0; 
1677  options[0] = 0;
1678  METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
1679
1680  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1681    printf("[%d:ok]", tstnum++);
1682  else
1683    printf("[%d:err-%d]", tstnum++, rcode);
1684  fflush(stdout);
1685
1686
1687/**/
1688  numflag = 0; 
1689  options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
1690  METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
1691
1692  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1693    printf("[%d:ok]", tstnum++);
1694  else
1695    printf("[%d:err-%d]", tstnum++, rcode);
1696  fflush(stdout);
1697
1698
1699/**/
1700  numflag = 0; 
1701  options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0; 
1702  METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
1703
1704  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1705    printf("[%d:ok]", tstnum++);
1706  else
1707    printf("[%d:err-%d]", tstnum++, rcode);
1708  fflush(stdout);
1709
1710
1711/**/
1712  numflag = 0; 
1713  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
1714  METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
1715
1716  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1717    printf("[%d:ok]", tstnum++);
1718  else
1719    printf("[%d:err-%d]", tstnum++, rcode);
1720  fflush(stdout);
1721
1722
1723/**/
1724  numflag = 0; 
1725  options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
1726  METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
1727
1728  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1729    printf("[%d:ok]", tstnum++);
1730  else
1731    printf("[%d:err-%d]", tstnum++, rcode);
1732  fflush(stdout);
1733
1734
1735/**/
1736  numflag = 0; 
1737  options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
1738  METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
1739
1740  if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
1741    printf("[%d:ok]", tstnum++);
1742  else
1743    printf("[%d:err-%d]", tstnum++, rcode);
1744  fflush(stdout);
1745
1746  printf("\n");
1747
1748
1749  GKfree(&vwgt, &perm, &iperm, LTERM);
1750}
1751
1752
1753
1754/*************************************************************************
1755* This function verifies that the partitioning was computed correctly
1756**************************************************************************/
1757int VerifyND(int nvtxs, idxtype *perm, idxtype *iperm)
1758{
1759  int i, j, k, rcode=0;
1760
1761  for (i=0; i<nvtxs; i++) {
1762    if (i != perm[iperm[i]])
1763      rcode = 1;
1764  }
1765
1766  for (i=0; i<nvtxs; i++) {
1767    if (i != iperm[perm[i]])
1768      rcode = 2;
1769  }
1770
1771  MALLOC_CHECK(NULL);
1772
1773  return rcode;
1774}
1775
1776
Note: See TracBrowser for help on using the repository browser.