1 /*
2 Copyright (C) 2016 Arb authors
3
4 This file is part of Arb.
5
6 Arb is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #include "bool_mat.h"
13
14 /* fixed-capacity stack */
15 typedef struct
16 {
17 slong *data;
18 slong capacity;
19 slong size;
20 } _si_stack_struct;
21
22 typedef _si_stack_struct _si_stack_t[1];
23
24 static void
_si_stack_init(_si_stack_t s,slong capacity)25 _si_stack_init(_si_stack_t s, slong capacity)
26 {
27 s->data = flint_malloc(capacity * sizeof(slong));
28 s->capacity = capacity;
29 s->size = 0;
30 }
31
32 static void
_si_stack_clear(_si_stack_t s)33 _si_stack_clear(_si_stack_t s)
34 {
35 flint_free(s->data);
36 }
37
38 static void
_si_stack_push(_si_stack_t s,slong x)39 _si_stack_push(_si_stack_t s, slong x)
40 {
41 if (s->size >= s->capacity) flint_abort(); /* assert */
42 s->data[s->size++] = x;
43 }
44
45 static slong
_si_stack_pop(_si_stack_t s)46 _si_stack_pop(_si_stack_t s)
47 {
48 slong x;
49 if (s->size <= 0) flint_abort(); /* assert */
50 x = s->data[s->size - 1];
51 s->size--;
52 return x;
53 }
54
55
56 /* struct for Tarjan's strongly connected components algorithm */
57 typedef struct
58 {
59 slong *index;
60 slong *lowlink;
61 int *onstack;
62 _si_stack_t S;
63 slong nsccs;
64 slong dim;
65 slong idx;
66 } _tarjan_struct;
67
68 typedef _tarjan_struct _tarjan_t[1];
69
70 static const slong _tarjan_UNDEFINED = -1;
71
72 static slong *
_tarjan_index(_tarjan_t t,slong i)73 _tarjan_index(_tarjan_t t, slong i)
74 {
75 return t->index + i;
76 }
77
78 static slong *
_tarjan_lowlink(_tarjan_t t,slong i)79 _tarjan_lowlink(_tarjan_t t, slong i)
80 {
81 return t->lowlink + i;
82 }
83
84 static int
_tarjan_onstack(_tarjan_t t,slong i)85 _tarjan_onstack(_tarjan_t t, slong i)
86 {
87 return t->onstack[i];
88 }
89
90 static void
_tarjan_push(_tarjan_t t,slong v)91 _tarjan_push(_tarjan_t t, slong v)
92 {
93 _si_stack_push(t->S, v);
94 t->onstack[v] = 1;
95 }
96
97 static slong
_tarjan_pop(_tarjan_t t)98 _tarjan_pop(_tarjan_t t)
99 {
100 slong v;
101 v = _si_stack_pop(t->S);
102 t->onstack[v] = 0;
103 return v;
104 }
105
106 static slong
_tarjan_next_scc(_tarjan_t t)107 _tarjan_next_scc(_tarjan_t t)
108 {
109 return t->nsccs++;
110 }
111
112 static slong
_tarjan_next_idx(_tarjan_t t)113 _tarjan_next_idx(_tarjan_t t)
114 {
115 return t->idx++;
116 }
117
118 static void
_tarjan_init(_tarjan_t t,slong dim)119 _tarjan_init(_tarjan_t t, slong dim)
120 {
121 slong i;
122 t->index = flint_calloc(dim, sizeof(slong));
123 t->lowlink = flint_calloc(dim, sizeof(slong));
124 t->onstack = flint_calloc(dim, sizeof(int));
125 _si_stack_init(t->S, dim);
126 t->dim = dim;
127 t->nsccs = 0;
128 t->idx = 0;
129 for (i = 0; i < dim; i++)
130 {
131 t->index[i] = _tarjan_UNDEFINED;
132 }
133 }
134
135 static void
_tarjan_clear(_tarjan_t t)136 _tarjan_clear(_tarjan_t t)
137 {
138 flint_free(t->index);
139 flint_free(t->lowlink);
140 flint_free(t->onstack);
141 _si_stack_clear(t->S);
142 }
143
144 static void
_tarjan_strongconnect(slong * sccs,_tarjan_t t,const bool_mat_t A,slong v)145 _tarjan_strongconnect(slong *sccs, _tarjan_t t, const bool_mat_t A, slong v)
146 {
147 slong idx, w, scc;
148
149 idx = _tarjan_next_idx(t);
150 *_tarjan_index(t, v) = idx;
151 *_tarjan_lowlink(t, v) = idx;
152 _tarjan_push(t, v);
153 for (w = 0; w < t->dim; w++)
154 {
155 if (bool_mat_get_entry(A, v, w))
156 {
157 if (*_tarjan_index(t, w) == _tarjan_UNDEFINED)
158 {
159 _tarjan_strongconnect(sccs, t, A, w);
160 *_tarjan_lowlink(t, v) = FLINT_MIN(
161 *_tarjan_lowlink(t, v), *_tarjan_lowlink(t, w));
162 }
163 else if (_tarjan_onstack(t, w))
164 {
165 *_tarjan_lowlink(t, v) = FLINT_MIN(
166 *_tarjan_lowlink(t, v), *_tarjan_index(t, w));
167 }
168 }
169 }
170 if (*_tarjan_lowlink(t, v) == *_tarjan_index(t, v))
171 {
172 scc = _tarjan_next_scc(t);
173 while (w != v)
174 {
175 w = _tarjan_pop(t);
176 if (sccs[w] != _tarjan_UNDEFINED) flint_abort(); /* assert */
177 sccs[w] = scc;
178 }
179 }
180 }
181
182
183 /* following Tarjan */
184 slong
bool_mat_get_strongly_connected_components(slong * partition,const bool_mat_t A)185 bool_mat_get_strongly_connected_components(slong *partition, const bool_mat_t A)
186 {
187 slong i, n, result;
188 _tarjan_t t;
189
190 if (!bool_mat_is_square(A))
191 {
192 flint_printf("bool_mat_get_strongly_connected_components: "
193 "a square matrix is required!\n");
194 flint_abort();
195 }
196
197 if (bool_mat_is_empty(A))
198 return 0;
199
200 n = bool_mat_nrows(A);
201
202 if (n == 1)
203 {
204 partition[0] = 0;
205 return 1;
206 }
207
208 _tarjan_init(t, n);
209
210 for (i = 0; i < n; i++)
211 {
212 partition[i] = _tarjan_UNDEFINED;
213 }
214 for (i = 0; i < n; i++)
215 {
216 if (*_tarjan_index(t, i) == _tarjan_UNDEFINED)
217 {
218 _tarjan_strongconnect(partition, t, A, i);
219 }
220 }
221
222 result = t->nsccs;
223
224 _tarjan_clear(t);
225
226 return result;
227 }
228