lemon-project-template-glpk

comparison 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
comparison
equal deleted inserted replaced
-1:000000000000 0:33e9c5be2c48
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, 2011 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 */