Zoltan2
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      *nVwgts,   /* # of vertex weights per node */
00282 float   **vweights,   /* vertex weight list data */
00283 int      *nEwgts,   /* # 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       error_flag; /* error reading input? */
00308   int       j;    /* loop counters */
00309 
00310   /* Read first line  of input (= nvtxs, narcs, option). */
00311   /* The (decimal) digits of the option variable mean: 1's digit not zero => input
00312      edge weights 10's digit not zero => input vertex weights 100's digit not zero
00313      => include vertex numbers */
00314 
00315   *start = NULL;
00316   *adjacency = NULL;
00317   *vweights = NULL;
00318   *eweights = NULL;
00319 
00320   error_flag = 0;
00321   line_num = 0;
00322 
00323   /* Read any leading comment lines */
00324   end_flag = 1;
00325   while (end_flag == 1) {
00326   *nvtxs = chaco_read_int(fin, &end_flag);
00327   ++line_num;
00328   }
00329   if (*nvtxs <= 0) {
00330   printf("ERROR in graph file `%s':", inname);
00331   printf(" Invalid number of vertices (%d).\n", *nvtxs);
00332   fclose(fin);
00333   return(1);
00334   }
00335 
00336   narcs = chaco_read_int(fin, &end_flag);
00337   if (narcs < 0) {
00338   printf("ERROR in graph file `%s':", inname);
00339   printf(" Invalid number of expected edges (%d).\n", narcs);
00340   fclose(fin);
00341   return(1);
00342   }
00343 
00344   /*  Check if vertex or edge weights are used */
00345   if (!end_flag) {
00346   option = chaco_read_int(fin, &end_flag);
00347   }
00348   using_ewgts = option - 10 * (option / 10);
00349   option /= 10;
00350   using_vwgts = option - 10 * (option / 10);
00351   option /= 10;
00352   vtxnums = option - 10 * (option / 10);
00353 
00354   /* Get weight info from Chaco option */
00355   (*nVwgts) = using_vwgts;
00356   (*nEwgts) = using_ewgts;
00357 
00358   /* Read numbers of weights if they are specified separately */
00359   if (!end_flag && using_vwgts==1){
00360      j = chaco_read_int(fin, &end_flag);
00361      if (!end_flag) (*nVwgts) = j;
00362   }
00363   if (!end_flag && using_ewgts==1){
00364      j = chaco_read_int(fin, &end_flag);
00365      if (!end_flag) (*nEwgts) = j;
00366   }
00367 
00368   /* Discard rest of line */
00369   while (!end_flag)
00370   j = chaco_read_int(fin, &end_flag);
00371 
00372   /* Allocate space for rows and columns. */
00373   *start = (int *) malloc((unsigned) (*nvtxs + 1) * sizeof(int));
00374   if (narcs != 0)
00375   *adjacency = (int *) malloc((unsigned) (2 * narcs + 1) * sizeof(int));
00376   else
00377   *adjacency = NULL;
00378 
00379   if (using_vwgts)
00380   *vweights = (float *) malloc((unsigned) (*nvtxs) * (*nVwgts) * sizeof(float));
00381   else
00382   *vweights = NULL;
00383 
00384   if (using_ewgts)
00385   *eweights = (float *)
00386                    malloc((unsigned) (2 * narcs + 1) * (*nEwgts) * sizeof(float));
00387   else
00388   *eweights = NULL;
00389 
00390   adjptr = *adjacency;
00391   ewptr = *eweights;
00392 
00393   sum_edges = 0;
00394   nedges = 0;
00395   (*start)[0] = 0;
00396   vertex = 0;
00397   vtx = 0;
00398   new_vertex = 1;
00399   while ((using_vwgts || vtxnums || narcs) && end_flag != -1) {
00400   ++line_num;
00401 
00402   /* If multiple input lines per vertex, read vertex number. */
00403   if (vtxnums) {
00404     j = chaco_read_int(fin, &end_flag);
00405     if (end_flag) {
00406     if (vertex == *nvtxs)
00407       break;
00408     printf("ERROR in graph file `%s':", inname);
00409     printf(" no vertex number in line %d.\n", line_num);
00410     fclose(fin);
00411     return (1);
00412     }
00413     if (j != vertex && j != vertex + 1) {
00414     printf("ERROR in graph file `%s':", inname);
00415     printf(" out-of-order vertex number in line %d.\n", line_num);
00416     fclose(fin);
00417     return (1);
00418     }
00419     if (j != vertex) {
00420     new_vertex = 1;
00421     vertex = j;
00422     }
00423     else
00424     new_vertex = 0;
00425   }
00426   else
00427     vertex = ++vtx;
00428 
00429   if (vertex > *nvtxs)
00430     break;
00431 
00432   /* If vertices are weighted, read vertex weight. */
00433   if (using_vwgts && new_vertex) {
00434           for (j=0; j<(*nVwgts); j++){
00435       weight = chaco_read_val(fin, &end_flag);
00436       if (end_flag) {
00437       printf("ERROR in graph file `%s':", inname);
00438       printf(" not enough weights for vertex %d.\n", vertex);
00439       fclose(fin);
00440       return (1);
00441       }
00442       (*vweights)[(vertex-1)*(*nVwgts)+j] = weight;
00443     }
00444   }
00445 
00446   nedge = 0;
00447 
00448   /* Read number of adjacent vertex. */
00449   neighbor = chaco_read_int(fin, &end_flag);
00450 
00451   while (!end_flag) {
00452     skip_flag = 0;
00453 
00454     if (using_ewgts) {  /* Read edge weight if it's being input. */
00455               for (j=0; j<(*nEwgts); j++){
00456       eweight = chaco_read_val(fin, &end_flag);
00457 
00458       if (end_flag) {
00459           printf("ERROR in graph file `%s':", inname);
00460           printf(" not enough weights for edge (%d,%d).\n", vertex, neighbor);
00461           fclose(fin);
00462           return (1);
00463       }
00464 
00465       else {
00466           *ewptr++ = eweight;
00467       }
00468     }
00469     }
00470 
00471     /* Add edge to data structure. */
00472     if (!skip_flag) {
00473     if (++nedges > 2*narcs) {
00474       printf("ERROR in graph file `%s':", inname);
00475       printf(" at least %d adjacencies entered, but nedges = %d\n",
00476       nedges, narcs);
00477       fclose(fin);
00478       return (1);
00479     }
00480     *adjptr++ = neighbor;
00481     nedge++;
00482     }
00483 
00484     /* Read number of next adjacent vertex. */
00485     neighbor = chaco_read_int(fin, &end_flag);
00486   }
00487 
00488   sum_edges += nedge;
00489   (*start)[vertex] = sum_edges;
00490   }
00491 
00492   /* Make sure there's nothing else in file. */
00493   flag = 0;
00494   while (!flag && end_flag != -1) {
00495   chaco_read_int(fin, &end_flag);
00496   if (!end_flag)
00497     flag = 1;
00498   }
00499 
00500   (*start)[*nvtxs] = sum_edges;
00501 
00502   if (vertex != 0) {    /* Normal file was read. */
00503       if (narcs) {
00504       }
00505       else { /* no edges, but did have vertex weights or vertex numbers */
00506       free(*start);
00507     *start = NULL;
00508     if (*adjacency != NULL)
00509         free(*adjacency);
00510     *adjacency = NULL;
00511     if (*eweights != NULL)
00512         free(*eweights);
00513           *eweights = NULL;
00514       }
00515   }
00516 
00517   else {
00518   /* Graph was empty */
00519   free(*start);
00520   if (*adjacency != NULL)
00521     free(*adjacency);
00522   if (*vweights != NULL)
00523     free(*vweights);
00524   if (*eweights != NULL)
00525     free(*eweights);
00526   *start = NULL;
00527   *adjacency = NULL;
00528   }
00529 
00530   fclose(fin);
00531 
00532   return (error_flag);
00533 }
00534 
00535 
00542 int chaco_input_geom(
00543 FILE *fingeom,    /* geometry input file */
00544 char     *geomname,   /* name of geometry file */
00545 int       nvtxs,    /* number of coordinates to read */
00546 int      *igeom,    /* dimensionality of geometry */
00547 float   **x,            /* coordinates of vertices */
00548 float   **y,
00549 float   **z
00550 )
00551 {
00552     float     xc, yc, zc =0;  /* first x, y, z coordinate */
00553     int       nread;    /* number of lines of coordinates read */
00554     int       flag;   /* any bad data at end of file? */
00555     int       line_num;   /* counts input lines in file */
00556     int       end_flag;   /* return conditional */
00557     int       ndims;    /* number of values in an input line */
00558     int       i=0;    /* loop counter */
00559 
00560     *x = *y = *z = NULL;
00561     line_num = 0;
00562     end_flag = 1;
00563     while (end_flag == 1) {
00564   xc = chaco_read_val(fingeom, &end_flag);
00565   ++line_num;
00566     }
00567 
00568     if (end_flag == -1) {
00569   printf("No values found in geometry file `%s'\n", geomname);
00570   fclose(fingeom);
00571   return (1);
00572     }
00573 
00574     ndims = 1;
00575     yc = chaco_read_val(fingeom, &end_flag);
00576     if (end_flag == 0) {
00577   ndims = 2;
00578   zc = chaco_read_val(fingeom, &end_flag);
00579   if (end_flag == 0) {
00580       ndims = 3;
00581       chaco_read_val(fingeom, &end_flag);
00582       if (!end_flag) {
00583     printf("Too many values on input line of geometry file `%s'\n",
00584            geomname);
00585 
00586     printf(" Maximum dimensionality is 3\n");
00587     fclose(fingeom);
00588     return (1);
00589       }
00590   }
00591     }
00592 
00593     *igeom = ndims;
00594 
00595     *x = (float *) malloc((unsigned) nvtxs * sizeof(float));
00596     (*x)[0] = xc;
00597     if (ndims > 1) {
00598   *y = (float *) malloc((unsigned) nvtxs * sizeof(float));
00599   (*y)[0] = yc;
00600     }
00601     if (ndims > 2) {
00602   *z = (float *) malloc((unsigned) nvtxs * sizeof(float));
00603   (*z)[0] = zc;
00604     }
00605 
00606     for (nread = 1; nread < nvtxs; nread++) {
00607   ++line_num;
00608   if (ndims == 1) {
00609       i = fscanf(fingeom, "%f", &((*x)[nread]));
00610   }
00611   else if (ndims == 2) {
00612       i = fscanf(fingeom, "%f%f", &((*x)[nread]), &((*y)[nread]));
00613   }
00614   else if (ndims == 3) {
00615       i = fscanf(fingeom, "%f%f%f", &((*x)[nread]), &((*y)[nread]),
00616            &((*z)[nread]));
00617   }
00618 
00619   if (i == EOF) {
00620       printf("Too few lines of values in geometry file; nvtxs=%d, but only %d read\n",
00621        nvtxs, nread);
00622       fclose(fingeom);
00623       return (1);
00624   }
00625   else if (i != ndims) {
00626       printf("Wrong number of values in line %d of geometry file `%s'\n",
00627        line_num, geomname);
00628       fclose(fingeom);
00629       return (1);
00630   }
00631     }
00632 
00633     /* Check for spurious extra stuff in file. */
00634     flag = 0;
00635     end_flag = 0;
00636     while (!flag && end_flag != -1) {
00637   chaco_read_val(fingeom, &end_flag);
00638   if (!end_flag)
00639       flag = 1;
00640     }
00641 
00642     fclose(fingeom);
00643 
00644     return (0);
00645 }
00646 
00647 }  // namespace Zoltan2