00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "metisbin.h"
00016
00017
00018
00019
00021
00022 graph_t *ReadGraph(params_t *params)
00023 {
00024 idx_t i, j, k, l, fmt, ncon, nfields, readew, readvw, readvs, edge, ewgt;
00025 idx_t *xadj, *adjncy, *vwgt, *adjwgt, *vsize;
00026 char *line=NULL, fmtstr[256], *curstr, *newstr;
00027 size_t lnlen=0;
00028 FILE *fpin;
00029 graph_t *graph;
00030
00031 if (!gk_fexists(params->filename))
00032 errexit("File %s does not exist!\n", params->filename);
00033
00034 graph = CreateGraph();
00035
00036 fpin = gk_fopen(params->filename, "r", "ReadGRaph: Graph");
00037
00038
00039 do {
00040 if (gk_getline(&line, &lnlen, fpin) == -1)
00041 errexit("Premature end of input file: file: %s\n", params->filename);
00042 } while (line[0] == '%');
00043
00044
00045 fmt = ncon = 0;
00046 nfields = sscanf(line, "%"SCIDX" %"SCIDX" %"SCIDX" %"SCIDX,
00047 &(graph->nvtxs), &(graph->nedges), &fmt, &ncon);
00048
00049 if (nfields < 2)
00050 errexit("The input file does not specify the number of vertices and edges.\n");
00051
00052 if (graph->nvtxs <= 0 || graph->nedges <= 0)
00053 errexit("The supplied nvtxs:%"PRIDX" and nedges:%"PRIDX" must be positive.\n",
00054 graph->nvtxs, graph->nedges);
00055
00056 if (fmt > 111)
00057 errexit("Cannot read this type of file format [fmt=%"PRIDX"]!\n", fmt);
00058
00059 sprintf(fmtstr, "%03"PRIDX, fmt%1000);
00060 readvs = (fmtstr[0] == '1');
00061 readvw = (fmtstr[1] == '1');
00062 readew = (fmtstr[2] == '1');
00063
00064
00065
00066
00067 if (ncon > 0 && !readvw)
00068 errexit(
00069 "------------------------------------------------------------------------------\n"
00070 "*** I detected an error in your input file ***\n\n"
00071 "You specified ncon=%"PRIDX", but the fmt parameter does not specify vertex weights\n"
00072 "Make sure that the fmt parameter is set to either 10 or 11.\n"
00073 "------------------------------------------------------------------------------\n", ncon);
00074
00075 graph->nedges *=2;
00076 ncon = graph->ncon = (ncon == 0 ? 1 : ncon);
00077
00078 xadj = graph->xadj = ismalloc(graph->nvtxs+1, 0, "ReadGraph: xadj");
00079 adjncy = graph->adjncy = imalloc(graph->nedges, "ReadGraph: adjncy");
00080 vwgt = graph->vwgt = ismalloc(ncon*graph->nvtxs, 1, "ReadGraph: vwgt");
00081 adjwgt = graph->adjwgt = ismalloc(graph->nedges, 1, "ReadGraph: adjwgt");
00082 vsize = graph->vsize = ismalloc(graph->nvtxs, 1, "ReadGraph: vsize");
00083
00084
00085
00086
00087
00088 for (xadj[0]=0, k=0, i=0; i<graph->nvtxs; i++) {
00089 do {
00090 if (gk_getline(&line, &lnlen, fpin) == -1)
00091 errexit("Premature end of input file while reading vertex %"PRIDX".\n", i+1);
00092 } while (line[0] == '%');
00093
00094 curstr = line;
00095 newstr = NULL;
00096
00097
00098 if (readvs) {
00099 vsize[i] = strtoidx(curstr, &newstr, 10);
00100 if (newstr == curstr)
00101 errexit("The line for vertex %"PRIDX" does not have vsize information\n", i+1);
00102 if (vsize[i] < 0)
00103 errexit("The size for vertex %"PRIDX" must be >= 0\n", i+1);
00104 curstr = newstr;
00105 }
00106
00107
00108
00109 if (readvw) {
00110 for (l=0; l<ncon; l++) {
00111 vwgt[i*ncon+l] = strtoidx(curstr, &newstr, 10);
00112 if (newstr == curstr)
00113 errexit("The line for vertex %"PRIDX" does not have enough weights "
00114 "for the %"PRIDX" constraints.\n", i+1, ncon);
00115 if (vwgt[i*ncon+l] < 0)
00116 errexit("The weight vertex %"PRIDX" and constraint %"PRIDX" must be >= 0\n", i+1, l);
00117 curstr = newstr;
00118 }
00119 }
00120
00121 while (1) {
00122 edge = strtoidx(curstr, &newstr, 10);
00123 if (newstr == curstr)
00124 break;
00125 curstr = newstr;
00126
00127 if (edge < 1 || edge > graph->nvtxs)
00128 errexit("Edge %"PRIDX" for vertex %"PRIDX" is out of bounds\n", edge, i+1);
00129
00130 ewgt = 1;
00131 if (readew) {
00132 ewgt = strtoidx(curstr, &newstr, 10);
00133 if (newstr == curstr)
00134 errexit("Premature end of line for vertex %"PRIDX"\n", i+1);
00135 if (ewgt <= 0)
00136 errexit("The weight (%"PRIDX") for edge (%"PRIDX", %"PRIDX") must be positive.\n",
00137 ewgt, i+1, edge);
00138 curstr = newstr;
00139 }
00140
00141 if (k == graph->nedges)
00142 errexit("There are more edges in the file than the %"PRIDX" specified.\n",
00143 graph->nedges/2);
00144
00145 adjncy[k] = edge-1;
00146 adjwgt[k] = ewgt;
00147 k++;
00148 }
00149 xadj[i+1] = k;
00150 }
00151 gk_fclose(fpin);
00152
00153 if (k != graph->nedges) {
00154 printf("------------------------------------------------------------------------------\n");
00155 printf("*** I detected an error in your input file ***\n\n");
00156 printf("In the first line of the file, you specified that the graph contained\n"
00157 "%"PRIDX" edges. However, I only found %"PRIDX" edges in the file.\n",
00158 graph->nedges/2, k/2);
00159 if (2*k == graph->nedges) {
00160 printf("\n *> I detected that you specified twice the number of edges that you have in\n");
00161 printf(" the file. Remember that the number of edges specified in the first line\n");
00162 printf(" counts each edge between vertices v and u only once.\n\n");
00163 }
00164 printf("Please specify the correct number of edges in the first line of the file.\n");
00165 printf("------------------------------------------------------------------------------\n");
00166 exit(0);
00167 }
00168
00169 gk_free((void *)&line, LTERM);
00170
00171 return graph;
00172 }
00173
00174
00175
00177
00178 mesh_t *ReadMesh(params_t *params)
00179 {
00180 idx_t i, j, k, l, nfields, ncon, node;
00181 idx_t *eptr, *eind, *ewgt;
00182 size_t nlines, ntokens;
00183 char *line=NULL, *curstr, *newstr;
00184 size_t lnlen=0;
00185 FILE *fpin;
00186 mesh_t *mesh;
00187
00188 if (!gk_fexists(params->filename))
00189 errexit("File %s does not exist!\n", params->filename);
00190
00191 mesh = CreateMesh();
00192
00193
00194 gk_getfilestats(params->filename, &nlines, &ntokens, NULL, NULL);
00195
00196 fpin = gk_fopen(params->filename, "r", __func__);
00197
00198
00199 do {
00200 if (gk_getline(&line, &lnlen, fpin) == -1)
00201 errexit("Premature end of input file: file: %s\n", params->filename);
00202 } while (line[0] == '%');
00203
00204
00205 mesh->ncon = 0;
00206 nfields = sscanf(line, "%"SCIDX" %"SCIDX, &(mesh->ne), &(mesh->ncon));
00207
00208 if (nfields < 1)
00209 errexit("The input file does not specify the number of elements.\n");
00210
00211 if (mesh->ne <= 0)
00212 errexit("The supplied number of elements:%"PRIDX" must be positive.\n", mesh->ne);
00213
00214 if (mesh->ne > nlines)
00215 errexit("The file has %zu lines which smaller than the number of "
00216 "elements of %"PRIDX" specified in the header line.\n", nlines, mesh->ne);
00217
00218 ncon = mesh->ncon;
00219 eptr = mesh->eptr = ismalloc(mesh->ne+1, 0, "ReadMesh: eptr");
00220 eind = mesh->eind = imalloc(ntokens, "ReadMesh: eind");
00221 ewgt = mesh->ewgt = ismalloc((ncon == 0 ? 1 : ncon)*mesh->ne, 1, "ReadMesh: ewgt");
00222
00223
00224
00225
00226
00227 for (eptr[0]=0, k=0, i=0; i<mesh->ne; i++) {
00228 do {
00229 if (gk_getline(&line, &lnlen, fpin) == -1)
00230 errexit("Premature end of input file while reading element %"PRIDX".\n", i+1);
00231 } while (line[0] == '%');
00232
00233 curstr = line;
00234 newstr = NULL;
00235
00236
00237 for (l=0; l<ncon; l++) {
00238 ewgt[i*ncon+l] = strtoidx(curstr, &newstr, 10);
00239 if (newstr == curstr)
00240 errexit("The line for vertex %"PRIDX" does not have enough weights "
00241 "for the %"PRIDX" constraints.\n", i+1, ncon);
00242 if (ewgt[i*ncon+l] < 0)
00243 errexit("The weight for element %"PRIDX" and constraint %"PRIDX" must be >= 0\n", i+1, l);
00244 curstr = newstr;
00245 }
00246
00247 while (1) {
00248 node = strtoidx(curstr, &newstr, 10);
00249 if (newstr == curstr)
00250 break;
00251 curstr = newstr;
00252
00253 if (node < 1)
00254 errexit("Node %"PRIDX" for element %"PRIDX" is out of bounds\n", node, i+1);
00255
00256 eind[k++] = node-1;
00257 }
00258 eptr[i+1] = k;
00259 }
00260 gk_fclose(fpin);
00261
00262 mesh->ncon = (ncon == 0 ? 1 : ncon);
00263 mesh->nn = imax(eptr[mesh->ne], eind)+1;
00264
00265 gk_free((void *)&line, LTERM);
00266
00267 return mesh;
00268 }
00269
00270
00271
00274
00275 void ReadTPwgts(params_t *params, idx_t ncon)
00276 {
00277 idx_t i, j, from, to, fromcnum, tocnum, nleft;
00278 real_t awgt=0.0, twgt;
00279 char *line=NULL, *curstr, *newstr;
00280 size_t lnlen=0;
00281 FILE *fpin;
00282
00283 params->tpwgts = rsmalloc(params->nparts*ncon, -1.0, "ReadTPwgts: tpwgts");
00284
00285 if (params->tpwgtsfile == NULL) {
00286 for (i=0; i<params->nparts; i++) {
00287 for (j=0; j<ncon; j++)
00288 params->tpwgts[i*ncon+j] = 1.0/params->nparts;
00289 }
00290 return;
00291 }
00292
00293 if (!gk_fexists(params->tpwgtsfile))
00294 errexit("Graph file %s does not exist!\n", params->tpwgtsfile);
00295
00296 fpin = gk_fopen(params->tpwgtsfile, "r", "ReadTPwgts: tpwgtsfile");
00297
00298 while (gk_getline(&line, &lnlen, fpin) != -1) {
00299 gk_strchr_replace(line, " ", "");
00300
00301
00302 curstr = line;
00303 newstr = NULL;
00304
00305 from = strtoidx(curstr, &newstr, 10);
00306 if (newstr == curstr)
00307 errexit("The 'from' component of line <%s> in the tpwgts file is incorrect.\n", line);
00308 curstr = newstr;
00309
00310 if (curstr[0] == '-') {
00311 to = strtoidx(curstr+1, &newstr, 10);
00312 if (newstr == curstr)
00313 errexit("The 'to' component of line <%s> in the tpwgts file is incorrect.\n", line);
00314 curstr = newstr;
00315 }
00316 else {
00317 to = from;
00318 }
00319
00320 if (curstr[0] == ':') {
00321 fromcnum = strtoidx(curstr+1, &newstr, 10);
00322 if (newstr == curstr)
00323 errexit("The 'fromcnum' component of line <%s> in the tpwgts file is incorrect.\n", line);
00324 curstr = newstr;
00325
00326 if (curstr[0] == '-') {
00327 tocnum = strtoidx(curstr+1, &newstr, 10);
00328 if (newstr == curstr)
00329 errexit("The 'tocnum' component of line <%s> in the tpwgts file is incorrect.\n", line);
00330 curstr = newstr;
00331 }
00332 else {
00333 tocnum = fromcnum;
00334 }
00335 }
00336 else {
00337 fromcnum = 0;
00338 tocnum = ncon-1;
00339 }
00340
00341 if (curstr[0] == '=') {
00342 awgt = strtoreal(curstr+1, &newstr);
00343 if (newstr == curstr)
00344 errexit("The 'wgt' component of line <%s> in the tpwgts file is incorrect.\n", line);
00345 curstr = newstr;
00346 }
00347 else {
00348 errexit("The 'wgt' component of line <%s> in the tpwgts file is missing.\n", line);
00349 }
00350
00351
00352
00353
00354 if (from < 0 || to < 0 || from >= params->nparts || to >= params->nparts)
00355 errexit("Invalid partition range for %"PRIDX":%"PRIDX"\n", from, to);
00356 if (fromcnum < 0 || tocnum < 0 || fromcnum >= ncon || tocnum >= ncon)
00357 errexit("Invalid constraint number range for %"PRIDX":%"PRIDX"\n",
00358 fromcnum, tocnum);
00359 if (awgt <= 0.0 || awgt >= 1.0)
00360 errexit("Invalid partition weight of %"PRREAL"\n", awgt);
00361 for (i=from; i<=to; i++) {
00362 for (j=fromcnum; j<=tocnum; j++)
00363 params->tpwgts[i*ncon+j] = awgt;
00364 }
00365 }
00366
00367 gk_fclose(fpin);
00368
00369
00370 for (j=0; j<ncon; j++) {
00371
00372 for (twgt=0.0, nleft=params->nparts, i=0; i<params->nparts; i++) {
00373 if (params->tpwgts[i*ncon+j] > 0) {
00374 twgt += params->tpwgts[i*ncon+j];
00375 nleft--;
00376 }
00377 }
00378
00379
00380 if (nleft == 0)
00381 rscale(params->nparts, 1.0/twgt, params->tpwgts+j, ncon);
00382
00383
00384 if (nleft > 0) {
00385 if (twgt > 1)
00386 errexit("The total specified target partition weights for constraint #%"PRIDX
00387 " of %"PRREAL" exceeds 1.0.\n", j, twgt);
00388
00389 awgt = (1.0 - twgt)/nleft;
00390 for (i=0; i<params->nparts; i++)
00391 params->tpwgts[i*ncon+j] =
00392 (params->tpwgts[i*ncon+j] < 0 ? awgt : params->tpwgts[i*ncon+j]);
00393 }
00394 }
00395 #ifdef HAVE_GETLINE
00396 free(line);
00397 line = NULL;
00398 #else
00399 gk_free((void *)&line, LTERM);
00400 #endif
00401 }
00402
00403
00404
00406
00407 void ReadPOVector(graph_t *graph, char *filename, idx_t *vector)
00408 {
00409 idx_t i;
00410 FILE *fpin;
00411
00412 fpin = gk_fopen(filename, "r", __func__);
00413 for (i=0; i<graph->nvtxs; i++) {
00414 if (fscanf(fpin, "%"SCIDX"\n", vector+i) != 1)
00415 errexit("[%s] Premature end of file %s at line %d [nvtxs: %d]\n",
00416 __func__, filename, i, graph->nvtxs);
00417 }
00418 gk_fclose(fpin);
00419 }
00420
00421
00422
00424
00425 void WritePartition(char *fname, idx_t *part, idx_t n, idx_t nparts)
00426 {
00427 FILE *fpout;
00428 idx_t i;
00429 char filename[MAXLINE];
00430
00431 sprintf(filename, "%s.part.%"PRIDX, fname, nparts);
00432
00433 fpout = gk_fopen(filename, "w", __func__);
00434
00435 for (i=0; i<n; i++)
00436 fprintf(fpout,"%" PRIDX "\n", part[i]);
00437
00438 gk_fclose(fpout);
00439 }
00440
00441
00442
00444
00445 void WriteMeshPartition(char *fname, idx_t nparts, idx_t ne, idx_t *epart,
00446 idx_t nn, idx_t *npart)
00447 {
00448 FILE *fpout;
00449 idx_t i;
00450 char filename[256];
00451
00452 sprintf(filename,"%s.epart.%"PRIDX,fname, nparts);
00453
00454 fpout = gk_fopen(filename, "w", __func__);
00455
00456 for (i=0; i<ne; i++)
00457 fprintf(fpout,"%" PRIDX "\n", epart[i]);
00458
00459 gk_fclose(fpout);
00460
00461
00462 sprintf(filename,"%s.npart.%"PRIDX,fname, nparts);
00463
00464 fpout = gk_fopen(filename, "w", __func__);
00465
00466 for (i=0; i<nn; i++)
00467 fprintf(fpout, "%" PRIDX "\n", npart[i]);
00468
00469 gk_fclose(fpout);
00470
00471 }
00472
00473
00474
00476
00477 void WritePermutation(char *fname, idx_t *iperm, idx_t n)
00478 {
00479 FILE *fpout;
00480 idx_t i;
00481 char filename[MAXLINE];
00482
00483 sprintf(filename, "%s.iperm", fname);
00484
00485 fpout = gk_fopen(filename, "w", __func__);
00486
00487 for (i=0; i<n; i++)
00488 fprintf(fpout, "%" PRIDX "\n", iperm[i]);
00489
00490 gk_fclose(fpout);
00491 }
00492
00493
00494
00496
00497 void WriteGraph(graph_t *graph, char *filename)
00498 {
00499 idx_t i, j, nvtxs, ncon;
00500 idx_t *xadj, *adjncy, *adjwgt, *vwgt, *vsize;
00501 int hasvwgt=0, hasewgt=0, hasvsize=0;
00502 FILE *fpout;
00503
00504 nvtxs = graph->nvtxs;
00505 ncon = graph->ncon;
00506 xadj = graph->xadj;
00507 adjncy = graph->adjncy;
00508 vwgt = graph->vwgt;
00509 vsize = graph->vsize;
00510 adjwgt = graph->adjwgt;
00511
00512
00513 if (vwgt) {
00514 for (i=0; i<nvtxs*ncon; i++) {
00515 if (vwgt[i] != 1) {
00516 hasvwgt = 1;
00517 break;
00518 }
00519 }
00520 }
00521 if (vsize) {
00522 for (i=0; i<nvtxs; i++) {
00523 if (vsize[i] != 1) {
00524 hasvsize = 1;
00525 break;
00526 }
00527 }
00528 }
00529 if (adjwgt) {
00530 for (i=0; i<xadj[nvtxs]; i++) {
00531 if (adjwgt[i] != 1) {
00532 hasewgt = 1;
00533 break;
00534 }
00535 }
00536 }
00537
00538 fpout = gk_fopen(filename, "w", __func__);
00539
00540
00541 fprintf(fpout, "%"PRIDX" %"PRIDX, nvtxs, xadj[nvtxs]/2);
00542 if (hasvwgt || hasvsize || hasewgt) {
00543 fprintf(fpout, " %d%d%d", hasvsize, hasvwgt, hasewgt);
00544 if (hasvwgt)
00545 fprintf(fpout, " %d", (int)graph->ncon);
00546 }
00547
00548
00549
00550 for (i=0; i<nvtxs; i++) {
00551 fprintf(fpout, "\n");
00552 if (hasvsize)
00553 fprintf(fpout, " %"PRIDX, vsize[i]);
00554
00555 if (hasvwgt) {
00556 for (j=0; j<ncon; j++)
00557 fprintf(fpout, " %"PRIDX, vwgt[i*ncon+j]);
00558 }
00559
00560 for (j=xadj[i]; j<xadj[i+1]; j++) {
00561 fprintf(fpout, " %"PRIDX, adjncy[j]+1);
00562 if (hasewgt)
00563 fprintf(fpout, " %"PRIDX, adjwgt[j]);
00564 }
00565 }
00566
00567 gk_fclose(fpout);
00568 }
1.5.5