lemon-project-template-glpk

comparison deps/glpk/src/glpdmx.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:627006beee6a
1 /* glpdmx.c (reading/writing data in DIMACS format) */
2
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 *
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
9 * E-mail: <mao@gnu.org>.
10 *
11 * GLPK is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation, either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
19 * License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
23 ***********************************************************************/
24
25 #define _GLPSTD_STDIO
26 #include "glpapi.h"
27
28 struct csa
29 { /* common storage area */
30 jmp_buf jump;
31 /* label for go to in case of error */
32 const char *fname;
33 /* name of input text file */
34 XFILE *fp;
35 /* stream assigned to input text file */
36 int count;
37 /* line count */
38 int c;
39 /* current character */
40 char field[255+1];
41 /* data field */
42 int empty;
43 /* warning 'empty line ignored' was printed */
44 int nonint;
45 /* warning 'non-integer data detected' was printed */
46 };
47
48 static void error(struct csa *csa, const char *fmt, ...)
49 { /* print error message and terminate processing */
50 va_list arg;
51 xprintf("%s:%d: error: ", csa->fname, csa->count);
52 va_start(arg, fmt);
53 xvprintf(fmt, arg);
54 va_end(arg);
55 xprintf("\n");
56 longjmp(csa->jump, 1);
57 /* no return */
58 }
59
60 static void warning(struct csa *csa, const char *fmt, ...)
61 { /* print warning message and continue processing */
62 va_list arg;
63 xprintf("%s:%d: warning: ", csa->fname, csa->count);
64 va_start(arg, fmt);
65 xvprintf(fmt, arg);
66 va_end(arg);
67 xprintf("\n");
68 return;
69 }
70
71 static void read_char(struct csa *csa)
72 { /* read character from input text file */
73 int c;
74 if (csa->c == '\n') csa->count++;
75 c = xfgetc(csa->fp);
76 if (c < 0)
77 { if (xferror(csa->fp))
78 error(csa, "read error - %s", xerrmsg());
79 else if (csa->c == '\n')
80 error(csa, "unexpected end of file");
81 else
82 { warning(csa, "missing final end of line");
83 c = '\n';
84 }
85 }
86 else if (c == '\n')
87 ;
88 else if (isspace(c))
89 c = ' ';
90 else if (iscntrl(c))
91 error(csa, "invalid control character 0x%02X", c);
92 csa->c = c;
93 return;
94 }
95
96 static void read_designator(struct csa *csa)
97 { /* read one-character line designator */
98 xassert(csa->c == '\n');
99 read_char(csa);
100 for (;;)
101 { /* skip preceding white-space characters */
102 while (csa->c == ' ')
103 read_char(csa);
104 if (csa->c == '\n')
105 { /* ignore empty line */
106 if (!csa->empty)
107 { warning(csa, "empty line ignored");
108 csa->empty = 1;
109 }
110 read_char(csa);
111 }
112 else if (csa->c == 'c')
113 { /* skip comment line */
114 while (csa->c != '\n')
115 read_char(csa);
116 read_char(csa);
117 }
118 else
119 { /* hmm... looks like a line designator */
120 csa->field[0] = (char)csa->c, csa->field[1] = '\0';
121 /* check that it is followed by a white-space character */
122 read_char(csa);
123 if (!(csa->c == ' ' || csa->c == '\n'))
124 error(csa, "line designator missing or invalid");
125 break;
126 }
127 }
128 return;
129 }
130
131 static void read_field(struct csa *csa)
132 { /* read data field */
133 int len = 0;
134 /* skip preceding white-space characters */
135 while (csa->c == ' ')
136 read_char(csa);
137 /* scan data field */
138 if (csa->c == '\n')
139 error(csa, "unexpected end of line");
140 while (!(csa->c == ' ' || csa->c == '\n'))
141 { if (len == sizeof(csa->field)-1)
142 error(csa, "data field `%.15s...' too long", csa->field);
143 csa->field[len++] = (char)csa->c;
144 read_char(csa);
145 }
146 csa->field[len] = '\0';
147 return;
148 }
149
150 static void end_of_line(struct csa *csa)
151 { /* skip white-space characters until end of line */
152 while (csa->c == ' ')
153 read_char(csa);
154 if (csa->c != '\n')
155 error(csa, "too many data fields specified");
156 return;
157 }
158
159 static void check_int(struct csa *csa, double num)
160 { /* print a warning if non-integer data are detected */
161 if (!csa->nonint && num != floor(num))
162 { warning(csa, "non-integer data detected");
163 csa->nonint = 1;
164 }
165 return;
166 }
167
168 /***********************************************************************
169 * NAME
170 *
171 * glp_read_mincost - read min-cost flow problem data in DIMACS format
172 *
173 * SYNOPSIS
174 *
175 * int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
176 * int a_cost, const char *fname);
177 *
178 * DESCRIPTION
179 *
180 * The routine glp_read_mincost reads minimum cost flow problem data in
181 * DIMACS format from a text file.
182 *
183 * RETURNS
184 *
185 * If the operation was successful, the routine returns zero. Otherwise
186 * it prints an error message and returns non-zero. */
187
188 int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
189 int a_cost, const char *fname)
190 { struct csa _csa, *csa = &_csa;
191 glp_vertex *v;
192 glp_arc *a;
193 int i, j, k, nv, na, ret = 0;
194 double rhs, low, cap, cost;
195 char *flag = NULL;
196 if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double))
197 xerror("glp_read_mincost: v_rhs = %d; invalid offset\n",
198 v_rhs);
199 if (a_low >= 0 && a_low > G->a_size - (int)sizeof(double))
200 xerror("glp_read_mincost: a_low = %d; invalid offset\n",
201 a_low);
202 if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
203 xerror("glp_read_mincost: a_cap = %d; invalid offset\n",
204 a_cap);
205 if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
206 xerror("glp_read_mincost: a_cost = %d; invalid offset\n",
207 a_cost);
208 glp_erase_graph(G, G->v_size, G->a_size);
209 if (setjmp(csa->jump))
210 { ret = 1;
211 goto done;
212 }
213 csa->fname = fname;
214 csa->fp = NULL;
215 csa->count = 0;
216 csa->c = '\n';
217 csa->field[0] = '\0';
218 csa->empty = csa->nonint = 0;
219 xprintf("Reading min-cost flow problem data from `%s'...\n",
220 fname);
221 csa->fp = xfopen(fname, "r");
222 if (csa->fp == NULL)
223 { xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
224 longjmp(csa->jump, 1);
225 }
226 /* read problem line */
227 read_designator(csa);
228 if (strcmp(csa->field, "p") != 0)
229 error(csa, "problem line missing or invalid");
230 read_field(csa);
231 if (strcmp(csa->field, "min") != 0)
232 error(csa, "wrong problem designator; `min' expected");
233 read_field(csa);
234 if (!(str2int(csa->field, &nv) == 0 && nv >= 0))
235 error(csa, "number of nodes missing or invalid");
236 read_field(csa);
237 if (!(str2int(csa->field, &na) == 0 && na >= 0))
238 error(csa, "number of arcs missing or invalid");
239 xprintf("Flow network has %d node%s and %d arc%s\n",
240 nv, nv == 1 ? "" : "s", na, na == 1 ? "" : "s");
241 if (nv > 0) glp_add_vertices(G, nv);
242 end_of_line(csa);
243 /* read node descriptor lines */
244 flag = xcalloc(1+nv, sizeof(char));
245 memset(&flag[1], 0, nv * sizeof(char));
246 if (v_rhs >= 0)
247 { rhs = 0.0;
248 for (i = 1; i <= nv; i++)
249 { v = G->v[i];
250 memcpy((char *)v->data + v_rhs, &rhs, sizeof(double));
251 }
252 }
253 for (;;)
254 { read_designator(csa);
255 if (strcmp(csa->field, "n") != 0) break;
256 read_field(csa);
257 if (str2int(csa->field, &i) != 0)
258 error(csa, "node number missing or invalid");
259 if (!(1 <= i && i <= nv))
260 error(csa, "node number %d out of range", i);
261 if (flag[i])
262 error(csa, "duplicate descriptor of node %d", i);
263 read_field(csa);
264 if (str2num(csa->field, &rhs) != 0)
265 error(csa, "node supply/demand missing or invalid");
266 check_int(csa, rhs);
267 if (v_rhs >= 0)
268 { v = G->v[i];
269 memcpy((char *)v->data + v_rhs, &rhs, sizeof(double));
270 }
271 flag[i] = 1;
272 end_of_line(csa);
273 }
274 xfree(flag), flag = NULL;
275 /* read arc descriptor lines */
276 for (k = 1; k <= na; k++)
277 { if (k > 1) read_designator(csa);
278 if (strcmp(csa->field, "a") != 0)
279 error(csa, "wrong line designator; `a' expected");
280 read_field(csa);
281 if (str2int(csa->field, &i) != 0)
282 error(csa, "starting node number missing or invalid");
283 if (!(1 <= i && i <= nv))
284 error(csa, "starting node number %d out of range", i);
285 read_field(csa);
286 if (str2int(csa->field, &j) != 0)
287 error(csa, "ending node number missing or invalid");
288 if (!(1 <= j && j <= nv))
289 error(csa, "ending node number %d out of range", j);
290 read_field(csa);
291 if (!(str2num(csa->field, &low) == 0 && low >= 0.0))
292 error(csa, "lower bound of arc flow missing or invalid");
293 check_int(csa, low);
294 read_field(csa);
295 if (!(str2num(csa->field, &cap) == 0 && cap >= low))
296 error(csa, "upper bound of arc flow missing or invalid");
297 check_int(csa, cap);
298 read_field(csa);
299 if (str2num(csa->field, &cost) != 0)
300 error(csa, "per-unit cost of arc flow missing or invalid");
301 check_int(csa, cost);
302 a = glp_add_arc(G, i, j);
303 if (a_low >= 0)
304 memcpy((char *)a->data + a_low, &low, sizeof(double));
305 if (a_cap >= 0)
306 memcpy((char *)a->data + a_cap, &cap, sizeof(double));
307 if (a_cost >= 0)
308 memcpy((char *)a->data + a_cost, &cost, sizeof(double));
309 end_of_line(csa);
310 }
311 xprintf("%d lines were read\n", csa->count);
312 done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
313 if (csa->fp != NULL) xfclose(csa->fp);
314 if (flag != NULL) xfree(flag);
315 return ret;
316 }
317
318 /***********************************************************************
319 * NAME
320 *
321 * glp_write_mincost - write min-cost flow problem data in DIMACS format
322 *
323 * SYNOPSIS
324 *
325 * int glp_write_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
326 * int a_cost, const char *fname);
327 *
328 * DESCRIPTION
329 *
330 * The routine glp_write_mincost writes minimum cost flow problem data
331 * in DIMACS format to a text file.
332 *
333 * RETURNS
334 *
335 * If the operation was successful, the routine returns zero. Otherwise
336 * it prints an error message and returns non-zero. */
337
338 int glp_write_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
339 int a_cost, const char *fname)
340 { XFILE *fp;
341 glp_vertex *v;
342 glp_arc *a;
343 int i, count = 0, ret;
344 double rhs, low, cap, cost;
345 if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double))
346 xerror("glp_write_mincost: v_rhs = %d; invalid offset\n",
347 v_rhs);
348 if (a_low >= 0 && a_low > G->a_size - (int)sizeof(double))
349 xerror("glp_write_mincost: a_low = %d; invalid offset\n",
350 a_low);
351 if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
352 xerror("glp_write_mincost: a_cap = %d; invalid offset\n",
353 a_cap);
354 if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
355 xerror("glp_write_mincost: a_cost = %d; invalid offset\n",
356 a_cost);
357 xprintf("Writing min-cost flow problem data to `%s'...\n",
358 fname);
359 fp = xfopen(fname, "w");
360 if (fp == NULL)
361 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
362 ret = 1;
363 goto done;
364 }
365 xfprintf(fp, "c %s\n",
366 G->name == NULL ? "unknown" : G->name), count++;
367 xfprintf(fp, "p min %d %d\n", G->nv, G->na), count++;
368 if (v_rhs >= 0)
369 { for (i = 1; i <= G->nv; i++)
370 { v = G->v[i];
371 memcpy(&rhs, (char *)v->data + v_rhs, sizeof(double));
372 if (rhs != 0.0)
373 xfprintf(fp, "n %d %.*g\n", i, DBL_DIG, rhs), count++;
374 }
375 }
376 for (i = 1; i <= G->nv; i++)
377 { v = G->v[i];
378 for (a = v->out; a != NULL; a = a->t_next)
379 { if (a_low >= 0)
380 memcpy(&low, (char *)a->data + a_low, sizeof(double));
381 else
382 low = 0.0;
383 if (a_cap >= 0)
384 memcpy(&cap, (char *)a->data + a_cap, sizeof(double));
385 else
386 cap = 1.0;
387 if (a_cost >= 0)
388 memcpy(&cost, (char *)a->data + a_cost, sizeof(double));
389 else
390 cost = 0.0;
391 xfprintf(fp, "a %d %d %.*g %.*g %.*g\n",
392 a->tail->i, a->head->i, DBL_DIG, low, DBL_DIG, cap,
393 DBL_DIG, cost), count++;
394 }
395 }
396 xfprintf(fp, "c eof\n"), count++;
397 xfflush(fp);
398 if (xferror(fp))
399 { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
400 ret = 1;
401 goto done;
402 }
403 xprintf("%d lines were written\n", count);
404 ret = 0;
405 done: if (fp != NULL) xfclose(fp);
406 return ret;
407 }
408
409 /***********************************************************************
410 * NAME
411 *
412 * glp_read_maxflow - read maximum flow problem data in DIMACS format
413 *
414 * SYNOPSIS
415 *
416 * int glp_read_maxflow(glp_graph *G, int *s, int *t, int a_cap,
417 * const char *fname);
418 *
419 * DESCRIPTION
420 *
421 * The routine glp_read_maxflow reads maximum flow problem data in
422 * DIMACS format from a text file.
423 *
424 * RETURNS
425 *
426 * If the operation was successful, the routine returns zero. Otherwise
427 * it prints an error message and returns non-zero. */
428
429 int glp_read_maxflow(glp_graph *G, int *_s, int *_t, int a_cap,
430 const char *fname)
431 { struct csa _csa, *csa = &_csa;
432 glp_arc *a;
433 int i, j, k, s, t, nv, na, ret = 0;
434 double cap;
435 if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
436 xerror("glp_read_maxflow: a_cap = %d; invalid offset\n",
437 a_cap);
438 glp_erase_graph(G, G->v_size, G->a_size);
439 if (setjmp(csa->jump))
440 { ret = 1;
441 goto done;
442 }
443 csa->fname = fname;
444 csa->fp = NULL;
445 csa->count = 0;
446 csa->c = '\n';
447 csa->field[0] = '\0';
448 csa->empty = csa->nonint = 0;
449 xprintf("Reading maximum flow problem data from `%s'...\n",
450 fname);
451 csa->fp = xfopen(fname, "r");
452 if (csa->fp == NULL)
453 { xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
454 longjmp(csa->jump, 1);
455 }
456 /* read problem line */
457 read_designator(csa);
458 if (strcmp(csa->field, "p") != 0)
459 error(csa, "problem line missing or invalid");
460 read_field(csa);
461 if (strcmp(csa->field, "max") != 0)
462 error(csa, "wrong problem designator; `max' expected");
463 read_field(csa);
464 if (!(str2int(csa->field, &nv) == 0 && nv >= 2))
465 error(csa, "number of nodes missing or invalid");
466 read_field(csa);
467 if (!(str2int(csa->field, &na) == 0 && na >= 0))
468 error(csa, "number of arcs missing or invalid");
469 xprintf("Flow network has %d node%s and %d arc%s\n",
470 nv, nv == 1 ? "" : "s", na, na == 1 ? "" : "s");
471 if (nv > 0) glp_add_vertices(G, nv);
472 end_of_line(csa);
473 /* read node descriptor lines */
474 s = t = 0;
475 for (;;)
476 { read_designator(csa);
477 if (strcmp(csa->field, "n") != 0) break;
478 read_field(csa);
479 if (str2int(csa->field, &i) != 0)
480 error(csa, "node number missing or invalid");
481 if (!(1 <= i && i <= nv))
482 error(csa, "node number %d out of range", i);
483 read_field(csa);
484 if (strcmp(csa->field, "s") == 0)
485 { if (s > 0)
486 error(csa, "only one source node allowed");
487 s = i;
488 }
489 else if (strcmp(csa->field, "t") == 0)
490 { if (t > 0)
491 error(csa, "only one sink node allowed");
492 t = i;
493 }
494 else
495 error(csa, "wrong node designator; `s' or `t' expected");
496 if (s > 0 && s == t)
497 error(csa, "source and sink nodes must be distinct");
498 end_of_line(csa);
499 }
500 if (s == 0)
501 error(csa, "source node descriptor missing\n");
502 if (t == 0)
503 error(csa, "sink node descriptor missing\n");
504 if (_s != NULL) *_s = s;
505 if (_t != NULL) *_t = t;
506 /* read arc descriptor lines */
507 for (k = 1; k <= na; k++)
508 { if (k > 1) read_designator(csa);
509 if (strcmp(csa->field, "a") != 0)
510 error(csa, "wrong line designator; `a' expected");
511 read_field(csa);
512 if (str2int(csa->field, &i) != 0)
513 error(csa, "starting node number missing or invalid");
514 if (!(1 <= i && i <= nv))
515 error(csa, "starting node number %d out of range", i);
516 read_field(csa);
517 if (str2int(csa->field, &j) != 0)
518 error(csa, "ending node number missing or invalid");
519 if (!(1 <= j && j <= nv))
520 error(csa, "ending node number %d out of range", j);
521 read_field(csa);
522 if (!(str2num(csa->field, &cap) == 0 && cap >= 0.0))
523 error(csa, "arc capacity missing or invalid");
524 check_int(csa, cap);
525 a = glp_add_arc(G, i, j);
526 if (a_cap >= 0)
527 memcpy((char *)a->data + a_cap, &cap, sizeof(double));
528 end_of_line(csa);
529 }
530 xprintf("%d lines were read\n", csa->count);
531 done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
532 if (csa->fp != NULL) xfclose(csa->fp);
533 return ret;
534 }
535
536 /***********************************************************************
537 * NAME
538 *
539 * glp_write_maxflow - write maximum flow problem data in DIMACS format
540 *
541 * SYNOPSIS
542 *
543 * int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
544 * const char *fname);
545 *
546 * DESCRIPTION
547 *
548 * The routine glp_write_maxflow writes maximum flow problem data in
549 * DIMACS format to a text file.
550 *
551 * RETURNS
552 *
553 * If the operation was successful, the routine returns zero. Otherwise
554 * it prints an error message and returns non-zero. */
555
556 int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
557 const char *fname)
558 { XFILE *fp;
559 glp_vertex *v;
560 glp_arc *a;
561 int i, count = 0, ret;
562 double cap;
563 if (!(1 <= s && s <= G->nv))
564 xerror("glp_write_maxflow: s = %d; source node number out of r"
565 "ange\n", s);
566 if (!(1 <= t && t <= G->nv))
567 xerror("glp_write_maxflow: t = %d: sink node number out of ran"
568 "ge\n", t);
569 if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
570 xerror("glp_write_mincost: a_cap = %d; invalid offset\n",
571 a_cap);
572 xprintf("Writing maximum flow problem data to `%s'...\n",
573 fname);
574 fp = xfopen(fname, "w");
575 if (fp == NULL)
576 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
577 ret = 1;
578 goto done;
579 }
580 xfprintf(fp, "c %s\n",
581 G->name == NULL ? "unknown" : G->name), count++;
582 xfprintf(fp, "p max %d %d\n", G->nv, G->na), count++;
583 xfprintf(fp, "n %d s\n", s), count++;
584 xfprintf(fp, "n %d t\n", t), count++;
585 for (i = 1; i <= G->nv; i++)
586 { v = G->v[i];
587 for (a = v->out; a != NULL; a = a->t_next)
588 { if (a_cap >= 0)
589 memcpy(&cap, (char *)a->data + a_cap, sizeof(double));
590 else
591 cap = 1.0;
592 xfprintf(fp, "a %d %d %.*g\n",
593 a->tail->i, a->head->i, DBL_DIG, cap), count++;
594 }
595 }
596 xfprintf(fp, "c eof\n"), count++;
597 xfflush(fp);
598 if (xferror(fp))
599 { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
600 ret = 1;
601 goto done;
602 }
603 xprintf("%d lines were written\n", count);
604 ret = 0;
605 done: if (fp != NULL) xfclose(fp);
606 return ret;
607 }
608
609 /***********************************************************************
610 * NAME
611 *
612 * glp_read_asnprob - read assignment problem data in DIMACS format
613 *
614 * SYNOPSIS
615 *
616 * int glp_read_asnprob(glp_graph *G, int v_set, int a_cost,
617 * const char *fname);
618 *
619 * DESCRIPTION
620 *
621 * The routine glp_read_asnprob reads assignment problem data in DIMACS
622 * format from a text file.
623 *
624 * RETURNS
625 *
626 * If the operation was successful, the routine returns zero. Otherwise
627 * it prints an error message and returns non-zero. */
628
629 int glp_read_asnprob(glp_graph *G, int v_set, int a_cost, const char
630 *fname)
631 { struct csa _csa, *csa = &_csa;
632 glp_vertex *v;
633 glp_arc *a;
634 int nv, na, n1, i, j, k, ret = 0;
635 double cost;
636 char *flag = NULL;
637 if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
638 xerror("glp_read_asnprob: v_set = %d; invalid offset\n",
639 v_set);
640 if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
641 xerror("glp_read_asnprob: a_cost = %d; invalid offset\n",
642 a_cost);
643 glp_erase_graph(G, G->v_size, G->a_size);
644 if (setjmp(csa->jump))
645 { ret = 1;
646 goto done;
647 }
648 csa->fname = fname;
649 csa->fp = NULL;
650 csa->count = 0;
651 csa->c = '\n';
652 csa->field[0] = '\0';
653 csa->empty = csa->nonint = 0;
654 xprintf("Reading assignment problem data from `%s'...\n", fname);
655 csa->fp = xfopen(fname, "r");
656 if (csa->fp == NULL)
657 { xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
658 longjmp(csa->jump, 1);
659 }
660 /* read problem line */
661 read_designator(csa);
662 if (strcmp(csa->field, "p") != 0)
663 error(csa, "problem line missing or invalid");
664 read_field(csa);
665 if (strcmp(csa->field, "asn") != 0)
666 error(csa, "wrong problem designator; `asn' expected");
667 read_field(csa);
668 if (!(str2int(csa->field, &nv) == 0 && nv >= 0))
669 error(csa, "number of nodes missing or invalid");
670 read_field(csa);
671 if (!(str2int(csa->field, &na) == 0 && na >= 0))
672 error(csa, "number of arcs missing or invalid");
673 if (nv > 0) glp_add_vertices(G, nv);
674 end_of_line(csa);
675 /* read node descriptor lines */
676 flag = xcalloc(1+nv, sizeof(char));
677 memset(&flag[1], 0, nv * sizeof(char));
678 n1 = 0;
679 for (;;)
680 { read_designator(csa);
681 if (strcmp(csa->field, "n") != 0) break;
682 read_field(csa);
683 if (str2int(csa->field, &i) != 0)
684 error(csa, "node number missing or invalid");
685 if (!(1 <= i && i <= nv))
686 error(csa, "node number %d out of range", i);
687 if (flag[i])
688 error(csa, "duplicate descriptor of node %d", i);
689 flag[i] = 1, n1++;
690 end_of_line(csa);
691 }
692 xprintf(
693 "Assignment problem has %d + %d = %d node%s and %d arc%s\n",
694 n1, nv - n1, nv, nv == 1 ? "" : "s", na, na == 1 ? "" : "s");
695 if (v_set >= 0)
696 { for (i = 1; i <= nv; i++)
697 { v = G->v[i];
698 k = (flag[i] ? 0 : 1);
699 memcpy((char *)v->data + v_set, &k, sizeof(int));
700 }
701 }
702 /* read arc descriptor lines */
703 for (k = 1; k <= na; k++)
704 { if (k > 1) read_designator(csa);
705 if (strcmp(csa->field, "a") != 0)
706 error(csa, "wrong line designator; `a' expected");
707 read_field(csa);
708 if (str2int(csa->field, &i) != 0)
709 error(csa, "starting node number missing or invalid");
710 if (!(1 <= i && i <= nv))
711 error(csa, "starting node number %d out of range", i);
712 if (!flag[i])
713 error(csa, "node %d cannot be a starting node", i);
714 read_field(csa);
715 if (str2int(csa->field, &j) != 0)
716 error(csa, "ending node number missing or invalid");
717 if (!(1 <= j && j <= nv))
718 error(csa, "ending node number %d out of range", j);
719 if (flag[j])
720 error(csa, "node %d cannot be an ending node", j);
721 read_field(csa);
722 if (str2num(csa->field, &cost) != 0)
723 error(csa, "arc cost missing or invalid");
724 check_int(csa, cost);
725 a = glp_add_arc(G, i, j);
726 if (a_cost >= 0)
727 memcpy((char *)a->data + a_cost, &cost, sizeof(double));
728 end_of_line(csa);
729 }
730 xprintf("%d lines were read\n", csa->count);
731 done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
732 if (csa->fp != NULL) xfclose(csa->fp);
733 if (flag != NULL) xfree(flag);
734 return ret;
735 }
736
737 /***********************************************************************
738 * NAME
739 *
740 * glp_write_asnprob - write assignment problem data in DIMACS format
741 *
742 * SYNOPSIS
743 *
744 * int glp_write_asnprob(glp_graph *G, int v_set, int a_cost,
745 * const char *fname);
746 *
747 * DESCRIPTION
748 *
749 * The routine glp_write_asnprob writes assignment problem data in
750 * DIMACS format to a text file.
751 *
752 * RETURNS
753 *
754 * If the operation was successful, the routine returns zero. Otherwise
755 * it prints an error message and returns non-zero. */
756
757 int glp_write_asnprob(glp_graph *G, int v_set, int a_cost, const char
758 *fname)
759 { XFILE *fp;
760 glp_vertex *v;
761 glp_arc *a;
762 int i, k, count = 0, ret;
763 double cost;
764 if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
765 xerror("glp_write_asnprob: v_set = %d; invalid offset\n",
766 v_set);
767 if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
768 xerror("glp_write_asnprob: a_cost = %d; invalid offset\n",
769 a_cost);
770 xprintf("Writing assignment problem data to `%s'...\n", fname);
771 fp = xfopen(fname, "w");
772 if (fp == NULL)
773 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
774 ret = 1;
775 goto done;
776 }
777 xfprintf(fp, "c %s\n",
778 G->name == NULL ? "unknown" : G->name), count++;
779 xfprintf(fp, "p asn %d %d\n", G->nv, G->na), count++;
780 for (i = 1; i <= G->nv; i++)
781 { v = G->v[i];
782 if (v_set >= 0)
783 memcpy(&k, (char *)v->data + v_set, sizeof(int));
784 else
785 k = (v->out != NULL ? 0 : 1);
786 if (k == 0)
787 xfprintf(fp, "n %d\n", i), count++;
788 }
789 for (i = 1; i <= G->nv; i++)
790 { v = G->v[i];
791 for (a = v->out; a != NULL; a = a->t_next)
792 { if (a_cost >= 0)
793 memcpy(&cost, (char *)a->data + a_cost, sizeof(double));
794 else
795 cost = 1.0;
796 xfprintf(fp, "a %d %d %.*g\n",
797 a->tail->i, a->head->i, DBL_DIG, cost), count++;
798 }
799 }
800 xfprintf(fp, "c eof\n"), count++;
801 xfflush(fp);
802 if (xferror(fp))
803 { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
804 ret = 1;
805 goto done;
806 }
807 xprintf("%d lines were written\n", count);
808 ret = 0;
809 done: if (fp != NULL) xfclose(fp);
810 return ret;
811 }
812
813 /***********************************************************************
814 * NAME
815 *
816 * glp_read_ccdata - read graph in DIMACS clique/coloring format
817 *
818 * SYNOPSIS
819 *
820 * int glp_read_ccdata(glp_graph *G, int v_wgt, const char *fname);
821 *
822 * DESCRIPTION
823 *
824 * The routine glp_read_ccdata reads an (undirected) graph in DIMACS
825 * clique/coloring format from a text file.
826 *
827 * RETURNS
828 *
829 * If the operation was successful, the routine returns zero. Otherwise
830 * it prints an error message and returns non-zero. */
831
832 int glp_read_ccdata(glp_graph *G, int v_wgt, const char *fname)
833 { struct csa _csa, *csa = &_csa;
834 glp_vertex *v;
835 int i, j, k, nv, ne, ret = 0;
836 double w;
837 char *flag = NULL;
838 if (v_wgt >= 0 && v_wgt > G->v_size - (int)sizeof(double))
839 xerror("glp_read_ccdata: v_wgt = %d; invalid offset\n",
840 v_wgt);
841 glp_erase_graph(G, G->v_size, G->a_size);
842 if (setjmp(csa->jump))
843 { ret = 1;
844 goto done;
845 }
846 csa->fname = fname;
847 csa->fp = NULL;
848 csa->count = 0;
849 csa->c = '\n';
850 csa->field[0] = '\0';
851 csa->empty = csa->nonint = 0;
852 xprintf("Reading graph from `%s'...\n", fname);
853 csa->fp = xfopen(fname, "r");
854 if (csa->fp == NULL)
855 { xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
856 longjmp(csa->jump, 1);
857 }
858 /* read problem line */
859 read_designator(csa);
860 if (strcmp(csa->field, "p") != 0)
861 error(csa, "problem line missing or invalid");
862 read_field(csa);
863 if (strcmp(csa->field, "edge") != 0)
864 error(csa, "wrong problem designator; `edge' expected");
865 read_field(csa);
866 if (!(str2int(csa->field, &nv) == 0 && nv >= 0))
867 error(csa, "number of vertices missing or invalid");
868 read_field(csa);
869 if (!(str2int(csa->field, &ne) == 0 && ne >= 0))
870 error(csa, "number of edges missing or invalid");
871 xprintf("Graph has %d vert%s and %d edge%s\n",
872 nv, nv == 1 ? "ex" : "ices", ne, ne == 1 ? "" : "s");
873 if (nv > 0) glp_add_vertices(G, nv);
874 end_of_line(csa);
875 /* read node descriptor lines */
876 flag = xcalloc(1+nv, sizeof(char));
877 memset(&flag[1], 0, nv * sizeof(char));
878 if (v_wgt >= 0)
879 { w = 1.0;
880 for (i = 1; i <= nv; i++)
881 { v = G->v[i];
882 memcpy((char *)v->data + v_wgt, &w, sizeof(double));
883 }
884 }
885 for (;;)
886 { read_designator(csa);
887 if (strcmp(csa->field, "n") != 0) break;
888 read_field(csa);
889 if (str2int(csa->field, &i) != 0)
890 error(csa, "vertex number missing or invalid");
891 if (!(1 <= i && i <= nv))
892 error(csa, "vertex number %d out of range", i);
893 if (flag[i])
894 error(csa, "duplicate descriptor of vertex %d", i);
895 read_field(csa);
896 if (str2num(csa->field, &w) != 0)
897 error(csa, "vertex weight missing or invalid");
898 check_int(csa, w);
899 if (v_wgt >= 0)
900 { v = G->v[i];
901 memcpy((char *)v->data + v_wgt, &w, sizeof(double));
902 }
903 flag[i] = 1;
904 end_of_line(csa);
905 }
906 xfree(flag), flag = NULL;
907 /* read edge descriptor lines */
908 for (k = 1; k <= ne; k++)
909 { if (k > 1) read_designator(csa);
910 if (strcmp(csa->field, "e") != 0)
911 error(csa, "wrong line designator; `e' expected");
912 read_field(csa);
913 if (str2int(csa->field, &i) != 0)
914 error(csa, "first vertex number missing or invalid");
915 if (!(1 <= i && i <= nv))
916 error(csa, "first vertex number %d out of range", i);
917 read_field(csa);
918 if (str2int(csa->field, &j) != 0)
919 error(csa, "second vertex number missing or invalid");
920 if (!(1 <= j && j <= nv))
921 error(csa, "second vertex number %d out of range", j);
922 glp_add_arc(G, i, j);
923 end_of_line(csa);
924 }
925 xprintf("%d lines were read\n", csa->count);
926 done: if (ret) glp_erase_graph(G, G->v_size, G->a_size);
927 if (csa->fp != NULL) xfclose(csa->fp);
928 if (flag != NULL) xfree(flag);
929 return ret;
930 }
931
932 /***********************************************************************
933 * NAME
934 *
935 * glp_write_ccdata - write graph in DIMACS clique/coloring format
936 *
937 * SYNOPSIS
938 *
939 * int glp_write_ccdata(glp_graph *G, int v_wgt, const char *fname);
940 *
941 * DESCRIPTION
942 *
943 * The routine glp_write_ccdata writes the specified graph in DIMACS
944 * clique/coloring format to a text file.
945 *
946 * RETURNS
947 *
948 * If the operation was successful, the routine returns zero. Otherwise
949 * it prints an error message and returns non-zero. */
950
951 int glp_write_ccdata(glp_graph *G, int v_wgt, const char *fname)
952 { XFILE *fp;
953 glp_vertex *v;
954 glp_arc *e;
955 int i, count = 0, ret;
956 double w;
957 if (v_wgt >= 0 && v_wgt > G->v_size - (int)sizeof(double))
958 xerror("glp_write_ccdata: v_wgt = %d; invalid offset\n",
959 v_wgt);
960 xprintf("Writing graph to `%s'\n", fname);
961 fp = xfopen(fname, "w");
962 if (fp == NULL)
963 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
964 ret = 1;
965 goto done;
966 }
967 xfprintf(fp, "c %s\n",
968 G->name == NULL ? "unknown" : G->name), count++;
969 xfprintf(fp, "p edge %d %d\n", G->nv, G->na), count++;
970 if (v_wgt >= 0)
971 { for (i = 1; i <= G->nv; i++)
972 { v = G->v[i];
973 memcpy(&w, (char *)v->data + v_wgt, sizeof(double));
974 if (w != 1.0)
975 xfprintf(fp, "n %d %.*g\n", i, DBL_DIG, w), count++;
976 }
977 }
978 for (i = 1; i <= G->nv; i++)
979 { v = G->v[i];
980 for (e = v->out; e != NULL; e = e->t_next)
981 xfprintf(fp, "e %d %d\n", e->tail->i, e->head->i), count++;
982 }
983 xfprintf(fp, "c eof\n"), count++;
984 xfflush(fp);
985 if (xferror(fp))
986 { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
987 ret = 1;
988 goto done;
989 }
990 xprintf("%d lines were written\n", count);
991 ret = 0;
992 done: if (fp != NULL) xfclose(fp);
993 return ret;
994 }
995
996 /***********************************************************************
997 * NAME
998 *
999 * glp_read_prob - read problem data in GLPK format
1000 *
1001 * SYNOPSIS
1002 *
1003 * int glp_read_prob(glp_prob *P, int flags, const char *fname);
1004 *
1005 * The routine glp_read_prob reads problem data in GLPK LP/MIP format
1006 * from a text file.
1007 *
1008 * RETURNS
1009 *
1010 * If the operation was successful, the routine returns zero. Otherwise
1011 * it prints an error message and returns non-zero. */
1012
1013 int glp_read_prob(glp_prob *P, int flags, const char *fname)
1014 { struct csa _csa, *csa = &_csa;
1015 int mip, m, n, nnz, ne, i, j, k, type, kind, ret, *ln = NULL,
1016 *ia = NULL, *ja = NULL;
1017 double lb, ub, temp, *ar = NULL;
1018 char *rf = NULL, *cf = NULL;
1019 if (P == NULL || P->magic != GLP_PROB_MAGIC)
1020 xerror("glp_read_prob: P = %p; invalid problem object\n",
1021 P);
1022 if (flags != 0)
1023 xerror("glp_read_prob: flags = %d; invalid parameter\n",
1024 flags);
1025 if (fname == NULL)
1026 xerror("glp_read_prob: fname = %d; invalid parameter\n",
1027 fname);
1028 glp_erase_prob(P);
1029 if (setjmp(csa->jump))
1030 { ret = 1;
1031 goto done;
1032 }
1033 csa->fname = fname;
1034 csa->fp = NULL;
1035 csa->count = 0;
1036 csa->c = '\n';
1037 csa->field[0] = '\0';
1038 csa->empty = csa->nonint = 0;
1039 xprintf("Reading problem data from `%s'...\n", fname);
1040 csa->fp = xfopen(fname, "r");
1041 if (csa->fp == NULL)
1042 { xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
1043 longjmp(csa->jump, 1);
1044 }
1045 /* read problem line */
1046 read_designator(csa);
1047 if (strcmp(csa->field, "p") != 0)
1048 error(csa, "problem line missing or invalid");
1049 read_field(csa);
1050 if (strcmp(csa->field, "lp") == 0)
1051 mip = 0;
1052 else if (strcmp(csa->field, "mip") == 0)
1053 mip = 1;
1054 else
1055 error(csa, "wrong problem designator; `lp' or `mip' expected\n"
1056 );
1057 read_field(csa);
1058 if (strcmp(csa->field, "min") == 0)
1059 glp_set_obj_dir(P, GLP_MIN);
1060 else if (strcmp(csa->field, "max") == 0)
1061 glp_set_obj_dir(P, GLP_MAX);
1062 else
1063 error(csa, "objective sense missing or invalid");
1064 read_field(csa);
1065 if (!(str2int(csa->field, &m) == 0 && m >= 0))
1066 error(csa, "number of rows missing or invalid");
1067 read_field(csa);
1068 if (!(str2int(csa->field, &n) == 0 && n >= 0))
1069 error(csa, "number of columns missing or invalid");
1070 read_field(csa);
1071 if (!(str2int(csa->field, &nnz) == 0 && nnz >= 0))
1072 error(csa, "number of constraint coefficients missing or inval"
1073 "id");
1074 if (m > 0)
1075 { glp_add_rows(P, m);
1076 for (i = 1; i <= m; i++)
1077 glp_set_row_bnds(P, i, GLP_FX, 0.0, 0.0);
1078 }
1079 if (n > 0)
1080 { glp_add_cols(P, n);
1081 for (j = 1; j <= n; j++)
1082 { if (!mip)
1083 glp_set_col_bnds(P, j, GLP_LO, 0.0, 0.0);
1084 else
1085 glp_set_col_kind(P, j, GLP_BV);
1086 }
1087 }
1088 end_of_line(csa);
1089 /* allocate working arrays */
1090 rf = xcalloc(1+m, sizeof(char));
1091 memset(rf, 0, 1+m);
1092 cf = xcalloc(1+n, sizeof(char));
1093 memset(cf, 0, 1+n);
1094 ln = xcalloc(1+nnz, sizeof(int));
1095 ia = xcalloc(1+nnz, sizeof(int));
1096 ja = xcalloc(1+nnz, sizeof(int));
1097 ar = xcalloc(1+nnz, sizeof(double));
1098 /* read descriptor lines */
1099 ne = 0;
1100 for (;;)
1101 { read_designator(csa);
1102 if (strcmp(csa->field, "i") == 0)
1103 { /* row descriptor */
1104 read_field(csa);
1105 if (str2int(csa->field, &i) != 0)
1106 error(csa, "row number missing or invalid");
1107 if (!(1 <= i && i <= m))
1108 error(csa, "row number out of range");
1109 read_field(csa);
1110 if (strcmp(csa->field, "f") == 0)
1111 type = GLP_FR;
1112 else if (strcmp(csa->field, "l") == 0)
1113 type = GLP_LO;
1114 else if (strcmp(csa->field, "u") == 0)
1115 type = GLP_UP;
1116 else if (strcmp(csa->field, "d") == 0)
1117 type = GLP_DB;
1118 else if (strcmp(csa->field, "s") == 0)
1119 type = GLP_FX;
1120 else
1121 error(csa, "row type missing or invalid");
1122 if (type == GLP_LO || type == GLP_DB || type == GLP_FX)
1123 { read_field(csa);
1124 if (str2num(csa->field, &lb) != 0)
1125 error(csa, "row lower bound/fixed value missing or in"
1126 "valid");
1127 }
1128 else
1129 lb = 0.0;
1130 if (type == GLP_UP || type == GLP_DB)
1131 { read_field(csa);
1132 if (str2num(csa->field, &ub) != 0)
1133 error(csa, "row upper bound missing or invalid");
1134 }
1135 else
1136 ub = 0.0;
1137 if (rf[i] & 0x01)
1138 error(csa, "duplicate row descriptor");
1139 glp_set_row_bnds(P, i, type, lb, ub), rf[i] |= 0x01;
1140 }
1141 else if (strcmp(csa->field, "j") == 0)
1142 { /* column descriptor */
1143 read_field(csa);
1144 if (str2int(csa->field, &j) != 0)
1145 error(csa, "column number missing or invalid");
1146 if (!(1 <= j && j <= n))
1147 error(csa, "column number out of range");
1148 if (!mip)
1149 kind = GLP_CV;
1150 else
1151 { read_field(csa);
1152 if (strcmp(csa->field, "c") == 0)
1153 kind = GLP_CV;
1154 else if (strcmp(csa->field, "i") == 0)
1155 kind = GLP_IV;
1156 else if (strcmp(csa->field, "b") == 0)
1157 { kind = GLP_IV;
1158 type = GLP_DB, lb = 0.0, ub = 1.0;
1159 goto skip;
1160 }
1161 else
1162 error(csa, "column kind missing or invalid");
1163 }
1164 read_field(csa);
1165 if (strcmp(csa->field, "f") == 0)
1166 type = GLP_FR;
1167 else if (strcmp(csa->field, "l") == 0)
1168 type = GLP_LO;
1169 else if (strcmp(csa->field, "u") == 0)
1170 type = GLP_UP;
1171 else if (strcmp(csa->field, "d") == 0)
1172 type = GLP_DB;
1173 else if (strcmp(csa->field, "s") == 0)
1174 type = GLP_FX;
1175 else
1176 error(csa, "column type missing or invalid");
1177 if (type == GLP_LO || type == GLP_DB || type == GLP_FX)
1178 { read_field(csa);
1179 if (str2num(csa->field, &lb) != 0)
1180 error(csa, "column lower bound/fixed value missing or"
1181 " invalid");
1182 }
1183 else
1184 lb = 0.0;
1185 if (type == GLP_UP || type == GLP_DB)
1186 { read_field(csa);
1187 if (str2num(csa->field, &ub) != 0)
1188 error(csa, "column upper bound missing or invalid");
1189 }
1190 else
1191 ub = 0.0;
1192 skip: if (cf[j] & 0x01)
1193 error(csa, "duplicate column descriptor");
1194 glp_set_col_kind(P, j, kind);
1195 glp_set_col_bnds(P, j, type, lb, ub), cf[j] |= 0x01;
1196 }
1197 else if (strcmp(csa->field, "a") == 0)
1198 { /* coefficient descriptor */
1199 read_field(csa);
1200 if (str2int(csa->field, &i) != 0)
1201 error(csa, "row number missing or invalid");
1202 if (!(0 <= i && i <= m))
1203 error(csa, "row number out of range");
1204 read_field(csa);
1205 if (str2int(csa->field, &j) != 0)
1206 error(csa, "column number missing or invalid");
1207 if (!((i == 0 ? 0 : 1) <= j && j <= n))
1208 error(csa, "column number out of range");
1209 read_field(csa);
1210 if (i == 0)
1211 { if (str2num(csa->field, &temp) != 0)
1212 error(csa, "objective %s missing or invalid",
1213 j == 0 ? "constant term" : "coefficient");
1214 if (cf[j] & 0x10)
1215 error(csa, "duplicate objective %s",
1216 j == 0 ? "constant term" : "coefficient");
1217 glp_set_obj_coef(P, j, temp), cf[j] |= 0x10;
1218 }
1219 else
1220 { if (str2num(csa->field, &temp) != 0)
1221 error(csa, "constraint coefficient missing or invalid"
1222 );
1223 if (ne == nnz)
1224 error(csa, "too many constraint coefficient descripto"
1225 "rs");
1226 ln[++ne] = csa->count;
1227 ia[ne] = i, ja[ne] = j, ar[ne] = temp;
1228 }
1229 }
1230 else if (strcmp(csa->field, "n") == 0)
1231 { /* symbolic name descriptor */
1232 read_field(csa);
1233 if (strcmp(csa->field, "p") == 0)
1234 { /* problem name */
1235 read_field(csa);
1236 if (P->name != NULL)
1237 error(csa, "duplicate problem name");
1238 glp_set_prob_name(P, csa->field);
1239 }
1240 else if (strcmp(csa->field, "z") == 0)
1241 { /* objective name */
1242 read_field(csa);
1243 if (P->obj != NULL)
1244 error(csa, "duplicate objective name");
1245 glp_set_obj_name(P, csa->field);
1246 }
1247 else if (strcmp(csa->field, "i") == 0)
1248 { /* row name */
1249 read_field(csa);
1250 if (str2int(csa->field, &i) != 0)
1251 error(csa, "row number missing or invalid");
1252 if (!(1 <= i && i <= m))
1253 error(csa, "row number out of range");
1254 read_field(csa);
1255 if (P->row[i]->name != NULL)
1256 error(csa, "duplicate row name");
1257 glp_set_row_name(P, i, csa->field);
1258 }
1259 else if (strcmp(csa->field, "j") == 0)
1260 { /* column name */
1261 read_field(csa);
1262 if (str2int(csa->field, &j) != 0)
1263 error(csa, "column number missing or invalid");
1264 if (!(1 <= j && j <= n))
1265 error(csa, "column number out of range");
1266 read_field(csa);
1267 if (P->col[j]->name != NULL)
1268 error(csa, "duplicate column name");
1269 glp_set_col_name(P, j, csa->field);
1270 }
1271 else
1272 error(csa, "object designator missing or invalid");
1273 }
1274 else if (strcmp(csa->field, "e") == 0)
1275 break;
1276 else
1277 error(csa, "line designator missing or invalid");
1278 end_of_line(csa);
1279 }
1280 if (ne < nnz)
1281 error(csa, "too few constraint coefficient descriptors");
1282 xassert(ne == nnz);
1283 k = glp_check_dup(m, n, ne, ia, ja);
1284 xassert(0 <= k && k <= nnz);
1285 if (k > 0)
1286 { csa->count = ln[k];
1287 error(csa, "duplicate constraint coefficient");
1288 }
1289 glp_load_matrix(P, ne, ia, ja, ar);
1290 /* print some statistics */
1291 if (P->name != NULL)
1292 xprintf("Problem: %s\n", P->name);
1293 if (P->obj != NULL)
1294 xprintf("Objective: %s\n", P->obj);
1295 xprintf("%d row%s, %d column%s, %d non-zero%s\n",
1296 m, m == 1 ? "" : "s", n, n == 1 ? "" : "s", nnz, nnz == 1 ?
1297 "" : "s");
1298 if (glp_get_num_int(P) > 0)
1299 { int ni = glp_get_num_int(P);
1300 int nb = glp_get_num_bin(P);
1301 if (ni == 1)
1302 { if (nb == 0)
1303 xprintf("One variable is integer\n");
1304 else
1305 xprintf("One variable is binary\n");
1306 }
1307 else
1308 { xprintf("%d integer variables, ", ni);
1309 if (nb == 0)
1310 xprintf("none");
1311 else if (nb == 1)
1312 xprintf("one");
1313 else if (nb == ni)
1314 xprintf("all");
1315 else
1316 xprintf("%d", nb);
1317 xprintf(" of which %s binary\n", nb == 1 ? "is" : "are");
1318 }
1319 }
1320 xprintf("%d lines were read\n", csa->count);
1321 /* problem data has been successfully read */
1322 glp_sort_matrix(P);
1323 ret = 0;
1324 done: if (csa->fp != NULL) xfclose(csa->fp);
1325 if (rf != NULL) xfree(rf);
1326 if (cf != NULL) xfree(cf);
1327 if (ln != NULL) xfree(ln);
1328 if (ia != NULL) xfree(ia);
1329 if (ja != NULL) xfree(ja);
1330 if (ar != NULL) xfree(ar);
1331 if (ret) glp_erase_prob(P);
1332 return ret;
1333 }
1334
1335 /***********************************************************************
1336 * NAME
1337 *
1338 * glp_write_prob - write problem data in GLPK format
1339 *
1340 * SYNOPSIS
1341 *
1342 * int glp_write_prob(glp_prob *P, int flags, const char *fname);
1343 *
1344 * The routine glp_write_prob writes problem data in GLPK LP/MIP format
1345 * to a text file.
1346 *
1347 * RETURNS
1348 *
1349 * If the operation was successful, the routine returns zero. Otherwise
1350 * it prints an error message and returns non-zero. */
1351
1352 int glp_write_prob(glp_prob *P, int flags, const char *fname)
1353 { XFILE *fp;
1354 GLPROW *row;
1355 GLPCOL *col;
1356 GLPAIJ *aij;
1357 int mip, i, j, count, ret;
1358 if (P == NULL || P->magic != GLP_PROB_MAGIC)
1359 xerror("glp_write_prob: P = %p; invalid problem object\n",
1360 P);
1361 if (flags != 0)
1362 xerror("glp_write_prob: flags = %d; invalid parameter\n",
1363 flags);
1364 if (fname == NULL)
1365 xerror("glp_write_prob: fname = %d; invalid parameter\n",
1366 fname);
1367 xprintf("Writing problem data to `%s'...\n", fname);
1368 fp = xfopen(fname, "w"), count = 0;
1369 if (fp == NULL)
1370 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
1371 ret = 1;
1372 goto done;
1373 }
1374 /* write problem line */
1375 mip = (glp_get_num_int(P) > 0);
1376 xfprintf(fp, "p %s %s %d %d %d\n", !mip ? "lp" : "mip",
1377 P->dir == GLP_MIN ? "min" : P->dir == GLP_MAX ? "max" : "???",
1378 P->m, P->n, P->nnz), count++;
1379 if (P->name != NULL)
1380 xfprintf(fp, "n p %s\n", P->name), count++;
1381 if (P->obj != NULL)
1382 xfprintf(fp, "n z %s\n", P->obj), count++;
1383 /* write row descriptors */
1384 for (i = 1; i <= P->m; i++)
1385 { row = P->row[i];
1386 if (row->type == GLP_FX && row->lb == 0.0)
1387 goto skip1;
1388 xfprintf(fp, "i %d ", i), count++;
1389 if (row->type == GLP_FR)
1390 xfprintf(fp, "f\n");
1391 else if (row->type == GLP_LO)
1392 xfprintf(fp, "l %.*g\n", DBL_DIG, row->lb);
1393 else if (row->type == GLP_UP)
1394 xfprintf(fp, "u %.*g\n", DBL_DIG, row->ub);
1395 else if (row->type == GLP_DB)
1396 xfprintf(fp, "d %.*g %.*g\n", DBL_DIG, row->lb, DBL_DIG,
1397 row->ub);
1398 else if (row->type == GLP_FX)
1399 xfprintf(fp, "s %.*g\n", DBL_DIG, row->lb);
1400 else
1401 xassert(row != row);
1402 skip1: if (row->name != NULL)
1403 xfprintf(fp, "n i %d %s\n", i, row->name), count++;
1404 }
1405 /* write column descriptors */
1406 for (j = 1; j <= P->n; j++)
1407 { col = P->col[j];
1408 if (!mip && col->type == GLP_LO && col->lb == 0.0)
1409 goto skip2;
1410 if (mip && col->kind == GLP_IV && col->type == GLP_DB &&
1411 col->lb == 0.0 && col->ub == 1.0)
1412 goto skip2;
1413 xfprintf(fp, "j %d ", j), count++;
1414 if (mip)
1415 { if (col->kind == GLP_CV)
1416 xfprintf(fp, "c ");
1417 else if (col->kind == GLP_IV)
1418 xfprintf(fp, "i ");
1419 else
1420 xassert(col != col);
1421 }
1422 if (col->type == GLP_FR)
1423 xfprintf(fp, "f\n");
1424 else if (col->type == GLP_LO)
1425 xfprintf(fp, "l %.*g\n", DBL_DIG, col->lb);
1426 else if (col->type == GLP_UP)
1427 xfprintf(fp, "u %.*g\n", DBL_DIG, col->ub);
1428 else if (col->type == GLP_DB)
1429 xfprintf(fp, "d %.*g %.*g\n", DBL_DIG, col->lb, DBL_DIG,
1430 col->ub);
1431 else if (col->type == GLP_FX)
1432 xfprintf(fp, "s %.*g\n", DBL_DIG, col->lb);
1433 else
1434 xassert(col != col);
1435 skip2: if (col->name != NULL)
1436 xfprintf(fp, "n j %d %s\n", j, col->name), count++;
1437 }
1438 /* write objective coefficient descriptors */
1439 if (P->c0 != 0.0)
1440 xfprintf(fp, "a 0 0 %.*g\n", DBL_DIG, P->c0), count++;
1441 for (j = 1; j <= P->n; j++)
1442 { col = P->col[j];
1443 if (col->coef != 0.0)
1444 xfprintf(fp, "a 0 %d %.*g\n", j, DBL_DIG, col->coef),
1445 count++;
1446 }
1447 /* write constraint coefficient descriptors */
1448 for (i = 1; i <= P->m; i++)
1449 { row = P->row[i];
1450 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1451 xfprintf(fp, "a %d %d %.*g\n", i, aij->col->j, DBL_DIG,
1452 aij->val), count++;
1453 }
1454 /* write end line */
1455 xfprintf(fp, "e o f\n"), count++;
1456 xfflush(fp);
1457 if (xferror(fp))
1458 { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
1459 ret = 1;
1460 goto done;
1461 }
1462 xprintf("%d lines were written\n", count);
1463 ret = 0;
1464 done: if (fp != NULL) xfclose(fp);
1465 return ret;
1466 }
1467
1468 /**********************************************************************/
1469
1470 int glp_read_cnfsat(glp_prob *P, const char *fname)
1471 { /* read CNF-SAT problem data in DIMACS format */
1472 struct csa _csa, *csa = &_csa;
1473 int m, n, i, j, len, neg, rhs, ret = 0, *ind = NULL;
1474 double *val = NULL;
1475 char *map = NULL;
1476 if (P == NULL || P->magic != GLP_PROB_MAGIC)
1477 xerror("glp_read_cnfsat: P = %p; invalid problem object\n",
1478 P);
1479 if (fname == NULL)
1480 xerror("glp_read_cnfsat: fname = %p; invalid parameter\n",
1481 fname);
1482 glp_erase_prob(P);
1483 if (setjmp(csa->jump))
1484 { ret = 1;
1485 goto done;
1486 }
1487 csa->fname = fname;
1488 csa->fp = NULL;
1489 csa->count = 0;
1490 csa->c = '\n';
1491 csa->field[0] = '\0';
1492 csa->empty = csa->nonint = 0;
1493 xprintf("Reading CNF-SAT problem data from `%s'...\n", fname);
1494 csa->fp = xfopen(fname, "r");
1495 if (csa->fp == NULL)
1496 { xprintf("Unable to open `%s' - %s\n", fname, xerrmsg());
1497 longjmp(csa->jump, 1);
1498 }
1499 /* read problem line */
1500 read_designator(csa);
1501 if (strcmp(csa->field, "p") != 0)
1502 error(csa, "problem line missing or invalid");
1503 read_field(csa);
1504 if (strcmp(csa->field, "cnf") != 0)
1505 error(csa, "wrong problem designator; `cnf' expected\n");
1506 read_field(csa);
1507 if (!(str2int(csa->field, &n) == 0 && n >= 0))
1508 error(csa, "number of variables missing or invalid\n");
1509 read_field(csa);
1510 if (!(str2int(csa->field, &m) == 0 && m >= 0))
1511 error(csa, "number of clauses missing or invalid\n");
1512 xprintf("Instance has %d variable%s and %d clause%s\n",
1513 n, n == 1 ? "" : "s", m, m == 1 ? "" : "s");
1514 end_of_line(csa);
1515 if (m > 0)
1516 glp_add_rows(P, m);
1517 if (n > 0)
1518 { glp_add_cols(P, n);
1519 for (j = 1; j <= n; j++)
1520 glp_set_col_kind(P, j, GLP_BV);
1521 }
1522 /* allocate working arrays */
1523 ind = xcalloc(1+n, sizeof(int));
1524 val = xcalloc(1+n, sizeof(double));
1525 map = xcalloc(1+n, sizeof(char));
1526 for (j = 1; j <= n; j++) map[j] = 0;
1527 /* read clauses */
1528 for (i = 1; i <= m; i++)
1529 { /* read i-th clause */
1530 len = 0, rhs = 1;
1531 for (;;)
1532 { /* skip white-space characters */
1533 while (csa->c == ' ' || csa->c == '\n')
1534 read_char(csa);
1535 /* read term */
1536 read_field(csa);
1537 if (str2int(csa->field, &j) != 0)
1538 error(csa, "variable number missing or invalid\n");
1539 if (j > 0)
1540 neg = 0;
1541 else if (j < 0)
1542 neg = 1, j = -j, rhs--;
1543 else
1544 break;
1545 if (!(1 <= j && j <= n))
1546 error(csa, "variable number out of range\n");
1547 if (map[j])
1548 error(csa, "duplicate variable number\n");
1549 len++, ind[len] = j, val[len] = (neg ? -1.0 : +1.0);
1550 map[j] = 1;
1551 }
1552 glp_set_row_bnds(P, i, GLP_LO, (double)rhs, 0.0);
1553 glp_set_mat_row(P, i, len, ind, val);
1554 while (len > 0) map[ind[len--]] = 0;
1555 }
1556 xprintf("%d lines were read\n", csa->count);
1557 /* problem data has been successfully read */
1558 glp_sort_matrix(P);
1559 done: if (csa->fp != NULL) xfclose(csa->fp);
1560 if (ind != NULL) xfree(ind);
1561 if (val != NULL) xfree(val);
1562 if (map != NULL) xfree(map);
1563 if (ret) glp_erase_prob(P);
1564 return ret;
1565 }
1566
1567 /**********************************************************************/
1568
1569 int glp_check_cnfsat(glp_prob *P)
1570 { /* check for CNF-SAT problem instance */
1571 int m = P->m;
1572 int n = P->n;
1573 GLPROW *row;
1574 GLPCOL *col;
1575 GLPAIJ *aij;
1576 int i, j, neg;
1577 if (P == NULL || P->magic != GLP_PROB_MAGIC)
1578 xerror("glp_check_cnfsat: P = %p; invalid problem object\n",
1579 P);
1580 /* check columns */
1581 for (j = 1; j <= n; j++)
1582 { col = P->col[j];
1583 /* the variable should be binary */
1584 if (!(col->kind == GLP_IV && col->type == GLP_DB &&
1585 col->lb == 0.0 && col->ub == 1.0))
1586 return 1;
1587 }
1588 /* objective function should be zero */
1589 if (P->c0 != 0.0)
1590 return 2;
1591 for (j = 1; j <= n; j++)
1592 { col = P->col[j];
1593 if (col->coef != 0.0)
1594 return 3;
1595 }
1596 /* check rows */
1597 for (i = 1; i <= m; i++)
1598 { row = P->row[i];
1599 /* the row should be of ">=" type */
1600 if (row->type != GLP_LO)
1601 return 4;
1602 /* check constraint coefficients */
1603 neg = 0;
1604 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1605 { /* the constraint coefficient should be +1 or -1 */
1606 if (aij->val == +1.0)
1607 ;
1608 else if (aij->val == -1.0)
1609 neg++;
1610 else
1611 return 5;
1612 }
1613 /* the right-hand side should be (1 - neg), where neg is the
1614 number of negative constraint coefficients in the row */
1615 if (row->lb != (double)(1 - neg))
1616 return 6;
1617 }
1618 /* congratulations; this is CNF-SAT */
1619 return 0;
1620 }
1621
1622 /**********************************************************************/
1623
1624 int glp_write_cnfsat(glp_prob *P, const char *fname)
1625 { /* write CNF-SAT problem data in DIMACS format */
1626 XFILE *fp = NULL;
1627 GLPAIJ *aij;
1628 int i, j, len, count = 0, ret;
1629 char s[50];
1630 if (P == NULL || P->magic != GLP_PROB_MAGIC)
1631 xerror("glp_write_cnfsat: P = %p; invalid problem object\n",
1632 P);
1633 if (glp_check_cnfsat(P) != 0)
1634 { xprintf("glp_write_cnfsat: problem object does not encode CNF-"
1635 "SAT instance\n");
1636 ret = 1;
1637 goto done;
1638 }
1639 xprintf("Writing CNF-SAT problem data to `%s'...\n", fname);
1640 fp = xfopen(fname, "w");
1641 if (fp == NULL)
1642 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
1643 ret = 1;
1644 goto done;
1645 }
1646 xfprintf(fp, "c %s\n",
1647 P->name == NULL ? "unknown" : P->name), count++;
1648 xfprintf(fp, "p cnf %d %d\n", P->n, P->m), count++;
1649 for (i = 1; i <= P->m; i++)
1650 { len = 0;
1651 for (aij = P->row[i]->ptr; aij != NULL; aij = aij->r_next)
1652 { j = aij->col->j;
1653 if (aij->val < 0.0) j = -j;
1654 sprintf(s, "%d", j);
1655 if (len > 0 && len + 1 + strlen(s) > 72)
1656 xfprintf(fp, "\n"), count++, len = 0;
1657 xfprintf(fp, "%s%s", len == 0 ? "" : " ", s);
1658 if (len > 0) len++;
1659 len += strlen(s);
1660 }
1661 if (len > 0 && len + 1 + 1 > 72)
1662 xfprintf(fp, "\n"), count++, len = 0;
1663 xfprintf(fp, "%s0\n", len == 0 ? "" : " "), count++;
1664 }
1665 xfprintf(fp, "c eof\n"), count++;
1666 xfflush(fp);
1667 if (xferror(fp))
1668 { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
1669 ret = 1;
1670 goto done;
1671 }
1672 xprintf("%d lines were written\n", count);
1673 ret = 0;
1674 done: if (fp != NULL) xfclose(fp);
1675 return ret;
1676 }
1677
1678 /* eof */