1 /* rdmcf.c (read min-cost flow problem data in DIMACS format) */
2 
3 /***********************************************************************
4 *  This code is part of GLPK (GNU Linear Programming Kit).
5 *  Copyright (C) 2009-2016 Free Software Foundation, Inc.
6 *  Written by Andrew Makhorin <mao@gnu.org>.
7 *
8 *  GLPK is free software: you can redistribute it and/or modify it
9 *  under the terms of the GNU General Public License as published by
10 *  the Free Software Foundation, either version 3 of the License, or
11 *  (at your option) any later version.
12 *
13 *  GLPK is distributed in the hope that it will be useful, but WITHOUT
14 *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
16 *  License for more details.
17 *
18 *  You should have received a copy of the GNU General Public License
19 *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
20 ***********************************************************************/
21 
22 #include "dimacs.h"
23 #include "glpk.h"
24 #include "misc.h"
25 
26 #define error           dmx_error
27 #define warning         dmx_warning
28 #define read_char       dmx_read_char
29 #define read_designator dmx_read_designator
30 #define read_field      dmx_read_field
31 #define end_of_line     dmx_end_of_line
32 #define check_int       dmx_check_int
33 
34 /***********************************************************************
35 *  NAME
36 *
37 *  glp_read_mincost - read min-cost flow problem data in DIMACS format
38 *
39 *  SYNOPSIS
40 *
41 *  int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
42 *     int a_cost, const char *fname);
43 *
44 *  DESCRIPTION
45 *
46 *  The routine glp_read_mincost reads minimum cost flow problem data in
47 *  DIMACS format from a text file.
48 *
49 *  RETURNS
50 *
51 *  If the operation was successful, the routine returns zero. Otherwise
52 *  it prints an error message and returns non-zero. */
53 
glp_read_mincost(glp_graph * G,int v_rhs,int a_low,int a_cap,int a_cost,const char * fname)54 int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
55       int a_cost, const char *fname)
56 {     DMX _csa, *csa = &_csa;
57       glp_vertex *v;
58       glp_arc *a;
59       int i, j, k, nv, na, ret = 0;
60       double rhs, low, cap, cost;
61       char *flag = NULL;
62       if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double))
63          xerror("glp_read_mincost: v_rhs = %d; invalid offset\n",
64             v_rhs);
65       if (a_low >= 0 && a_low > G->a_size - (int)sizeof(double))
66          xerror("glp_read_mincost: a_low = %d; invalid offset\n",
67             a_low);
68       if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
69          xerror("glp_read_mincost: a_cap = %d; invalid offset\n",
70             a_cap);
71       if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
72          xerror("glp_read_mincost: a_cost = %d; invalid offset\n",
73             a_cost);
74       glp_erase_graph(G, G->v_size, G->a_size);
75       if (setjmp(csa->jump))
76       {  ret = 1;
77          goto done;
78       }
79       csa->fname = fname;
80       csa->fp = NULL;
81       csa->count = 0;
82       csa->c = '\n';
83       csa->field[0] = '\0';
84       csa->empty = csa->nonint = 0;
85       xprintf("Reading min-cost flow problem data from '%s'...\n",
86          fname);
87       csa->fp = glp_open(fname, "r");
88       if (csa->fp == NULL)
89       {  xprintf("Unable to open '%s' - %s\n", fname, get_err_msg());
90          longjmp(csa->jump, 1);
91       }
92       /* read problem line */
93       read_designator(csa);
94       if (strcmp(csa->field, "p") != 0)
95          error(csa, "problem line missing or invalid");
96       read_field(csa);
97       if (strcmp(csa->field, "min") != 0)
98          error(csa, "wrong problem designator; 'min' expected");
99       read_field(csa);
100       if (!(str2int(csa->field, &nv) == 0 && nv >= 0))
101          error(csa, "number of nodes missing or invalid");
102       read_field(csa);
103       if (!(str2int(csa->field, &na) == 0 && na >= 0))
104          error(csa, "number of arcs missing or invalid");
105       xprintf("Flow network has %d node%s and %d arc%s\n",
106          nv, nv == 1 ? "" : "s", na, na == 1 ? "" : "s");
107       if (nv > 0) glp_add_vertices(G, nv);
108       end_of_line(csa);
109       /* read node descriptor lines */
110       flag = xcalloc(1+nv, sizeof(char));
111       memset(&flag[1], 0, nv * sizeof(char));
112       if (v_rhs >= 0)
113       {  rhs = 0.0;
114          for (i = 1; i <= nv; i++)
115          {  v = G->v[i];
116             memcpy((char *)v->data + v_rhs, &rhs, sizeof(double));
117          }
118       }
119       for (;;)
120       {  read_designator(csa);
121          if (strcmp(csa->field, "n") != 0) break;
122          read_field(csa);
123          if (str2int(csa->field, &i) != 0)
124             error(csa, "node number missing or invalid");
125          if (!(1 <= i && i <= nv))
126             error(csa, "node number %d out of range", i);
127          if (flag[i])
128             error(csa, "duplicate descriptor of node %d", i);
129          read_field(csa);
130          if (str2num(csa->field, &rhs) != 0)
131             error(csa, "node supply/demand missing or invalid");
132          check_int(csa, rhs);
133          if (v_rhs >= 0)
134          {  v = G->v[i];
135             memcpy((char *)v->data + v_rhs, &rhs, sizeof(double));
136          }
137          flag[i] = 1;
138          end_of_line(csa);
139       }
140       xfree(flag), flag = NULL;
141       /* read arc descriptor lines */
142       for (k = 1; k <= na; k++)
143       {  if (k > 1) read_designator(csa);
144          if (strcmp(csa->field, "a") != 0)
145             error(csa, "wrong line designator; 'a' expected");
146          read_field(csa);
147          if (str2int(csa->field, &i) != 0)
148             error(csa, "starting node number missing or invalid");
149          if (!(1 <= i && i <= nv))
150             error(csa, "starting node number %d out of range", i);
151          read_field(csa);
152          if (str2int(csa->field, &j) != 0)
153             error(csa, "ending node number missing or invalid");
154          if (!(1 <= j && j <= nv))
155             error(csa, "ending node number %d out of range", j);
156          read_field(csa);
157          if (!(str2num(csa->field, &low) == 0 && low >= 0.0))
158             error(csa, "lower bound of arc flow missing or invalid");
159          check_int(csa, low);
160          read_field(csa);
161          if (!(str2num(csa->field, &cap) == 0 && cap >= low))
162             error(csa, "upper bound of arc flow missing or invalid");
163          check_int(csa, cap);
164          read_field(csa);
165          if (str2num(csa->field, &cost) != 0)
166             error(csa, "per-unit cost of arc flow missing or invalid");
167          check_int(csa, cost);
168          a = glp_add_arc(G, i, j);
169          if (a_low >= 0)
170             memcpy((char *)a->data + a_low, &low, sizeof(double));
171          if (a_cap >= 0)
172             memcpy((char *)a->data + a_cap, &cap, sizeof(double));
173          if (a_cost >= 0)
174             memcpy((char *)a->data + a_cost, &cost, sizeof(double));
175          end_of_line(csa);
176       }
177       xprintf("%d lines were read\n", csa->count);
178 done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
179       if (csa->fp != NULL) glp_close(csa->fp);
180       if (flag != NULL) xfree(flag);
181       return ret;
182 }
183 
184 /* eof */
185