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 */ |
---|