src/libs/ck-libs/metis/programs/io.c

   1 /*
   2  * Copyright 1997, Regents of the University of Minnesota
   3  *
   4  * io.c
   5  *
   6  * This file contains routines related to I/O
   7  *
   8  * Started 8/28/94
   9  * George
  10  *
  11  * $Id: io.c 11932 2012-05-10 18:18:23Z dominique $
  12  *
  13  */
  14
  15 #include "metisbin.h"
  16
  17
  18
  19 /*************************************************************************/
  20 /*! This function reads in a sparse graph */
  21 /*************************************************************************/
  22 graph_t *ReadGraph(params_t *params)
  23 {
  24   idx_t i, j, k, l, fmt, ncon, nfields, readew, readvw, readvs, edge, ewgt;
  25   idx_t *xadj, *adjncy, *vwgt, *adjwgt, *vsize;
  26   char *line=NULL, fmtstr[256], *curstr, *newstr;
  27   size_t lnlen=0;
  28   FILE *fpin;
  29   graph_t *graph;
  30
  31   if (!gk_fexists(params->filename))
  32     errexit("File %s does not exist!\n", params->filename);
  33
  34   graph = CreateGraph();
  35
  36   fpin = gk_fopen(params->filename, "r", "ReadGRaph: Graph");
  37
  38   /* Skip comment lines until you get to the first valid line */
  39   do {
  40     if (gk_getline(&line, &lnlen, fpin) == -1)
  41       errexit("Premature end of input file: file: %s\n", params->filename);
  42   } while (line[0] == '%');
  43
  44
  45   fmt = ncon = 0;
  46   nfields = sscanf(line, "%"SCIDX" %"SCIDX" %"SCIDX" %"SCIDX,
  47                 &(graph->nvtxs), &(graph->nedges), &fmt, &ncon);
  48
  49   if (nfields < 2)
  50     errexit("The input file does not specify the number of vertices and edges.\n");
  51
  52   if (graph->nvtxs <= 0 || graph->nedges <= 0)
  53     errexit("The supplied nvtxs:%"PRIDX" and nedges:%"PRIDX" must be positive.\n",
  54         graph->nvtxs, graph->nedges);
  55
  56   if (fmt > 111)
  57     errexit("Cannot read this type of file format [fmt=%"PRIDX"]!\n", fmt);
  58
  59   sprintf(fmtstr, "%03"PRIDX, fmt%1000);
  60   readvs = (fmtstr[0] == '1');
  61   readvw = (fmtstr[1] == '1');
  62   readew = (fmtstr[2] == '1');
  63
  64   /*printf("%s %"PRIDX" %"PRIDX" %"PRIDX"\n", fmtstr, readvs, readvw, readew); */
  65
  66
  67   if (ncon > 0 && !readvw)
  68     errexit(
  69       "------------------------------------------------------------------------------\n"
  70       "***  I detected an error in your input file  ***\n\n"
  71       "You specified ncon=%"PRIDX", but the fmt parameter does not specify vertex weights\n"
  72       "Make sure that the fmt parameter is set to either 10 or 11.\n"
  73       "------------------------------------------------------------------------------\n", ncon);
  74
  75   graph->nedges *=2;
  76   ncon = graph->ncon = (ncon == 0 ? 1 : ncon);
  77
  78   xadj   = graph->xadj   = ismalloc(graph->nvtxs+1, 0, "ReadGraph: xadj");
  79   adjncy = graph->adjncy = imalloc(graph->nedges, "ReadGraph: adjncy");
  80   vwgt   = graph->vwgt   = ismalloc(ncon*graph->nvtxs, 1, "ReadGraph: vwgt");
  81   adjwgt = graph->adjwgt = ismalloc(graph->nedges, 1, "ReadGraph: adjwgt");
  82   vsize  = graph->vsize  = ismalloc(graph->nvtxs, 1, "ReadGraph: vsize");
  83
  84
  85   /*----------------------------------------------------------------------
  86    * Read the sparse graph file
  87    *---------------------------------------------------------------------*/
  88   for (xadj[0]=0, k=0, i=0; i<graph->nvtxs; i++) {
  89     do {
  90       if (gk_getline(&line, &lnlen, fpin) == -1)
  91         errexit("Premature end of input file while reading vertex %"PRIDX".\n", i+1);
  92     } while (line[0] == '%');
  93
  94     curstr = line;
  95     newstr = NULL;
  96
  97     /* Read vertex sizes */
  98     if (readvs) {
  99       vsize[i] = strtoidx(curstr, &newstr, 10);
 100       if (newstr == curstr)
 101         errexit("The line for vertex %"PRIDX" does not have vsize information\n", i+1);
 102       if (vsize[i] < 0)
 103         errexit("The size for vertex %"PRIDX" must be >= 0\n", i+1);
 104       curstr = newstr;
 105     }
 106
 107
 108     /* Read vertex weights */
 109     if (readvw) {
 110       for (l=0; l<ncon; l++) {
 111         vwgt[i*ncon+l] = strtoidx(curstr, &newstr, 10);
 112         if (newstr == curstr)
 113           errexit("The line for vertex %"PRIDX" does not have enough weights "
 114                   "for the %"PRIDX" constraints.\n", i+1, ncon);
 115         if (vwgt[i*ncon+l] < 0)
 116           errexit("The weight vertex %"PRIDX" and constraint %"PRIDX" must be >= 0\n", i+1, l);
 117         curstr = newstr;
 118       }
 119     }
 120
 121     while (1) {
 122       edge = strtoidx(curstr, &newstr, 10);
 123       if (newstr == curstr)
 124         break; /* End of line */
 125       curstr = newstr;
 126
 127       if (edge < 1 || edge > graph->nvtxs)
 128         errexit("Edge %"PRIDX" for vertex %"PRIDX" is out of bounds\n", edge, i+1);
 129
 130       ewgt = 1;
 131       if (readew) {
 132         ewgt = strtoidx(curstr, &newstr, 10);
 133         if (newstr == curstr)
 134           errexit("Premature end of line for vertex %"PRIDX"\n", i+1);
 135         if (ewgt <= 0)
 136           errexit("The weight (%"PRIDX") for edge (%"PRIDX", %"PRIDX") must be positive.\n",
 137               ewgt, i+1, edge);
 138         curstr = newstr;
 139       }
 140
 141       if (k == graph->nedges)
 142         errexit("There are more edges in the file than the %"PRIDX" specified.\n",
 143             graph->nedges/2);
 144
 145       adjncy[k] = edge-1;
 146       adjwgt[k] = ewgt;
 147       k++;
 148     }
 149     xadj[i+1] = k;
 150   }
 151   gk_fclose(fpin);
 152
 153   if (k != graph->nedges) {
 154     printf("------------------------------------------------------------------------------\n");
 155     printf("***  I detected an error in your input file  ***\n\n");
 156     printf("In the first line of the file, you specified that the graph contained\n"
 157            "%"PRIDX" edges. However, I only found %"PRIDX" edges in the file.\n",
 158            graph->nedges/2, k/2);
 159     if (2*k == graph->nedges) {
 160       printf("\n *> I detected that you specified twice the number of edges that you have in\n");
 161       printf("    the file. Remember that the number of edges specified in the first line\n");
 162       printf("    counts each edge between vertices v and u only once.\n\n");
 163     }
 164     printf("Please specify the correct number of edges in the first line of the file.\n");
 165     printf("------------------------------------------------------------------------------\n");
 166     exit(0);
 167   }
 168
 169   gk_free((void *)&line, LTERM);
 170
 171   return graph;
 172 }
 173
 174
 175 /*************************************************************************/
 176 /*! This function reads in a mesh */
 177 /*************************************************************************/
 178 mesh_t *ReadMesh(params_t *params)
 179 {
 180   idx_t i, j, k, l, nfields, ncon, node;
 181   idx_t *eptr, *eind, *ewgt;
 182   size_t nlines, ntokens;
 183   char *line=NULL, *curstr, *newstr;
 184   size_t lnlen=0;
 185   FILE *fpin;
 186   mesh_t *mesh;
 187
 188   if (!gk_fexists(params->filename))
 189     errexit("File %s does not exist!\n", params->filename);
 190
 191   mesh = CreateMesh();
 192
 193   /* get some file stats */
 194   gk_getfilestats(params->filename, &nlines, &ntokens, NULL, NULL);
 195
 196   fpin = gk_fopen(params->filename, "r", __func__);
 197
 198   /* Skip comment lines until you get to the first valid line */
 199   do {
 200     if (gk_getline(&line, &lnlen, fpin) == -1)
 201       errexit("Premature end of input file: file: %s\n", params->filename);
 202   } while (line[0] == '%');
 203
 204
 205   mesh->ncon = 0;
 206   nfields = sscanf(line, "%"SCIDX" %"SCIDX, &(mesh->ne), &(mesh->ncon));
 207
 208   if (nfields < 1)
 209     errexit("The input file does not specify the number of elements.\n");
 210
 211   if (mesh->ne <= 0)
 212     errexit("The supplied number of elements:%"PRIDX" must be positive.\n", mesh->ne);
 213
 214   if (mesh->ne > nlines)
 215     errexit("The file has %zu lines which smaller than the number of "
 216             "elements of %"PRIDX" specified in the header line.\n", nlines, mesh->ne);
 217
 218   ncon = mesh->ncon;
 219   eptr = mesh->eptr = ismalloc(mesh->ne+1, 0, "ReadMesh: eptr");
 220   eind = mesh->eind = imalloc(ntokens, "ReadMesh: eind");
 221   ewgt = mesh->ewgt = ismalloc((ncon == 0 ? 1 : ncon)*mesh->ne, 1, "ReadMesh: ewgt");
 222
 223
 224   /*----------------------------------------------------------------------
 225    * Read the mesh file
 226    *---------------------------------------------------------------------*/
 227   for (eptr[0]=0, k=0, i=0; i<mesh->ne; i++) {
 228     do {
 229       if (gk_getline(&line, &lnlen, fpin) == -1)
 230         errexit("Premature end of input file while reading element %"PRIDX".\n", i+1);
 231     } while (line[0] == '%');
 232
 233     curstr = line;
 234     newstr = NULL;
 235
 236     /* Read element weights */
 237     for (l=0; l<ncon; l++) {
 238       ewgt[i*ncon+l] = strtoidx(curstr, &newstr, 10);
 239       if (newstr == curstr)
 240         errexit("The line for vertex %"PRIDX" does not have enough weights "
 241                 "for the %"PRIDX" constraints.\n", i+1, ncon);
 242       if (ewgt[i*ncon+l] < 0)
 243         errexit("The weight for element %"PRIDX" and constraint %"PRIDX" must be >= 0\n", i+1, l);
 244       curstr = newstr;
 245     }
 246
 247     while (1) {
 248       node = strtoidx(curstr, &newstr, 10);
 249       if (newstr == curstr)
 250         break; /* End of line */
 251       curstr = newstr;
 252
 253       if (node < 1)
 254         errexit("Node %"PRIDX" for element %"PRIDX" is out of bounds\n", node, i+1);
 255
 256       eind[k++] = node-1;
 257     }
 258     eptr[i+1] = k;
 259   }
 260   gk_fclose(fpin);
 261
 262   mesh->ncon = (ncon == 0 ? 1 : ncon);
 263   mesh->nn   = imax(eptr[mesh->ne], eind)+1;
 264
 265   gk_free((void *)&line, LTERM);
 266
 267   return mesh;
 268 }
 269
 270
 271 /*************************************************************************/
 272 /*! This function reads in the target partition weights. If no file is
 273     specified the weights are set to 1/nparts */
 274 /*************************************************************************/
 275 void ReadTPwgts(params_t *params, idx_t ncon)
 276 {
 277   idx_t i, j, from, to, fromcnum, tocnum, nleft;
 278   real_t awgt=0.0, twgt;
 279   char *line=NULL, *curstr, *newstr;
 280   size_t lnlen=0;
 281   FILE *fpin;
 282
 283   params->tpwgts = rsmalloc(params->nparts*ncon, -1.0, "ReadTPwgts: tpwgts");
 284
 285   if (params->tpwgtsfile == NULL) {
 286     for (i=0; i<params->nparts; i++) {
 287       for (j=0; j<ncon; j++)
 288         params->tpwgts[i*ncon+j] = 1.0/params->nparts;
 289     }
 290     return;
 291   }
 292
 293   if (!gk_fexists(params->tpwgtsfile))
 294     errexit("Graph file %s does not exist!\n", params->tpwgtsfile);
 295
 296   fpin = gk_fopen(params->tpwgtsfile, "r", "ReadTPwgts: tpwgtsfile");
 297
 298   while (gk_getline(&line, &lnlen, fpin) != -1) {
 299     gk_strchr_replace(line, " ", "");
 300     /* start extracting the fields */
 301
 302     curstr = line;
 303     newstr = NULL;
 304
 305     from = strtoidx(curstr, &newstr, 10);
 306     if (newstr == curstr)
 307       errexit("The 'from' component of line <%s> in the tpwgts file is incorrect.\n", line);
 308     curstr = newstr;
 309
 310     if (curstr[0] == '-') {
 311       to = strtoidx(curstr+1, &newstr, 10);
 312       if (newstr == curstr)
 313         errexit("The 'to' component of line <%s> in the tpwgts file is incorrect.\n", line);
 314       curstr = newstr;
 315     }
 316     else {
 317       to = from;
 318     }
 319
 320     if (curstr[0] == ':') {
 321       fromcnum = strtoidx(curstr+1, &newstr, 10);
 322       if (newstr == curstr)
 323         errexit("The 'fromcnum' component of line <%s> in the tpwgts file is incorrect.\n", line);
 324       curstr = newstr;
 325
 326       if (curstr[0] == '-') {
 327         tocnum = strtoidx(curstr+1, &newstr, 10);
 328         if (newstr == curstr)
 329           errexit("The 'tocnum' component of line <%s> in the tpwgts file is incorrect.\n", line);
 330         curstr = newstr;
 331       }
 332       else {
 333         tocnum = fromcnum;
 334       }
 335     }
 336     else {
 337       fromcnum = 0;
 338       tocnum   = ncon-1;
 339     }
 340
 341     if (curstr[0] == '=') {
 342       awgt = strtoreal(curstr+1, &newstr);
 343       if (newstr == curstr)
 344         errexit("The 'wgt' component of line <%s> in the tpwgts file is incorrect.\n", line);
 345       curstr = newstr;
 346     }
 347     else {
 348       errexit("The 'wgt' component of line <%s> in the tpwgts file is missing.\n", line);
 349     }
 350
 351     /*printf("Read: %"PRIDX"-%"PRIDX":%"PRIDX"-%"PRIDX"=%"PRREAL"\n",
 352         from, to, fromcnum, tocnum, awgt);*/
 353
 354     if (from < 0 || to < 0 || from >= params->nparts || to >= params->nparts)
 355       errexit("Invalid partition range for %"PRIDX":%"PRIDX"\n", from, to);
 356     if (fromcnum < 0 || tocnum < 0 || fromcnum >= ncon || tocnum >= ncon)
 357       errexit("Invalid constraint number range for %"PRIDX":%"PRIDX"\n",
 358           fromcnum, tocnum);
 359     if (awgt <= 0.0 || awgt >= 1.0)
 360       errexit("Invalid partition weight of %"PRREAL"\n", awgt);
 361     for (i=from; i<=to; i++) {
 362       for (j=fromcnum; j<=tocnum; j++)
 363         params->tpwgts[i*ncon+j] = awgt;
 364     }
 365   }
 366
 367   gk_fclose(fpin);
 368
 369   /* Assign weight to the unspecified constraints x partitions */
 370   for (j=0; j<ncon; j++) {
 371     /* Sum up the specified weights for the jth constraint */
 372     for (twgt=0.0, nleft=params->nparts, i=0; i<params->nparts; i++) {
 373       if (params->tpwgts[i*ncon+j] > 0) {
 374         twgt += params->tpwgts[i*ncon+j];
 375         nleft--;
 376       }
 377     }
 378
 379     /* Rescale the weights to be on the safe side */
 380     if (nleft == 0)
 381       rscale(params->nparts, 1.0/twgt, params->tpwgts+j, ncon);
 382
 383     /* Assign the left-over weight to the remaining partitions */
 384     if (nleft > 0) {
 385       if (twgt > 1)
 386         errexit("The total specified target partition weights for constraint #%"PRIDX
 387                 " of %"PRREAL" exceeds 1.0.\n", j, twgt);
 388
 389       awgt = (1.0 - twgt)/nleft;
 390       for (i=0; i<params->nparts; i++)
 391         params->tpwgts[i*ncon+j] =
 392             (params->tpwgts[i*ncon+j] < 0 ? awgt : params->tpwgts[i*ncon+j]);
 393     }
 394   }
 395   #ifdef HAVE_GETLINE
 396   free(line);
 397   line = NULL; /* set to null to match behavior of gk_free() */
 398   #else
 399   gk_free((void *)&line, LTERM);
 400   #endif
 401 }
 402
 403
 404 /*************************************************************************/
 405 /*! This function reads in a partition/ordering vector  */
 406 /**************************************************************************/
 407 void ReadPOVector(graph_t *graph, char *filename, idx_t *vector)
 408 {
 409   idx_t i;
 410   FILE *fpin;
 411
 412   fpin = gk_fopen(filename, "r", __func__);
 413   for (i=0; i<graph->nvtxs; i++) {
 414     if (fscanf(fpin, "%"SCIDX"\n", vector+i) != 1)
 415       errexit("[%s] Premature end of file %s at line %d [nvtxs: %d]\n",
 416           __func__, filename, i, graph->nvtxs);
 417   }
 418   gk_fclose(fpin);
 419 }
 420
 421
 422 /*************************************************************************/
 423 /*! This function writes out the partition vector */
 424 /*************************************************************************/
 425 void WritePartition(char *fname, idx_t *part, idx_t n, idx_t nparts)
 426 {
 427   FILE *fpout;
 428   idx_t i;
 429   char filename[MAXLINE];
 430
 431   sprintf(filename, "%s.part.%"PRIDX, fname, nparts);
 432
 433   fpout = gk_fopen(filename, "w", __func__);
 434
 435   for (i=0; i<n; i++)
 436     fprintf(fpout,"%" PRIDX "\n", part[i]);
 437
 438   gk_fclose(fpout);
 439 }
 440
 441
 442 /*************************************************************************/
 443 /*! This function writes out the partition vectors for a mesh */
 444 /*************************************************************************/
 445 void WriteMeshPartition(char *fname, idx_t nparts, idx_t ne, idx_t *epart,
 446        idx_t nn, idx_t *npart)
 447 {
 448   FILE *fpout;
 449   idx_t i;
 450   char filename[256];
 451
 452   sprintf(filename,"%s.epart.%"PRIDX,fname, nparts);
 453
 454   fpout = gk_fopen(filename, "w", __func__);
 455
 456   for (i=0; i<ne; i++)
 457     fprintf(fpout,"%" PRIDX "\n", epart[i]);
 458
 459   gk_fclose(fpout);
 460
 461
 462   sprintf(filename,"%s.npart.%"PRIDX,fname, nparts);
 463
 464   fpout = gk_fopen(filename, "w", __func__);
 465
 466   for (i=0; i<nn; i++)
 467     fprintf(fpout, "%" PRIDX "\n", npart[i]);
 468
 469   gk_fclose(fpout);
 470
 471 }
 472
 473
 474 /*************************************************************************/
 475 /*! This function writes out the permutation vector */
 476 /*************************************************************************/
 477 void WritePermutation(char *fname, idx_t *iperm, idx_t n)
 478 {
 479   FILE *fpout;
 480   idx_t i;
 481   char filename[MAXLINE];
 482
 483   sprintf(filename, "%s.iperm", fname);
 484
 485   fpout = gk_fopen(filename, "w", __func__);
 486
 487   for (i=0; i<n; i++)
 488     fprintf(fpout, "%" PRIDX "\n", iperm[i]);
 489
 490   gk_fclose(fpout);
 491 }
 492
 493
 494 /*************************************************************************/
 495 /*! This function writes a graph into a file  */
 496 /*************************************************************************/
 497 void WriteGraph(graph_t *graph, char *filename)
 498 {
 499   idx_t i, j, nvtxs, ncon;
 500   idx_t *xadj, *adjncy, *adjwgt, *vwgt, *vsize;
 501   int hasvwgt=0, hasewgt=0, hasvsize=0;
 502   FILE *fpout;
 503
 504   nvtxs  = graph->nvtxs;
 505   ncon   = graph->ncon;
 506   xadj   = graph->xadj;
 507   adjncy = graph->adjncy;
 508   vwgt   = graph->vwgt;
 509   vsize  = graph->vsize;
 510   adjwgt = graph->adjwgt;
 511
 512   /* determine if the graph has non-unity vwgt, vsize, or adjwgt */
 513   if (vwgt) {
 514     for (i=0; i<nvtxs*ncon; i++) {
 515       if (vwgt[i] != 1) {
 516         hasvwgt = 1;
 517         break;
 518       }
 519     }
 520   }
 521   if (vsize) {
 522     for (i=0; i<nvtxs; i++) {
 523       if (vsize[i] != 1) {
 524         hasvsize = 1;
 525         break;
 526       }
 527     }
 528   }
 529   if (adjwgt) {
 530     for (i=0; i<xadj[nvtxs]; i++) {
 531       if (adjwgt[i] != 1) {
 532         hasewgt = 1;
 533         break;
 534       }
 535     }
 536   }
 537
 538   fpout = gk_fopen(filename, "w", __func__);
 539
 540   /* write the header line */
 541   fprintf(fpout, "%"PRIDX" %"PRIDX, nvtxs, xadj[nvtxs]/2);
 542   if (hasvwgt || hasvsize || hasewgt) {
 543     fprintf(fpout, " %d%d%d", hasvsize, hasvwgt, hasewgt);
 544     if (hasvwgt)
 545       fprintf(fpout, " %d", (int)graph->ncon);
 546   }
 547
 548
 549   /* write the rest of the graph */
 550   for (i=0; i<nvtxs; i++) {
 551     fprintf(fpout, "\n");
 552     if (hasvsize)
 553       fprintf(fpout, " %"PRIDX, vsize[i]);
 554
 555     if (hasvwgt) {
 556       for (j=0; j<ncon; j++)
 557         fprintf(fpout, " %"PRIDX, vwgt[i*ncon+j]);
 558     }
 559
 560     for (j=xadj[i]; j<xadj[i+1]; j++) {
 561       fprintf(fpout, " %"PRIDX, adjncy[j]+1);
 562       if (hasewgt)
 563         fprintf(fpout, " %"PRIDX, adjwgt[j]);
 564     }
 565   }
 566
 567   gk_fclose(fpout);
 568 }