You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1771 lines
55 KiB
1771 lines
55 KiB
/*
|
|
* Copyright 1997, Regents of the University of Minnesota
|
|
*
|
|
* mtest.c
|
|
*
|
|
* This file is a comprehensive tester for all the graph partitioning/ordering
|
|
* routines of METIS
|
|
*
|
|
* Started 9/18/98
|
|
* George
|
|
*
|
|
* $Id: mtest.c,v 1.1 2002/08/10 04:34:53 karypis Exp $
|
|
*
|
|
*/
|
|
|
|
#include <metislib.h>
|
|
#include "../libmetis/proto.h"
|
|
#include "proto.h"
|
|
|
|
|
|
|
|
/*************************************************************************
|
|
* Let the game begin
|
|
**************************************************************************/
|
|
int main(int argc, char *argv[])
|
|
{
|
|
graph_t *graph;
|
|
|
|
if (argc != 2) {
|
|
printf("Usage: %s <GraphFile>\n",argv[0]);
|
|
exit(0);
|
|
}
|
|
|
|
graph = ReadGraph(argv[1], &wgtflag);
|
|
|
|
printf("**********************************************************************\n");
|
|
printf("%s", METISTITLE);
|
|
printf("Graph Information ---------------------------------------------------\n");
|
|
printf(" Name: %s, #Vertices: %"PRIDX", #Edges: %"PRIDX"\n", argv[1], graph.nvtxs, graph.nedges/2);
|
|
|
|
Test_PartGraph(graph.nvtxs, graph.xadj, graph.adjncy);
|
|
|
|
Test_PartGraphV(graph.nvtxs, graph.xadj, graph.adjncy);
|
|
|
|
Test_PartGraphmC(graph.nvtxs, graph.xadj, graph.adjncy);
|
|
|
|
Test_ND(graph.nvtxs, graph.xadj, graph.adjncy);
|
|
|
|
printf("\n---------------------------------------------------------------------\n");
|
|
printf(" Testing completed.\n");
|
|
printf("**********************************************************************\n");
|
|
|
|
gk_free((void **)&graph.xadj, &graph.adjncy, &graph.vwgt, &graph.adjwgt, LTERM);
|
|
}
|
|
|
|
|
|
|
|
/*************************************************************************
|
|
* This function tests the regular graph partitioning routines
|
|
**************************************************************************/
|
|
void Test_PartGraph(idx_t nvtxs, idx_t *xadj, idx_t *adjncy)
|
|
{
|
|
idx_t i, j, jj, k, tstnum, rcode;
|
|
idx_t nparts, numflag, wgtflag, edgecut, options[METIS_NOPTIONS];
|
|
idx_t *part, *vwgt, *adjwgt;
|
|
real_t tpwgts[256];
|
|
|
|
vwgt = imalloc(nvtxs, "vwgt");
|
|
for (i=0; i<nvtxs; i++)
|
|
vwgt[i] = RandomInRange(10);
|
|
|
|
adjwgt = imalloc(xadj[nvtxs], "adjwgt");
|
|
for (i=0; i<nvtxs; i++) {
|
|
for (j=xadj[i]; j<xadj[i+1]; j++) {
|
|
k = adjncy[j];
|
|
if (i < k) {
|
|
adjwgt[j] = 1+RandomInRange(5);
|
|
for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
|
|
if (adjncy[jj] == i) {
|
|
adjwgt[jj] = adjwgt[j];
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
part = imalloc(nvtxs, "part");
|
|
|
|
tpwgts[0] = .1;
|
|
tpwgts[1] = .2;
|
|
tpwgts[2] = .3;
|
|
tpwgts[3] = .1;
|
|
tpwgts[4] = .05;
|
|
tpwgts[5] = .25;
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_PartGraphRecursive ------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 2; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_PartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_WPartGraphRecursive -----------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 2; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_WPartGraphRecursive(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_PartGraphKway -----------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 2; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 3; options[4] = 0;
|
|
METIS_PartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_WPartGraphKway ----------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, NULL, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, NULL, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, NULL, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 2; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, NULL, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 3; options[4] = 0;
|
|
METIS_WPartGraphKway(&nvtxs, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyWPart(nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
gk_free((void **)&vwgt, &adjwgt, &part, LTERM);
|
|
}
|
|
|
|
|
|
|
|
/*************************************************************************
|
|
* This function verifies that the partitioning was computed correctly
|
|
**************************************************************************/
|
|
int VerifyPart(idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
|
|
idx_t *adjwgt, idx_t nparts, idx_t edgecut, idx_t *part)
|
|
{
|
|
idx_t i, j, k, cut, vfree=0, efree=0, rcode=0;
|
|
idx_t *pwgts;
|
|
|
|
if (part[iargmax(nvtxs, part)] != nparts-1)
|
|
return 1; /* the total number of partitions is different than nparts */
|
|
|
|
/* compute the cut and the pwgts */
|
|
if (vwgt == NULL) {
|
|
vfree = 1;
|
|
vwgt = ismalloc(nvtxs, 1, "vwgt");
|
|
}
|
|
if (adjwgt == NULL) {
|
|
efree = 1;
|
|
adjwgt = ismalloc(xadj[nvtxs], 1, "adjwgt");
|
|
}
|
|
pwgts = ismalloc(nparts, 0, "pwgts");
|
|
|
|
for (cut=0, i=0; i<nvtxs; i++) {
|
|
pwgts[part[i]] += vwgt[i];
|
|
for (j=xadj[i]; j<xadj[i+1]; j++)
|
|
cut += (part[i] != part[adjncy[j]] ? adjwgt[j] : 0);
|
|
}
|
|
|
|
if (cut != 2*edgecut)
|
|
rcode = 2;
|
|
|
|
if (nparts*pwgts[iargmax(nparts, pwgts)] > 1.10*isum(nparts, pwgts, 1))
|
|
rcode = 3;
|
|
|
|
if (vfree)
|
|
gk_free((void **)&vwgt, LTERM);
|
|
|
|
if (efree)
|
|
gk_free((void **)&adjwgt, LTERM);
|
|
|
|
gk_free((void **)&pwgts, LTERM);
|
|
|
|
MALLOC_CHECK(NULL);
|
|
|
|
return rcode;
|
|
}
|
|
|
|
|
|
/*************************************************************************
|
|
* This function verifies that the partitioning was computed correctly
|
|
**************************************************************************/
|
|
int VerifyWPart(idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
|
|
idx_t *adjwgt, idx_t nparts, real_t *tpwgts, idx_t edgecut, idx_t *part)
|
|
{
|
|
idx_t i, j, k, tvwgt, cut, vfree=0, efree=0, rcode=0;
|
|
idx_t *pwgts;
|
|
|
|
if (part[iargmax(nvtxs, part)] != nparts-1)
|
|
return 1; /* the total number of partitions is different than nparts */
|
|
|
|
/* compute the cut and the pwgts */
|
|
if (vwgt == NULL) {
|
|
vfree = 1;
|
|
vwgt = ismalloc(nvtxs, 1, "vwgt");
|
|
}
|
|
if (adjwgt == NULL) {
|
|
efree = 1;
|
|
adjwgt = ismalloc(xadj[nvtxs], 1, "adjwgt");
|
|
}
|
|
pwgts = ismalloc(nparts, 0, "pwgts");
|
|
|
|
for (cut=0, i=0; i<nvtxs; i++) {
|
|
pwgts[part[i]] += vwgt[i];
|
|
for (j=xadj[i]; j<xadj[i+1]; j++)
|
|
cut += (part[i] != part[adjncy[j]] ? adjwgt[j] : 0);
|
|
}
|
|
|
|
if (cut != 2*edgecut)
|
|
rcode = 2;
|
|
|
|
tvwgt = isum(nparts, pwgts, 1);
|
|
for (i=0; i<nparts; i++) {
|
|
if (pwgts[i] > 1.10*tpwgts[i]*tvwgt) {
|
|
rcode = 3;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (vfree)
|
|
gk_free((void **)&vwgt, LTERM);
|
|
|
|
if (efree)
|
|
gk_free((void **)&adjwgt, LTERM);
|
|
|
|
gk_free((void **)&pwgts, LTERM);
|
|
|
|
MALLOC_CHECK(NULL);
|
|
|
|
return rcode;
|
|
}
|
|
|
|
|
|
|
|
/*************************************************************************
|
|
* This function tests the regular graph partitioning routines
|
|
**************************************************************************/
|
|
void Test_PartGraphV(idx_t nvtxs, idx_t *xadj, idx_t *adjncy)
|
|
{
|
|
idx_t i, j, jj, k, tstnum, rcode;
|
|
idx_t nparts, numflag, wgtflag, totalv, options[10];
|
|
idx_t *part, *vwgt, *vsize;
|
|
real_t tpwgts[256];
|
|
|
|
vwgt = imalloc(nvtxs, "vwgt");
|
|
for (i=0; i<nvtxs; i++)
|
|
vwgt[i] = RandomInRange(10);
|
|
|
|
vsize = imalloc(nvtxs, "vsize");
|
|
for (i=0; i<nvtxs; i++)
|
|
vsize[i] = RandomInRange(10);
|
|
|
|
part = imalloc(nvtxs, "part");
|
|
|
|
tpwgts[0] = .1;
|
|
tpwgts[1] = .2;
|
|
tpwgts[2] = .3;
|
|
tpwgts[3] = .1;
|
|
tpwgts[4] = .05;
|
|
tpwgts[5] = .25;
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_PartGraphVKway ----------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphVKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
|
|
&nparts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, NULL, NULL, nparts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphVKway(&nvtxs, xadj, adjncy, NULL, vsize, &wgtflag, &numflag,
|
|
&nparts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, NULL, vsize, nparts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 2; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, NULL, nparts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 0;
|
|
METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 20;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 3; options[4] = 0;
|
|
METIS_PartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_WPartGraphVKway ---------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, NULL, NULL, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, NULL, NULL, nparts, tpwgts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, NULL, vsize, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, NULL, vsize, nparts, tpwgts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 2; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, NULL, nparts, tpwgts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 0;
|
|
METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 3; nparts = 6;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 3; options[4] = 0;
|
|
METIS_WPartGraphVKway(&nvtxs, xadj, adjncy, vwgt, vsize, &wgtflag, &numflag,
|
|
&nparts, tpwgts, options, &totalv, part);
|
|
|
|
if ((rcode = VerifyWPartV(nvtxs, xadj, adjncy, vwgt, vsize, nparts, tpwgts, totalv, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
gk_free((void **)&vwgt, &vsize, &part, LTERM);
|
|
}
|
|
|
|
|
|
/*************************************************************************
|
|
* This function verifies that the partitioning was computed correctly
|
|
**************************************************************************/
|
|
int VerifyPartV(idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
|
|
idx_t *vsize, idx_t nparts, idx_t totalv, idx_t *part)
|
|
{
|
|
idx_t i, j, k, ttlv, vfree=0, efree=0, rcode=0;
|
|
idx_t *pwgts, *marker;
|
|
|
|
if (part[iargmax(nvtxs, part)] != nparts-1)
|
|
return 1; /* the total number of partitions is different than nparts */
|
|
|
|
/* compute the cut and the pwgts */
|
|
if (vwgt == NULL) {
|
|
vfree = 1;
|
|
vwgt = ismalloc(nvtxs, 1, "vwgt");
|
|
}
|
|
if (vsize == NULL) {
|
|
efree = 1;
|
|
vsize = ismalloc(nvtxs, 1, "vsize");
|
|
}
|
|
pwgts = ismalloc(nparts, 0, "pwgts");
|
|
|
|
marker = ismalloc(nparts, -1, "htable");
|
|
for (ttlv=0, i=0; i<nvtxs; i++) {
|
|
pwgts[part[i]] += vwgt[i];
|
|
marker[part[i]] = i;
|
|
for (j=xadj[i]; j<xadj[i+1]; j++) {
|
|
if (marker[part[adjncy[j]]] != i) {
|
|
ttlv += vsize[i];
|
|
marker[part[adjncy[j]]] = i;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (ttlv != totalv)
|
|
rcode = 2;
|
|
|
|
if (nparts*pwgts[iargmax(nparts, pwgts)] > 1.05*isum(nparts, pwgts, 1))
|
|
rcode = 3;
|
|
|
|
if (vfree)
|
|
gk_free((void **)&vwgt, LTERM);
|
|
|
|
if (efree)
|
|
gk_free((void **)&vsize, LTERM);
|
|
|
|
gk_free((void **)&pwgts, &marker, LTERM);
|
|
|
|
MALLOC_CHECK(NULL);
|
|
|
|
return rcode;
|
|
}
|
|
|
|
|
|
/*************************************************************************
|
|
* This function verifies that the partitioning was computed correctly
|
|
**************************************************************************/
|
|
int VerifyWPartV(idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
|
|
idx_t *vsize, idx_t nparts, real_t *tpwgts, idx_t totalv,
|
|
idx_t *part)
|
|
{
|
|
idx_t i, j, k, tvwgt, ttlv, vfree=0, efree=0, rcode=0;
|
|
idx_t *pwgts, *marker;
|
|
|
|
if (part[iargmax(nvtxs, part)] != nparts-1)
|
|
return 1; /* the total number of partitions is different than nparts */
|
|
|
|
/* compute the cut and the pwgts */
|
|
if (vwgt == NULL) {
|
|
vfree = 1;
|
|
vwgt = ismalloc(nvtxs, 1, "vwgt");
|
|
}
|
|
if (vsize == NULL) {
|
|
efree = 1;
|
|
vsize = ismalloc(nvtxs, 1, "vsize");
|
|
}
|
|
pwgts = ismalloc(nparts, 0, "pwgts");
|
|
|
|
marker = ismalloc(nparts, -1, "htable");
|
|
for (ttlv=0, i=0; i<nvtxs; i++) {
|
|
pwgts[part[i]] += vwgt[i];
|
|
marker[part[i]] = i;
|
|
for (j=xadj[i]; j<xadj[i+1]; j++) {
|
|
if (marker[part[adjncy[j]]] != i) {
|
|
ttlv += vsize[i];
|
|
marker[part[adjncy[j]]] = i;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (ttlv != totalv)
|
|
rcode = 2;
|
|
|
|
tvwgt = isum(nparts, pwgts, 1);
|
|
for (i=0; i<nparts; i++) {
|
|
if (pwgts[i] > 1.05*tpwgts[i]*tvwgt) {
|
|
rcode = 3;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (vfree)
|
|
gk_free((void **)&vwgt, LTERM);
|
|
|
|
if (efree)
|
|
gk_free((void **)&vsize, LTERM);
|
|
|
|
gk_free((void **)&pwgts, &marker, LTERM);
|
|
|
|
MALLOC_CHECK(NULL);
|
|
|
|
return rcode;
|
|
}
|
|
|
|
|
|
|
|
/*************************************************************************
|
|
* This function tests the regular graph partitioning routines
|
|
**************************************************************************/
|
|
void Test_PartGraphmC(idx_t nvtxs, idx_t *xadj, idx_t *adjncy)
|
|
{
|
|
idx_t i, j, jj, k, tstnum, rcode;
|
|
idx_t nparts, ncon, numflag, wgtflag, edgecut, options[10];
|
|
idx_t *part, *vwgt, *adjwgt;
|
|
real_t ubvec[MAXNCON];
|
|
|
|
ncon = 3;
|
|
|
|
vwgt = imalloc(nvtxs*ncon, "vwgt");
|
|
for (i=0; i<ncon*nvtxs; i++)
|
|
vwgt[i] = RandomInRange(10);
|
|
|
|
adjwgt = imalloc(xadj[nvtxs], "adjwgt");
|
|
for (i=0; i<nvtxs; i++) {
|
|
for (j=xadj[i]; j<xadj[i+1]; j++) {
|
|
k = adjncy[j];
|
|
if (i < k) {
|
|
adjwgt[j] = 1+RandomInRange(5);
|
|
for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
|
|
if (adjncy[jj] == i) {
|
|
adjwgt[jj] = adjwgt[j];
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
part = imalloc(nvtxs, "part");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_mCPartGraphRecursive ----------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, NULL, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 5; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 6; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 7; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 8; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n ");
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 4; options[2] = 2; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
|
|
printf("\nTesting METIS_mCPartGraphKway ---------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 0; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, NULL, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, NULL, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 5; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 6; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 7; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 8; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n ");
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 6; options[2] = 2; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.5; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 1.05; ubvec[1] = 1.5; ubvec[2] = 1.5;
|
|
options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0; wgtflag = 1; nparts = 10;
|
|
ubvec[0] = 2.05; ubvec[1] = 1.05; ubvec[2] = 1.05;
|
|
options[0] = 1; options[1] = 4; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_mCPartGraphKway(&nvtxs, &ncon, xadj, adjncy, vwgt, adjwgt, &wgtflag, &numflag,
|
|
&nparts, ubvec, options, &edgecut, part);
|
|
|
|
if ((rcode = VerifyPartmC(nvtxs, ncon, xadj, adjncy, vwgt, adjwgt, nparts, ubvec, edgecut, part)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
printf("\n");
|
|
|
|
gk_free((void **)&vwgt, &adjwgt, &part, LTERM);
|
|
}
|
|
|
|
|
|
|
|
/*************************************************************************
|
|
* This function verifies that the partitioning was computed correctly
|
|
**************************************************************************/
|
|
int VerifyPartmC(idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
|
|
idx_t *adjwgt, idx_t nparts, real_t *ubvec, idx_t edgecut, idx_t *part)
|
|
{
|
|
idx_t i, j, k, cut, efree=0, rcode=0;
|
|
idx_t *pwgts;
|
|
real_t lb;
|
|
|
|
if (part[iargmax(nvtxs, part)] != nparts-1)
|
|
return 1; /* the total number of partitions is different than nparts */
|
|
|
|
if (adjwgt == NULL) {
|
|
efree = 1;
|
|
adjwgt = ismalloc(xadj[nvtxs], 1, "adjwgt");
|
|
}
|
|
pwgts = ismalloc(ncon*nparts, 0, "pwgts");
|
|
|
|
for (cut=0, i=0; i<nvtxs; i++) {
|
|
for (j=0; j<ncon; j++)
|
|
pwgts[part[i]*ncon+j] += vwgt[i*ncon+j];
|
|
for (j=xadj[i]; j<xadj[i+1]; j++)
|
|
cut += (part[i] != part[adjncy[j]] ? adjwgt[j] : 0);
|
|
}
|
|
|
|
if (cut != 2*edgecut)
|
|
rcode = 2;
|
|
|
|
/*
|
|
printf("\n");
|
|
for (i=0; i<nparts; i++) {
|
|
for (j=0; j<ncon; j++)
|
|
printf("%5"PRIDX" ", pwgts[i*ncon+j]);
|
|
printf("\n");
|
|
}
|
|
printf("---------------------------------\n");
|
|
for (j=0; j<ncon; j++)
|
|
printf("%5"PRIDX" ", isum(nparts, pwgts+j, ncon));
|
|
printf("\n---------------------------------\n");
|
|
for (j=0; j<ncon; j++)
|
|
printf("%5"PRIDX" ", pwgts[ncon*iargmax_strd(nparts, pwgts+j, ncon)+j]);
|
|
printf("\n%"PRIDX" %"PRIDX"\n", isum(ncon*nvtxs, vwgt, 1), isum(ncon*nparts, pwgts, 1));
|
|
*/
|
|
|
|
for (i=0; i<ncon; i++) {
|
|
lb = 1.0*nparts*pwgts[ncon*iargmax_strd(nparts, pwgts+i, ncon)+i]/(1.0*isum(nparts, pwgts+i, ncon));
|
|
/*printf("[%3.2"PRREAL"]", lb);*/
|
|
if (lb > ubvec[i])
|
|
rcode = 3;
|
|
}
|
|
|
|
|
|
if (efree)
|
|
gk_free((void **)&adjwgt, LTERM);
|
|
|
|
gk_free((void **)&pwgts, LTERM);
|
|
|
|
MALLOC_CHECK(NULL);
|
|
|
|
return rcode;
|
|
}
|
|
|
|
|
|
/*************************************************************************
|
|
* This function tests the regular graph partitioning routines
|
|
**************************************************************************/
|
|
void Test_ND(idx_t nvtxs, idx_t *xadj, idx_t *adjncy)
|
|
{
|
|
idx_t i, j, jj, k, tstnum, rcode;
|
|
idx_t numflag, wgtflag, options[10];
|
|
idx_t *perm, *iperm, *vwgt;
|
|
|
|
vwgt = imalloc(nvtxs, "vwgt");
|
|
for (i=0; i<nvtxs; i++)
|
|
vwgt[i] = 1+RandomInRange(10);
|
|
|
|
|
|
perm = imalloc(nvtxs, "perm");
|
|
iperm = imalloc(nvtxs, "iperm");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_EdgeND ------------------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 0;
|
|
METIS_EdgeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_EdgeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_EdgeND(&nvtxs, xadj, adjncy, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_NodeND ------------------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 0;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
options[5] = 0; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
options[5] = 0; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
options[5] = 0; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
|
|
options[5] = 0; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 0; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 1; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 2; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 3; options[6] = 0; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 3; options[6] = 40; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n ");
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 3; options[6] = 20; options[7] = 1;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 3; options[6] = 20; options[7] = 2;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
options[5] = 0; options[6] = 0; options[7] = 2;
|
|
METIS_NodeND(&nvtxs, xadj, adjncy, NULL, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
|
|
/*===========================================================================*/
|
|
printf("\nTesting METIS_NodeWND -----------------------------------------------\n ");
|
|
tstnum = 1;
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 0;
|
|
METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 1; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 2; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 1; options[4] = 0;
|
|
METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 2; options[3] = 1; options[4] = 0;
|
|
METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
|
|
/**/
|
|
numflag = 0;
|
|
options[0] = 1; options[1] = 3; options[2] = 1; options[3] = 2; options[4] = 0;
|
|
METIS_NodeWND(&nvtxs, xadj, adjncy, vwgt, &numflag, options, perm, iperm);
|
|
|
|
if ((rcode = VerifyND(nvtxs, perm, iperm)) == 0)
|
|
printf("[%"PRIDX":ok]", tstnum++);
|
|
else
|
|
printf("[%"PRIDX":err-%"PRIDX"]", tstnum++, rcode);
|
|
fflush(stdout);
|
|
|
|
printf("\n");
|
|
|
|
|
|
gk_free((void **)&vwgt, &perm, &iperm, LTERM);
|
|
}
|
|
|
|
|
|
/*************************************************************************
|
|
* This function verifies that the partitioning was computed correctly
|
|
**************************************************************************/
|
|
int VerifyND(idx_t nvtxs, idx_t *perm, idx_t *iperm)
|
|
{
|
|
idx_t i, j, k, rcode=0;
|
|
|
|
for (i=0; i<nvtxs; i++) {
|
|
if (i != perm[iperm[i]])
|
|
rcode = 1;
|
|
}
|
|
|
|
for (i=0; i<nvtxs; i++) {
|
|
if (i != iperm[perm[i]])
|
|
rcode = 2;
|
|
}
|
|
|
|
MALLOC_CHECK(NULL);
|
|
|
|
return rcode;
|
|
}
|
|
|
|
|
|
|