Zoltan2 Version of the Day
Zoltan2_ChacoReader.cpp
Go to the documentation of this file.
00001 // @HEADER
00002 //
00003 // ***********************************************************************
00004 //
00005 //   Zoltan2: A package of combinatorial algorithms for scientific computing
00006 //                  Copyright 2012 Sandia Corporation
00007 //
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Karen Devine      (kddevin@sandia.gov)
00039 //                    Erik Boman        (egboman@sandia.gov)
00040 //                    Siva Rajamanickam (srajama@sandia.gov)
00041 //
00042 // ***********************************************************************
00043 //
00044 // @HEADER
00045 
00050 #include <stdio.h>
00051 #include <ctype.h>
00052 #include <string.h>
00053 #include <stdlib.h>
00054 
00055 namespace Zoltan2 {
00056 
00057 #define LINE_LENGTH 200
00058 static char chaco_line[LINE_LENGTH];  /* space to hold values */
00059 static int chaco_offset = 0;    /* offset into line for next data */
00060 static int chaco_break_pnt = LINE_LENGTH; /* place in sequence to pause */
00061 static int chaco_save_pnt;    /* place in sequence to save */
00062 static void chaco_flush_line(FILE*);
00063 
00068 double    chaco_read_val(
00069   FILE* infile,   /* file to read value from */
00070   int      *end_flag    /* 0 => OK, 1 => EOL, -1 => EOF */
00071 )
00072 {
00073     double    val;    /* return value */
00074     char     *ptr;    /* ptr to next string to read */
00075     char     *ptr2;   /* ptr to next string to read */
00076     int       length;   /* length of line to read */
00077     int       length_left;  /* length of line still around */
00078     int       white_seen; /* have I detected white space yet? */
00079     int       done;   /* checking for end of scan */
00080     int       i;    /* loop counter */
00081 
00082     *end_flag = 0;
00083 
00084     if (chaco_offset == 0 || chaco_offset >= chaco_break_pnt) {
00085   if (chaco_offset >= chaco_break_pnt) { /* Copy rest of line back to beginning. */
00086       length_left = LINE_LENGTH - chaco_save_pnt - 1;
00087       ptr2 = chaco_line;
00088       ptr = &chaco_line[chaco_save_pnt];
00089       for (i=length_left; i; i--) *ptr2++ = *ptr++;
00090       length = chaco_save_pnt + 1;
00091   }
00092   else {
00093       length = LINE_LENGTH;
00094       length_left = 0;
00095   }
00096 
00097   /* Now read next line, or next segment of current one. */
00098   ptr2 = fgets(&chaco_line[length_left], length, infile);
00099 
00100   if (ptr2 == (char *) NULL) {  /* We've hit end of file. */
00101       *end_flag = -1;
00102       return((double) 0.0);
00103   }
00104 
00105   if ((chaco_line[LINE_LENGTH - 2] != '\n') && (chaco_line[LINE_LENGTH - 2] != '\f')
00106       && (strlen(chaco_line) == LINE_LENGTH - 1)){
00107       /* Line too long.  Find last safe place in chaco_line. */
00108       chaco_break_pnt = LINE_LENGTH - 1;
00109       chaco_save_pnt = chaco_break_pnt;
00110       white_seen = 0;
00111       done = 0;
00112       while (!done) {
00113     --chaco_break_pnt;
00114     if (chaco_line[chaco_break_pnt] != '\0') {
00115         if (isspace((int)(chaco_line[chaco_break_pnt]))) {
00116       if (!white_seen) {
00117           chaco_save_pnt = chaco_break_pnt + 1;
00118                 white_seen = 1;
00119       }
00120         }
00121         else if (white_seen) {
00122             done= 1;
00123         }
00124     }
00125       }
00126   }
00127   else {
00128       chaco_break_pnt = LINE_LENGTH;
00129   }
00130 
00131   chaco_offset = 0;
00132     }
00133 
00134     while (isspace((int)(chaco_line[chaco_offset])) && chaco_offset < LINE_LENGTH) chaco_offset++;
00135     if (chaco_line[chaco_offset] == '%' || chaco_line[chaco_offset] == '#') {
00136   *end_flag = 1;
00137   if (chaco_break_pnt < LINE_LENGTH) {
00138       chaco_flush_line(infile);
00139   }
00140   return((double) 0.0);
00141     }
00142 
00143     ptr = &(chaco_line[chaco_offset]);
00144     val = strtod(ptr, &ptr2);
00145 
00146     if (ptr2 == ptr) {  /* End of input line. */
00147   chaco_offset = 0;
00148   *end_flag = 1;
00149   return((double) 0.0);
00150     }
00151     else {
00152   chaco_offset = (int) (ptr2 - chaco_line) / sizeof(char);
00153     }
00154 
00155     return(val);
00156 }
00157 
00158 
00163 int     chaco_read_int(
00164 FILE *infile,   /* file to read value from */
00165 int      *end_flag    /* 0 => OK, 1 => EOL, -1 => EOF */
00166 )
00167 {
00168     int       val;    /* return value */
00169     char     *ptr;    /* ptr to next string to read */
00170     char     *ptr2;   /* ptr to next string to read */
00171     int       length;   /* length of line to read */
00172     int       length_left;  /* length of line still around */
00173     int       white_seen; /* have I detected white space yet? */
00174     int       done;   /* checking for end of scan */
00175     int       i;    /* loop counter */
00176 
00177     *end_flag = 0;
00178 
00179     if (chaco_offset == 0 || chaco_offset >= chaco_break_pnt) {
00180   if (chaco_offset >= chaco_break_pnt) { /* Copy rest of line back to beginning. */
00181       length_left = LINE_LENGTH - chaco_save_pnt - 1;
00182       ptr2 = chaco_line;
00183       ptr = &chaco_line[chaco_save_pnt];
00184       for (i=length_left; i; i--) *ptr2++ = *ptr++;
00185       length = chaco_save_pnt + 1;
00186   }
00187   else {
00188       length = LINE_LENGTH;
00189       length_left = 0;
00190   }
00191 
00192   /* Now read next line, or next segment of current one. */
00193   ptr2 = fgets(&chaco_line[length_left], length, infile);
00194 
00195   if (ptr2 == (char *) NULL) {  /* We've hit end of file. */
00196       *end_flag = -1;
00197       return(0);
00198   }
00199 
00200   if ((chaco_line[LINE_LENGTH - 2] != '\n') && (chaco_line[LINE_LENGTH - 2] != '\f')
00201       && (strlen(chaco_line) == LINE_LENGTH - 1)){
00202       /* Line too long.  Find last safe place in line. */
00203       chaco_break_pnt = LINE_LENGTH - 1;
00204       chaco_save_pnt = chaco_break_pnt;
00205       white_seen = 0;
00206       done = 0;
00207       while (!done) {
00208     --chaco_break_pnt;
00209     if (chaco_line[chaco_break_pnt] != '\0') {
00210         if (isspace((int)(chaco_line[chaco_break_pnt]))) {
00211       if (!white_seen) {
00212           chaco_save_pnt = chaco_break_pnt + 1;
00213                 white_seen = 1;
00214       }
00215         }
00216         else if (white_seen) {
00217             done= 1;
00218         }
00219     }
00220       }
00221   }
00222   else {
00223       chaco_break_pnt = LINE_LENGTH;
00224   }
00225 
00226   chaco_offset = 0;
00227     }
00228 
00229     while (isspace((int)(chaco_line[chaco_offset])) && chaco_offset < LINE_LENGTH) chaco_offset++;
00230     if (chaco_line[chaco_offset] == '%' || chaco_line[chaco_offset] == '#') {
00231   *end_flag = 1;
00232   if (chaco_break_pnt < LINE_LENGTH) {
00233       chaco_flush_line(infile);
00234   }
00235   return(0);
00236     }
00237 
00238     ptr = &(chaco_line[chaco_offset]);
00239     val = (int) strtol(ptr, &ptr2, 10);
00240 
00241     if (ptr2 == ptr) {  /* End of input chaco_line. */
00242   chaco_offset = 0;
00243   *end_flag = 1;
00244   return(0);
00245     }
00246     else {
00247   chaco_offset = (int) (ptr2 - chaco_line) / sizeof(char);
00248     }
00249 
00250     return(val);
00251 }
00252 
00253 
00258 void chaco_flush_line(
00259 FILE *infile    /* file to read value from */
00260 )
00261 {
00262     char      c;    /* character being read */
00263 
00264     c = fgetc(infile);
00265     while (c != '\n' && c != '\f')
00266   c = fgetc(infile);
00267 }
00268 
00275 int chaco_input_graph(
00276 FILE *fin,      /* input file */
00277 char     *inname,   /* name of input file */
00278 int     **start,    /* start of edge list for each vertex */
00279 int     **adjacency,    /* edge list data */
00280 int      *nvtxs,    /* number of vertices in graph */
00281 int      *vwgt_dim,   /* # of vertex weights per node */
00282 float   **vweights,   /* vertex weight list data */
00283 int      *ewgt_dim,   /* # of edge weights per edge */
00284 float   **eweights    /* edge weight list data */
00285 )
00286 {
00287   int      *adjptr;   /* loops through adjacency data */
00288   float    *ewptr;    /* loops through edge weight data */
00289   int       narcs;    /* number of edges expected in graph */
00290   int       nedges;   /* twice number of edges really in graph */
00291   int       nedge;    /* loops through edges for each vertex */
00292   int       flag;   /* condition indicator */
00293   int       skip_flag;  /* should this edge be ignored? */
00294   int       end_flag;   /* indicates end of line or file */
00295   int       vtx;    /* vertex in graph */
00296   int       line_num;   /* line number in input file */
00297   int       sum_edges;  /* total number of edges read so far */
00298   int       option = 0; /* input option */
00299   int       using_ewgts;  /* are edge weights in input file? */
00300   int       using_vwgts;  /* are vertex weights in input file? */
00301   int       vtxnums;    /* are vertex numbers in input file? */
00302   int       vertex;   /* current vertex being read */
00303   int       new_vertex; /* new vertex being read */
00304   float     weight;   /* weight being read */
00305   float     eweight;    /* edge weight being read */
00306   int       neighbor;   /* neighbor of current vertex */
00307   int       self_edge;  /* is a self edge encountered? */
00308   int       ignore_me;  /* is this edge being ignored? */
00309   int       ignored;    /* how many edges are ignored? */
00310   int       error_flag; /* error reading input? */
00311   int       j;    /* loop counters */
00312 
00313   /* Read first line  of input (= nvtxs, narcs, option). */
00314   /* The (decimal) digits of the option variable mean: 1's digit not zero => input
00315      edge weights 10's digit not zero => input vertex weights 100's digit not zero
00316      => include vertex numbers */
00317 
00318   *start = NULL;
00319   *adjacency = NULL;
00320   *vweights = NULL;
00321   *eweights = NULL;
00322 
00323   error_flag = 0;
00324   line_num = 0;
00325 
00326   /* Read any leading comment lines */
00327   end_flag = 1;
00328   while (end_flag == 1) {
00329   *nvtxs = chaco_read_int(fin, &end_flag);
00330   ++line_num;
00331   }
00332   if (*nvtxs <= 0) {
00333   printf("ERROR in graph file `%s':", inname);
00334   printf(" Invalid number of vertices (%d).\n", *nvtxs);
00335   fclose(fin);
00336   return(1);
00337   }
00338 
00339   narcs = chaco_read_int(fin, &end_flag);
00340   if (narcs < 0) {
00341   printf("ERROR in graph file `%s':", inname);
00342   printf(" Invalid number of expected edges (%d).\n", narcs);
00343   fclose(fin);
00344   return(1);
00345   }
00346 
00347   /*  Check if vertex or edge weights are used */
00348   if (!end_flag) {
00349   option = chaco_read_int(fin, &end_flag);
00350   }
00351   using_ewgts = option - 10 * (option / 10);
00352   option /= 10;
00353   using_vwgts = option - 10 * (option / 10);
00354   option /= 10;
00355   vtxnums = option - 10 * (option / 10);
00356 
00357   /* Get weight dimensions from Chaco option */
00358   (*vwgt_dim) = using_vwgts;
00359   (*ewgt_dim) = using_ewgts;
00360 
00361   /* Read weight dimensions if they are specified separately */
00362   if (!end_flag && using_vwgts==1){
00363      j = chaco_read_int(fin, &end_flag);
00364      if (!end_flag) (*vwgt_dim) = j;
00365   }
00366   if (!end_flag && using_ewgts==1){
00367      j = chaco_read_int(fin, &end_flag);
00368      if (!end_flag) (*ewgt_dim) = j;
00369   }
00370 
00371   /* Discard rest of line */
00372   while (!end_flag)
00373   j = chaco_read_int(fin, &end_flag);
00374 
00375   /* Allocate space for rows and columns. */
00376   *start = (int *) malloc((unsigned) (*nvtxs + 1) * sizeof(int));
00377   if (narcs != 0)
00378   *adjacency = (int *) malloc((unsigned) (2 * narcs + 1) * sizeof(int));
00379   else
00380   *adjacency = NULL;
00381 
00382   if (using_vwgts)
00383   *vweights = (float *) malloc((unsigned) (*nvtxs) * (*vwgt_dim) * sizeof(float));
00384   else
00385   *vweights = NULL;
00386 
00387   if (using_ewgts)
00388   *eweights = (float *)
00389                    malloc((unsigned) (2 * narcs + 1) * (*ewgt_dim) * sizeof(float));
00390   else
00391   *eweights = NULL;
00392 
00393   adjptr = *adjacency;
00394   ewptr = *eweights;
00395   self_edge = 0;
00396   ignored = 0;
00397 
00398   sum_edges = 0;
00399   nedges = 0;
00400   (*start)[0] = 0;
00401   vertex = 0;
00402   vtx = 0;
00403   new_vertex = 1;
00404   while ((using_vwgts || vtxnums || narcs) && end_flag != -1) {
00405   ++line_num;
00406 
00407   /* If multiple input lines per vertex, read vertex number. */
00408   if (vtxnums) {
00409     j = chaco_read_int(fin, &end_flag);
00410     if (end_flag) {
00411     if (vertex == *nvtxs)
00412       break;
00413     printf("ERROR in graph file `%s':", inname);
00414     printf(" no vertex number in line %d.\n", line_num);
00415     fclose(fin);
00416     return (1);
00417     }
00418     if (j != vertex && j != vertex + 1) {
00419     printf("ERROR in graph file `%s':", inname);
00420     printf(" out-of-order vertex number in line %d.\n", line_num);
00421     fclose(fin);
00422     return (1);
00423     }
00424     if (j != vertex) {
00425     new_vertex = 1;
00426     vertex = j;
00427     }
00428     else
00429     new_vertex = 0;
00430   }
00431   else
00432     vertex = ++vtx;
00433 
00434   if (vertex > *nvtxs)
00435     break;
00436 
00437   /* If vertices are weighted, read vertex weight. */
00438   if (using_vwgts && new_vertex) {
00439           for (j=0; j<(*vwgt_dim); j++){
00440       weight = chaco_read_val(fin, &end_flag);
00441       if (end_flag) {
00442       printf("ERROR in graph file `%s':", inname);
00443       printf(" not enough weights for vertex %d.\n", vertex);
00444       fclose(fin);
00445       return (1);
00446       }
00447       (*vweights)[(vertex-1)*(*vwgt_dim)+j] = weight;
00448     }
00449   }
00450 
00451   nedge = 0;
00452 
00453   /* Read number of adjacent vertex. */
00454   neighbor = chaco_read_int(fin, &end_flag);
00455 
00456   while (!end_flag) {
00457     skip_flag = 0;
00458     ignore_me = 0;
00459 
00460     if (using_ewgts) {  /* Read edge weight if it's being input. */
00461               for (j=0; j<(*ewgt_dim); j++){
00462       eweight = chaco_read_val(fin, &end_flag);
00463 
00464       if (end_flag) {
00465           printf("ERROR in graph file `%s':", inname);
00466           printf(" not enough weights for edge (%d,%d).\n", vertex, neighbor);
00467           fclose(fin);
00468           return (1);
00469       }
00470 
00471       else {
00472           *ewptr++ = eweight;
00473       }
00474     }
00475     }
00476 
00477     /* Add edge to data structure. */
00478     if (!skip_flag) {
00479     if (++nedges > 2*narcs) {
00480       printf("ERROR in graph file `%s':", inname);
00481       printf(" at least %d adjacencies entered, but nedges = %d\n",
00482       nedges, narcs);
00483       fclose(fin);
00484       return (1);
00485     }
00486     *adjptr++ = neighbor;
00487     nedge++;
00488     }
00489 
00490     /* Read number of next adjacent vertex. */
00491     neighbor = chaco_read_int(fin, &end_flag);
00492   }
00493 
00494   sum_edges += nedge;
00495   (*start)[vertex] = sum_edges;
00496   }
00497 
00498   /* Make sure there's nothing else in file. */
00499   flag = 0;
00500   while (!flag && end_flag != -1) {
00501   chaco_read_int(fin, &end_flag);
00502   if (!end_flag)
00503     flag = 1;
00504   }
00505 
00506   (*start)[*nvtxs] = sum_edges;
00507 
00508   if (vertex != 0) {    /* Normal file was read. */
00509       if (narcs) {
00510       }
00511       else { /* no edges, but did have vertex weights or vertex numbers */
00512       free(*start);
00513     *start = NULL;
00514     if (*adjacency != NULL)
00515         free(*adjacency);
00516     *adjacency = NULL;
00517     if (*eweights != NULL)
00518         free(*eweights);
00519           *eweights = NULL;
00520       }
00521   }
00522 
00523   else {
00524   /* Graph was empty */
00525   free(*start);
00526   if (*adjacency != NULL)
00527     free(*adjacency);
00528   if (*vweights != NULL)
00529     free(*vweights);
00530   if (*eweights != NULL)
00531     free(*eweights);
00532   *start = NULL;
00533   *adjacency = NULL;
00534   }
00535 
00536   fclose(fin);
00537 
00538   return (error_flag);
00539 }
00540 
00541 
00548 int chaco_input_geom(
00549 FILE *fingeom,    /* geometry input file */
00550 char     *geomname,   /* name of geometry file */
00551 int       nvtxs,    /* number of coordinates to read */
00552 int      *igeom,    /* dimensionality of geometry */
00553 float   **x,            /* coordinates of vertices */
00554 float   **y,
00555 float   **z
00556 )
00557 {
00558     float     xc, yc, zc =0;  /* first x, y, z coordinate */
00559     int       nread;    /* number of lines of coordinates read */
00560     int       flag;   /* any bad data at end of file? */
00561     int       line_num;   /* counts input lines in file */
00562     int       end_flag;   /* return conditional */
00563     int       ndims;    /* number of values in an input line */
00564     int       i=0;    /* loop counter */
00565 
00566     *x = *y = *z = NULL;
00567     line_num = 0;
00568     end_flag = 1;
00569     while (end_flag == 1) {
00570   xc = chaco_read_val(fingeom, &end_flag);
00571   ++line_num;
00572     }
00573 
00574     if (end_flag == -1) {
00575   printf("No values found in geometry file `%s'\n", geomname);
00576   fclose(fingeom);
00577   return (1);
00578     }
00579 
00580     ndims = 1;
00581     yc = chaco_read_val(fingeom, &end_flag);
00582     if (end_flag == 0) {
00583   ndims = 2;
00584   zc = chaco_read_val(fingeom, &end_flag);
00585   if (end_flag == 0) {
00586       ndims = 3;
00587       chaco_read_val(fingeom, &end_flag);
00588       if (!end_flag) {
00589     printf("Too many values on input line of geometry file `%s'\n",
00590            geomname);
00591 
00592     printf(" Maximum dimensionality is 3\n");
00593     fclose(fingeom);
00594     return (1);
00595       }
00596   }
00597     }
00598 
00599     *igeom = ndims;
00600 
00601     *x = (float *) malloc((unsigned) nvtxs * sizeof(float));
00602     (*x)[0] = xc;
00603     if (ndims > 1) {
00604   *y = (float *) malloc((unsigned) nvtxs * sizeof(float));
00605   (*y)[0] = yc;
00606     }
00607     if (ndims > 2) {
00608   *z = (float *) malloc((unsigned) nvtxs * sizeof(float));
00609   (*z)[0] = zc;
00610     }
00611 
00612     for (nread = 1; nread < nvtxs; nread++) {
00613   ++line_num;
00614   if (ndims == 1) {
00615       i = fscanf(fingeom, "%f", &((*x)[nread]));
00616   }
00617   else if (ndims == 2) {
00618       i = fscanf(fingeom, "%f%f", &((*x)[nread]), &((*y)[nread]));
00619   }
00620   else if (ndims == 3) {
00621       i = fscanf(fingeom, "%f%f%f", &((*x)[nread]), &((*y)[nread]),
00622            &((*z)[nread]));
00623   }
00624 
00625   if (i == EOF) {
00626       printf("Too few lines of values in geometry file; nvtxs=%d, but only %d read\n",
00627        nvtxs, nread);
00628       fclose(fingeom);
00629       return (1);
00630   }
00631   else if (i != ndims) {
00632       printf("Wrong number of values in line %d of geometry file `%s'\n",
00633        line_num, geomname);
00634       fclose(fingeom);
00635       return (1);
00636   }
00637     }
00638 
00639     /* Check for spurious extra stuff in file. */
00640     flag = 0;
00641     end_flag = 0;
00642     while (!flag && end_flag != -1) {
00643   chaco_read_val(fingeom, &end_flag);
00644   if (!end_flag)
00645       flag = 1;
00646     }
00647 
00648     fclose(fingeom);
00649 
00650     return (0);
00651 }
00652 
00653 }  // namespace Zoltan2