lemon-project-template-glpk

comparison deps/glpk/src/glpapi16.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:eaaff60fda2a
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, 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 #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
54 int 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);
148 done: 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
179 int 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);
230 done: 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
264 static 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
308 int 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);
326 done: return cnt;
327 }
328
329 /* eof */