alpar@9: /* glpdmx.c (reading/writing data in DIMACS format) */
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@9: *
alpar@9: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9: *  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9: *  E-mail: <mao@gnu.org>.
alpar@9: *
alpar@9: *  GLPK is free software: you can redistribute it and/or modify it
alpar@9: *  under the terms of the GNU General Public License as published by
alpar@9: *  the Free Software Foundation, either version 3 of the License, or
alpar@9: *  (at your option) any later version.
alpar@9: *
alpar@9: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9: *  License for more details.
alpar@9: *
alpar@9: *  You should have received a copy of the GNU General Public License
alpar@9: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9: ***********************************************************************/
alpar@9: 
alpar@9: #define _GLPSTD_STDIO
alpar@9: #include "glpapi.h"
alpar@9: 
alpar@9: struct csa
alpar@9: {     /* common storage area */
alpar@9:       jmp_buf jump;
alpar@9:       /* label for go to in case of error */
alpar@9:       const char *fname;
alpar@9:       /* name of input text file */
alpar@9:       XFILE *fp;
alpar@9:       /* stream assigned to input text file */
alpar@9:       int count;
alpar@9:       /* line count */
alpar@9:       int c;
alpar@9:       /* current character */
alpar@9:       char field[255+1];
alpar@9:       /* data field */
alpar@9:       int empty;
alpar@9:       /* warning 'empty line ignored' was printed */
alpar@9:       int nonint;
alpar@9:       /* warning 'non-integer data detected' was printed */
alpar@9: };
alpar@9: 
alpar@9: static void error(struct csa *csa, const char *fmt, ...)
alpar@9: {     /* print error message and terminate processing */
alpar@9:       va_list arg;
alpar@9:       xprintf("%s:%d: error: ", csa->fname, csa->count);
alpar@9:       va_start(arg, fmt);
alpar@9:       xvprintf(fmt, arg);
alpar@9:       va_end(arg);
alpar@9:       xprintf("\n");
alpar@9:       longjmp(csa->jump, 1);
alpar@9:       /* no return */
alpar@9: }
alpar@9: 
alpar@9: static void warning(struct csa *csa, const char *fmt, ...)
alpar@9: {     /* print warning message and continue processing */
alpar@9:       va_list arg;
alpar@9:       xprintf("%s:%d: warning: ", csa->fname, csa->count);
alpar@9:       va_start(arg, fmt);
alpar@9:       xvprintf(fmt, arg);
alpar@9:       va_end(arg);
alpar@9:       xprintf("\n");
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: static void read_char(struct csa *csa)
alpar@9: {     /* read character from input text file */
alpar@9:       int c;
alpar@9:       if (csa->c == '\n') csa->count++;
alpar@9:       c = xfgetc(csa->fp);
alpar@9:       if (c < 0)
alpar@9:       {  if (xferror(csa->fp))
alpar@9:             error(csa, "read error - %s", xerrmsg());
alpar@9:          else if (csa->c == '\n')
alpar@9:             error(csa, "unexpected end of file");
alpar@9:          else
alpar@9:          {  warning(csa, "missing final end of line");
alpar@9:             c = '\n';
alpar@9:          }
alpar@9:       }
alpar@9:       else if (c == '\n')
alpar@9:          ;
alpar@9:       else if (isspace(c))
alpar@9:          c = ' ';
alpar@9:       else if (iscntrl(c))
alpar@9:          error(csa, "invalid control character 0x%02X", c);
alpar@9:       csa->c = c;
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: static void read_designator(struct csa *csa)
alpar@9: {     /* read one-character line designator */
alpar@9:       xassert(csa->c == '\n');
alpar@9:       read_char(csa);
alpar@9:       for (;;)
alpar@9:       {  /* skip preceding white-space characters */
alpar@9:          while (csa->c == ' ')
alpar@9:             read_char(csa);
alpar@9:          if (csa->c == '\n')
alpar@9:          {  /* ignore empty line */
alpar@9:             if (!csa->empty)
alpar@9:             {  warning(csa, "empty line ignored");
alpar@9:                csa->empty = 1;
alpar@9:             }
alpar@9:             read_char(csa);
alpar@9:          }
alpar@9:          else if (csa->c == 'c')
alpar@9:          {  /* skip comment line */
alpar@9:             while (csa->c != '\n')
alpar@9:                read_char(csa);
alpar@9:             read_char(csa);
alpar@9:          }
alpar@9:          else
alpar@9:          {  /* hmm... looks like a line designator */
alpar@9:             csa->field[0] = (char)csa->c, csa->field[1] = '\0';
alpar@9:             /* check that it is followed by a white-space character */
alpar@9:             read_char(csa);
alpar@9:             if (!(csa->c == ' ' || csa->c == '\n'))
alpar@9:                error(csa, "line designator missing or invalid");
alpar@9:             break;
alpar@9:          }
alpar@9:       }
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: static void read_field(struct csa *csa)
alpar@9: {     /* read data field */
alpar@9:       int len = 0;
alpar@9:       /* skip preceding white-space characters */
alpar@9:       while (csa->c == ' ')
alpar@9:          read_char(csa);
alpar@9:       /* scan data field */
alpar@9:       if (csa->c == '\n')
alpar@9:          error(csa, "unexpected end of line");
alpar@9:       while (!(csa->c == ' ' || csa->c == '\n'))
alpar@9:       {  if (len == sizeof(csa->field)-1)
alpar@9:             error(csa, "data field `%.15s...' too long", csa->field);
alpar@9:          csa->field[len++] = (char)csa->c;
alpar@9:          read_char(csa);
alpar@9:       }
alpar@9:       csa->field[len] = '\0';
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: static void end_of_line(struct csa *csa)
alpar@9: {     /* skip white-space characters until end of line */
alpar@9:       while (csa->c == ' ')
alpar@9:          read_char(csa);
alpar@9:       if (csa->c != '\n')
alpar@9:          error(csa, "too many data fields specified");
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: static void check_int(struct csa *csa, double num)
alpar@9: {     /* print a warning if non-integer data are detected */
alpar@9:       if (!csa->nonint && num != floor(num))
alpar@9:       {  warning(csa, "non-integer data detected");
alpar@9:          csa->nonint = 1;
alpar@9:       }
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_read_mincost - read min-cost flow problem data in DIMACS format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
alpar@9: *     int a_cost, const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_read_mincost reads minimum cost flow problem data in
alpar@9: *  DIMACS format from a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
alpar@9:       int a_cost, const char *fname)
alpar@9: {     struct csa _csa, *csa = &_csa;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *a;
alpar@9:       int i, j, k, nv, na, ret = 0;
alpar@9:       double rhs, low, cap, cost;
alpar@9:       char *flag = NULL;
alpar@9:       if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double))
alpar@9:          xerror("glp_read_mincost: v_rhs = %d; invalid offset\n",
alpar@9:             v_rhs);
alpar@9:       if (a_low >= 0 && a_low > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_read_mincost: a_low = %d; invalid offset\n",
alpar@9:             a_low);
alpar@9:       if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_read_mincost: a_cap = %d; invalid offset\n",
alpar@9:             a_cap);
alpar@9:       if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_read_mincost: a_cost = %d; invalid offset\n",
alpar@9:             a_cost);
alpar@9:       glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (setjmp(csa->jump))
alpar@9:       {  ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       csa->fname = fname;
alpar@9:       csa->fp = NULL;
alpar@9:       csa->count = 0;
alpar@9:       csa->c = '\n';
alpar@9:       csa->field[0] = '\0';
alpar@9:       csa->empty = csa->nonint = 0;
alpar@9:       xprintf("Reading min-cost flow problem data from `%s'...\n",
alpar@9:          fname);
alpar@9:       csa->fp = xfopen(fname, "r");
alpar@9:       if (csa->fp == NULL)
alpar@9:       {  xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
alpar@9:          longjmp(csa->jump, 1);
alpar@9:       }
alpar@9:       /* read problem line */
alpar@9:       read_designator(csa);
alpar@9:       if (strcmp(csa->field, "p") != 0)
alpar@9:          error(csa, "problem line missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (strcmp(csa->field, "min") != 0)
alpar@9:          error(csa, "wrong problem designator; `min' expected");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &nv) == 0 && nv >= 0))
alpar@9:          error(csa, "number of nodes missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &na) == 0 && na >= 0))
alpar@9:          error(csa, "number of arcs missing or invalid");
alpar@9:       xprintf("Flow network has %d node%s and %d arc%s\n",
alpar@9:          nv, nv == 1 ? "" : "s", na, na == 1 ? "" : "s");
alpar@9:       if (nv > 0) glp_add_vertices(G, nv);
alpar@9:       end_of_line(csa);
alpar@9:       /* read node descriptor lines */
alpar@9:       flag = xcalloc(1+nv, sizeof(char));
alpar@9:       memset(&flag[1], 0, nv * sizeof(char));
alpar@9:       if (v_rhs >= 0)
alpar@9:       {  rhs = 0.0;
alpar@9:          for (i = 1; i <= nv; i++)
alpar@9:          {  v = G->v[i];
alpar@9:             memcpy((char *)v->data + v_rhs, &rhs, sizeof(double));
alpar@9:          }
alpar@9:       }
alpar@9:       for (;;)
alpar@9:       {  read_designator(csa);
alpar@9:          if (strcmp(csa->field, "n") != 0) break;
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "node number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "node number %d out of range", i);
alpar@9:          if (flag[i])
alpar@9:             error(csa, "duplicate descriptor of node %d", i);
alpar@9:          read_field(csa);
alpar@9:          if (str2num(csa->field, &rhs) != 0)
alpar@9:             error(csa, "node supply/demand missing or invalid");
alpar@9:          check_int(csa, rhs);
alpar@9:          if (v_rhs >= 0)
alpar@9:          {  v = G->v[i];
alpar@9:             memcpy((char *)v->data + v_rhs, &rhs, sizeof(double));
alpar@9:          }
alpar@9:          flag[i] = 1;
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       xfree(flag), flag = NULL;
alpar@9:       /* read arc descriptor lines */
alpar@9:       for (k = 1; k <= na; k++)
alpar@9:       {  if (k > 1) read_designator(csa);
alpar@9:          if (strcmp(csa->field, "a") != 0)
alpar@9:             error(csa, "wrong line designator; `a' expected");
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "starting node number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "starting node number %d out of range", i);
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &j) != 0)
alpar@9:             error(csa, "ending node number missing or invalid");
alpar@9:          if (!(1 <= j && j <= nv))
alpar@9:             error(csa, "ending node number %d out of range", j);
alpar@9:          read_field(csa);
alpar@9:          if (!(str2num(csa->field, &low) == 0 && low >= 0.0))
alpar@9:             error(csa, "lower bound of arc flow missing or invalid");
alpar@9:          check_int(csa, low);
alpar@9:          read_field(csa);
alpar@9:          if (!(str2num(csa->field, &cap) == 0 && cap >= low))
alpar@9:             error(csa, "upper bound of arc flow missing or invalid");
alpar@9:          check_int(csa, cap);
alpar@9:          read_field(csa);
alpar@9:          if (str2num(csa->field, &cost) != 0)
alpar@9:             error(csa, "per-unit cost of arc flow missing or invalid");
alpar@9:          check_int(csa, cost);
alpar@9:          a = glp_add_arc(G, i, j);
alpar@9:          if (a_low >= 0)
alpar@9:             memcpy((char *)a->data + a_low, &low, sizeof(double));
alpar@9:          if (a_cap >= 0)
alpar@9:             memcpy((char *)a->data + a_cap, &cap, sizeof(double));
alpar@9:          if (a_cost >= 0)
alpar@9:             memcpy((char *)a->data + a_cost, &cost, sizeof(double));
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       xprintf("%d lines were read\n", csa->count);
alpar@9: done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (csa->fp != NULL) xfclose(csa->fp);
alpar@9:       if (flag != NULL) xfree(flag);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_write_mincost - write min-cost flow problem data in DIMACS format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_write_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
alpar@9: *     int a_cost, const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_write_mincost writes minimum cost flow problem data
alpar@9: *  in DIMACS format to a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_write_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
alpar@9:       int a_cost, const char *fname)
alpar@9: {     XFILE *fp;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *a;
alpar@9:       int i, count = 0, ret;
alpar@9:       double rhs, low, cap, cost;
alpar@9:       if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double))
alpar@9:          xerror("glp_write_mincost: v_rhs = %d; invalid offset\n",
alpar@9:             v_rhs);
alpar@9:       if (a_low >= 0 && a_low > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_write_mincost: a_low = %d; invalid offset\n",
alpar@9:             a_low);
alpar@9:       if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_write_mincost: a_cap = %d; invalid offset\n",
alpar@9:             a_cap);
alpar@9:       if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_write_mincost: a_cost = %d; invalid offset\n",
alpar@9:             a_cost);
alpar@9:       xprintf("Writing min-cost flow problem data to `%s'...\n",
alpar@9:          fname);
alpar@9:       fp = xfopen(fname, "w");
alpar@9:       if (fp == NULL)
alpar@9:       {  xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xfprintf(fp, "c %s\n",
alpar@9:          G->name == NULL ? "unknown" : G->name), count++;
alpar@9:       xfprintf(fp, "p min %d %d\n", G->nv, G->na), count++;
alpar@9:       if (v_rhs >= 0)
alpar@9:       {  for (i = 1; i <= G->nv; i++)
alpar@9:          {  v = G->v[i];
alpar@9:             memcpy(&rhs, (char *)v->data + v_rhs, sizeof(double));
alpar@9:             if (rhs != 0.0)
alpar@9:                xfprintf(fp, "n %d %.*g\n", i, DBL_DIG, rhs), count++;
alpar@9:          }
alpar@9:       }
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          for (a = v->out; a != NULL; a = a->t_next)
alpar@9:          {  if (a_low >= 0)
alpar@9:                memcpy(&low, (char *)a->data + a_low, sizeof(double));
alpar@9:             else
alpar@9:                low = 0.0;
alpar@9:             if (a_cap >= 0)
alpar@9:                memcpy(&cap, (char *)a->data + a_cap, sizeof(double));
alpar@9:             else
alpar@9:                cap = 1.0;
alpar@9:             if (a_cost >= 0)
alpar@9:                memcpy(&cost, (char *)a->data + a_cost, sizeof(double));
alpar@9:             else
alpar@9:                cost = 0.0;
alpar@9:             xfprintf(fp, "a %d %d %.*g %.*g %.*g\n",
alpar@9:                a->tail->i, a->head->i, DBL_DIG, low, DBL_DIG, cap,
alpar@9:                DBL_DIG, cost), count++;
alpar@9:          }
alpar@9:       }
alpar@9:       xfprintf(fp, "c eof\n"), count++;
alpar@9:       xfflush(fp);
alpar@9:       if (xferror(fp))
alpar@9:       {  xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xprintf("%d lines were written\n", count);
alpar@9:       ret = 0;
alpar@9: done: if (fp != NULL) xfclose(fp);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_read_maxflow - read maximum flow problem data in DIMACS format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_read_maxflow(glp_graph *G, int *s, int *t, int a_cap,
alpar@9: *     const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_read_maxflow reads maximum flow problem data in
alpar@9: *  DIMACS format from a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_read_maxflow(glp_graph *G, int *_s, int *_t, int a_cap,
alpar@9:       const char *fname)
alpar@9: {     struct csa _csa, *csa = &_csa;
alpar@9:       glp_arc *a;
alpar@9:       int i, j, k, s, t, nv, na, ret = 0;
alpar@9:       double cap;
alpar@9:       if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_read_maxflow: a_cap = %d; invalid offset\n",
alpar@9:             a_cap);
alpar@9:       glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (setjmp(csa->jump))
alpar@9:       {  ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       csa->fname = fname;
alpar@9:       csa->fp = NULL;
alpar@9:       csa->count = 0;
alpar@9:       csa->c = '\n';
alpar@9:       csa->field[0] = '\0';
alpar@9:       csa->empty = csa->nonint = 0;
alpar@9:       xprintf("Reading maximum flow problem data from `%s'...\n",
alpar@9:          fname);
alpar@9:       csa->fp = xfopen(fname, "r");
alpar@9:       if (csa->fp == NULL)
alpar@9:       {  xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
alpar@9:          longjmp(csa->jump, 1);
alpar@9:       }
alpar@9:       /* read problem line */
alpar@9:       read_designator(csa);
alpar@9:       if (strcmp(csa->field, "p") != 0)
alpar@9:          error(csa, "problem line missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (strcmp(csa->field, "max") != 0)
alpar@9:          error(csa, "wrong problem designator; `max' expected");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &nv) == 0 && nv >= 2))
alpar@9:          error(csa, "number of nodes missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &na) == 0 && na >= 0))
alpar@9:          error(csa, "number of arcs missing or invalid");
alpar@9:       xprintf("Flow network has %d node%s and %d arc%s\n",
alpar@9:          nv, nv == 1 ? "" : "s", na, na == 1 ? "" : "s");
alpar@9:       if (nv > 0) glp_add_vertices(G, nv);
alpar@9:       end_of_line(csa);
alpar@9:       /* read node descriptor lines */
alpar@9:       s = t = 0;
alpar@9:       for (;;)
alpar@9:       {  read_designator(csa);
alpar@9:          if (strcmp(csa->field, "n") != 0) break;
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "node number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "node number %d out of range", i);
alpar@9:          read_field(csa);
alpar@9:          if (strcmp(csa->field, "s") == 0)
alpar@9:          {  if (s > 0)
alpar@9:                error(csa, "only one source node allowed");
alpar@9:             s = i;
alpar@9:          }
alpar@9:          else if (strcmp(csa->field, "t") == 0)
alpar@9:          {  if (t > 0)
alpar@9:                error(csa, "only one sink node allowed");
alpar@9:             t = i;
alpar@9:          }
alpar@9:          else
alpar@9:             error(csa, "wrong node designator; `s' or `t' expected");
alpar@9:          if (s > 0 && s == t)
alpar@9:             error(csa, "source and sink nodes must be distinct");
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       if (s == 0)
alpar@9:          error(csa, "source node descriptor missing\n");
alpar@9:       if (t == 0)
alpar@9:          error(csa, "sink node descriptor missing\n");
alpar@9:       if (_s != NULL) *_s = s;
alpar@9:       if (_t != NULL) *_t = t;
alpar@9:       /* read arc descriptor lines */
alpar@9:       for (k = 1; k <= na; k++)
alpar@9:       {  if (k > 1) read_designator(csa);
alpar@9:          if (strcmp(csa->field, "a") != 0)
alpar@9:             error(csa, "wrong line designator; `a' expected");
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "starting node number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "starting node number %d out of range", i);
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &j) != 0)
alpar@9:             error(csa, "ending node number missing or invalid");
alpar@9:          if (!(1 <= j && j <= nv))
alpar@9:             error(csa, "ending node number %d out of range", j);
alpar@9:          read_field(csa);
alpar@9:          if (!(str2num(csa->field, &cap) == 0 && cap >= 0.0))
alpar@9:             error(csa, "arc capacity missing or invalid");
alpar@9:          check_int(csa, cap);
alpar@9:          a = glp_add_arc(G, i, j);
alpar@9:          if (a_cap >= 0)
alpar@9:             memcpy((char *)a->data + a_cap, &cap, sizeof(double));
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       xprintf("%d lines were read\n", csa->count);
alpar@9: done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (csa->fp != NULL) xfclose(csa->fp);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_write_maxflow - write maximum flow problem data in DIMACS format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
alpar@9: *     const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_write_maxflow writes maximum flow problem data in
alpar@9: *  DIMACS format to a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
alpar@9:       const char *fname)
alpar@9: {     XFILE *fp;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *a;
alpar@9:       int i, count = 0, ret;
alpar@9:       double cap;
alpar@9:       if (!(1 <= s && s <= G->nv))
alpar@9:          xerror("glp_write_maxflow: s = %d; source node number out of r"
alpar@9:             "ange\n", s);
alpar@9:       if (!(1 <= t && t <= G->nv))
alpar@9:          xerror("glp_write_maxflow: t = %d: sink node number out of ran"
alpar@9:             "ge\n", t);
alpar@9:       if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_write_mincost: a_cap = %d; invalid offset\n",
alpar@9:             a_cap);
alpar@9:       xprintf("Writing maximum flow problem data to `%s'...\n",
alpar@9:          fname);
alpar@9:       fp = xfopen(fname, "w");
alpar@9:       if (fp == NULL)
alpar@9:       {  xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xfprintf(fp, "c %s\n",
alpar@9:          G->name == NULL ? "unknown" : G->name), count++;
alpar@9:       xfprintf(fp, "p max %d %d\n", G->nv, G->na), count++;
alpar@9:       xfprintf(fp, "n %d s\n", s), count++;
alpar@9:       xfprintf(fp, "n %d t\n", t), count++;
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          for (a = v->out; a != NULL; a = a->t_next)
alpar@9:          {  if (a_cap >= 0)
alpar@9:                memcpy(&cap, (char *)a->data + a_cap, sizeof(double));
alpar@9:             else
alpar@9:                cap = 1.0;
alpar@9:             xfprintf(fp, "a %d %d %.*g\n",
alpar@9:                a->tail->i, a->head->i, DBL_DIG, cap), count++;
alpar@9:          }
alpar@9:       }
alpar@9:       xfprintf(fp, "c eof\n"), count++;
alpar@9:       xfflush(fp);
alpar@9:       if (xferror(fp))
alpar@9:       {  xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xprintf("%d lines were written\n", count);
alpar@9:       ret = 0;
alpar@9: done: if (fp != NULL) xfclose(fp);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_read_asnprob - read assignment problem data in DIMACS format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_read_asnprob(glp_graph *G, int v_set, int a_cost,
alpar@9: *     const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_read_asnprob reads assignment problem data in DIMACS
alpar@9: *  format from a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_read_asnprob(glp_graph *G, int v_set, int a_cost, const char
alpar@9:       *fname)
alpar@9: {     struct csa _csa, *csa = &_csa;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *a;
alpar@9:       int nv, na, n1, i, j, k, ret = 0;
alpar@9:       double cost;
alpar@9:       char *flag = NULL;
alpar@9:       if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
alpar@9:          xerror("glp_read_asnprob: v_set = %d; invalid offset\n",
alpar@9:             v_set);
alpar@9:       if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_read_asnprob: a_cost = %d; invalid offset\n",
alpar@9:             a_cost);
alpar@9:       glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (setjmp(csa->jump))
alpar@9:       {  ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       csa->fname = fname;
alpar@9:       csa->fp = NULL;
alpar@9:       csa->count = 0;
alpar@9:       csa->c = '\n';
alpar@9:       csa->field[0] = '\0';
alpar@9:       csa->empty = csa->nonint = 0;
alpar@9:       xprintf("Reading assignment problem data from `%s'...\n", fname);
alpar@9:       csa->fp = xfopen(fname, "r");
alpar@9:       if (csa->fp == NULL)
alpar@9:       {  xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
alpar@9:          longjmp(csa->jump, 1);
alpar@9:       }
alpar@9:       /* read problem line */
alpar@9:       read_designator(csa);
alpar@9:       if (strcmp(csa->field, "p") != 0)
alpar@9:          error(csa, "problem line missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (strcmp(csa->field, "asn") != 0)
alpar@9:          error(csa, "wrong problem designator; `asn' expected");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &nv) == 0 && nv >= 0))
alpar@9:          error(csa, "number of nodes missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &na) == 0 && na >= 0))
alpar@9:          error(csa, "number of arcs missing or invalid");
alpar@9:       if (nv > 0) glp_add_vertices(G, nv);
alpar@9:       end_of_line(csa);
alpar@9:       /* read node descriptor lines */
alpar@9:       flag = xcalloc(1+nv, sizeof(char));
alpar@9:       memset(&flag[1], 0, nv * sizeof(char));
alpar@9:       n1 = 0;
alpar@9:       for (;;)
alpar@9:       {  read_designator(csa);
alpar@9:          if (strcmp(csa->field, "n") != 0) break;
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "node number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "node number %d out of range", i);
alpar@9:          if (flag[i])
alpar@9:             error(csa, "duplicate descriptor of node %d", i);
alpar@9:          flag[i] = 1, n1++;
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       xprintf(
alpar@9:          "Assignment problem has %d + %d = %d node%s and %d arc%s\n",
alpar@9:          n1, nv - n1, nv, nv == 1 ? "" : "s", na, na == 1 ? "" : "s");
alpar@9:       if (v_set >= 0)
alpar@9:       {  for (i = 1; i <= nv; i++)
alpar@9:          {  v = G->v[i];
alpar@9:             k = (flag[i] ? 0 : 1);
alpar@9:             memcpy((char *)v->data + v_set, &k, sizeof(int));
alpar@9:          }
alpar@9:       }
alpar@9:       /* read arc descriptor lines */
alpar@9:       for (k = 1; k <= na; k++)
alpar@9:       {  if (k > 1) read_designator(csa);
alpar@9:          if (strcmp(csa->field, "a") != 0)
alpar@9:             error(csa, "wrong line designator; `a' expected");
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "starting node number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "starting node number %d out of range", i);
alpar@9:          if (!flag[i])
alpar@9:             error(csa, "node %d cannot be a starting node", i);
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &j) != 0)
alpar@9:             error(csa, "ending node number missing or invalid");
alpar@9:          if (!(1 <= j && j <= nv))
alpar@9:             error(csa, "ending node number %d out of range", j);
alpar@9:          if (flag[j])
alpar@9:             error(csa, "node %d cannot be an ending node", j);
alpar@9:          read_field(csa);
alpar@9:          if (str2num(csa->field, &cost) != 0)
alpar@9:             error(csa, "arc cost missing or invalid");
alpar@9:          check_int(csa, cost);
alpar@9:          a = glp_add_arc(G, i, j);
alpar@9:          if (a_cost >= 0)
alpar@9:             memcpy((char *)a->data + a_cost, &cost, sizeof(double));
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       xprintf("%d lines were read\n", csa->count);
alpar@9: done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (csa->fp != NULL) xfclose(csa->fp);
alpar@9:       if (flag != NULL) xfree(flag);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_write_asnprob - write assignment problem data in DIMACS format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_write_asnprob(glp_graph *G, int v_set, int a_cost,
alpar@9: *     const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_write_asnprob writes assignment problem data in
alpar@9: *  DIMACS format to a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_write_asnprob(glp_graph *G, int v_set, int a_cost, const char
alpar@9:       *fname)
alpar@9: {     XFILE *fp;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *a;
alpar@9:       int i, k, count = 0, ret;
alpar@9:       double cost;
alpar@9:       if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
alpar@9:          xerror("glp_write_asnprob: v_set = %d; invalid offset\n",
alpar@9:             v_set);
alpar@9:       if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
alpar@9:          xerror("glp_write_asnprob: a_cost = %d; invalid offset\n",
alpar@9:             a_cost);
alpar@9:       xprintf("Writing assignment problem data to `%s'...\n", fname);
alpar@9:       fp = xfopen(fname, "w");
alpar@9:       if (fp == NULL)
alpar@9:       {  xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xfprintf(fp, "c %s\n",
alpar@9:          G->name == NULL ? "unknown" : G->name), count++;
alpar@9:       xfprintf(fp, "p asn %d %d\n", G->nv, G->na), count++;
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          if (v_set >= 0)
alpar@9:             memcpy(&k, (char *)v->data + v_set, sizeof(int));
alpar@9:          else
alpar@9:             k = (v->out != NULL ? 0 : 1);
alpar@9:          if (k == 0)
alpar@9:             xfprintf(fp, "n %d\n", i), count++;
alpar@9:       }
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          for (a = v->out; a != NULL; a = a->t_next)
alpar@9:          {  if (a_cost >= 0)
alpar@9:                memcpy(&cost, (char *)a->data + a_cost, sizeof(double));
alpar@9:             else
alpar@9:                cost = 1.0;
alpar@9:             xfprintf(fp, "a %d %d %.*g\n",
alpar@9:                a->tail->i, a->head->i, DBL_DIG, cost), count++;
alpar@9:          }
alpar@9:       }
alpar@9:       xfprintf(fp, "c eof\n"), count++;
alpar@9:       xfflush(fp);
alpar@9:       if (xferror(fp))
alpar@9:       {  xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xprintf("%d lines were written\n", count);
alpar@9:       ret = 0;
alpar@9: done: if (fp != NULL) xfclose(fp);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_read_ccdata - read graph in DIMACS clique/coloring format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_read_ccdata(glp_graph *G, int v_wgt, const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_read_ccdata reads an (undirected) graph in DIMACS
alpar@9: *  clique/coloring format from a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_read_ccdata(glp_graph *G, int v_wgt, const char *fname)
alpar@9: {     struct csa _csa, *csa = &_csa;
alpar@9:       glp_vertex *v;
alpar@9:       int i, j, k, nv, ne, ret = 0;
alpar@9:       double w;
alpar@9:       char *flag = NULL;
alpar@9:       if (v_wgt >= 0 && v_wgt > G->v_size - (int)sizeof(double))
alpar@9:          xerror("glp_read_ccdata: v_wgt = %d; invalid offset\n",
alpar@9:             v_wgt);
alpar@9:       glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (setjmp(csa->jump))
alpar@9:       {  ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       csa->fname = fname;
alpar@9:       csa->fp = NULL;
alpar@9:       csa->count = 0;
alpar@9:       csa->c = '\n';
alpar@9:       csa->field[0] = '\0';
alpar@9:       csa->empty = csa->nonint = 0;
alpar@9:       xprintf("Reading graph from `%s'...\n", fname);
alpar@9:       csa->fp = xfopen(fname, "r");
alpar@9:       if (csa->fp == NULL)
alpar@9:       {  xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
alpar@9:          longjmp(csa->jump, 1);
alpar@9:       }
alpar@9:       /* read problem line */
alpar@9:       read_designator(csa);
alpar@9:       if (strcmp(csa->field, "p") != 0)
alpar@9:          error(csa, "problem line missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (strcmp(csa->field, "edge") != 0)
alpar@9:          error(csa, "wrong problem designator; `edge' expected");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &nv) == 0 && nv >= 0))
alpar@9:          error(csa, "number of vertices missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &ne) == 0 && ne >= 0))
alpar@9:          error(csa, "number of edges missing or invalid");
alpar@9:       xprintf("Graph has %d vert%s and %d edge%s\n",
alpar@9:          nv, nv == 1 ? "ex" : "ices", ne, ne == 1 ? "" : "s");
alpar@9:       if (nv > 0) glp_add_vertices(G, nv);
alpar@9:       end_of_line(csa);
alpar@9:       /* read node descriptor lines */
alpar@9:       flag = xcalloc(1+nv, sizeof(char));
alpar@9:       memset(&flag[1], 0, nv * sizeof(char));
alpar@9:       if (v_wgt >= 0)
alpar@9:       {  w = 1.0;
alpar@9:          for (i = 1; i <= nv; i++)
alpar@9:          {  v = G->v[i];
alpar@9:             memcpy((char *)v->data + v_wgt, &w, sizeof(double));
alpar@9:          }
alpar@9:       }
alpar@9:       for (;;)
alpar@9:       {  read_designator(csa);
alpar@9:          if (strcmp(csa->field, "n") != 0) break;
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "vertex number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "vertex number %d out of range", i);
alpar@9:          if (flag[i])
alpar@9:             error(csa, "duplicate descriptor of vertex %d", i);
alpar@9:          read_field(csa);
alpar@9:          if (str2num(csa->field, &w) != 0)
alpar@9:             error(csa, "vertex weight missing or invalid");
alpar@9:          check_int(csa, w);
alpar@9:          if (v_wgt >= 0)
alpar@9:          {  v = G->v[i];
alpar@9:             memcpy((char *)v->data + v_wgt, &w, sizeof(double));
alpar@9:          }
alpar@9:          flag[i] = 1;
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       xfree(flag), flag = NULL;
alpar@9:       /* read edge descriptor lines */
alpar@9:       for (k = 1; k <= ne; k++)
alpar@9:       {  if (k > 1) read_designator(csa);
alpar@9:          if (strcmp(csa->field, "e") != 0)
alpar@9:             error(csa, "wrong line designator; `e' expected");
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &i) != 0)
alpar@9:             error(csa, "first vertex number missing or invalid");
alpar@9:          if (!(1 <= i && i <= nv))
alpar@9:             error(csa, "first vertex number %d out of range", i);
alpar@9:          read_field(csa);
alpar@9:          if (str2int(csa->field, &j) != 0)
alpar@9:             error(csa, "second vertex number missing or invalid");
alpar@9:          if (!(1 <= j && j <= nv))
alpar@9:             error(csa, "second vertex number %d out of range", j);
alpar@9:          glp_add_arc(G, i, j);
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       xprintf("%d lines were read\n", csa->count);
alpar@9: done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
alpar@9:       if (csa->fp != NULL) xfclose(csa->fp);
alpar@9:       if (flag != NULL) xfree(flag);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_write_ccdata - write graph in DIMACS clique/coloring format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_write_ccdata(glp_graph *G, int v_wgt, const char *fname);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine glp_write_ccdata writes the specified graph in DIMACS
alpar@9: *  clique/coloring format to a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_write_ccdata(glp_graph *G, int v_wgt, const char *fname)
alpar@9: {     XFILE *fp;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *e;
alpar@9:       int i, count = 0, ret;
alpar@9:       double w;
alpar@9:       if (v_wgt >= 0 && v_wgt > G->v_size - (int)sizeof(double))
alpar@9:          xerror("glp_write_ccdata: v_wgt = %d; invalid offset\n",
alpar@9:             v_wgt);
alpar@9:       xprintf("Writing graph to `%s'\n", fname);
alpar@9:       fp = xfopen(fname, "w");
alpar@9:       if (fp == NULL)
alpar@9:       {  xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xfprintf(fp, "c %s\n",
alpar@9:          G->name == NULL ? "unknown" : G->name), count++;
alpar@9:       xfprintf(fp, "p edge %d %d\n", G->nv, G->na), count++;
alpar@9:       if (v_wgt >= 0)
alpar@9:       {  for (i = 1; i <= G->nv; i++)
alpar@9:          {  v = G->v[i];
alpar@9:             memcpy(&w, (char *)v->data + v_wgt, sizeof(double));
alpar@9:             if (w != 1.0)
alpar@9:                xfprintf(fp, "n %d %.*g\n", i, DBL_DIG, w), count++;
alpar@9:          }
alpar@9:       }
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          for (e = v->out; e != NULL; e = e->t_next)
alpar@9:             xfprintf(fp, "e %d %d\n", e->tail->i, e->head->i), count++;
alpar@9:       }
alpar@9:       xfprintf(fp, "c eof\n"), count++;
alpar@9:       xfflush(fp);
alpar@9:       if (xferror(fp))
alpar@9:       {  xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xprintf("%d lines were written\n", count);
alpar@9:       ret = 0;
alpar@9: done: if (fp != NULL) xfclose(fp);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_read_prob - read problem data in GLPK format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_read_prob(glp_prob *P, int flags, const char *fname);
alpar@9: *
alpar@9: *  The routine glp_read_prob reads problem data in GLPK LP/MIP format
alpar@9: *  from a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_read_prob(glp_prob *P, int flags, const char *fname)
alpar@9: {     struct csa _csa, *csa = &_csa;
alpar@9:       int mip, m, n, nnz, ne, i, j, k, type, kind, ret, *ln = NULL,
alpar@9:          *ia = NULL, *ja = NULL;
alpar@9:       double lb, ub, temp, *ar = NULL;
alpar@9:       char *rf = NULL, *cf = NULL;
alpar@9:       if (P == NULL || P->magic != GLP_PROB_MAGIC)
alpar@9:          xerror("glp_read_prob: P = %p; invalid problem object\n",
alpar@9:             P);
alpar@9:       if (flags != 0)
alpar@9:          xerror("glp_read_prob: flags = %d; invalid parameter\n",
alpar@9:             flags);
alpar@9:       if (fname == NULL)
alpar@9:          xerror("glp_read_prob: fname = %d; invalid parameter\n",
alpar@9:             fname);
alpar@9:       glp_erase_prob(P);
alpar@9:       if (setjmp(csa->jump))
alpar@9:       {  ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       csa->fname = fname;
alpar@9:       csa->fp = NULL;
alpar@9:       csa->count = 0;
alpar@9:       csa->c = '\n';
alpar@9:       csa->field[0] = '\0';
alpar@9:       csa->empty = csa->nonint = 0;
alpar@9:       xprintf("Reading problem data from `%s'...\n", fname);
alpar@9:       csa->fp = xfopen(fname, "r");
alpar@9:       if (csa->fp == NULL)
alpar@9:       {  xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
alpar@9:          longjmp(csa->jump, 1);
alpar@9:       }
alpar@9:       /* read problem line */
alpar@9:       read_designator(csa);
alpar@9:       if (strcmp(csa->field, "p") != 0)
alpar@9:          error(csa, "problem line missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (strcmp(csa->field, "lp") == 0)
alpar@9:          mip = 0;
alpar@9:       else if (strcmp(csa->field, "mip") == 0)
alpar@9:          mip = 1;
alpar@9:       else
alpar@9:          error(csa, "wrong problem designator; `lp' or `mip' expected\n"
alpar@9:             );
alpar@9:       read_field(csa);
alpar@9:       if (strcmp(csa->field, "min") == 0)
alpar@9:          glp_set_obj_dir(P, GLP_MIN);
alpar@9:       else if (strcmp(csa->field, "max") == 0)
alpar@9:          glp_set_obj_dir(P, GLP_MAX);
alpar@9:       else
alpar@9:          error(csa, "objective sense missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &m) == 0 && m >= 0))
alpar@9:          error(csa, "number of rows missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &n) == 0 && n >= 0))
alpar@9:          error(csa, "number of columns missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &nnz) == 0 && nnz >= 0))
alpar@9:          error(csa, "number of constraint coefficients missing or inval"
alpar@9:             "id");
alpar@9:       if (m > 0)
alpar@9:       {  glp_add_rows(P, m);
alpar@9:          for (i = 1; i <= m; i++)
alpar@9:             glp_set_row_bnds(P, i, GLP_FX, 0.0, 0.0);
alpar@9:       }
alpar@9:       if (n > 0)
alpar@9:       {  glp_add_cols(P, n);
alpar@9:          for (j = 1; j <= n; j++)
alpar@9:          {  if (!mip)
alpar@9:                glp_set_col_bnds(P, j, GLP_LO, 0.0, 0.0);
alpar@9:             else
alpar@9:                glp_set_col_kind(P, j, GLP_BV);
alpar@9:          }
alpar@9:       }
alpar@9:       end_of_line(csa);
alpar@9:       /* allocate working arrays */
alpar@9:       rf = xcalloc(1+m, sizeof(char));
alpar@9:       memset(rf, 0, 1+m);
alpar@9:       cf = xcalloc(1+n, sizeof(char));
alpar@9:       memset(cf, 0, 1+n);
alpar@9:       ln = xcalloc(1+nnz, sizeof(int));
alpar@9:       ia = xcalloc(1+nnz, sizeof(int));
alpar@9:       ja = xcalloc(1+nnz, sizeof(int));
alpar@9:       ar = xcalloc(1+nnz, sizeof(double));
alpar@9:       /* read descriptor lines */
alpar@9:       ne = 0;
alpar@9:       for (;;)
alpar@9:       {  read_designator(csa);
alpar@9:          if (strcmp(csa->field, "i") == 0)
alpar@9:          {  /* row descriptor */
alpar@9:             read_field(csa);
alpar@9:             if (str2int(csa->field, &i) != 0)
alpar@9:                error(csa, "row number missing or invalid");
alpar@9:             if (!(1 <= i && i <= m))
alpar@9:                error(csa, "row number out of range");
alpar@9:             read_field(csa);
alpar@9:             if (strcmp(csa->field, "f") == 0)
alpar@9:                type = GLP_FR;
alpar@9:             else if (strcmp(csa->field, "l") == 0)
alpar@9:                type = GLP_LO;
alpar@9:             else if (strcmp(csa->field, "u") == 0)
alpar@9:                type = GLP_UP;
alpar@9:             else if (strcmp(csa->field, "d") == 0)
alpar@9:                type = GLP_DB;
alpar@9:             else if (strcmp(csa->field, "s") == 0)
alpar@9:                type = GLP_FX;
alpar@9:             else
alpar@9:                error(csa, "row type missing or invalid");
alpar@9:             if (type == GLP_LO || type == GLP_DB || type == GLP_FX)
alpar@9:             {  read_field(csa);
alpar@9:                if (str2num(csa->field, &lb) != 0)
alpar@9:                   error(csa, "row lower bound/fixed value missing or in"
alpar@9:                      "valid");
alpar@9:             }
alpar@9:             else
alpar@9:                lb = 0.0;
alpar@9:             if (type == GLP_UP || type == GLP_DB)
alpar@9:             {  read_field(csa);
alpar@9:                if (str2num(csa->field, &ub) != 0)
alpar@9:                   error(csa, "row upper bound missing or invalid");
alpar@9:             }
alpar@9:             else
alpar@9:                ub = 0.0;
alpar@9:             if (rf[i] & 0x01)
alpar@9:                error(csa, "duplicate row descriptor");
alpar@9:             glp_set_row_bnds(P, i, type, lb, ub), rf[i] |= 0x01;
alpar@9:          }
alpar@9:          else if (strcmp(csa->field, "j") == 0)
alpar@9:          {  /* column descriptor */
alpar@9:             read_field(csa);
alpar@9:             if (str2int(csa->field, &j) != 0)
alpar@9:                error(csa, "column number missing or invalid");
alpar@9:             if (!(1 <= j && j <= n))
alpar@9:                error(csa, "column number out of range");
alpar@9:             if (!mip)
alpar@9:                kind = GLP_CV;
alpar@9:             else
alpar@9:             {  read_field(csa);
alpar@9:                if (strcmp(csa->field, "c") == 0)
alpar@9:                   kind = GLP_CV;
alpar@9:                else if (strcmp(csa->field, "i") == 0)
alpar@9:                   kind = GLP_IV;
alpar@9:                else if (strcmp(csa->field, "b") == 0)
alpar@9:                {  kind = GLP_IV;
alpar@9:                   type = GLP_DB, lb = 0.0, ub = 1.0;
alpar@9:                   goto skip;
alpar@9:                }
alpar@9:                else
alpar@9:                   error(csa, "column kind missing or invalid");
alpar@9:             }
alpar@9:             read_field(csa);
alpar@9:             if (strcmp(csa->field, "f") == 0)
alpar@9:                type = GLP_FR;
alpar@9:             else if (strcmp(csa->field, "l") == 0)
alpar@9:                type = GLP_LO;
alpar@9:             else if (strcmp(csa->field, "u") == 0)
alpar@9:                type = GLP_UP;
alpar@9:             else if (strcmp(csa->field, "d") == 0)
alpar@9:                type = GLP_DB;
alpar@9:             else if (strcmp(csa->field, "s") == 0)
alpar@9:                type = GLP_FX;
alpar@9:             else
alpar@9:                error(csa, "column type missing or invalid");
alpar@9:             if (type == GLP_LO || type == GLP_DB || type == GLP_FX)
alpar@9:             {  read_field(csa);
alpar@9:                if (str2num(csa->field, &lb) != 0)
alpar@9:                   error(csa, "column lower bound/fixed value missing or"
alpar@9:                      " invalid");
alpar@9:             }
alpar@9:             else
alpar@9:                lb = 0.0;
alpar@9:             if (type == GLP_UP || type == GLP_DB)
alpar@9:             {  read_field(csa);
alpar@9:                if (str2num(csa->field, &ub) != 0)
alpar@9:                   error(csa, "column upper bound missing or invalid");
alpar@9:             }
alpar@9:             else
alpar@9:                ub = 0.0;
alpar@9: skip:       if (cf[j] & 0x01)
alpar@9:                error(csa, "duplicate column descriptor");
alpar@9:             glp_set_col_kind(P, j, kind);
alpar@9:             glp_set_col_bnds(P, j, type, lb, ub), cf[j] |= 0x01;
alpar@9:          }
alpar@9:          else if (strcmp(csa->field, "a") == 0)
alpar@9:          {  /* coefficient descriptor */
alpar@9:             read_field(csa);
alpar@9:             if (str2int(csa->field, &i) != 0)
alpar@9:                error(csa, "row number missing or invalid");
alpar@9:             if (!(0 <= i && i <= m))
alpar@9:                error(csa, "row number out of range");
alpar@9:             read_field(csa);
alpar@9:             if (str2int(csa->field, &j) != 0)
alpar@9:                error(csa, "column number missing or invalid");
alpar@9:             if (!((i == 0 ? 0 : 1) <= j && j <= n))
alpar@9:                error(csa, "column number out of range");
alpar@9:             read_field(csa);
alpar@9:             if (i == 0)
alpar@9:             {  if (str2num(csa->field, &temp) != 0)
alpar@9:                   error(csa, "objective %s missing or invalid",
alpar@9:                      j == 0 ? "constant term" : "coefficient");
alpar@9:                if (cf[j] & 0x10)
alpar@9:                   error(csa, "duplicate objective %s",
alpar@9:                      j == 0 ? "constant term" : "coefficient");
alpar@9:                glp_set_obj_coef(P, j, temp), cf[j] |= 0x10;
alpar@9:             }
alpar@9:             else
alpar@9:             {  if (str2num(csa->field, &temp) != 0)
alpar@9:                   error(csa, "constraint coefficient missing or invalid"
alpar@9:                      );
alpar@9:                if (ne == nnz)
alpar@9:                   error(csa, "too many constraint coefficient descripto"
alpar@9:                      "rs");
alpar@9:                ln[++ne] = csa->count;
alpar@9:                ia[ne] = i, ja[ne] = j, ar[ne] = temp;
alpar@9:             }
alpar@9:          }
alpar@9:          else if (strcmp(csa->field, "n") == 0)
alpar@9:          {  /* symbolic name descriptor */
alpar@9:             read_field(csa);
alpar@9:             if (strcmp(csa->field, "p") == 0)
alpar@9:             {  /* problem name */
alpar@9:                read_field(csa);
alpar@9:                if (P->name != NULL)
alpar@9:                   error(csa, "duplicate problem name");
alpar@9:                glp_set_prob_name(P, csa->field);
alpar@9:             }
alpar@9:             else if (strcmp(csa->field, "z") == 0)
alpar@9:             {  /* objective name */
alpar@9:                read_field(csa);
alpar@9:                if (P->obj != NULL)
alpar@9:                   error(csa, "duplicate objective name");
alpar@9:                glp_set_obj_name(P, csa->field);
alpar@9:             }
alpar@9:             else if (strcmp(csa->field, "i") == 0)
alpar@9:             {  /* row name */
alpar@9:                read_field(csa);
alpar@9:                if (str2int(csa->field, &i) != 0)
alpar@9:                   error(csa, "row number missing or invalid");
alpar@9:                if (!(1 <= i && i <= m))
alpar@9:                   error(csa, "row number out of range");
alpar@9:                read_field(csa);
alpar@9:                if (P->row[i]->name != NULL)
alpar@9:                   error(csa, "duplicate row name");
alpar@9:                glp_set_row_name(P, i, csa->field);
alpar@9:             }
alpar@9:             else if (strcmp(csa->field, "j") == 0)
alpar@9:             {  /* column name */
alpar@9:                read_field(csa);
alpar@9:                if (str2int(csa->field, &j) != 0)
alpar@9:                   error(csa, "column number missing or invalid");
alpar@9:                if (!(1 <= j && j <= n))
alpar@9:                   error(csa, "column number out of range");
alpar@9:                read_field(csa);
alpar@9:                if (P->col[j]->name != NULL)
alpar@9:                   error(csa, "duplicate column name");
alpar@9:                glp_set_col_name(P, j, csa->field);
alpar@9:             }
alpar@9:             else
alpar@9:                error(csa, "object designator missing or invalid");
alpar@9:          }
alpar@9:          else if (strcmp(csa->field, "e") == 0)
alpar@9:             break;
alpar@9:          else
alpar@9:             error(csa, "line designator missing or invalid");
alpar@9:          end_of_line(csa);
alpar@9:       }
alpar@9:       if (ne < nnz)
alpar@9:          error(csa, "too few constraint coefficient descriptors");
alpar@9:       xassert(ne == nnz);
alpar@9:       k = glp_check_dup(m, n, ne, ia, ja);
alpar@9:       xassert(0 <= k && k <= nnz);
alpar@9:       if (k > 0)
alpar@9:       {  csa->count = ln[k];
alpar@9:          error(csa, "duplicate constraint coefficient");
alpar@9:       }
alpar@9:       glp_load_matrix(P, ne, ia, ja, ar);
alpar@9:       /* print some statistics */
alpar@9:       if (P->name != NULL)
alpar@9:          xprintf("Problem: %s\n", P->name);
alpar@9:       if (P->obj != NULL)
alpar@9:          xprintf("Objective: %s\n", P->obj);
alpar@9:       xprintf("%d row%s, %d column%s, %d non-zero%s\n",
alpar@9:          m, m == 1 ? "" : "s", n, n == 1 ? "" : "s", nnz, nnz == 1 ?
alpar@9:          "" : "s");
alpar@9:       if (glp_get_num_int(P) > 0)
alpar@9:       {  int ni = glp_get_num_int(P);
alpar@9:          int nb = glp_get_num_bin(P);
alpar@9:          if (ni == 1)
alpar@9:          {  if (nb == 0)
alpar@9:                xprintf("One variable is integer\n");
alpar@9:             else
alpar@9:                xprintf("One variable is binary\n");
alpar@9:          }
alpar@9:          else
alpar@9:          {  xprintf("%d integer variables, ", ni);
alpar@9:             if (nb == 0)
alpar@9:                xprintf("none");
alpar@9:             else if (nb == 1)
alpar@9:                xprintf("one");
alpar@9:             else if (nb == ni)
alpar@9:                xprintf("all");
alpar@9:             else
alpar@9:                xprintf("%d", nb);
alpar@9:             xprintf(" of which %s binary\n", nb == 1 ? "is" : "are");
alpar@9:          }
alpar@9:       }
alpar@9:       xprintf("%d lines were read\n", csa->count);
alpar@9:       /* problem data has been successfully read */
alpar@9:       glp_sort_matrix(P);
alpar@9:       ret = 0;
alpar@9: done: if (csa->fp != NULL) xfclose(csa->fp);
alpar@9:       if (rf != NULL) xfree(rf);
alpar@9:       if (cf != NULL) xfree(cf);
alpar@9:       if (ln != NULL) xfree(ln);
alpar@9:       if (ia != NULL) xfree(ia);
alpar@9:       if (ja != NULL) xfree(ja);
alpar@9:       if (ar != NULL) xfree(ar);
alpar@9:       if (ret) glp_erase_prob(P);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  glp_write_prob - write problem data in GLPK format
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  int glp_write_prob(glp_prob *P, int flags, const char *fname);
alpar@9: *
alpar@9: *  The routine glp_write_prob writes problem data in GLPK LP/MIP format
alpar@9: *  to a text file.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  If the operation was successful, the routine returns zero. Otherwise
alpar@9: *  it prints an error message and returns non-zero. */
alpar@9: 
alpar@9: int glp_write_prob(glp_prob *P, int flags, const char *fname)
alpar@9: {     XFILE *fp;
alpar@9:       GLPROW *row;
alpar@9:       GLPCOL *col;
alpar@9:       GLPAIJ *aij;
alpar@9:       int mip, i, j, count, ret;
alpar@9:       if (P == NULL || P->magic != GLP_PROB_MAGIC)
alpar@9:          xerror("glp_write_prob: P = %p; invalid problem object\n",
alpar@9:             P);
alpar@9:       if (flags != 0)
alpar@9:          xerror("glp_write_prob: flags = %d; invalid parameter\n",
alpar@9:             flags);
alpar@9:       if (fname == NULL)
alpar@9:          xerror("glp_write_prob: fname = %d; invalid parameter\n",
alpar@9:             fname);
alpar@9:       xprintf("Writing problem data to `%s'...\n", fname);
alpar@9:       fp = xfopen(fname, "w"), count = 0;
alpar@9:       if (fp == NULL)
alpar@9:       {  xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       /* write problem line */
alpar@9:       mip = (glp_get_num_int(P) > 0);
alpar@9:       xfprintf(fp, "p %s %s %d %d %d\n", !mip ? "lp" : "mip",
alpar@9:          P->dir == GLP_MIN ? "min" : P->dir == GLP_MAX ? "max" : "???",
alpar@9:          P->m, P->n, P->nnz), count++;
alpar@9:       if (P->name != NULL)
alpar@9:          xfprintf(fp, "n p %s\n", P->name), count++;
alpar@9:       if (P->obj != NULL)
alpar@9:          xfprintf(fp, "n z %s\n", P->obj), count++;
alpar@9:       /* write row descriptors */
alpar@9:       for (i = 1; i <= P->m; i++)
alpar@9:       {  row = P->row[i];
alpar@9:          if (row->type == GLP_FX && row->lb == 0.0)
alpar@9:             goto skip1;
alpar@9:          xfprintf(fp, "i %d ", i), count++;
alpar@9:          if (row->type == GLP_FR)
alpar@9:             xfprintf(fp, "f\n");
alpar@9:          else if (row->type == GLP_LO)
alpar@9:             xfprintf(fp, "l %.*g\n", DBL_DIG, row->lb);
alpar@9:          else if (row->type == GLP_UP)
alpar@9:             xfprintf(fp, "u %.*g\n", DBL_DIG, row->ub);
alpar@9:          else if (row->type == GLP_DB)
alpar@9:             xfprintf(fp, "d %.*g %.*g\n", DBL_DIG, row->lb, DBL_DIG,
alpar@9:                   row->ub);
alpar@9:          else if (row->type == GLP_FX)
alpar@9:             xfprintf(fp, "s %.*g\n", DBL_DIG, row->lb);
alpar@9:          else
alpar@9:             xassert(row != row);
alpar@9: skip1:   if (row->name != NULL)
alpar@9:             xfprintf(fp, "n i %d %s\n", i, row->name), count++;
alpar@9:       }
alpar@9:       /* write column descriptors */
alpar@9:       for (j = 1; j <= P->n; j++)
alpar@9:       {  col = P->col[j];
alpar@9:          if (!mip && col->type == GLP_LO && col->lb == 0.0)
alpar@9:             goto skip2;
alpar@9:          if (mip && col->kind == GLP_IV && col->type == GLP_DB &&
alpar@9:              col->lb == 0.0 && col->ub == 1.0)
alpar@9:             goto skip2;
alpar@9:          xfprintf(fp, "j %d ", j), count++;
alpar@9:          if (mip)
alpar@9:          {  if (col->kind == GLP_CV)
alpar@9:                xfprintf(fp, "c ");
alpar@9:             else if (col->kind == GLP_IV)
alpar@9:                xfprintf(fp, "i ");
alpar@9:             else
alpar@9:                xassert(col != col);
alpar@9:          }
alpar@9:          if (col->type == GLP_FR)
alpar@9:             xfprintf(fp, "f\n");
alpar@9:          else if (col->type == GLP_LO)
alpar@9:             xfprintf(fp, "l %.*g\n", DBL_DIG, col->lb);
alpar@9:          else if (col->type == GLP_UP)
alpar@9:             xfprintf(fp, "u %.*g\n", DBL_DIG, col->ub);
alpar@9:          else if (col->type == GLP_DB)
alpar@9:             xfprintf(fp, "d %.*g %.*g\n", DBL_DIG, col->lb, DBL_DIG,
alpar@9:                   col->ub);
alpar@9:          else if (col->type == GLP_FX)
alpar@9:             xfprintf(fp, "s %.*g\n", DBL_DIG, col->lb);
alpar@9:          else
alpar@9:             xassert(col != col);
alpar@9: skip2:   if (col->name != NULL)
alpar@9:             xfprintf(fp, "n j %d %s\n", j, col->name), count++;
alpar@9:       }
alpar@9:       /* write objective coefficient descriptors */
alpar@9:       if (P->c0 != 0.0)
alpar@9:          xfprintf(fp, "a 0 0 %.*g\n", DBL_DIG, P->c0), count++;
alpar@9:       for (j = 1; j <= P->n; j++)
alpar@9:       {  col = P->col[j];
alpar@9:          if (col->coef != 0.0)
alpar@9:             xfprintf(fp, "a 0 %d %.*g\n", j, DBL_DIG, col->coef),
alpar@9:                count++;
alpar@9:       }
alpar@9:       /* write constraint coefficient descriptors */
alpar@9:       for (i = 1; i <= P->m; i++)
alpar@9:       {  row = P->row[i];
alpar@9:          for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9:             xfprintf(fp, "a %d %d %.*g\n", i, aij->col->j, DBL_DIG,
alpar@9:                aij->val), count++;
alpar@9:       }
alpar@9:       /* write end line */
alpar@9:       xfprintf(fp, "e o f\n"), count++;
alpar@9:       xfflush(fp);
alpar@9:       if (xferror(fp))
alpar@9:       {  xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xprintf("%d lines were written\n", count);
alpar@9:       ret = 0;
alpar@9: done: if (fp != NULL) xfclose(fp);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /**********************************************************************/
alpar@9: 
alpar@9: int glp_read_cnfsat(glp_prob *P, const char *fname)
alpar@9: {     /* read CNF-SAT problem data in DIMACS format */
alpar@9:       struct csa _csa, *csa = &_csa;
alpar@9:       int m, n, i, j, len, neg, rhs, ret = 0, *ind = NULL;
alpar@9:       double *val = NULL;
alpar@9:       char *map = NULL;
alpar@9:       if (P == NULL || P->magic != GLP_PROB_MAGIC)
alpar@9:          xerror("glp_read_cnfsat: P = %p; invalid problem object\n",
alpar@9:             P);
alpar@9:       if (fname == NULL)
alpar@9:          xerror("glp_read_cnfsat: fname = %p; invalid parameter\n",
alpar@9:             fname);
alpar@9:       glp_erase_prob(P);
alpar@9:       if (setjmp(csa->jump))
alpar@9:       {  ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       csa->fname = fname;
alpar@9:       csa->fp = NULL;
alpar@9:       csa->count = 0;
alpar@9:       csa->c = '\n';
alpar@9:       csa->field[0] = '\0';
alpar@9:       csa->empty = csa->nonint = 0;
alpar@9:       xprintf("Reading CNF-SAT problem data from `%s'...\n", fname);
alpar@9:       csa->fp = xfopen(fname, "r");
alpar@9:       if (csa->fp == NULL)
alpar@9:       {  xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
alpar@9:          longjmp(csa->jump, 1);
alpar@9:       }
alpar@9:       /* read problem line */
alpar@9:       read_designator(csa);
alpar@9:       if (strcmp(csa->field, "p") != 0)
alpar@9:          error(csa, "problem line missing or invalid");
alpar@9:       read_field(csa);
alpar@9:       if (strcmp(csa->field, "cnf") != 0)
alpar@9:          error(csa, "wrong problem designator; `cnf' expected\n");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &n) == 0 && n >= 0))
alpar@9:          error(csa, "number of variables missing or invalid\n");
alpar@9:       read_field(csa);
alpar@9:       if (!(str2int(csa->field, &m) == 0 && m >= 0))
alpar@9:          error(csa, "number of clauses missing or invalid\n");
alpar@9:       xprintf("Instance has %d variable%s and %d clause%s\n",
alpar@9:          n, n == 1 ? "" : "s", m, m == 1 ? "" : "s");
alpar@9:       end_of_line(csa);
alpar@9:       if (m > 0)
alpar@9:          glp_add_rows(P, m);
alpar@9:       if (n > 0)
alpar@9:       {  glp_add_cols(P, n);
alpar@9:          for (j = 1; j <= n; j++)
alpar@9:             glp_set_col_kind(P, j, GLP_BV);
alpar@9:       }
alpar@9:       /* allocate working arrays */
alpar@9:       ind = xcalloc(1+n, sizeof(int));
alpar@9:       val = xcalloc(1+n, sizeof(double));
alpar@9:       map = xcalloc(1+n, sizeof(char));
alpar@9:       for (j = 1; j <= n; j++) map[j] = 0;
alpar@9:       /* read clauses */
alpar@9:       for (i = 1; i <= m; i++)
alpar@9:       {  /* read i-th clause */
alpar@9:          len = 0, rhs = 1;
alpar@9:          for (;;)
alpar@9:          {  /* skip white-space characters */
alpar@9:             while (csa->c == ' ' || csa->c == '\n')
alpar@9:                read_char(csa);
alpar@9:             /* read term */
alpar@9:             read_field(csa);
alpar@9:             if (str2int(csa->field, &j) != 0)
alpar@9:                error(csa, "variable number missing or invalid\n");
alpar@9:             if (j > 0)
alpar@9:                neg = 0;
alpar@9:             else if (j < 0)
alpar@9:                neg = 1, j = -j, rhs--;
alpar@9:             else
alpar@9:                break;
alpar@9:             if (!(1 <= j && j <= n))
alpar@9:                error(csa, "variable number out of range\n");
alpar@9:             if (map[j])
alpar@9:                error(csa, "duplicate variable number\n");
alpar@9:             len++, ind[len] = j, val[len] = (neg ? -1.0 : +1.0);
alpar@9:             map[j] = 1;
alpar@9:          }
alpar@9:          glp_set_row_bnds(P, i, GLP_LO, (double)rhs, 0.0);
alpar@9:          glp_set_mat_row(P, i, len, ind, val);
alpar@9:          while (len > 0) map[ind[len--]] = 0;
alpar@9:       }
alpar@9:       xprintf("%d lines were read\n", csa->count);
alpar@9:       /* problem data has been successfully read */
alpar@9:       glp_sort_matrix(P);
alpar@9: done: if (csa->fp != NULL) xfclose(csa->fp);
alpar@9:       if (ind != NULL) xfree(ind);
alpar@9:       if (val != NULL) xfree(val);
alpar@9:       if (map != NULL) xfree(map);
alpar@9:       if (ret) glp_erase_prob(P);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /**********************************************************************/
alpar@9: 
alpar@9: int glp_check_cnfsat(glp_prob *P)
alpar@9: {     /* check for CNF-SAT problem instance */
alpar@9:       int m = P->m;
alpar@9:       int n = P->n;
alpar@9:       GLPROW *row;
alpar@9:       GLPCOL *col;
alpar@9:       GLPAIJ *aij;
alpar@9:       int i, j, neg;
alpar@9:       if (P == NULL || P->magic != GLP_PROB_MAGIC)
alpar@9:          xerror("glp_check_cnfsat: P = %p; invalid problem object\n",
alpar@9:             P);
alpar@9:       /* check columns */
alpar@9:       for (j = 1; j <= n; j++)
alpar@9:       {  col = P->col[j];
alpar@9:          /* the variable should be binary */
alpar@9:          if (!(col->kind == GLP_IV && col->type == GLP_DB &&
alpar@9:                col->lb == 0.0 && col->ub == 1.0))
alpar@9:             return 1;
alpar@9:       }
alpar@9:       /* objective function should be zero */
alpar@9:       if (P->c0 != 0.0)
alpar@9:          return 2;
alpar@9:       for (j = 1; j <= n; j++)
alpar@9:       {  col = P->col[j];
alpar@9:          if (col->coef != 0.0)
alpar@9:             return 3;
alpar@9:       }
alpar@9:       /* check rows */
alpar@9:       for (i = 1; i <= m; i++)
alpar@9:       {  row = P->row[i];
alpar@9:          /* the row should be of ">=" type */
alpar@9:          if (row->type != GLP_LO)
alpar@9:             return 4;
alpar@9:          /* check constraint coefficients */
alpar@9:          neg = 0;
alpar@9:          for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9:          {  /* the constraint coefficient should be +1 or -1 */
alpar@9:             if (aij->val == +1.0)
alpar@9:                ;
alpar@9:             else if (aij->val == -1.0)
alpar@9:                neg++;
alpar@9:             else
alpar@9:                return 5;
alpar@9:          }
alpar@9:          /* the right-hand side should be (1 - neg), where neg is the
alpar@9:             number of negative constraint coefficients in the row */
alpar@9:          if (row->lb != (double)(1 - neg))
alpar@9:             return 6;
alpar@9:       }
alpar@9:       /* congratulations; this is CNF-SAT */
alpar@9:       return 0;
alpar@9: }
alpar@9: 
alpar@9: /**********************************************************************/
alpar@9: 
alpar@9: int glp_write_cnfsat(glp_prob *P, const char *fname)
alpar@9: {     /* write CNF-SAT problem data in DIMACS format */
alpar@9:       XFILE *fp = NULL;
alpar@9:       GLPAIJ *aij;
alpar@9:       int i, j, len, count = 0, ret;
alpar@9:       char s[50];
alpar@9:       if (P == NULL || P->magic != GLP_PROB_MAGIC)
alpar@9:          xerror("glp_write_cnfsat: P = %p; invalid problem object\n",
alpar@9:             P);
alpar@9:       if (glp_check_cnfsat(P) != 0)
alpar@9:       {  xprintf("glp_write_cnfsat: problem object does not encode CNF-"
alpar@9:             "SAT instance\n");
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xprintf("Writing CNF-SAT problem data to `%s'...\n", fname);
alpar@9:       fp = xfopen(fname, "w");
alpar@9:       if (fp == NULL)
alpar@9:       {  xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xfprintf(fp, "c %s\n",
alpar@9:          P->name == NULL ? "unknown" : P->name), count++;
alpar@9:       xfprintf(fp, "p cnf %d %d\n", P->n, P->m), count++;
alpar@9:       for (i = 1; i <= P->m; i++)
alpar@9:       {  len = 0;
alpar@9:          for (aij = P->row[i]->ptr; aij != NULL; aij = aij->r_next)
alpar@9:          {  j = aij->col->j;
alpar@9:             if (aij->val < 0.0) j = -j;
alpar@9:             sprintf(s, "%d", j);
alpar@9:             if (len > 0 && len + 1 + strlen(s) > 72)
alpar@9:                xfprintf(fp, "\n"), count++, len = 0;
alpar@9:             xfprintf(fp, "%s%s", len == 0 ? "" : " ", s);
alpar@9:             if (len > 0) len++;
alpar@9:             len += strlen(s);
alpar@9:          }
alpar@9:          if (len > 0 && len + 1 + 1 > 72)
alpar@9:             xfprintf(fp, "\n"), count++, len = 0;
alpar@9:          xfprintf(fp, "%s0\n", len == 0 ? "" : " "), count++;
alpar@9:       }
alpar@9:       xfprintf(fp, "c eof\n"), count++;
alpar@9:       xfflush(fp);
alpar@9:       if (xferror(fp))
alpar@9:       {  xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
alpar@9:          ret = 1;
alpar@9:          goto done;
alpar@9:       }
alpar@9:       xprintf("%d lines were written\n", count);
alpar@9:       ret = 0;
alpar@9: done: if (fp != NULL) xfclose(fp);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /* eof */