Context Navigation

glpdmx.c @ 9:33de93886c88

subpack-glpk

Last change on this file since 9:33de93886c88 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 12 years ago
Import GLPK 4.47
File size: 56.5 KB

Line
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 */

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: lemon-project-template-glpk/deps/glpk/src/glpdmx.c @ 9:33de93886c88

Download in other formats: