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