lemon-project-template-glpk

annotate deps/glpk/src/glpapi15.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpapi15.c (basic graph and network routines) */
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 #include "glpapi.h"
alpar@9 26
alpar@9 27 /* CAUTION: DO NOT CHANGE THE LIMITS BELOW */
alpar@9 28
alpar@9 29 #define NV_MAX 100000000 /* = 100*10^6 */
alpar@9 30 /* maximal number of vertices in the graph */
alpar@9 31
alpar@9 32 #define NA_MAX 500000000 /* = 500*10^6 */
alpar@9 33 /* maximal number of arcs in the graph */
alpar@9 34
alpar@9 35 /***********************************************************************
alpar@9 36 * NAME
alpar@9 37 *
alpar@9 38 * glp_create_graph - create graph
alpar@9 39 *
alpar@9 40 * SYNOPSIS
alpar@9 41 *
alpar@9 42 * glp_graph *glp_create_graph(int v_size, int a_size);
alpar@9 43 *
alpar@9 44 * DESCRIPTION
alpar@9 45 *
alpar@9 46 * The routine creates a new graph, which initially is empty, i.e. has
alpar@9 47 * no vertices and arcs.
alpar@9 48 *
alpar@9 49 * The parameter v_size specifies the size of data associated with each
alpar@9 50 * vertex of the graph (0 to 256 bytes).
alpar@9 51 *
alpar@9 52 * The parameter a_size specifies the size of data associated with each
alpar@9 53 * arc of the graph (0 to 256 bytes).
alpar@9 54 *
alpar@9 55 * RETURNS
alpar@9 56 *
alpar@9 57 * The routine returns a pointer to the graph created. */
alpar@9 58
alpar@9 59 static void create_graph(glp_graph *G, int v_size, int a_size)
alpar@9 60 { G->pool = dmp_create_pool();
alpar@9 61 G->name = NULL;
alpar@9 62 G->nv_max = 50;
alpar@9 63 G->nv = G->na = 0;
alpar@9 64 G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));
alpar@9 65 G->index = NULL;
alpar@9 66 G->v_size = v_size;
alpar@9 67 G->a_size = a_size;
alpar@9 68 return;
alpar@9 69 }
alpar@9 70
alpar@9 71 glp_graph *glp_create_graph(int v_size, int a_size)
alpar@9 72 { glp_graph *G;
alpar@9 73 if (!(0 <= v_size && v_size <= 256))
alpar@9 74 xerror("glp_create_graph: v_size = %d; invalid size of vertex "
alpar@9 75 "data\n", v_size);
alpar@9 76 if (!(0 <= a_size && a_size <= 256))
alpar@9 77 xerror("glp_create_graph: a_size = %d; invalid size of arc dat"
alpar@9 78 "a\n", a_size);
alpar@9 79 G = xmalloc(sizeof(glp_graph));
alpar@9 80 create_graph(G, v_size, a_size);
alpar@9 81 return G;
alpar@9 82 }
alpar@9 83
alpar@9 84 /***********************************************************************
alpar@9 85 * NAME
alpar@9 86 *
alpar@9 87 * glp_set_graph_name - assign (change) graph name
alpar@9 88 *
alpar@9 89 * SYNOPSIS
alpar@9 90 *
alpar@9 91 * void glp_set_graph_name(glp_graph *G, const char *name);
alpar@9 92 *
alpar@9 93 * DESCRIPTION
alpar@9 94 *
alpar@9 95 * The routine glp_set_graph_name assigns a symbolic name specified by
alpar@9 96 * the character string name (1 to 255 chars) to the graph.
alpar@9 97 *
alpar@9 98 * If the parameter name is NULL or an empty string, the routine erases
alpar@9 99 * the existing symbolic name of the graph. */
alpar@9 100
alpar@9 101 void glp_set_graph_name(glp_graph *G, const char *name)
alpar@9 102 { if (G->name != NULL)
alpar@9 103 { dmp_free_atom(G->pool, G->name, strlen(G->name)+1);
alpar@9 104 G->name = NULL;
alpar@9 105 }
alpar@9 106 if (!(name == NULL || name[0] == '\0'))
alpar@9 107 { int j;
alpar@9 108 for (j = 0; name[j] != '\0'; j++)
alpar@9 109 { if (j == 256)
alpar@9 110 xerror("glp_set_graph_name: graph name too long\n");
alpar@9 111 if (iscntrl((unsigned char)name[j]))
alpar@9 112 xerror("glp_set_graph_name: graph name contains invalid "
alpar@9 113 "character(s)\n");
alpar@9 114 }
alpar@9 115 G->name = dmp_get_atom(G->pool, strlen(name)+1);
alpar@9 116 strcpy(G->name, name);
alpar@9 117 }
alpar@9 118 return;
alpar@9 119 }
alpar@9 120
alpar@9 121 /***********************************************************************
alpar@9 122 * NAME
alpar@9 123 *
alpar@9 124 * glp_add_vertices - add new vertices to graph
alpar@9 125 *
alpar@9 126 * SYNOPSIS
alpar@9 127 *
alpar@9 128 * int glp_add_vertices(glp_graph *G, int nadd);
alpar@9 129 *
alpar@9 130 * DESCRIPTION
alpar@9 131 *
alpar@9 132 * The routine glp_add_vertices adds nadd vertices to the specified
alpar@9 133 * graph. New vertices are always added to the end of the vertex list,
alpar@9 134 * so ordinal numbers of existing vertices remain unchanged.
alpar@9 135 *
alpar@9 136 * Being added each new vertex is isolated (has no incident arcs).
alpar@9 137 *
alpar@9 138 * RETURNS
alpar@9 139 *
alpar@9 140 * The routine glp_add_vertices returns an ordinal number of the first
alpar@9 141 * new vertex added to the graph. */
alpar@9 142
alpar@9 143 int glp_add_vertices(glp_graph *G, int nadd)
alpar@9 144 { int i, nv_new;
alpar@9 145 if (nadd < 1)
alpar@9 146 xerror("glp_add_vertices: nadd = %d; invalid number of vertice"
alpar@9 147 "s\n", nadd);
alpar@9 148 if (nadd > NV_MAX - G->nv)
alpar@9 149 xerror("glp_add_vertices: nadd = %d; too many vertices\n",
alpar@9 150 nadd);
alpar@9 151 /* determine new number of vertices */
alpar@9 152 nv_new = G->nv + nadd;
alpar@9 153 /* increase the room, if necessary */
alpar@9 154 if (G->nv_max < nv_new)
alpar@9 155 { glp_vertex **save = G->v;
alpar@9 156 while (G->nv_max < nv_new)
alpar@9 157 { G->nv_max += G->nv_max;
alpar@9 158 xassert(G->nv_max > 0);
alpar@9 159 }
alpar@9 160 G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));
alpar@9 161 memcpy(&G->v[1], &save[1], G->nv * sizeof(glp_vertex *));
alpar@9 162 xfree(save);
alpar@9 163 }
alpar@9 164 /* add new vertices to the end of the vertex list */
alpar@9 165 for (i = G->nv+1; i <= nv_new; i++)
alpar@9 166 { glp_vertex *v;
alpar@9 167 G->v[i] = v = dmp_get_atom(G->pool, sizeof(glp_vertex));
alpar@9 168 v->i = i;
alpar@9 169 v->name = NULL;
alpar@9 170 v->entry = NULL;
alpar@9 171 if (G->v_size == 0)
alpar@9 172 v->data = NULL;
alpar@9 173 else
alpar@9 174 { v->data = dmp_get_atom(G->pool, G->v_size);
alpar@9 175 memset(v->data, 0, G->v_size);
alpar@9 176 }
alpar@9 177 v->temp = NULL;
alpar@9 178 v->in = v->out = NULL;
alpar@9 179 }
alpar@9 180 /* set new number of vertices */
alpar@9 181 G->nv = nv_new;
alpar@9 182 /* return the ordinal number of the first vertex added */
alpar@9 183 return nv_new - nadd + 1;
alpar@9 184 }
alpar@9 185
alpar@9 186 /**********************************************************************/
alpar@9 187
alpar@9 188 void glp_set_vertex_name(glp_graph *G, int i, const char *name)
alpar@9 189 { /* assign (change) vertex name */
alpar@9 190 glp_vertex *v;
alpar@9 191 if (!(1 <= i && i <= G->nv))
alpar@9 192 xerror("glp_set_vertex_name: i = %d; vertex number out of rang"
alpar@9 193 "e\n", i);
alpar@9 194 v = G->v[i];
alpar@9 195 if (v->name != NULL)
alpar@9 196 { if (v->entry != NULL)
alpar@9 197 { xassert(G->index != NULL);
alpar@9 198 avl_delete_node(G->index, v->entry);
alpar@9 199 v->entry = NULL;
alpar@9 200 }
alpar@9 201 dmp_free_atom(G->pool, v->name, strlen(v->name)+1);
alpar@9 202 v->name = NULL;
alpar@9 203 }
alpar@9 204 if (!(name == NULL || name[0] == '\0'))
alpar@9 205 { int k;
alpar@9 206 for (k = 0; name[k] != '\0'; k++)
alpar@9 207 { if (k == 256)
alpar@9 208 xerror("glp_set_vertex_name: i = %d; vertex name too lon"
alpar@9 209 "g\n", i);
alpar@9 210 if (iscntrl((unsigned char)name[k]))
alpar@9 211 xerror("glp_set_vertex_name: i = %d; vertex name contain"
alpar@9 212 "s invalid character(s)\n", i);
alpar@9 213 }
alpar@9 214 v->name = dmp_get_atom(G->pool, strlen(name)+1);
alpar@9 215 strcpy(v->name, name);
alpar@9 216 if (G->index != NULL)
alpar@9 217 { xassert(v->entry == NULL);
alpar@9 218 v->entry = avl_insert_node(G->index, v->name);
alpar@9 219 avl_set_node_link(v->entry, v);
alpar@9 220 }
alpar@9 221 }
alpar@9 222 return;
alpar@9 223 }
alpar@9 224
alpar@9 225 /***********************************************************************
alpar@9 226 * NAME
alpar@9 227 *
alpar@9 228 * glp_add_arc - add new arc to graph
alpar@9 229 *
alpar@9 230 * SYNOPSIS
alpar@9 231 *
alpar@9 232 * glp_arc *glp_add_arc(glp_graph *G, int i, int j);
alpar@9 233 *
alpar@9 234 * DESCRIPTION
alpar@9 235 *
alpar@9 236 * The routine glp_add_arc adds a new arc to the specified graph.
alpar@9 237 *
alpar@9 238 * The parameters i and j specify the ordinal numbers of, resp., tail
alpar@9 239 * and head vertices of the arc. Note that self-loops and multiple arcs
alpar@9 240 * are allowed.
alpar@9 241 *
alpar@9 242 * RETURNS
alpar@9 243 *
alpar@9 244 * The routine glp_add_arc returns a pointer to the arc added. */
alpar@9 245
alpar@9 246 glp_arc *glp_add_arc(glp_graph *G, int i, int j)
alpar@9 247 { glp_arc *a;
alpar@9 248 if (!(1 <= i && i <= G->nv))
alpar@9 249 xerror("glp_add_arc: i = %d; tail vertex number out of range\n"
alpar@9 250 , i);
alpar@9 251 if (!(1 <= j && j <= G->nv))
alpar@9 252 xerror("glp_add_arc: j = %d; head vertex number out of range\n"
alpar@9 253 , j);
alpar@9 254 if (G->na == NA_MAX)
alpar@9 255 xerror("glp_add_arc: too many arcs\n");
alpar@9 256 a = dmp_get_atom(G->pool, sizeof(glp_arc));
alpar@9 257 a->tail = G->v[i];
alpar@9 258 a->head = G->v[j];
alpar@9 259 if (G->a_size == 0)
alpar@9 260 a->data = NULL;
alpar@9 261 else
alpar@9 262 { a->data = dmp_get_atom(G->pool, G->a_size);
alpar@9 263 memset(a->data, 0, G->a_size);
alpar@9 264 }
alpar@9 265 a->temp = NULL;
alpar@9 266 a->t_prev = NULL;
alpar@9 267 a->t_next = G->v[i]->out;
alpar@9 268 if (a->t_next != NULL) a->t_next->t_prev = a;
alpar@9 269 a->h_prev = NULL;
alpar@9 270 a->h_next = G->v[j]->in;
alpar@9 271 if (a->h_next != NULL) a->h_next->h_prev = a;
alpar@9 272 G->v[i]->out = G->v[j]->in = a;
alpar@9 273 G->na++;
alpar@9 274 return a;
alpar@9 275 }
alpar@9 276
alpar@9 277 /***********************************************************************
alpar@9 278 * NAME
alpar@9 279 *
alpar@9 280 * glp_del_vertices - delete vertices from graph
alpar@9 281 *
alpar@9 282 * SYNOPSIS
alpar@9 283 *
alpar@9 284 * void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
alpar@9 285 *
alpar@9 286 * DESCRIPTION
alpar@9 287 *
alpar@9 288 * The routine glp_del_vertices deletes vertices along with all
alpar@9 289 * incident arcs from the specified graph. Ordinal numbers of vertices
alpar@9 290 * to be deleted should be placed in locations num[1], ..., num[ndel],
alpar@9 291 * ndel > 0.
alpar@9 292 *
alpar@9 293 * Note that deleting vertices involves changing ordinal numbers of
alpar@9 294 * other vertices remaining in the graph. New ordinal numbers of the
alpar@9 295 * remaining vertices are assigned under the assumption that the
alpar@9 296 * original order of vertices is not changed. */
alpar@9 297
alpar@9 298 void glp_del_vertices(glp_graph *G, int ndel, const int num[])
alpar@9 299 { glp_vertex *v;
alpar@9 300 int i, k, nv_new;
alpar@9 301 /* scan the list of vertices to be deleted */
alpar@9 302 if (!(1 <= ndel && ndel <= G->nv))
alpar@9 303 xerror("glp_del_vertices: ndel = %d; invalid number of vertice"
alpar@9 304 "s\n", ndel);
alpar@9 305 for (k = 1; k <= ndel; k++)
alpar@9 306 { /* take the number of vertex to be deleted */
alpar@9 307 i = num[k];
alpar@9 308 /* obtain pointer to i-th vertex */
alpar@9 309 if (!(1 <= i && i <= G->nv))
alpar@9 310 xerror("glp_del_vertices: num[%d] = %d; vertex number out o"
alpar@9 311 "f range\n", k, i);
alpar@9 312 v = G->v[i];
alpar@9 313 /* check that the vertex is not marked yet */
alpar@9 314 if (v->i == 0)
alpar@9 315 xerror("glp_del_vertices: num[%d] = %d; duplicate vertex nu"
alpar@9 316 "mbers not allowed\n", k, i);
alpar@9 317 /* erase symbolic name assigned to the vertex */
alpar@9 318 glp_set_vertex_name(G, i, NULL);
alpar@9 319 xassert(v->name == NULL);
alpar@9 320 xassert(v->entry == NULL);
alpar@9 321 /* free vertex data, if allocated */
alpar@9 322 if (v->data != NULL)
alpar@9 323 dmp_free_atom(G->pool, v->data, G->v_size);
alpar@9 324 /* delete all incoming arcs */
alpar@9 325 while (v->in != NULL)
alpar@9 326 glp_del_arc(G, v->in);
alpar@9 327 /* delete all outgoing arcs */
alpar@9 328 while (v->out != NULL)
alpar@9 329 glp_del_arc(G, v->out);
alpar@9 330 /* mark the vertex to be deleted */
alpar@9 331 v->i = 0;
alpar@9 332 }
alpar@9 333 /* delete all marked vertices from the vertex list */
alpar@9 334 nv_new = 0;
alpar@9 335 for (i = 1; i <= G->nv; i++)
alpar@9 336 { /* obtain pointer to i-th vertex */
alpar@9 337 v = G->v[i];
alpar@9 338 /* check if the vertex is marked */
alpar@9 339 if (v->i == 0)
alpar@9 340 { /* it is marked, delete it */
alpar@9 341 dmp_free_atom(G->pool, v, sizeof(glp_vertex));
alpar@9 342 }
alpar@9 343 else
alpar@9 344 { /* it is not marked, keep it */
alpar@9 345 v->i = ++nv_new;
alpar@9 346 G->v[v->i] = v;
alpar@9 347 }
alpar@9 348 }
alpar@9 349 /* set new number of vertices in the graph */
alpar@9 350 G->nv = nv_new;
alpar@9 351 return;
alpar@9 352 }
alpar@9 353
alpar@9 354 /***********************************************************************
alpar@9 355 * NAME
alpar@9 356 *
alpar@9 357 * glp_del_arc - delete arc from graph
alpar@9 358 *
alpar@9 359 * SYNOPSIS
alpar@9 360 *
alpar@9 361 * void glp_del_arc(glp_graph *G, glp_arc *a);
alpar@9 362 *
alpar@9 363 * DESCRIPTION
alpar@9 364 *
alpar@9 365 * The routine glp_del_arc deletes an arc from the specified graph.
alpar@9 366 * The arc to be deleted must exist. */
alpar@9 367
alpar@9 368 void glp_del_arc(glp_graph *G, glp_arc *a)
alpar@9 369 { /* some sanity checks */
alpar@9 370 xassert(G->na > 0);
alpar@9 371 xassert(1 <= a->tail->i && a->tail->i <= G->nv);
alpar@9 372 xassert(a->tail == G->v[a->tail->i]);
alpar@9 373 xassert(1 <= a->head->i && a->head->i <= G->nv);
alpar@9 374 xassert(a->head == G->v[a->head->i]);
alpar@9 375 /* remove the arc from the list of incoming arcs */
alpar@9 376 if (a->h_prev == NULL)
alpar@9 377 a->head->in = a->h_next;
alpar@9 378 else
alpar@9 379 a->h_prev->h_next = a->h_next;
alpar@9 380 if (a->h_next == NULL)
alpar@9 381 ;
alpar@9 382 else
alpar@9 383 a->h_next->h_prev = a->h_prev;
alpar@9 384 /* remove the arc from the list of outgoing arcs */
alpar@9 385 if (a->t_prev == NULL)
alpar@9 386 a->tail->out = a->t_next;
alpar@9 387 else
alpar@9 388 a->t_prev->t_next = a->t_next;
alpar@9 389 if (a->t_next == NULL)
alpar@9 390 ;
alpar@9 391 else
alpar@9 392 a->t_next->t_prev = a->t_prev;
alpar@9 393 /* free arc data, if allocated */
alpar@9 394 if (a->data != NULL)
alpar@9 395 dmp_free_atom(G->pool, a->data, G->a_size);
alpar@9 396 /* delete the arc from the graph */
alpar@9 397 dmp_free_atom(G->pool, a, sizeof(glp_arc));
alpar@9 398 G->na--;
alpar@9 399 return;
alpar@9 400 }
alpar@9 401
alpar@9 402 /***********************************************************************
alpar@9 403 * NAME
alpar@9 404 *
alpar@9 405 * glp_erase_graph - erase graph content
alpar@9 406 *
alpar@9 407 * SYNOPSIS
alpar@9 408 *
alpar@9 409 * void glp_erase_graph(glp_graph *G, int v_size, int a_size);
alpar@9 410 *
alpar@9 411 * DESCRIPTION
alpar@9 412 *
alpar@9 413 * The routine glp_erase_graph erases the content of the specified
alpar@9 414 * graph. The effect of this operation is the same as if the graph
alpar@9 415 * would be deleted with the routine glp_delete_graph and then created
alpar@9 416 * anew with the routine glp_create_graph, with exception that the
alpar@9 417 * handle (pointer) to the graph remains valid. */
alpar@9 418
alpar@9 419 static void delete_graph(glp_graph *G)
alpar@9 420 { dmp_delete_pool(G->pool);
alpar@9 421 xfree(G->v);
alpar@9 422 if (G->index != NULL) avl_delete_tree(G->index);
alpar@9 423 return;
alpar@9 424 }
alpar@9 425
alpar@9 426 void glp_erase_graph(glp_graph *G, int v_size, int a_size)
alpar@9 427 { if (!(0 <= v_size && v_size <= 256))
alpar@9 428 xerror("glp_erase_graph: v_size = %d; invalid size of vertex d"
alpar@9 429 "ata\n", v_size);
alpar@9 430 if (!(0 <= a_size && a_size <= 256))
alpar@9 431 xerror("glp_erase_graph: a_size = %d; invalid size of arc data"
alpar@9 432 "\n", a_size);
alpar@9 433 delete_graph(G);
alpar@9 434 create_graph(G, v_size, a_size);
alpar@9 435 return;
alpar@9 436 }
alpar@9 437
alpar@9 438 /***********************************************************************
alpar@9 439 * NAME
alpar@9 440 *
alpar@9 441 * glp_delete_graph - delete graph
alpar@9 442 *
alpar@9 443 * SYNOPSIS
alpar@9 444 *
alpar@9 445 * void glp_delete_graph(glp_graph *G);
alpar@9 446 *
alpar@9 447 * DESCRIPTION
alpar@9 448 *
alpar@9 449 * The routine glp_delete_graph deletes the specified graph and frees
alpar@9 450 * all the memory allocated to this program object. */
alpar@9 451
alpar@9 452 void glp_delete_graph(glp_graph *G)
alpar@9 453 { delete_graph(G);
alpar@9 454 xfree(G);
alpar@9 455 return;
alpar@9 456 }
alpar@9 457
alpar@9 458 /**********************************************************************/
alpar@9 459
alpar@9 460 void glp_create_v_index(glp_graph *G)
alpar@9 461 { /* create vertex name index */
alpar@9 462 glp_vertex *v;
alpar@9 463 int i;
alpar@9 464 if (G->index == NULL)
alpar@9 465 { G->index = avl_create_tree(avl_strcmp, NULL);
alpar@9 466 for (i = 1; i <= G->nv; i++)
alpar@9 467 { v = G->v[i];
alpar@9 468 xassert(v->entry == NULL);
alpar@9 469 if (v->name != NULL)
alpar@9 470 { v->entry = avl_insert_node(G->index, v->name);
alpar@9 471 avl_set_node_link(v->entry, v);
alpar@9 472 }
alpar@9 473 }
alpar@9 474 }
alpar@9 475 return;
alpar@9 476 }
alpar@9 477
alpar@9 478 int glp_find_vertex(glp_graph *G, const char *name)
alpar@9 479 { /* find vertex by its name */
alpar@9 480 AVLNODE *node;
alpar@9 481 int i = 0;
alpar@9 482 if (G->index == NULL)
alpar@9 483 xerror("glp_find_vertex: vertex name index does not exist\n");
alpar@9 484 if (!(name == NULL || name[0] == '\0' || strlen(name) > 255))
alpar@9 485 { node = avl_find_node(G->index, name);
alpar@9 486 if (node != NULL)
alpar@9 487 i = ((glp_vertex *)avl_get_node_link(node))->i;
alpar@9 488 }
alpar@9 489 return i;
alpar@9 490 }
alpar@9 491
alpar@9 492 void glp_delete_v_index(glp_graph *G)
alpar@9 493 { /* delete vertex name index */
alpar@9 494 int i;
alpar@9 495 if (G->index != NULL)
alpar@9 496 { avl_delete_tree(G->index), G->index = NULL;
alpar@9 497 for (i = 1; i <= G->nv; i++) G->v[i]->entry = NULL;
alpar@9 498 }
alpar@9 499 return;
alpar@9 500 }
alpar@9 501
alpar@9 502 /***********************************************************************
alpar@9 503 * NAME
alpar@9 504 *
alpar@9 505 * glp_read_graph - read graph from plain text file
alpar@9 506 *
alpar@9 507 * SYNOPSIS
alpar@9 508 *
alpar@9 509 * int glp_read_graph(glp_graph *G, const char *fname);
alpar@9 510 *
alpar@9 511 * DESCRIPTION
alpar@9 512 *
alpar@9 513 * The routine glp_read_graph reads a graph from a plain text file.
alpar@9 514 *
alpar@9 515 * RETURNS
alpar@9 516 *
alpar@9 517 * If the operation was successful, the routine returns zero. Otherwise
alpar@9 518 * it prints an error message and returns non-zero. */
alpar@9 519
alpar@9 520 int glp_read_graph(glp_graph *G, const char *fname)
alpar@9 521 { glp_data *data;
alpar@9 522 jmp_buf jump;
alpar@9 523 int nv, na, i, j, k, ret;
alpar@9 524 glp_erase_graph(G, G->v_size, G->a_size);
alpar@9 525 xprintf("Reading graph from `%s'...\n", fname);
alpar@9 526 data = glp_sdf_open_file(fname);
alpar@9 527 if (data == NULL)
alpar@9 528 { ret = 1;
alpar@9 529 goto done;
alpar@9 530 }
alpar@9 531 if (setjmp(jump))
alpar@9 532 { ret = 1;
alpar@9 533 goto done;
alpar@9 534 }
alpar@9 535 glp_sdf_set_jump(data, jump);
alpar@9 536 nv = glp_sdf_read_int(data);
alpar@9 537 if (nv < 0)
alpar@9 538 glp_sdf_error(data, "invalid number of vertices\n");
alpar@9 539 na = glp_sdf_read_int(data);
alpar@9 540 if (na < 0)
alpar@9 541 glp_sdf_error(data, "invalid number of arcs\n");
alpar@9 542 xprintf("Graph has %d vert%s and %d arc%s\n",
alpar@9 543 nv, nv == 1 ? "ex" : "ices", na, na == 1 ? "" : "s");
alpar@9 544 if (nv > 0) glp_add_vertices(G, nv);
alpar@9 545 for (k = 1; k <= na; k++)
alpar@9 546 { i = glp_sdf_read_int(data);
alpar@9 547 if (!(1 <= i && i <= nv))
alpar@9 548 glp_sdf_error(data, "tail vertex number out of range\n");
alpar@9 549 j = glp_sdf_read_int(data);
alpar@9 550 if (!(1 <= j && j <= nv))
alpar@9 551 glp_sdf_error(data, "head vertex number out of range\n");
alpar@9 552 glp_add_arc(G, i, j);
alpar@9 553 }
alpar@9 554 xprintf("%d lines were read\n", glp_sdf_line(data));
alpar@9 555 ret = 0;
alpar@9 556 done: if (data != NULL) glp_sdf_close_file(data);
alpar@9 557 return ret;
alpar@9 558 }
alpar@9 559
alpar@9 560 /***********************************************************************
alpar@9 561 * NAME
alpar@9 562 *
alpar@9 563 * glp_write_graph - write graph to plain text file
alpar@9 564 *
alpar@9 565 * SYNOPSIS
alpar@9 566 *
alpar@9 567 * int glp_write_graph(glp_graph *G, const char *fname).
alpar@9 568 *
alpar@9 569 * DESCRIPTION
alpar@9 570 *
alpar@9 571 * The routine glp_write_graph writes the specified graph to a plain
alpar@9 572 * text file.
alpar@9 573 *
alpar@9 574 * RETURNS
alpar@9 575 *
alpar@9 576 * If the operation was successful, the routine returns zero. Otherwise
alpar@9 577 * it prints an error message and returns non-zero. */
alpar@9 578
alpar@9 579 int glp_write_graph(glp_graph *G, const char *fname)
alpar@9 580 { XFILE *fp;
alpar@9 581 glp_vertex *v;
alpar@9 582 glp_arc *a;
alpar@9 583 int i, count, ret;
alpar@9 584 xprintf("Writing graph to `%s'...\n", fname);
alpar@9 585 fp = xfopen(fname, "w"), count = 0;
alpar@9 586 if (fp == NULL)
alpar@9 587 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());
alpar@9 588 ret = 1;
alpar@9 589 goto done;
alpar@9 590 }
alpar@9 591 xfprintf(fp, "%d %d\n", G->nv, G->na), count++;
alpar@9 592 for (i = 1; i <= G->nv; i++)
alpar@9 593 { v = G->v[i];
alpar@9 594 for (a = v->out; a != NULL; a = a->t_next)
alpar@9 595 xfprintf(fp, "%d %d\n", a->tail->i, a->head->i), count++;
alpar@9 596 }
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 /* eof */