glphbm.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* glphbm.c */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#define _GLPSTD_ERRNO
#define _GLPSTD_STDIO
#include "glphbm.h"
#include "glplib.h"

/***********************************************************************
*  NAME
*
*  hbm_read_mat - read sparse matrix in Harwell-Boeing format
*
*  SYNOPSIS
*
*  #include "glphbm.h"
*  HBM *hbm_read_mat(const char *fname);
*
*  DESCRIPTION
*
*  The routine hbm_read_mat reads a sparse matrix in the Harwell-Boeing
*  format from a text file whose name is the character string fname.
*
*  Detailed description of the Harwell-Boeing format recognised by this
*  routine is given in the following report:
*
*  I.S.Duff, R.G.Grimes, J.G.Lewis. User's Guide for the Harwell-Boeing
*  Sparse Matrix Collection (Release I), TR/PA/92/86, October 1992.
*
*  RETURNS
*
*  If no error occured, the routine hbm_read_mat returns a pointer to
*  a data structure containing the matrix. In case of error the routine
*  prints an appropriate error message and returns NULL. */

struct dsa
{     /* working area used by routine hbm_read_mat */
      const char *fname;
      /* name of input text file */
      FILE *fp;
      /* stream assigned to input text file */
      int seqn;
      /* card sequential number */
      char card[80+1];
      /* card image buffer */
      int fmt_p;
      /* scale factor */
      int fmt_k;
      /* iterator */
      int fmt_f;
      /* format code */
      int fmt_w;
      /* field width */
      int fmt_d;
      /* number of decimal places after point */
};

/***********************************************************************
*  read_card - read next data card
*
*  This routine reads the next 80-column card from the input text file
*  and stores its image into the character string card. If the card was
*  read successfully, the routine returns zero, otherwise non-zero. */

static int read_card(struct dsa *dsa)
{     int k, c;
      dsa->seqn++;
      memset(dsa->card, ' ', 80), dsa->card[80] = '\0';
      k = 0;
      for (;;)
      {  c = fgetc(dsa->fp);
         if (ferror(dsa->fp))
         {  xprintf("%s:%d: read error - %s\n", dsa->fname, dsa->seqn,
               strerror(errno));
            return 1;
         }
         if (feof(dsa->fp))
         {  if (k == 0)
               xprintf("%s:%d: unexpected EOF\n", dsa->fname,
                  dsa->seqn);
            else
               xprintf("%s:%d: missing final LF\n", dsa->fname,
                  dsa->seqn);
            return 1;
         }
         if (c == '\r') continue;
         if (c == '\n') break;
         if (iscntrl(c))
         {  xprintf("%s:%d: invalid control character 0x%02X\n",
               dsa->fname, dsa->seqn, c);
            return 1;
         }
         if (k == 80)
         {  xprintf("%s:%d: card image too long\n", dsa->fname,
               dsa->seqn);
            return 1;
         }
         dsa->card[k++] = (char)c;
      }
      return 0;
}

/***********************************************************************
*  scan_int - scan integer value from the current card
*
*  This routine scans an integer value from the current card, where fld
*  is the name of the field, pos is the position of the field, width is
*  the width of the field, val points to a location to which the scanned
*  value should be stored. If the value was scanned successfully, the
*  routine returns zero, otherwise non-zero. */

static int scan_int(struct dsa *dsa, char *fld, int pos, int width,
      int *val)
{     char str[80+1];
      xassert(1 <= width && width <= 80);
      memcpy(str, dsa->card + pos, width), str[width] = '\0';
      if (str2int(strspx(str), val))
      {  xprintf("%s:%d: field `%s' contains invalid value `%s'\n",
            dsa->fname, dsa->seqn, fld, str);
         return 1;
      }
      return 0;
}

/***********************************************************************
*  parse_fmt - parse Fortran format specification
*
*  This routine parses the Fortran format specification represented as
*  character string which fmt points to and stores format elements into
*  appropriate static locations. Should note that not all valid Fortran
*  format specifications may be recognised. If the format specification
*  was recognised, the routine returns zero, otherwise non-zero. */

static int parse_fmt(struct dsa *dsa, char *fmt)
{     int k, s, val;
      char str[80+1];
      /* first character should be left parenthesis */
      if (fmt[0] != '(')
fail: {  xprintf("hbm_read_mat: format `%s' not recognised\n", fmt);
         return 1;
      }
      k = 1;
      /* optional scale factor */
      dsa->fmt_p = 0;
      if (isdigit((unsigned char)fmt[k]))
      {  s = 0;
         while (isdigit((unsigned char)fmt[k]))
         {  if (s == 80) goto fail;
            str[s++] = fmt[k++];
         }
         str[s] = '\0';
         if (str2int(str, &val)) goto fail;
         if (toupper((unsigned char)fmt[k]) != 'P') goto iter;
         dsa->fmt_p = val, k++;
         if (!(0 <= dsa->fmt_p && dsa->fmt_p <= 255)) goto fail;
         /* optional comma may follow scale factor */
         if (fmt[k] == ',') k++;
      }
      /* optional iterator */
      dsa->fmt_k = 1;
      if (isdigit((unsigned char)fmt[k]))
      {  s = 0;
         while (isdigit((unsigned char)fmt[k]))
         {  if (s == 80) goto fail;
            str[s++] = fmt[k++];
         }
         str[s] = '\0';
         if (str2int(str, &val)) goto fail;
iter:    dsa->fmt_k = val;
         if (!(1 <= dsa->fmt_k && dsa->fmt_k <= 255)) goto fail;
      }
      /* format code */
      dsa->fmt_f = toupper((unsigned char)fmt[k++]);
      if (!(dsa->fmt_f == 'D' || dsa->fmt_f == 'E' ||
            dsa->fmt_f == 'F' || dsa->fmt_f == 'G' ||
            dsa->fmt_f == 'I')) goto fail;
      /* field width */
      if (!isdigit((unsigned char)fmt[k])) goto fail;
      s = 0;
      while (isdigit((unsigned char)fmt[k]))
      {  if (s == 80) goto fail;
         str[s++] = fmt[k++];
      }
      str[s] = '\0';
      if (str2int(str, &dsa->fmt_w)) goto fail;
      if (!(1 <= dsa->fmt_w && dsa->fmt_w <= 255)) goto fail;
      /* optional number of decimal places after point */
      dsa->fmt_d = 0;
      if (fmt[k] == '.')
      {  k++;
         if (!isdigit((unsigned char)fmt[k])) goto fail;
         s = 0;
         while (isdigit((unsigned char)fmt[k]))
         {  if (s == 80) goto fail;
            str[s++] = fmt[k++];
         }
         str[s] = '\0';
         if (str2int(str, &dsa->fmt_d)) goto fail;
         if (!(0 <= dsa->fmt_d && dsa->fmt_d <= 255)) goto fail;
      }
      /* last character should be right parenthesis */
      if (!(fmt[k] == ')' && fmt[k+1] == '\0')) goto fail;
      return 0;
}

/***********************************************************************
*  read_int_array - read array of integer type
*
*  This routine reads an integer array from the input text file, where
*  name is array name, fmt is Fortran format specification that controls
*  reading, n is number of array elements, val is array of integer type.
*  If the array was read successful, the routine returns zero, otherwise
*  non-zero. */

static int read_int_array(struct dsa *dsa, char *name, char *fmt,
      int n, int val[])
{     int k, pos;
      char str[80+1];
      if (parse_fmt(dsa, fmt)) return 1;
      if (!(dsa->fmt_f == 'I' && dsa->fmt_w <= 80 &&
            dsa->fmt_k * dsa->fmt_w <= 80))
      {  xprintf(
            "%s:%d: can't read array `%s' - invalid format `%s'\n",
            dsa->fname, dsa->seqn, name, fmt);
         return 1;
      }
      for (k = 1, pos = INT_MAX; k <= n; k++, pos++)
      {  if (pos >= dsa->fmt_k)
         {  if (read_card(dsa)) return 1;
            pos = 0;
         }
         memcpy(str, dsa->card + dsa->fmt_w * pos, dsa->fmt_w);
         str[dsa->fmt_w] = '\0';
         strspx(str);
         if (str2int(str, &val[k]))
         {  xprintf(
               "%s:%d: can't read array `%s' - invalid value `%s'\n",
               dsa->fname, dsa->seqn, name, str);
            return 1;
         }