1 /* strong.c (find all strongly connected components of graph) */
2
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 * Copyright (C) 2009-2016 Free Software Foundation, Inc.
6 * Written by Andrew Makhorin <mao@gnu.org>.
7 *
8 * GLPK is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * GLPK is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
16 * License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
20 ***********************************************************************/
21
22 #include "env.h"
23 #include "glpk.h"
24 #include "mc13d.h"
25
26 /***********************************************************************
27 * NAME
28 *
29 * glp_strong_comp - find all strongly connected components of graph
30 *
31 * SYNOPSIS
32 *
33 * int glp_strong_comp(glp_graph *G, int v_num);
34 *
35 * DESCRIPTION
36 *
37 * The routine glp_strong_comp finds all strongly connected components
38 * of the specified graph.
39 *
40 * The parameter v_num specifies an offset of the field of type int
41 * in the vertex data block, to which the routine stores the number of
42 * a strongly connected component containing that vertex. If v_num < 0,
43 * no component numbers are stored.
44 *
45 * The components are numbered in arbitrary order from 1 to nc, where
46 * nc is the total number of components found, 0 <= nc <= |V|. However,
47 * the component numbering has the property that for every arc (i->j)
48 * in the graph the condition num(i) >= num(j) holds.
49 *
50 * RETURNS
51 *
52 * The routine returns nc, the total number of components found. */
53
glp_strong_comp(glp_graph * G,int v_num)54 int glp_strong_comp(glp_graph *G, int v_num)
55 { glp_vertex *v;
56 glp_arc *a;
57 int i, k, last, n, na, nc, *icn, *ip, *lenr, *ior, *ib, *lowl,
58 *numb, *prev;
59 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
60 xerror("glp_strong_comp: v_num = %d; invalid offset\n",
61 v_num);
62 n = G->nv;
63 if (n == 0)
64 { nc = 0;
65 goto done;
66 }
67 na = G->na;
68 icn = xcalloc(1+na, sizeof(int));
69 ip = xcalloc(1+n, sizeof(int));
70 lenr = xcalloc(1+n, sizeof(int));
71 ior = xcalloc(1+n, sizeof(int));
72 ib = xcalloc(1+n, sizeof(int));
73 lowl = xcalloc(1+n, sizeof(int));
74 numb = xcalloc(1+n, sizeof(int));
75 prev = xcalloc(1+n, sizeof(int));
76 k = 1;
77 for (i = 1; i <= n; i++)
78 { v = G->v[i];
79 ip[i] = k;
80 for (a = v->out; a != NULL; a = a->t_next)
81 icn[k++] = a->head->i;
82 lenr[i] = k - ip[i];
83 }
84 xassert(na == k-1);
85 nc = mc13d(n, icn, ip, lenr, ior, ib, lowl, numb, prev);
86 if (v_num >= 0)
87 { xassert(ib[1] == 1);
88 for (k = 1; k <= nc; k++)
89 { last = (k < nc ? ib[k+1] : n+1);
90 xassert(ib[k] < last);
91 for (i = ib[k]; i < last; i++)
92 { v = G->v[ior[i]];
93 memcpy((char *)v->data + v_num, &k, sizeof(int));
94 }
95 }
96 }
97 xfree(icn);
98 xfree(ip);
99 xfree(lenr);
100 xfree(ior);
101 xfree(ib);
102 xfree(lowl);
103 xfree(numb);
104 xfree(prev);
105 done: return nc;
106 }
107
108 /* eof */
109