COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/src/glpapi15.c

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 18.3 KB
Line 
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
59static 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
71glp_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
101void 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
143int 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
188void 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
246glp_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
298void 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
368void 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
419static 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
426void 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
452void glp_delete_graph(glp_graph *G)
453{     delete_graph(G);
454      xfree(G);
455      return;
456}
457
458/**********************************************************************/
459
460void 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
478int 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
492void 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
520int 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;
556done: 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
579int 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;
605done: if (fp != NULL) xfclose(fp);
606      return ret;
607}
608
609/* eof */
Note: See TracBrowser for help on using the repository browser.