COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpapi16.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 10.9 KB
Line 
1/* glpapi16.c (graph and network analysis 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#include "glpnet.h"
27
28/***********************************************************************
29*  NAME
30*
31*  glp_weak_comp - find all weakly connected components of graph
32*
33*  SYNOPSIS
34*
35*  int glp_weak_comp(glp_graph *G, int v_num);
36*
37*  DESCRIPTION
38*
39*  The routine glp_weak_comp finds all weakly connected components of
40*  the specified graph.
41*
42*  The parameter v_num specifies an offset of the field of type int
43*  in the vertex data block, to which the routine stores the number of
44*  a (weakly) connected component containing that vertex. If v_num < 0,
45*  no component numbers are stored.
46*
47*  The components are numbered in arbitrary order from 1 to nc, where
48*  nc is the total number of components found, 0 <= nc <= |V|.
49*
50*  RETURNS
51*
52*  The routine returns nc, the total number of components found. */
53
54int glp_weak_comp(glp_graph *G, int v_num)
55{     glp_vertex *v;
56      glp_arc *a;
57      int f, i, j, nc, nv, pos1, pos2, *prev, *next, *list;
58      if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
59         xerror("glp_weak_comp: v_num = %d; invalid offset\n", v_num);
60      nv = G->nv;
61      if (nv == 0)
62      {  nc = 0;
63         goto done;
64      }
65      /* allocate working arrays */
66      prev = xcalloc(1+nv, sizeof(int));
67      next = xcalloc(1+nv, sizeof(int));
68      list = xcalloc(1+nv, sizeof(int));
69      /* if vertex i is unlabelled, prev[i] is the index of previous
70         unlabelled vertex, and next[i] is the index of next unlabelled
71         vertex; if vertex i is labelled, then prev[i] < 0, and next[i]
72         is the connected component number */
73      /* initially all vertices are unlabelled */
74      f = 1;
75      for (i = 1; i <= nv; i++)
76         prev[i] = i - 1, next[i] = i + 1;
77      next[nv] = 0;
78      /* main loop (until all vertices have been labelled) */
79      nc = 0;
80      while (f != 0)
81      {  /* take an unlabelled vertex */
82         i = f;
83         /* and remove it from the list of unlabelled vertices */
84         f = next[i];
85         if (f != 0) prev[f] = 0;
86         /* label the vertex; it begins a new component */
87         prev[i] = -1, next[i] = ++nc;
88         /* breadth first search */
89         list[1] = i, pos1 = pos2 = 1;
90         while (pos1 <= pos2)
91         {  /* dequeue vertex i */
92            i = list[pos1++];
93            /* consider all arcs incoming to vertex i */
94            for (a = G->v[i]->in; a != NULL; a = a->h_next)
95            {  /* vertex j is adjacent to vertex i */
96               j = a->tail->i;
97               if (prev[j] >= 0)
98               {  /* vertex j is unlabelled */
99                  /* remove it from the list of unlabelled vertices */
100                  if (prev[j] == 0)
101                     f = next[j];
102                  else
103                     next[prev[j]] = next[j];
104                  if (next[j] == 0)
105                     ;
106                  else
107                     prev[next[j]] = prev[j];
108                  /* label the vertex */
109                  prev[j] = -1, next[j] = nc;
110                  /* and enqueue it for further consideration */
111                  list[++pos2] = j;
112               }
113            }
114            /* consider all arcs outgoing from vertex i */
115            for (a = G->v[i]->out; a != NULL; a = a->t_next)
116            {  /* vertex j is adjacent to vertex i */
117               j = a->head->i;
118               if (prev[j] >= 0)
119               {  /* vertex j is unlabelled */
120                  /* remove it from the list of unlabelled vertices */
121                  if (prev[j] == 0)
122                     f = next[j];
123                  else
124                     next[prev[j]] = next[j];
125                  if (next[j] == 0)
126                     ;
127                  else
128                     prev[next[j]] = prev[j];
129                  /* label the vertex */
130                  prev[j] = -1, next[j] = nc;
131                  /* and enqueue it for further consideration */
132                  list[++pos2] = j;
133               }
134            }
135         }
136      }
137      /* store component numbers */
138      if (v_num >= 0)
139      {  for (i = 1; i <= nv; i++)
140         {  v = G->v[i];
141            memcpy((char *)v->data + v_num, &next[i], sizeof(int));
142         }
143      }
144      /* free working arrays */
145      xfree(prev);
146      xfree(next);
147      xfree(list);
148done: return nc;
149}
150
151/***********************************************************************
152*  NAME
153*
154*  glp_strong_comp - find all strongly connected components of graph
155*
156*  SYNOPSIS
157*
158*  int glp_strong_comp(glp_graph *G, int v_num);
159*
160*  DESCRIPTION
161*
162*  The routine glp_strong_comp finds all strongly connected components
163*  of the specified graph.
164*
165*  The parameter v_num specifies an offset of the field of type int
166*  in the vertex data block, to which the routine stores the number of
167*  a strongly connected component containing that vertex. If v_num < 0,
168*  no component numbers are stored.
169*
170*  The components are numbered in arbitrary order from 1 to nc, where
171*  nc is the total number of components found, 0 <= nc <= |V|. However,
172*  the component numbering has the property that for every arc (i->j)
173*  in the graph the condition num(i) >= num(j) holds.
174*
175*  RETURNS
176*
177*  The routine returns nc, the total number of components found. */
178
179int glp_strong_comp(glp_graph *G, int v_num)
180{     glp_vertex *v;
181      glp_arc *a;
182      int i, k, last, n, na, nc, *icn, *ip, *lenr, *ior, *ib, *lowl,
183         *numb, *prev;
184      if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
185         xerror("glp_strong_comp: v_num = %d; invalid offset\n",
186            v_num);
187      n = G->nv;
188      if (n == 0)
189      {  nc = 0;
190         goto done;
191      }
192      na = G->na;
193      icn = xcalloc(1+na, sizeof(int));
194      ip = xcalloc(1+n, sizeof(int));
195      lenr = xcalloc(1+n, sizeof(int));
196      ior = xcalloc(1+n, sizeof(int));
197      ib = xcalloc(1+n, sizeof(int));
198      lowl = xcalloc(1+n, sizeof(int));
199      numb = xcalloc(1+n, sizeof(int));
200      prev = xcalloc(1+n, sizeof(int));
201      k = 1;
202      for (i = 1; i <= n; i++)
203      {  v = G->v[i];
204         ip[i] = k;
205         for (a = v->out; a != NULL; a = a->t_next)
206            icn[k++] = a->head->i;
207         lenr[i] = k - ip[i];
208      }
209      xassert(na == k-1);
210      nc = mc13d(n, icn, ip, lenr, ior, ib, lowl, numb, prev);
211      if (v_num >= 0)
212      {  xassert(ib[1] == 1);
213         for (k = 1; k <= nc; k++)
214         {  last = (k < nc ? ib[k+1] : n+1);
215            xassert(ib[k] < last);
216            for (i = ib[k]; i < last; i++)
217            {  v = G->v[ior[i]];
218               memcpy((char *)v->data + v_num, &k, sizeof(int));
219            }
220         }
221      }
222      xfree(icn);
223      xfree(ip);
224      xfree(lenr);
225      xfree(ior);
226      xfree(ib);
227      xfree(lowl);
228      xfree(numb);
229      xfree(prev);
230done: return nc;
231}
232
233/***********************************************************************
234*  NAME
235*
236*  glp_top_sort - topological sorting of acyclic digraph
237*
238*  SYNOPSIS
239*
240*  int glp_top_sort(glp_graph *G, int v_num);
241*
242*  DESCRIPTION
243*
244*  The routine glp_top_sort performs topological sorting of vertices of
245*  the specified acyclic digraph.
246*
247*  The parameter v_num specifies an offset of the field of type int in
248*  the vertex data block, to which the routine stores the vertex number
249*  assigned. If v_num < 0, vertex numbers are not stored.
250*
251*  The vertices are numbered from 1 to n, where n is the total number
252*  of vertices in the graph. The vertex numbering has the property that
253*  for every arc (i->j) in the graph the condition num(i) < num(j)
254*  holds. Special case num(i) = 0 means that vertex i is not assigned a
255*  number, because the graph is *not* acyclic.
256*
257*  RETURNS
258*
259*  If the graph is acyclic and therefore all the vertices have been
260*  assigned numbers, the routine glp_top_sort returns zero. Otherwise,
261*  if the graph is not acyclic, the routine returns the number of
262*  vertices which have not been numbered, i.e. for which num(i) = 0. */
263
264static int top_sort(glp_graph *G, int num[])
265{     glp_arc *a;
266      int i, j, cnt, top, *stack, *indeg;
267      /* allocate working arrays */
268      indeg = xcalloc(1+G->nv, sizeof(int));
269      stack = xcalloc(1+G->nv, sizeof(int));
270      /* determine initial indegree of each vertex; push into the stack
271         the vertices having zero indegree */
272      top = 0;
273      for (i = 1; i <= G->nv; i++)
274      {  num[i] = indeg[i] = 0;
275         for (a = G->v[i]->in; a != NULL; a = a->h_next)
276            indeg[i]++;
277         if (indeg[i] == 0)
278            stack[++top] = i;
279      }
280      /* assign numbers to vertices in the sorted order */
281      cnt = 0;
282      while (top > 0)
283      {  /* pull vertex i from the stack */
284         i = stack[top--];
285         /* it has zero indegree in the current graph */
286         xassert(indeg[i] == 0);
287         /* so assign it a next number */
288         xassert(num[i] == 0);
289         num[i] = ++cnt;
290         /* remove vertex i from the current graph, update indegree of
291            its adjacent vertices, and push into the stack new vertices
292            whose indegree becomes zero */
293         for (a = G->v[i]->out; a != NULL; a = a->t_next)
294         {  j = a->head->i;
295            /* there exists arc (i->j) in the graph */
296            xassert(indeg[j] > 0);
297            indeg[j]--;
298            if (indeg[j] == 0)
299               stack[++top] = j;
300         }
301      }
302      /* free working arrays */
303      xfree(indeg);
304      xfree(stack);
305      return G->nv - cnt;
306}
307
308int glp_top_sort(glp_graph *G, int v_num)
309{     glp_vertex *v;
310      int i, cnt, *num;
311      if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
312         xerror("glp_top_sort: v_num = %d; invalid offset\n", v_num);
313      if (G->nv == 0)
314      {  cnt = 0;
315         goto done;
316      }
317      num = xcalloc(1+G->nv, sizeof(int));
318      cnt = top_sort(G, num);
319      if (v_num >= 0)
320      {  for (i = 1; i <= G->nv; i++)
321         {  v = G->v[i];
322            memcpy((char *)v->data + v_num, &num[i], sizeof(int));
323         }
324      }
325      xfree(num);
326done: return cnt;
327}
328
329/* eof */
Note: See TracBrowser for help on using the repository browser.