lemon-project-template-glpk

annotate deps/glpk/src/glpdmx.c @ 11:4fc6ad2fb8a6

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