1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi15.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,609 @@
1.4 +/* glpapi15.c (basic graph and network routines) */
1.5 +
1.6 +/***********************************************************************
1.7 +* This code is part of GLPK (GNU Linear Programming Kit).
1.8 +*
1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
1.10 +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
1.12 +* E-mail: <mao@gnu.org>.
1.13 +*
1.14 +* GLPK is free software: you can redistribute it and/or modify it
1.15 +* under the terms of the GNU General Public License as published by
1.16 +* the Free Software Foundation, either version 3 of the License, or
1.17 +* (at your option) any later version.
1.18 +*
1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT
1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1.22 +* License for more details.
1.23 +*
1.24 +* You should have received a copy of the GNU General Public License
1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
1.26 +***********************************************************************/
1.27 +
1.28 +#include "glpapi.h"
1.29 +
1.30 +/* CAUTION: DO NOT CHANGE THE LIMITS BELOW */
1.31 +
1.32 +#define NV_MAX 100000000 /* = 100*10^6 */
1.33 +/* maximal number of vertices in the graph */
1.34 +
1.35 +#define NA_MAX 500000000 /* = 500*10^6 */
1.36 +/* maximal number of arcs in the graph */
1.37 +
1.38 +/***********************************************************************
1.39 +* NAME
1.40 +*
1.41 +* glp_create_graph - create graph
1.42 +*
1.43 +* SYNOPSIS
1.44 +*
1.45 +* glp_graph *glp_create_graph(int v_size, int a_size);
1.46 +*
1.47 +* DESCRIPTION
1.48 +*
1.49 +* The routine creates a new graph, which initially is empty, i.e. has
1.50 +* no vertices and arcs.
1.51 +*
1.52 +* The parameter v_size specifies the size of data associated with each
1.53 +* vertex of the graph (0 to 256 bytes).
1.54 +*
1.55 +* The parameter a_size specifies the size of data associated with each
1.56 +* arc of the graph (0 to 256 bytes).
1.57 +*
1.58 +* RETURNS
1.59 +*
1.60 +* The routine returns a pointer to the graph created. */
1.61 +
1.62 +static void create_graph(glp_graph *G, int v_size, int a_size)
1.63 +{ G->pool = dmp_create_pool();
1.64 + G->name = NULL;
1.65 + G->nv_max = 50;
1.66 + G->nv = G->na = 0;
1.67 + G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));
1.68 + G->index = NULL;
1.69 + G->v_size = v_size;
1.70 + G->a_size = a_size;
1.71 + return;
1.72 +}
1.73 +
1.74 +glp_graph *glp_create_graph(int v_size, int a_size)
1.75 +{ glp_graph *G;
1.76 + if (!(0 <= v_size && v_size <= 256))
1.77 + xerror("glp_create_graph: v_size = %d; invalid size of vertex "
1.78 + "data\n", v_size);
1.79 + if (!(0 <= a_size && a_size <= 256))
1.80 + xerror("glp_create_graph: a_size = %d; invalid size of arc dat"
1.81 + "a\n", a_size);
1.82 + G = xmalloc(sizeof(glp_graph));
1.83 + create_graph(G, v_size, a_size);
1.84 + return G;
1.85 +}
1.86 +
1.87 +/***********************************************************************
1.88 +* NAME
1.89 +*
1.90 +* glp_set_graph_name - assign (change) graph name
1.91 +*
1.92 +* SYNOPSIS
1.93 +*
1.94 +* void glp_set_graph_name(glp_graph *G, const char *name);
1.95 +*
1.96 +* DESCRIPTION
1.97 +*
1.98 +* The routine glp_set_graph_name assigns a symbolic name specified by
1.99 +* the character string name (1 to 255 chars) to the graph.
1.100 +*
1.101 +* If the parameter name is NULL or an empty string, the routine erases
1.102 +* the existing symbolic name of the graph. */
1.103 +
1.104 +void glp_set_graph_name(glp_graph *G, const char *name)
1.105 +{ if (G->name != NULL)
1.106 + { dmp_free_atom(G->pool, G->name, strlen(G->name)+1);
1.107 + G->name = NULL;
1.108 + }
1.109 + if (!(name == NULL || name[0] == '\0'))
1.110 + { int j;
1.111 + for (j = 0; name[j] != '\0'; j++)
1.112 + { if (j == 256)
1.113 + xerror("glp_set_graph_name: graph name too long\n");
1.114 + if (iscntrl((unsigned char)name[j]))
1.115 + xerror("glp_set_graph_name: graph name contains invalid "
1.116 + "character(s)\n");
1.117 + }
1.118 + G->name = dmp_get_atom(G->pool, strlen(name)+1);
1.119 + strcpy(G->name, name);
1.120 + }
1.121 + return;
1.122 +}
1.123 +
1.124 +/***********************************************************************
1.125 +* NAME
1.126 +*
1.127 +* glp_add_vertices - add new vertices to graph
1.128 +*
1.129 +* SYNOPSIS
1.130 +*
1.131 +* int glp_add_vertices(glp_graph *G, int nadd);
1.132 +*
1.133 +* DESCRIPTION
1.134 +*
1.135 +* The routine glp_add_vertices adds nadd vertices to the specified
1.136 +* graph. New vertices are always added to the end of the vertex list,
1.137 +* so ordinal numbers of existing vertices remain unchanged.
1.138 +*
1.139 +* Being added each new vertex is isolated (has no incident arcs).
1.140 +*
1.141 +* RETURNS
1.142 +*
1.143 +* The routine glp_add_vertices returns an ordinal number of the first
1.144 +* new vertex added to the graph. */
1.145 +
1.146 +int glp_add_vertices(glp_graph *G, int nadd)
1.147 +{ int i, nv_new;
1.148 + if (nadd < 1)
1.149 + xerror("glp_add_vertices: nadd = %d; invalid number of vertice"
1.150 + "s\n", nadd);
1.151 + if (nadd > NV_MAX - G->nv)
1.152 + xerror("glp_add_vertices: nadd = %d; too many vertices\n",
1.153 + nadd);
1.154 + /* determine new number of vertices */
1.155 + nv_new = G->nv + nadd;
1.156 + /* increase the room, if necessary */
1.157 + if (G->nv_max < nv_new)
1.158 + { glp_vertex **save = G->v;
1.159 + while (G->nv_max < nv_new)
1.160 + { G->nv_max += G->nv_max;
1.161 + xassert(G->nv_max > 0);
1.162 + }
1.163 + G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));
1.164 + memcpy(&G->v[1], &save[1], G->nv * sizeof(glp_vertex *));
1.165 + xfree(save);
1.166 + }
1.167 + /* add new vertices to the end of the vertex list */
1.168 + for (i = G->nv+1; i <= nv_new; i++)
1.169 + { glp_vertex *v;
1.170 + G->v[i] = v = dmp_get_atom(G->pool, sizeof(glp_vertex));
1.171 + v->i = i;
1.172 + v->name = NULL;
1.173 + v->entry = NULL;
1.174 + if (G->v_size == 0)
1.175 + v->data = NULL;
1.176 + else
1.177 + { v->data = dmp_get_atom(G->pool, G->v_size);
1.178 + memset(v->data, 0, G->v_size);
1.179 + }
1.180 + v->temp = NULL;
1.181 + v->in = v->out = NULL;
1.182 + }
1.183 + /* set new number of vertices */
1.184 + G->nv = nv_new;
1.185 + /* return the ordinal number of the first vertex added */
1.186 + return nv_new - nadd + 1;
1.187 +}
1.188 +
1.189 +/**********************************************************************/
1.190 +
1.191 +void glp_set_vertex_name(glp_graph *G, int i, const char *name)
1.192 +{ /* assign (change) vertex name */
1.193 + glp_vertex *v;
1.194 + if (!(1 <= i && i <= G->nv))
1.195 + xerror("glp_set_vertex_name: i = %d; vertex number out of rang"
1.196 + "e\n", i);
1.197 + v = G->v[i];
1.198 + if (v->name != NULL)
1.199 + { if (v->entry != NULL)
1.200 + { xassert(G->index != NULL);
1.201 + avl_delete_node(G->index, v->entry);
1.202 + v->entry = NULL;
1.203 + }
1.204 + dmp_free_atom(G->pool, v->name, strlen(v->name)+1);
1.205 + v->name = NULL;
1.206 + }
1.207 + if (!(name == NULL || name[0] == '\0'))
1.208 + { int k;
1.209 + for (k = 0; name[k] != '\0'; k++)
1.210 + { if (k == 256)
1.211 + xerror("glp_set_vertex_name: i = %d; vertex name too lon"
1.212 + "g\n", i);
1.213 + if (iscntrl((unsigned char)name[k]))
1.214 + xerror("glp_set_vertex_name: i = %d; vertex name contain"
1.215 + "s invalid character(s)\n", i);
1.216 + }
1.217 + v->name = dmp_get_atom(G->pool, strlen(name)+1);
1.218 + strcpy(v->name, name);
1.219 + if (G->index != NULL)
1.220 + { xassert(v->entry == NULL);
1.221 + v->entry = avl_insert_node(G->index, v->name);
1.222 + avl_set_node_link(v->entry, v);
1.223 + }
1.224 + }
1.225 + return;
1.226 +}
1.227 +
1.228 +/***********************************************************************
1.229 +* NAME
1.230 +*
1.231 +* glp_add_arc - add new arc to graph
1.232 +*
1.233 +* SYNOPSIS
1.234 +*
1.235 +* glp_arc *glp_add_arc(glp_graph *G, int i, int j);
1.236 +*
1.237 +* DESCRIPTION
1.238 +*
1.239 +* The routine glp_add_arc adds a new arc to the specified graph.
1.240 +*
1.241 +* The parameters i and j specify the ordinal numbers of, resp., tail
1.242 +* and head vertices of the arc. Note that self-loops and multiple arcs
1.243 +* are allowed.
1.244 +*
1.245 +* RETURNS
1.246 +*
1.247 +* The routine glp_add_arc returns a pointer to the arc added. */
1.248 +
1.249 +glp_arc *glp_add_arc(glp_graph *G, int i, int j)
1.250 +{ glp_arc *a;
1.251 + if (!(1 <= i && i <= G->nv))
1.252 + xerror("glp_add_arc: i = %d; tail vertex number out of range\n"
1.253 + , i);
1.254 + if (!(1 <= j && j <= G->nv))
1.255 + xerror("glp_add_arc: j = %d; head vertex number out of range\n"
1.256 + , j);
1.257 + if (G->na == NA_MAX)
1.258 + xerror("glp_add_arc: too many arcs\n");
1.259 + a = dmp_get_atom(G->pool, sizeof(glp_arc));
1.260 + a->tail = G->v[i];
1.261 + a->head = G->v[j];
1.262 + if (G->a_size == 0)
1.263 + a->data = NULL;
1.264 + else
1.265 + { a->data = dmp_get_atom(G->pool, G->a_size);
1.266 + memset(a->data, 0, G->a_size);
1.267 + }
1.268 + a->temp = NULL;
1.269 + a->t_prev = NULL;
1.270 + a->t_next = G->v[i]->out;
1.271 + if (a->t_next != NULL) a->t_next->t_prev = a;
1.272 + a->h_prev = NULL;
1.273 + a->h_next = G->v[j]->in;
1.274 + if (a->h_next != NULL) a->h_next->h_prev = a;
1.275 + G->v[i]->out = G->v[j]->in = a;
1.276 + G->na++;
1.277 + return a;
1.278 +}
1.279 +
1.280 +/***********************************************************************
1.281 +* NAME
1.282 +*
1.283 +* glp_del_vertices - delete vertices from graph
1.284 +*
1.285 +* SYNOPSIS
1.286 +*
1.287 +* void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
1.288 +*
1.289 +* DESCRIPTION
1.290 +*
1.291 +* The routine glp_del_vertices deletes vertices along with all
1.292 +* incident arcs from the specified graph. Ordinal numbers of vertices
1.293 +* to be deleted should be placed in locations num[1], ..., num[ndel],
1.294 +* ndel > 0.
1.295 +*
1.296 +* Note that deleting vertices involves changing ordinal numbers of
1.297 +* other vertices remaining in the graph. New ordinal numbers of the
1.298 +* remaining vertices are assigned under the assumption that the
1.299 +* original order of vertices is not changed. */
1.300 +
1.301 +void glp_del_vertices(glp_graph *G, int ndel, const int num[])
1.302 +{ glp_vertex *v;
1.303 + int i, k, nv_new;
1.304 + /* scan the list of vertices to be deleted */
1.305 + if (!(1 <= ndel && ndel <= G->nv))
1.306 + xerror("glp_del_vertices: ndel = %d; invalid number of vertice"
1.307 + "s\n", ndel);
1.308 + for (k = 1; k <= ndel; k++)
1.309 + { /* take the number of vertex to be deleted */
1.310 + i = num[k];
1.311 + /* obtain pointer to i-th vertex */
1.312 + if (!(1 <= i && i <= G->nv))
1.313 + xerror("glp_del_vertices: num[%d] = %d; vertex number out o"
1.314 + "f range\n", k, i);
1.315 + v = G->v[i];
1.316 + /* check that the vertex is not marked yet */
1.317 + if (v->i == 0)
1.318 + xerror("glp_del_vertices: num[%d] = %d; duplicate vertex nu"
1.319 + "mbers not allowed\n", k, i);
1.320 + /* erase symbolic name assigned to the vertex */
1.321 + glp_set_vertex_name(G, i, NULL);
1.322 + xassert(v->name == NULL);
1.323 + xassert(v->entry == NULL);
1.324 + /* free vertex data, if allocated */
1.325 + if (v->data != NULL)
1.326 + dmp_free_atom(G->pool, v->data, G->v_size);
1.327 + /* delete all incoming arcs */
1.328 + while (v->in != NULL)
1.329 + glp_del_arc(G, v->in);
1.330 + /* delete all outgoing arcs */
1.331 + while (v->out != NULL)
1.332 + glp_del_arc(G, v->out);
1.333 + /* mark the vertex to be deleted */
1.334 + v->i = 0;
1.335 + }
1.336 + /* delete all marked vertices from the vertex list */
1.337 + nv_new = 0;
1.338 + for (i = 1; i <= G->nv; i++)
1.339 + { /* obtain pointer to i-th vertex */
1.340 + v = G->v[i];
1.341 + /* check if the vertex is marked */
1.342 + if (v->i == 0)
1.343 + { /* it is marked, delete it */
1.344 + dmp_free_atom(G->pool, v, sizeof(glp_vertex));
1.345 + }
1.346 + else
1.347 + { /* it is not marked, keep it */
1.348 + v->i = ++nv_new;
1.349 + G->v[v->i] = v;
1.350 + }
1.351 + }
1.352 + /* set new number of vertices in the graph */
1.353 + G->nv = nv_new;
1.354 + return;
1.355 +}
1.356 +
1.357 +/***********************************************************************
1.358 +* NAME
1.359 +*
1.360 +* glp_del_arc - delete arc from graph
1.361 +*
1.362 +* SYNOPSIS
1.363 +*
1.364 +* void glp_del_arc(glp_graph *G, glp_arc *a);
1.365 +*
1.366 +* DESCRIPTION
1.367 +*
1.368 +* The routine glp_del_arc deletes an arc from the specified graph.
1.369 +* The arc to be deleted must exist. */
1.370 +
1.371 +void glp_del_arc(glp_graph *G, glp_arc *a)
1.372 +{ /* some sanity checks */
1.373 + xassert(G->na > 0);
1.374 + xassert(1 <= a->tail->i && a->tail->i <= G->nv);
1.375 + xassert(a->tail == G->v[a->tail->i]);
1.376 + xassert(1 <= a->head->i && a->head->i <= G->nv);
1.377 + xassert(a->head == G->v[a->head->i]);
1.378 + /* remove the arc from the list of incoming arcs */
1.379 + if (a->h_prev == NULL)
1.380 + a->head->in = a->h_next;
1.381 + else
1.382 + a->h_prev->h_next = a->h_next;
1.383 + if (a->h_next == NULL)
1.384 + ;
1.385 + else
1.386 + a->h_next->h_prev = a->h_prev;
1.387 + /* remove the arc from the list of outgoing arcs */
1.388 + if (a->t_prev == NULL)
1.389 + a->tail->out = a->t_next;
1.390 + else
1.391 + a->t_prev->t_next = a->t_next;
1.392 + if (a->t_next == NULL)
1.393 + ;
1.394 + else
1.395 + a->t_next->t_prev = a->t_prev;
1.396 + /* free arc data, if allocated */
1.397 + if (a->data != NULL)
1.398 + dmp_free_atom(G->pool, a->data, G->a_size);
1.399 + /* delete the arc from the graph */
1.400 + dmp_free_atom(G->pool, a, sizeof(glp_arc));
1.401 + G->na--;
1.402 + return;
1.403 +}
1.404 +
1.405 +/***********************************************************************
1.406 +* NAME
1.407 +*
1.408 +* glp_erase_graph - erase graph content
1.409 +*
1.410 +* SYNOPSIS
1.411 +*
1.412 +* void glp_erase_graph(glp_graph *G, int v_size, int a_size);
1.413 +*
1.414 +* DESCRIPTION
1.415 +*
1.416 +* The routine glp_erase_graph erases the content of the specified
1.417 +* graph. The effect of this operation is the same as if the graph
1.418 +* would be deleted with the routine glp_delete_graph and then created
1.419 +* anew with the routine glp_create_graph, with exception that the
1.420 +* handle (pointer) to the graph remains valid. */
1.421 +
1.422 +static void delete_graph(glp_graph *G)
1.423 +{ dmp_delete_pool(G->pool);
1.424 + xfree(G->v);
1.425 + if (G->index != NULL) avl_delete_tree(G->index);
1.426 + return;
1.427 +}
1.428 +
1.429 +void glp_erase_graph(glp_graph *G, int v_size, int a_size)
1.430 +{ if (!(0 <= v_size && v_size <= 256))
1.431 + xerror("glp_erase_graph: v_size = %d; invalid size of vertex d"
1.432 + "ata\n", v_size);
1.433 + if (!(0 <= a_size && a_size <= 256))
1.434 + xerror("glp_erase_graph: a_size = %d; invalid size of arc data"
1.435 + "\n", a_size);
1.436 + delete_graph(G);
1.437 + create_graph(G, v_size, a_size);
1.438 + return;
1.439 +}
1.440 +
1.441 +/***********************************************************************
1.442 +* NAME
1.443 +*
1.444 +* glp_delete_graph - delete graph
1.445 +*
1.446 +* SYNOPSIS
1.447 +*
1.448 +* void glp_delete_graph(glp_graph *G);
1.449 +*
1.450 +* DESCRIPTION
1.451 +*
1.452 +* The routine glp_delete_graph deletes the specified graph and frees
1.453 +* all the memory allocated to this program object. */
1.454 +
1.455 +void glp_delete_graph(glp_graph *G)
1.456 +{ delete_graph(G);
1.457 + xfree(G);
1.458 + return;
1.459 +}
1.460 +
1.461 +/**********************************************************************/
1.462 +
1.463 +void glp_create_v_index(glp_graph *G)
1.464 +{ /* create vertex name index */
1.465 + glp_vertex *v;
1.466 + int i;
1.467 + if (G->index == NULL)
1.468 + { G->index = avl_create_tree(avl_strcmp, NULL);
1.469 + for (i = 1; i <= G->nv; i++)
1.470 + { v = G->v[i];
1.471 + xassert(v->entry == NULL);
1.472 + if (v->name != NULL)
1.473 + { v->entry = avl_insert_node(G->index, v->name);
1.474 + avl_set_node_link(v->entry, v);
1.475 + }
1.476 + }
1.477 + }
1.478 + return;
1.479 +}
1.480 +
1.481 +int glp_find_vertex(glp_graph *G, const char *name)
1.482 +{ /* find vertex by its name */
1.483 + AVLNODE *node;
1.484 + int i = 0;
1.485 + if (G->index == NULL)
1.486 + xerror("glp_find_vertex: vertex name index does not exist\n");
1.487 + if (!(name == NULL || name[0] == '\0' || strlen(name) > 255))
1.488 + { node = avl_find_node(G->index, name);
1.489 + if (node != NULL)
1.490 + i = ((glp_vertex *)avl_get_node_link(node))->i;
1.491 + }
1.492 + return i;
1.493 +}
1.494 +
1.495 +void glp_delete_v_index(glp_graph *G)
1.496 +{ /* delete vertex name index */
1.497 + int i;
1.498 + if (G->index != NULL)
1.499 + { avl_delete_tree(G->index), G->index = NULL;
1.500 + for (i = 1; i <= G->nv; i++) G->v[i]->entry = NULL;
1.501 + }
1.502 + return;
1.503 +}
1.504 +
1.505 +/***********************************************************************
1.506 +* NAME
1.507 +*
1.508 +* glp_read_graph - read graph from plain text file
1.509 +*
1.510 +* SYNOPSIS
1.511 +*
1.512 +* int glp_read_graph(glp_graph *G, const char *fname);
1.513 +*
1.514 +* DESCRIPTION
1.515 +*
1.516 +* The routine glp_read_graph reads a graph from a plain text file.
1.517 +*
1.518 +* RETURNS
1.519 +*
1.520 +* If the operation was successful, the routine returns zero. Otherwise
1.521 +* it prints an error message and returns non-zero. */
1.522 +
1.523 +int glp_read_graph(glp_graph *G, const char *fname)
1.524 +{ glp_data *data;
1.525 + jmp_buf jump;
1.526 + int nv, na, i, j, k, ret;
1.527 + glp_erase_graph(G, G->v_size, G->a_size);
1.528 + xprintf("Reading graph from `%s'...\n", fname);
1.529 + data = glp_sdf_open_file(fname);
1.530 + if (data == NULL)
1.531 + { ret = 1;
1.532 + goto done;
1.533 + }
1.534 + if (setjmp(jump))
1.535 + { ret = 1;
1.536 + goto done;
1.537 + }
1.538 + glp_sdf_set_jump(data, jump);
1.539 + nv = glp_sdf_read_int(data);
1.540 + if (nv < 0)
1.541 + glp_sdf_error(data, "invalid number of vertices\n");
1.542 + na = glp_sdf_read_int(data);
1.543 + if (na < 0)
1.544 + glp_sdf_error(data, "invalid number of arcs\n");
1.545 + xprintf("Graph has %d vert%s and %d arc%s\n",
1.546 + nv, nv == 1 ? "ex" : "ices", na, na == 1 ? "" : "s");
1.547 + if (nv > 0) glp_add_vertices(G, nv);
1.548 + for (k = 1; k <= na; k++)
1.549 + { i = glp_sdf_read_int(data);
1.550 + if (!(1 <= i && i <= nv))
1.551 + glp_sdf_error(data, "tail vertex number out of range\n");
1.552 + j = glp_sdf_read_int(data);
1.553 + if (!(1 <= j && j <= nv))
1.554 + glp_sdf_error(data, "head vertex number out of range\n");
1.555 + glp_add_arc(G, i, j);
1.556 + }
1.557 + xprintf("%d lines were read\n", glp_sdf_line(data));
1.558 + ret = 0;
1.559 +done: if (data != NULL) glp_sdf_close_file(data);
1.560 + return ret;
1.561 +}
1.562 +
1.563 +/***********************************************************************
1.564 +* NAME
1.565 +*
1.566 +* glp_write_graph - write graph to plain text file
1.567 +*
1.568 +* SYNOPSIS
1.569 +*
1.570 +* int glp_write_graph(glp_graph *G, const char *fname).
1.571 +*
1.572 +* DESCRIPTION
1.573 +*
1.574 +* The routine glp_write_graph writes the specified graph to a plain
1.575 +* text file.
1.576 +*
1.577 +* RETURNS
1.578 +*
1.579 +* If the operation was successful, the routine returns zero. Otherwise
1.580 +* it prints an error message and returns non-zero. */
1.581 +
1.582 +int glp_write_graph(glp_graph *G, const char *fname)
1.583 +{ XFILE *fp;
1.584 + glp_vertex *v;
1.585 + glp_arc *a;
1.586 + int i, count, ret;
1.587 + xprintf("Writing graph to `%s'...\n", fname);
1.588 + fp = xfopen(fname, "w"), count = 0;
1.589 + if (fp == NULL)
1.590 + { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
1.591 + ret = 1;
1.592 + goto done;
1.593 + }
1.594 + xfprintf(fp, "%d %d\n", G->nv, G->na), count++;
1.595 + for (i = 1; i <= G->nv; i++)
1.596 + { v = G->v[i];
1.597 + for (a = v->out; a != NULL; a = a->t_next)
1.598 + xfprintf(fp, "%d %d\n", a->tail->i, a->head->i), count++;
1.599 + }
1.600 + xfflush(fp);
1.601 + if (xferror(fp))
1.602 + { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());
1.603 + ret = 1;
1.604 + goto done;
1.605 + }
1.606 + xprintf("%d lines were written\n", count);
1.607 + ret = 0;
1.608 +done: if (fp != NULL) xfclose(fp);
1.609 + return ret;
1.610 +}
1.611 +
1.612 +/* eof */