1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpapi15.c	Sun Nov 06 20:59:10 2011 +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, 2011 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 */