1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2003-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #include "igraph_components.h"
25 #include "igraph_memory.h"
26 #include "igraph_interface.h"
27 #include "igraph_adjlist.h"
28 #include "igraph_interrupt_internal.h"
29 #include "igraph_progress.h"
30 #include "igraph_structural.h"
31 #include "igraph_dqueue.h"
32 #include "igraph_stack.h"
33 #include "igraph_vector.h"
34 #include "config.h"
35 #include <limits.h>
36
37 static int igraph_i_clusters_weak(const igraph_t *graph, igraph_vector_t *membership,
38 igraph_vector_t *csize, igraph_integer_t *no);
39
40 static int igraph_i_clusters_strong(const igraph_t *graph, igraph_vector_t *membership,
41 igraph_vector_t *csize, igraph_integer_t *no);
42
43 /**
44 * \ingroup structural
45 * \function igraph_clusters
46 * \brief Calculates the (weakly or strongly) connected components in a graph.
47 *
48 * \param graph The graph object to analyze.
49 * \param membership First half of the result will be stored here. For
50 * every vertex the id of its component is given. The vector
51 * has to be preinitialized and will be resized. Alternatively
52 * this argument can be \c NULL, in which case it is ignored.
53 * \param csize The second half of the result. For every component it
54 * gives its size, the order is defined by the component ids.
55 * The vector has to be preinitialized and will be resized.
56 * Alternatively this argument can be \c NULL, in which
57 * case it is ignored.
58 * \param no Pointer to an integer, if not \c NULL then the number of
59 * clusters will be stored here.
60 * \param mode For directed graph this specifies whether to calculate
61 * weakly or strongly connected components. Possible values:
62 * \c IGRAPH_WEAK,
63 * \c IGRAPH_STRONG. This argument is
64 * ignored for undirected graphs.
65 * \return Error code:
66 * \c IGRAPH_EINVAL: invalid mode argument.
67 *
68 * Time complexity: O(|V|+|E|),
69 * |V| and
70 * |E| are the number of vertices and
71 * edges in the graph.
72 */
73
igraph_clusters(const igraph_t * graph,igraph_vector_t * membership,igraph_vector_t * csize,igraph_integer_t * no,igraph_connectedness_t mode)74 int igraph_clusters(const igraph_t *graph, igraph_vector_t *membership,
75 igraph_vector_t *csize, igraph_integer_t *no,
76 igraph_connectedness_t mode) {
77 if (mode == IGRAPH_WEAK || !igraph_is_directed(graph)) {
78 return igraph_i_clusters_weak(graph, membership, csize, no);
79 } else if (mode == IGRAPH_STRONG) {
80 return igraph_i_clusters_strong(graph, membership, csize, no);
81 } else {
82 IGRAPH_ERROR("Cannot calculate clusters", IGRAPH_EINVAL);
83 }
84
85 return 1;
86 }
87
igraph_i_clusters_weak(const igraph_t * graph,igraph_vector_t * membership,igraph_vector_t * csize,igraph_integer_t * no)88 static int igraph_i_clusters_weak(const igraph_t *graph, igraph_vector_t *membership,
89 igraph_vector_t *csize, igraph_integer_t *no) {
90
91 long int no_of_nodes = igraph_vcount(graph);
92 char *already_added;
93 long int first_node, act_cluster_size = 0, no_of_clusters = 1;
94
95 igraph_dqueue_t q = IGRAPH_DQUEUE_NULL;
96
97 long int i;
98 igraph_vector_t neis = IGRAPH_VECTOR_NULL;
99
100 already_added = igraph_Calloc(no_of_nodes, char);
101 if (already_added == 0) {
102 IGRAPH_ERROR("Cannot calculate clusters", IGRAPH_ENOMEM);
103 }
104 IGRAPH_FINALLY(igraph_free, already_added);
105
106 IGRAPH_DQUEUE_INIT_FINALLY(&q, no_of_nodes > 100000 ? 10000 : no_of_nodes / 10);
107 IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
108
109 /* Memory for result, csize is dynamically allocated */
110 if (membership) {
111 IGRAPH_CHECK(igraph_vector_resize(membership, no_of_nodes));
112 }
113 if (csize) {
114 igraph_vector_clear(csize);
115 }
116
117 /* The algorithm */
118
119 for (first_node = 0; first_node < no_of_nodes; ++first_node) {
120 if (already_added[first_node] == 1) {
121 continue;
122 }
123 IGRAPH_ALLOW_INTERRUPTION();
124
125 already_added[first_node] = 1;
126 act_cluster_size = 1;
127 if (membership) {
128 VECTOR(*membership)[first_node] = no_of_clusters - 1;
129 }
130 IGRAPH_CHECK(igraph_dqueue_push(&q, first_node));
131
132 while ( !igraph_dqueue_empty(&q) ) {
133 long int act_node = (long int) igraph_dqueue_pop(&q);
134 IGRAPH_CHECK(igraph_neighbors(graph, &neis,
135 (igraph_integer_t) act_node, IGRAPH_ALL));
136 for (i = 0; i < igraph_vector_size(&neis); i++) {
137 long int neighbor = (long int) VECTOR(neis)[i];
138 if (already_added[neighbor] == 1) {
139 continue;
140 }
141 IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
142 already_added[neighbor] = 1;
143 act_cluster_size++;
144 if (membership) {
145 VECTOR(*membership)[neighbor] = no_of_clusters - 1;
146 }
147 }
148 }
149 no_of_clusters++;
150 if (csize) {
151 IGRAPH_CHECK(igraph_vector_push_back(csize, act_cluster_size));
152 }
153 }
154
155 /* Cleaning up */
156
157 if (no) {
158 *no = (igraph_integer_t) no_of_clusters - 1;
159 }
160
161 igraph_Free(already_added);
162 igraph_dqueue_destroy(&q);
163 igraph_vector_destroy(&neis);
164 IGRAPH_FINALLY_CLEAN(3);
165
166 return 0;
167 }
168
igraph_i_clusters_strong(const igraph_t * graph,igraph_vector_t * membership,igraph_vector_t * csize,igraph_integer_t * no)169 static int igraph_i_clusters_strong(const igraph_t *graph, igraph_vector_t *membership,
170 igraph_vector_t *csize, igraph_integer_t *no) {
171
172 long int no_of_nodes = igraph_vcount(graph);
173 igraph_vector_t next_nei = IGRAPH_VECTOR_NULL;
174
175 long int i, n, num_seen;
176 igraph_dqueue_t q = IGRAPH_DQUEUE_NULL;
177
178 long int no_of_clusters = 1;
179 long int act_cluster_size;
180
181 igraph_vector_t out = IGRAPH_VECTOR_NULL;
182 const igraph_vector_int_t* tmp;
183
184 igraph_adjlist_t adjlist;
185
186 /* The result */
187
188 IGRAPH_VECTOR_INIT_FINALLY(&next_nei, no_of_nodes);
189 IGRAPH_VECTOR_INIT_FINALLY(&out, 0);
190 IGRAPH_DQUEUE_INIT_FINALLY(&q, 100);
191
192 if (membership) {
193 IGRAPH_CHECK(igraph_vector_resize(membership, no_of_nodes));
194 }
195 IGRAPH_CHECK(igraph_vector_reserve(&out, no_of_nodes));
196
197 igraph_vector_null(&out);
198 if (csize) {
199 igraph_vector_clear(csize);
200 }
201
202 IGRAPH_CHECK(igraph_adjlist_init(graph, &adjlist, IGRAPH_OUT));
203 IGRAPH_FINALLY(igraph_adjlist_destroy, &adjlist);
204
205 num_seen = 0;
206 for (i = 0; i < no_of_nodes; i++) {
207 IGRAPH_ALLOW_INTERRUPTION();
208
209 tmp = igraph_adjlist_get(&adjlist, i);
210 if (VECTOR(next_nei)[i] > igraph_vector_int_size(tmp)) {
211 continue;
212 }
213
214 IGRAPH_CHECK(igraph_dqueue_push(&q, i));
215 while (!igraph_dqueue_empty(&q)) {
216 long int act_node = (long int) igraph_dqueue_back(&q);
217 tmp = igraph_adjlist_get(&adjlist, act_node);
218 if (VECTOR(next_nei)[act_node] == 0) {
219 /* this is the first time we've met this vertex */
220 VECTOR(next_nei)[act_node]++;
221 } else if (VECTOR(next_nei)[act_node] <= igraph_vector_int_size(tmp)) {
222 /* we've already met this vertex but it has more children */
223 long int neighbor = (long int) VECTOR(*tmp)[(long int)
224 VECTOR(next_nei)[act_node] - 1];
225 if (VECTOR(next_nei)[neighbor] == 0) {
226 IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
227 }
228 VECTOR(next_nei)[act_node]++;
229 } else {
230 /* we've met this vertex and it has no more children */
231 IGRAPH_CHECK(igraph_vector_push_back(&out, act_node));
232 igraph_dqueue_pop_back(&q);
233 num_seen++;
234
235 if (num_seen % 10000 == 0) {
236 /* time to report progress and allow the user to interrupt */
237 IGRAPH_PROGRESS("Strongly connected components: ",
238 num_seen * 50.0 / no_of_nodes, NULL);
239 IGRAPH_ALLOW_INTERRUPTION();
240 }
241 }
242 } /* while q */
243 } /* for */
244
245 IGRAPH_PROGRESS("Strongly connected components: ", 50.0, NULL);
246
247 igraph_adjlist_destroy(&adjlist);
248 IGRAPH_FINALLY_CLEAN(1);
249
250 IGRAPH_CHECK(igraph_adjlist_init(graph, &adjlist, IGRAPH_IN));
251 IGRAPH_FINALLY(igraph_adjlist_destroy, &adjlist);
252
253 /* OK, we've the 'out' values for the nodes, let's use them in
254 decreasing order with the help of a heap */
255
256 igraph_vector_null(&next_nei); /* mark already added vertices */
257 num_seen = 0;
258
259 while (!igraph_vector_empty(&out)) {
260 long int grandfather = (long int) igraph_vector_pop_back(&out);
261
262 if (VECTOR(next_nei)[grandfather] != 0) {
263 continue;
264 }
265 VECTOR(next_nei)[grandfather] = 1;
266 act_cluster_size = 1;
267 if (membership) {
268 VECTOR(*membership)[grandfather] = no_of_clusters - 1;
269 }
270 IGRAPH_CHECK(igraph_dqueue_push(&q, grandfather));
271
272 num_seen++;
273 if (num_seen % 10000 == 0) {
274 /* time to report progress and allow the user to interrupt */
275 IGRAPH_PROGRESS("Strongly connected components: ",
276 50.0 + num_seen * 50.0 / no_of_nodes, NULL);
277 IGRAPH_ALLOW_INTERRUPTION();
278 }
279
280 while (!igraph_dqueue_empty(&q)) {
281 long int act_node = (long int) igraph_dqueue_pop_back(&q);
282 tmp = igraph_adjlist_get(&adjlist, act_node);
283 n = igraph_vector_int_size(tmp);
284 for (i = 0; i < n; i++) {
285 long int neighbor = (long int) VECTOR(*tmp)[i];
286 if (VECTOR(next_nei)[neighbor] != 0) {
287 continue;
288 }
289 IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
290 VECTOR(next_nei)[neighbor] = 1;
291 act_cluster_size++;
292 if (membership) {
293 VECTOR(*membership)[neighbor] = no_of_clusters - 1;
294 }
295
296 num_seen++;
297 if (num_seen % 10000 == 0) {
298 /* time to report progress and allow the user to interrupt */
299 IGRAPH_PROGRESS("Strongly connected components: ",
300 50.0 + num_seen * 50.0 / no_of_nodes, NULL);
301 IGRAPH_ALLOW_INTERRUPTION();
302 }
303 }
304 }
305
306 no_of_clusters++;
307 if (csize) {
308 IGRAPH_CHECK(igraph_vector_push_back(csize, act_cluster_size));
309 }
310 }
311
312 IGRAPH_PROGRESS("Strongly connected components: ", 100.0, NULL);
313
314 if (no) {
315 *no = (igraph_integer_t) no_of_clusters - 1;
316 }
317
318 /* Clean up, return */
319
320 igraph_adjlist_destroy(&adjlist);
321 igraph_vector_destroy(&out);
322 igraph_dqueue_destroy(&q);
323 igraph_vector_destroy(&next_nei);
324 IGRAPH_FINALLY_CLEAN(4);
325
326 return 0;
327 }
328
329 int igraph_is_connected_weak(const igraph_t *graph, igraph_bool_t *res);
330
331 /**
332 * \ingroup structural
333 * \function igraph_is_connected
334 * \brief Decides whether the graph is (weakly or strongly) connected.
335 *
336 * A graph with zero vertices (i.e. the null graph) is connected by definition.
337 *
338 * \param graph The graph object to analyze.
339 * \param res Pointer to a logical variable, the result will be stored
340 * here.
341 * \param mode For a directed graph this specifies whether to calculate
342 * weak or strong connectedness. Possible values:
343 * \c IGRAPH_WEAK,
344 * \c IGRAPH_STRONG. This argument is
345 * ignored for undirected graphs.
346 * \return Error code:
347 * \c IGRAPH_EINVAL: invalid mode argument.
348 *
349 * Time complexity: O(|V|+|E|), the
350 * number of vertices
351 * plus the number of edges in the graph.
352 */
353
igraph_is_connected(const igraph_t * graph,igraph_bool_t * res,igraph_connectedness_t mode)354 int igraph_is_connected(const igraph_t *graph, igraph_bool_t *res,
355 igraph_connectedness_t mode) {
356 if (igraph_vcount(graph) == 0) {
357 *res = 1;
358 return IGRAPH_SUCCESS;
359 }
360
361 if (mode == IGRAPH_WEAK || !igraph_is_directed(graph)) {
362 return igraph_is_connected_weak(graph, res);
363 } else if (mode == IGRAPH_STRONG) {
364 int retval;
365 igraph_integer_t no;
366 retval = igraph_i_clusters_strong(graph, 0, 0, &no);
367 *res = (no == 1);
368 return retval;
369 } else {
370 IGRAPH_ERROR("mode argument", IGRAPH_EINVAL);
371 }
372 return 0;
373 }
374
375 /**
376 * \ingroup structural
377 * \function igraph_is_connected_weak
378 * \brief Query whether the graph is weakly connected.
379 *
380 * A graph with zero vertices (i.e. the null graph) is weakly connected by
381 * definition. A directed graph is weakly connected if its undirected version
382 * is connected. In the case of undirected graphs, weakly connected and
383 * connected are equivalent.
384 *
385 * \param graph The graph object to analyze.
386 * \param res Pointer to a logical variable; the result will be stored here.
387 * \return Error code:
388 * \c IGRAPH_ENOMEM: unable to allocate requested memory.
389 *
390 * Time complexity: O(|V|+|E|), the number of vertices plus the number of
391 * edges in the graph.
392 */
393
igraph_is_connected_weak(const igraph_t * graph,igraph_bool_t * res)394 int igraph_is_connected_weak(const igraph_t *graph, igraph_bool_t *res) {
395
396 long int no_of_nodes = igraph_vcount(graph);
397 char *already_added;
398 igraph_vector_t neis = IGRAPH_VECTOR_NULL;
399 igraph_dqueue_t q = IGRAPH_DQUEUE_NULL;
400
401 long int i, j;
402
403 if (no_of_nodes == 0) {
404 *res = 1;
405 return IGRAPH_SUCCESS;
406 }
407
408 already_added = igraph_Calloc(no_of_nodes, char);
409 if (already_added == 0) {
410 IGRAPH_ERROR("is connected (weak) failed", IGRAPH_ENOMEM);
411 }
412 IGRAPH_FINALLY(igraph_free, already_added);
413
414 IGRAPH_DQUEUE_INIT_FINALLY(&q, 10);
415 IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
416
417 /* Try to find at least two clusters */
418 already_added[0] = 1;
419 IGRAPH_CHECK(igraph_dqueue_push(&q, 0));
420
421 j = 1;
422 while ( !igraph_dqueue_empty(&q)) {
423 long int actnode = (long int) igraph_dqueue_pop(&q);
424 IGRAPH_ALLOW_INTERRUPTION();
425 IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) actnode,
426 IGRAPH_ALL));
427 for (i = 0; i < igraph_vector_size(&neis); i++) {
428 long int neighbor = (long int) VECTOR(neis)[i];
429 if (already_added[neighbor] != 0) {
430 continue;
431 }
432 IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
433 j++;
434 already_added[neighbor]++;
435 }
436 }
437
438 /* Connected? */
439 *res = (j == no_of_nodes);
440
441 igraph_Free(already_added);
442 igraph_dqueue_destroy(&q);
443 igraph_vector_destroy(&neis);
444 IGRAPH_FINALLY_CLEAN(3);
445
446 return 0;
447 }
448
449 /**
450 * \function igraph_decompose_destroy
451 * \brief Free the memory allocated by \ref igraph_decompose().
452 *
453 * \param complist The list of graph components, as returned by
454 * \ref igraph_decompose().
455 *
456 * Time complexity: O(c), c is the number of components.
457 */
458
igraph_decompose_destroy(igraph_vector_ptr_t * complist)459 void igraph_decompose_destroy(igraph_vector_ptr_t *complist) {
460 long int i;
461 for (i = 0; i < igraph_vector_ptr_size(complist); i++) {
462 if (VECTOR(*complist)[i] != 0) {
463 igraph_destroy(VECTOR(*complist)[i]);
464 igraph_free(VECTOR(*complist)[i]);
465 }
466 }
467 }
468
469 static int igraph_i_decompose_weak(const igraph_t *graph,
470 igraph_vector_ptr_t *components,
471 long int maxcompno, long int minelements);
472
473 static int igraph_i_decompose_strong(const igraph_t *graph,
474 igraph_vector_ptr_t *components,
475 long int maxcompno, long int minelements);
476
477 /**
478 * \function igraph_decompose
479 * \brief Decompose a graph into connected components.
480 *
481 * Create separate graph for each component of a graph. Note that the
482 * vertex ids in the new graphs will be different than in the original
483 * graph. (Except if there is only one component in the original graph.)
484 *
485 * \param graph The original graph.
486 * \param components This pointer vector will contain pointers to the
487 * subcomponent graphs. It should be initialized before calling this
488 * function and will be resized to hold the graphs. Don't forget to
489 * call \ref igraph_destroy() and free() on the elements of
490 * this pointer vector to free unneeded memory. Alternatively, you can
491 * simply call \ref igraph_decompose_destroy() that does this for you.
492 * \param mode Either \c IGRAPH_WEAK or \c IGRAPH_STRONG for weakly
493 * and strongly connected components respectively.
494 * \param maxcompno The maximum number of components to return. The
495 * first \p maxcompno components will be returned (which hold at
496 * least \p minelements vertices, see the next parameter), the
497 * others will be ignored. Supply -1 here if you don't want to limit
498 * the number of components.
499 * \param minelements The minimum number of vertices a component
500 * should contain in order to place it in the \p components
501 * vector. Eg. supply 2 here to ignore isolated vertices.
502 * \return Error code, \c IGRAPH_ENOMEM if there is not enough memory
503 * to perform the operation.
504 *
505 * Added in version 0.2.</para><para>
506 *
507 * Time complexity: O(|V|+|E|), the number of vertices plus the number
508 * of edges.
509 *
510 * \example examples/simple/igraph_decompose.c
511 */
512
igraph_decompose(const igraph_t * graph,igraph_vector_ptr_t * components,igraph_connectedness_t mode,long int maxcompno,long int minelements)513 int igraph_decompose(const igraph_t *graph, igraph_vector_ptr_t *components,
514 igraph_connectedness_t mode,
515 long int maxcompno, long int minelements) {
516 if (mode == IGRAPH_WEAK || !igraph_is_directed(graph)) {
517 return igraph_i_decompose_weak(graph, components, maxcompno, minelements);
518 } else if (mode == IGRAPH_STRONG) {
519 return igraph_i_decompose_strong(graph, components, maxcompno, minelements);
520 } else {
521 IGRAPH_ERROR("Cannot decompose graph", IGRAPH_EINVAL);
522 }
523
524 return 1;
525 }
526
igraph_i_decompose_weak(const igraph_t * graph,igraph_vector_ptr_t * components,long int maxcompno,long int minelements)527 static int igraph_i_decompose_weak(const igraph_t *graph,
528 igraph_vector_ptr_t *components,
529 long int maxcompno, long int minelements) {
530
531 long int actstart;
532 long int no_of_nodes = igraph_vcount(graph);
533 long int resco = 0; /* number of graphs created so far */
534 char *already_added;
535 igraph_dqueue_t q;
536 igraph_vector_t verts;
537 igraph_vector_t neis;
538 long int i;
539 igraph_t *newg;
540
541
542 if (maxcompno < 0) {
543 maxcompno = LONG_MAX;
544 }
545
546 igraph_vector_ptr_clear(components);
547 IGRAPH_FINALLY(igraph_decompose_destroy, components);
548
549 /* already_added keeps track of what nodes made it into a graph already */
550 already_added = igraph_Calloc(no_of_nodes, char);
551 if (already_added == 0) {
552 IGRAPH_ERROR("Cannot decompose graph", IGRAPH_ENOMEM);
553 }
554 IGRAPH_FINALLY(igraph_free, already_added);
555
556 IGRAPH_CHECK(igraph_dqueue_init(&q, 100));
557 IGRAPH_FINALLY(igraph_dqueue_destroy, &q);
558 IGRAPH_VECTOR_INIT_FINALLY(&verts, 0);
559 IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
560
561 /* add a node and its neighbors at once, recursively
562 then switch to next node that has not been added already */
563 for (actstart = 0; resco < maxcompno && actstart < no_of_nodes; actstart++) {
564
565 if (already_added[actstart]) {
566 continue;
567 }
568 IGRAPH_ALLOW_INTERRUPTION();
569
570 igraph_vector_clear(&verts);
571
572 /* add the node itself */
573 already_added[actstart] = 1;
574 IGRAPH_CHECK(igraph_vector_push_back(&verts, actstart));
575 IGRAPH_CHECK(igraph_dqueue_push(&q, actstart));
576
577 /* add the neighbors, recursively */
578 while (!igraph_dqueue_empty(&q) ) {
579 /* pop from the queue of this component */
580 long int actvert = (long int) igraph_dqueue_pop(&q);
581 IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) actvert,
582 IGRAPH_ALL));
583 /* iterate over the neighbors */
584 for (i = 0; i < igraph_vector_size(&neis); i++) {
585 long int neighbor = (long int) VECTOR(neis)[i];
586 if (already_added[neighbor] == 1) {
587 continue;
588 }
589 /* add neighbor */
590 already_added[neighbor] = 1;
591
592 /* recursion: append neighbor to the queues */
593 IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
594 IGRAPH_CHECK(igraph_vector_push_back(&verts, neighbor));
595 }
596 }
597
598 /* ok, we have a component */
599 if (igraph_vector_size(&verts) < minelements) {
600 continue;
601 }
602
603 newg = igraph_Calloc(1, igraph_t);
604 if (newg == 0) {
605 IGRAPH_ERROR("Cannot decompose graph", IGRAPH_ENOMEM);
606 }
607 IGRAPH_CHECK(igraph_vector_ptr_push_back(components, newg));
608 IGRAPH_CHECK(igraph_induced_subgraph(graph, newg,
609 igraph_vss_vector(&verts),
610 IGRAPH_SUBGRAPH_AUTO));
611 resco++;
612
613 } /* for actstart++ */
614
615 igraph_vector_destroy(&neis);
616 igraph_vector_destroy(&verts);
617 igraph_dqueue_destroy(&q);
618 igraph_Free(already_added);
619 IGRAPH_FINALLY_CLEAN(5); /* + components */
620
621 return 0;
622 }
623
igraph_i_decompose_strong(const igraph_t * graph,igraph_vector_ptr_t * components,long int maxcompno,long int minelements)624 static int igraph_i_decompose_strong(const igraph_t *graph,
625 igraph_vector_ptr_t *components,
626 long int maxcompno, long int minelements) {
627
628
629 long int no_of_nodes = igraph_vcount(graph);
630
631 /* this is a heap used twice for checking what nodes have
632 * been counted already */
633 igraph_vector_t next_nei = IGRAPH_VECTOR_NULL;
634
635 long int i, n, num_seen;
636 igraph_dqueue_t q = IGRAPH_DQUEUE_NULL;
637
638 long int no_of_clusters = 1;
639 long int act_cluster_size;
640
641 igraph_vector_t out = IGRAPH_VECTOR_NULL;
642 const igraph_vector_int_t* tmp;
643
644 igraph_adjlist_t adjlist;
645 igraph_vector_t verts;
646 igraph_t *newg;
647
648 igraph_vector_ptr_clear(components);
649 IGRAPH_FINALLY(igraph_decompose_destroy, components);
650
651 /* The result */
652
653 IGRAPH_VECTOR_INIT_FINALLY(&verts, 0);
654 IGRAPH_VECTOR_INIT_FINALLY(&next_nei, no_of_nodes);
655 IGRAPH_VECTOR_INIT_FINALLY(&out, 0);
656 IGRAPH_DQUEUE_INIT_FINALLY(&q, 100);
657
658 IGRAPH_CHECK(igraph_vector_reserve(&out, no_of_nodes));
659
660 igraph_vector_null(&out);
661
662 IGRAPH_CHECK(igraph_adjlist_init(graph, &adjlist, IGRAPH_OUT));
663 IGRAPH_FINALLY(igraph_adjlist_destroy, &adjlist);
664
665 /* number of components seen */
666 num_seen = 0;
667 /* populate the 'out' vector by browsing a node and following up
668 all its neighbors recursively, then switching to the next
669 unassigned node */
670 for (i = 0; i < no_of_nodes; i++) {
671 IGRAPH_ALLOW_INTERRUPTION();
672
673 /* get all the 'out' neighbors of this node
674 * NOTE: next_nei is initialized [0, 0, ...] */
675 tmp = igraph_adjlist_get(&adjlist, i);
676 if (VECTOR(next_nei)[i] > igraph_vector_int_size(tmp)) {
677 continue;
678 }
679
680 /* add this node to the queue for this component */
681 IGRAPH_CHECK(igraph_dqueue_push(&q, i));
682
683 /* consume the tree from this node ("root") recursively
684 * until there is no more */
685 while (!igraph_dqueue_empty(&q)) {
686 /* this looks up but does NOT consume the queue */
687 long int act_node = (long int) igraph_dqueue_back(&q);
688
689 /* get all neighbors of this node */
690 tmp = igraph_adjlist_get(&adjlist, act_node);
691 if (VECTOR(next_nei)[act_node] == 0) {
692 /* this is the first time we've met this vertex,
693 * because next_nei is initialized [0, 0, ...] */
694 VECTOR(next_nei)[act_node]++;
695 /* back to the queue, same vertex is up again */
696
697 } else if (VECTOR(next_nei)[act_node] <= igraph_vector_int_size(tmp)) {
698 /* we've already met this vertex but it has more children */
699 long int neighbor = (long int) VECTOR(*tmp)[(long int)
700 VECTOR(next_nei)[act_node] - 1];
701 if (VECTOR(next_nei)[neighbor] == 0) {
702 /* add the root of the other children to the queue */
703 IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
704 }
705 VECTOR(next_nei)[act_node]++;
706 } else {
707 /* we've met this vertex and it has no more children */
708 IGRAPH_CHECK(igraph_vector_push_back(&out, act_node));
709 /* this consumes the queue, since there's nowhere to go */
710 igraph_dqueue_pop_back(&q);
711 num_seen++;
712
713 if (num_seen % 10000 == 0) {
714 /* time to report progress and allow the user to interrupt */
715 IGRAPH_PROGRESS("Strongly connected components: ",
716 num_seen * 50.0 / no_of_nodes, NULL);
717 IGRAPH_ALLOW_INTERRUPTION();
718 }
719 }
720 } /* while q */
721 } /* for */
722
723 IGRAPH_PROGRESS("Strongly connected components: ", 50.0, NULL);
724
725 igraph_adjlist_destroy(&adjlist);
726 IGRAPH_FINALLY_CLEAN(1);
727
728 IGRAPH_CHECK(igraph_adjlist_init(graph, &adjlist, IGRAPH_IN));
729 IGRAPH_FINALLY(igraph_adjlist_destroy, &adjlist);
730
731 /* OK, we've the 'out' values for the nodes, let's use them in
732 * decreasing order with the help of the next_nei heap */
733
734 igraph_vector_null(&next_nei); /* mark already added vertices */
735
736 /* number of components built */
737 num_seen = 0;
738 while (!igraph_vector_empty(&out)) {
739 /* consume the vector from the last element */
740 long int grandfather = (long int) igraph_vector_pop_back(&out);
741
742 /* been here, done that
743 * NOTE: next_nei is initialized as [0, 0, ...] */
744 if (VECTOR(next_nei)[grandfather] != 0) {
745 continue;
746 }
747
748 /* collect all the members of this component */
749 igraph_vector_clear(&verts);
750
751 /* this node is gone for any future components */
752 VECTOR(next_nei)[grandfather] = 1;
753 act_cluster_size = 1;
754
755 /* add to component */
756 IGRAPH_CHECK(igraph_vector_push_back(&verts, grandfather));
757 IGRAPH_CHECK(igraph_dqueue_push(&q, grandfather));
758
759 num_seen++;
760 if (num_seen % 10000 == 0) {
761 /* time to report progress and allow the user to interrupt */
762 IGRAPH_PROGRESS("Strongly connected components: ",
763 50.0 + num_seen * 50.0 / no_of_nodes, NULL);
764 IGRAPH_ALLOW_INTERRUPTION();
765 }
766
767 while (!igraph_dqueue_empty(&q)) {
768 /* consume the queue from this node */
769 long int act_node = (long int) igraph_dqueue_pop_back(&q);
770 tmp = igraph_adjlist_get(&adjlist, act_node);
771 n = igraph_vector_int_size(tmp);
772 for (i = 0; i < n; i++) {
773 long int neighbor = (long int) VECTOR(*tmp)[i];
774 if (VECTOR(next_nei)[neighbor] != 0) {
775 continue;
776 }
777 IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
778 VECTOR(next_nei)[neighbor] = 1;
779 act_cluster_size++;
780
781 /* add to component */
782 IGRAPH_CHECK(igraph_vector_push_back(&verts, neighbor));
783
784 num_seen++;
785 if (num_seen % 10000 == 0) {
786 /* time to report progress and allow the user to interrupt */
787 IGRAPH_PROGRESS("Strongly connected components: ",
788 50.0 + num_seen * 50.0 / no_of_nodes, NULL);
789 IGRAPH_ALLOW_INTERRUPTION();
790 }
791 }
792 }
793
794 /* ok, we have a component */
795 if (igraph_vector_size(&verts) < minelements) {
796 continue;
797 }
798
799 newg = igraph_Calloc(1, igraph_t);
800 if (newg == 0) {
801 IGRAPH_ERROR("Cannot decompose graph", IGRAPH_ENOMEM);
802 }
803 IGRAPH_CHECK(igraph_vector_ptr_push_back(components, newg));
804 IGRAPH_CHECK(igraph_induced_subgraph(graph, newg,
805 igraph_vss_vector(&verts),
806 IGRAPH_SUBGRAPH_AUTO));
807
808 no_of_clusters++;
809 }
810
811 IGRAPH_PROGRESS("Strongly connected components: ", 100.0, NULL);
812
813 /* Clean up, return */
814
815 igraph_vector_destroy(&verts);
816 igraph_adjlist_destroy(&adjlist);
817 igraph_vector_destroy(&out);
818 igraph_dqueue_destroy(&q);
819 igraph_vector_destroy(&next_nei);
820 IGRAPH_FINALLY_CLEAN(6); /* + components */
821
822 return 0;
823
824 }
825
826 /**
827 * \function igraph_articulation_points
828 * Find the articulation points in a graph.
829 *
830 * A vertex is an articulation point if its removal increases
831 * the number of connected components in the graph.
832 * \param graph The input graph.
833 * \param res Pointer to an initialized vector, the
834 * articulation points will be stored here.
835 * \return Error code.
836 *
837 * Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
838 *
839 * \sa \ref igraph_biconnected_components(), \ref igraph_clusters(), \ref igraph_bridges()
840 */
841
igraph_articulation_points(const igraph_t * graph,igraph_vector_t * res)842 int igraph_articulation_points(const igraph_t *graph,
843 igraph_vector_t *res) {
844
845 igraph_integer_t no;
846 return igraph_biconnected_components(graph, &no, 0, 0, 0, res);
847 }
848
849 void igraph_i_free_vectorlist(igraph_vector_ptr_t *list);
850
igraph_i_free_vectorlist(igraph_vector_ptr_t * list)851 void igraph_i_free_vectorlist(igraph_vector_ptr_t *list) {
852 long int i, n = igraph_vector_ptr_size(list);
853 for (i = 0; i < n; i++) {
854 igraph_vector_t *v = VECTOR(*list)[i];
855 if (v) {
856 igraph_vector_destroy(v);
857 igraph_Free(v);
858 }
859 }
860 igraph_vector_ptr_destroy(list);
861 }
862
863 /**
864 * \function igraph_biconnected_components
865 * Calculate biconnected components
866 *
867 * A graph is biconnected if the removal of any single vertex (and
868 * its incident edges) does not disconnect it.
869 *
870 * </para><para>
871 * A biconnected component of a graph is a maximal biconnected
872 * subgraph of it. The biconnected components of a graph can be given
873 * by the partition of its edges: every edge is a member of exactly
874 * one biconnected component. Note that this is not true for
875 * vertices: the same vertex can be part of many biconnected
876 * components.
877 *
878 * </para><para>
879 * Somewhat arbitrarily, igraph does not consider components containing
880 * a single vertex only as being biconnected. Isolated vertices will
881 * not be part of any of the biconnected components.
882 *
883 * \param graph The input graph.
884 * \param no The number of biconnected components will be stored here.
885 * \param tree_edges If not a NULL pointer, then the found components
886 * are stored here, in a list of vectors. Every vector in the list
887 * is a biconnected component, represented by its edges. More precisely,
888 * a spanning tree of the biconnected component is returned.
889 * Note you'll have to
890 * destroy each vector first by calling \ref igraph_vector_destroy()
891 * and then \ref igraph_free() on it, plus you need to call
892 * \ref igraph_vector_ptr_destroy() on the list to regain all
893 * allocated memory.
894 * \param component_edges If not a NULL pointer, then the edges of the
895 * biconnected components are stored here, in the same form as for
896 * \c tree_edges.
897 * \param components If not a NULL pointer, then the vertices of the
898 * biconnected components are stored here, in the same format as
899 * for the previous two arguments.
900 * \param articulation_points If not a NULL pointer, then the
901 * articulation points of the graph are stored in this vector.
902 * A vertex is an articulation point if its removal increases the
903 * number of (weakly) connected components in the graph.
904 * \return Error code.
905 *
906 * Time complexity: O(|V|+|E|), linear in the number of vertices and
907 * edges, but only if you do not calculate \c components and
908 * \c component_edges. If you calculate \c components, then it is
909 * quadratic in the number of vertices. If you calculate \c
910 * component_edges as well, then it is cubic in the number of
911 * vertices.
912 *
913 * \sa \ref igraph_articulation_points(), \ref igraph_clusters().
914 *
915 * \example examples/simple/igraph_biconnected_components.c
916 */
917
igraph_biconnected_components(const igraph_t * graph,igraph_integer_t * no,igraph_vector_ptr_t * tree_edges,igraph_vector_ptr_t * component_edges,igraph_vector_ptr_t * components,igraph_vector_t * articulation_points)918 int igraph_biconnected_components(const igraph_t *graph,
919 igraph_integer_t *no,
920 igraph_vector_ptr_t *tree_edges,
921 igraph_vector_ptr_t *component_edges,
922 igraph_vector_ptr_t *components,
923 igraph_vector_t *articulation_points) {
924
925 long int no_of_nodes = igraph_vcount(graph);
926 igraph_vector_long_t nextptr;
927 igraph_vector_long_t num, low;
928 igraph_vector_bool_t found;
929 igraph_vector_int_t *adjedges;
930 igraph_stack_t path;
931 igraph_vector_t edgestack;
932 igraph_inclist_t inclist;
933 long int i, counter, rootdfs = 0;
934 igraph_vector_long_t vertex_added;
935 long int comps = 0;
936 igraph_vector_ptr_t *mycomponents = components, vcomponents;
937
938 IGRAPH_CHECK(igraph_vector_long_init(&nextptr, no_of_nodes));
939 IGRAPH_FINALLY(igraph_vector_long_destroy, &nextptr);
940 IGRAPH_CHECK(igraph_vector_long_init(&num, no_of_nodes));
941 IGRAPH_FINALLY(igraph_vector_long_destroy, &num);
942 IGRAPH_CHECK(igraph_vector_long_init(&low, no_of_nodes));
943 IGRAPH_FINALLY(igraph_vector_long_destroy, &low);
944 IGRAPH_CHECK(igraph_vector_bool_init(&found, no_of_nodes));
945 IGRAPH_FINALLY(igraph_vector_bool_destroy, &found);
946
947 IGRAPH_CHECK(igraph_stack_init(&path, 100));
948 IGRAPH_FINALLY(igraph_stack_destroy, &path);
949 IGRAPH_VECTOR_INIT_FINALLY(&edgestack, 0);
950 IGRAPH_CHECK(igraph_vector_reserve(&edgestack, 100));
951
952 IGRAPH_CHECK(igraph_inclist_init(graph, &inclist, IGRAPH_ALL));
953 IGRAPH_FINALLY(igraph_inclist_destroy, &inclist);
954
955 IGRAPH_CHECK(igraph_vector_long_init(&vertex_added, no_of_nodes));
956 IGRAPH_FINALLY(igraph_vector_long_destroy, &vertex_added);
957
958 if (no) {
959 *no = 0;
960 }
961 if (tree_edges) {
962 igraph_vector_ptr_clear(tree_edges);
963 }
964 if (components) {
965 igraph_vector_ptr_clear(components);
966 }
967 if (component_edges) {
968 igraph_vector_ptr_clear(component_edges);
969 }
970 if (articulation_points) {
971 igraph_vector_clear(articulation_points);
972 }
973 if (component_edges && !components) {
974 mycomponents = &vcomponents;
975 IGRAPH_CHECK(igraph_vector_ptr_init(mycomponents, 0));
976 IGRAPH_FINALLY(igraph_i_free_vectorlist, mycomponents);
977 }
978
979 for (i = 0; i < no_of_nodes; i++) {
980
981 if (VECTOR(low)[i] != 0) {
982 continue; /* already visited */
983 }
984
985 IGRAPH_ALLOW_INTERRUPTION();
986
987 IGRAPH_CHECK(igraph_stack_push(&path, i));
988 counter = 1;
989 rootdfs = 0;
990 VECTOR(low)[i] = VECTOR(num)[i] = counter++;
991 while (!igraph_stack_empty(&path)) {
992 long int n;
993 long int act = (long int) igraph_stack_top(&path);
994 long int actnext = VECTOR(nextptr)[act];
995
996 adjedges = igraph_inclist_get(&inclist, act);
997 n = igraph_vector_int_size(adjedges);
998 if (actnext < n) {
999 /* Step down (maybe) */
1000 long int edge = (long int) VECTOR(*adjedges)[actnext];
1001 long int nei = IGRAPH_OTHER(graph, edge, act);
1002 if (VECTOR(low)[nei] == 0) {
1003 if (act == i) {
1004 rootdfs++;
1005 }
1006 IGRAPH_CHECK(igraph_vector_push_back(&edgestack, edge));
1007 IGRAPH_CHECK(igraph_stack_push(&path, nei));
1008 VECTOR(low)[nei] = VECTOR(num)[nei] = counter++;
1009 } else {
1010 /* Update low value if needed */
1011 if (VECTOR(num)[nei] < VECTOR(low)[act]) {
1012 VECTOR(low)[act] = VECTOR(num)[nei];
1013 }
1014 }
1015 VECTOR(nextptr)[act] += 1;
1016 } else {
1017 /* Step up */
1018 igraph_stack_pop(&path);
1019 if (!igraph_stack_empty(&path)) {
1020 long int prev = (long int) igraph_stack_top(&path);
1021 /* Update LOW value if needed */
1022 if (VECTOR(low)[act] < VECTOR(low)[prev]) {
1023 VECTOR(low)[prev] = VECTOR(low)[act];
1024 }
1025 /* Check for articulation point */
1026 if (VECTOR(low)[act] >= VECTOR(num)[prev]) {
1027 if (articulation_points && !VECTOR(found)[prev]
1028 && prev != i /* the root */) {
1029 IGRAPH_CHECK(igraph_vector_push_back(articulation_points, prev));
1030 VECTOR(found)[prev] = 1;
1031 }
1032 if (no) {
1033 *no += 1;
1034 }
1035
1036 /*------------------------------------*/
1037 /* Record the biconnected component just found */
1038 if (tree_edges || mycomponents) {
1039 igraph_vector_t *v = 0, *v2 = 0;
1040 comps++;
1041 if (tree_edges) {
1042 v = igraph_Calloc(1, igraph_vector_t);
1043 if (!v) {
1044 IGRAPH_ERROR("Out of memory", IGRAPH_ENOMEM);
1045 }
1046 IGRAPH_CHECK(igraph_vector_init(v, 0));
1047 IGRAPH_FINALLY(igraph_vector_destroy, v);
1048 }
1049 if (mycomponents) {
1050 v2 = igraph_Calloc(1, igraph_vector_t);
1051 if (!v2) {
1052 IGRAPH_ERROR("Out of memory", IGRAPH_ENOMEM);
1053 }
1054 IGRAPH_CHECK(igraph_vector_init(v2, 0));
1055 IGRAPH_FINALLY(igraph_vector_destroy, v2);
1056 }
1057
1058 while (!igraph_vector_empty(&edgestack)) {
1059 long int e = (long int) igraph_vector_pop_back(&edgestack);
1060 long int from = IGRAPH_FROM(graph, e);
1061 long int to = IGRAPH_TO(graph, e);
1062 if (tree_edges) {
1063 IGRAPH_CHECK(igraph_vector_push_back(v, e));
1064 }
1065 if (mycomponents) {
1066 if (VECTOR(vertex_added)[from] != comps) {
1067 VECTOR(vertex_added)[from] = comps;
1068 IGRAPH_CHECK(igraph_vector_push_back(v2, from));
1069 }
1070 if (VECTOR(vertex_added)[to] != comps) {
1071 VECTOR(vertex_added)[to] = comps;
1072 IGRAPH_CHECK(igraph_vector_push_back(v2, to));
1073 }
1074 }
1075 if (from == prev || to == prev) {
1076 break;
1077 }
1078 }
1079
1080 if (mycomponents) {
1081 IGRAPH_CHECK(igraph_vector_ptr_push_back(mycomponents, v2));
1082 IGRAPH_FINALLY_CLEAN(1);
1083 }
1084 if (tree_edges) {
1085 IGRAPH_CHECK(igraph_vector_ptr_push_back(tree_edges, v));
1086 IGRAPH_FINALLY_CLEAN(1);
1087 }
1088 if (component_edges) {
1089 igraph_vector_t *nodes = VECTOR(*mycomponents)[comps - 1];
1090 igraph_vector_t *vv = igraph_Calloc(1, igraph_vector_t);
1091 long int ii, no_vert = igraph_vector_size(nodes);
1092 if (!vv) {
1093 IGRAPH_ERROR("Out of memory", IGRAPH_ENOMEM);
1094 }
1095 IGRAPH_CHECK(igraph_vector_init(vv, 0));
1096 IGRAPH_FINALLY(igraph_vector_destroy, vv);
1097 for (ii = 0; ii < no_vert; ii++) {
1098 long int vert = (long int) VECTOR(*nodes)[ii];
1099 igraph_vector_int_t *edges = igraph_inclist_get(&inclist,
1100 vert);
1101 long int j, nn = igraph_vector_int_size(edges);
1102 for (j = 0; j < nn; j++) {
1103 long int e = (long int) VECTOR(*edges)[j];
1104 long int nei = IGRAPH_OTHER(graph, e, vert);
1105 if (VECTOR(vertex_added)[nei] == comps && nei < vert) {
1106 IGRAPH_CHECK(igraph_vector_push_back(vv, e));
1107 }
1108 }
1109 }
1110 IGRAPH_CHECK(igraph_vector_ptr_push_back(component_edges, vv));
1111 IGRAPH_FINALLY_CLEAN(1);
1112 }
1113 } /* record component if requested */
1114 /*------------------------------------*/
1115
1116 }
1117 } /* !igraph_stack_empty(&path) */
1118 }
1119
1120 } /* !igraph_stack_empty(&path) */
1121
1122 if (articulation_points && rootdfs >= 2) {
1123 IGRAPH_CHECK(igraph_vector_push_back(articulation_points, i));
1124 }
1125
1126 } /* i < no_of_nodes */
1127
1128 if (mycomponents != components) {
1129 igraph_i_free_vectorlist(mycomponents);
1130 IGRAPH_FINALLY_CLEAN(1);
1131 }
1132
1133 igraph_vector_long_destroy(&vertex_added);
1134 igraph_inclist_destroy(&inclist);
1135 igraph_vector_destroy(&edgestack);
1136 igraph_stack_destroy(&path);
1137 igraph_vector_bool_destroy(&found);
1138 igraph_vector_long_destroy(&low);
1139 igraph_vector_long_destroy(&num);
1140 igraph_vector_long_destroy(&nextptr);
1141 IGRAPH_FINALLY_CLEAN(8);
1142
1143 return 0;
1144 }
1145
1146
1147 /* igraph_bridges -- find all bridges in the graph */
1148 /* The algorithm is based on https://www.geeksforgeeks.org/bridge-in-a-graph/
1149 but instead of keeping track of the parent of each vertex in the DFS tree
1150 we keep track of its incoming edge. This is necessary to support multigraphs. */
1151
igraph_i_bridges_rec(const igraph_t * graph,const igraph_inclist_t * il,igraph_integer_t u,igraph_integer_t * time,igraph_vector_t * bridges,igraph_vector_bool_t * visited,igraph_vector_int_t * disc,igraph_vector_int_t * low,igraph_vector_int_t * incoming_edge)1152 static int igraph_i_bridges_rec(
1153 const igraph_t *graph, const igraph_inclist_t *il, igraph_integer_t u,
1154 igraph_integer_t *time, igraph_vector_t *bridges, igraph_vector_bool_t *visited,
1155 igraph_vector_int_t *disc, igraph_vector_int_t *low, igraph_vector_int_t *incoming_edge)
1156 {
1157 igraph_vector_int_t *incedges;
1158 long nc; /* neighbour count */
1159 long i;
1160
1161 VECTOR(*visited)[u] = 1;
1162
1163 *time += 1;
1164
1165 VECTOR(*disc)[u] = *time;
1166 VECTOR(*low)[u] = *time;
1167
1168 incedges = igraph_inclist_get(il, u);
1169 nc = igraph_vector_int_size(incedges);
1170 for (i = 0; i < nc; ++i) {
1171 long edge = (long) VECTOR(*incedges)[i];
1172 igraph_integer_t v = IGRAPH_TO(graph, edge) == u ? IGRAPH_FROM(graph, edge) : IGRAPH_TO(graph, edge);
1173
1174 if (! VECTOR(*visited)[v]) {
1175 VECTOR(*incoming_edge)[v] = edge;
1176 IGRAPH_CHECK(igraph_i_bridges_rec(graph, il, v, time, bridges, visited, disc, low, incoming_edge));
1177
1178 VECTOR(*low)[u] = VECTOR(*low)[u] < VECTOR(*low)[v] ? VECTOR(*low)[u] : VECTOR(*low)[v];
1179
1180 if (VECTOR(*low)[v] > VECTOR(*disc)[u]) {
1181 IGRAPH_CHECK(igraph_vector_push_back(bridges, edge));
1182 }
1183 } else if (edge != VECTOR(*incoming_edge)[u]) {
1184 VECTOR(*low)[u] = VECTOR(*low)[u] < VECTOR(*disc)[v] ? VECTOR(*low)[u] : VECTOR(*disc)[v];
1185 }
1186 }
1187
1188 return IGRAPH_SUCCESS;
1189 }
1190
1191 /**
1192 * \function igraph_bridges
1193 * Find all bridges in a graph.
1194 *
1195 * An edge is a bridge if its removal increases the number of (weakly)
1196 * connected components in the graph.
1197 *
1198 * \param graph The input graph.
1199 * \param res Pointer to an initialized vector, the
1200 * bridges will be stored here as edge indices.
1201 * \return Error code.
1202 *
1203 * Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
1204 *
1205 * \sa \ref igraph_articulation_points(), \ref igraph_biconnected_components(), \ref igraph_clusters()
1206 */
1207
igraph_bridges(const igraph_t * graph,igraph_vector_t * bridges)1208 int igraph_bridges(const igraph_t *graph, igraph_vector_t *bridges) {
1209 igraph_inclist_t il;
1210 igraph_vector_bool_t visited;
1211 igraph_vector_int_t disc, low;
1212 igraph_vector_int_t incoming_edge;
1213 long n;
1214 long i;
1215 igraph_integer_t time;
1216
1217 n = igraph_vcount(graph);
1218
1219 IGRAPH_CHECK(igraph_inclist_init(graph, &il, IGRAPH_ALL));
1220 IGRAPH_FINALLY(igraph_inclist_destroy, &il);
1221
1222 IGRAPH_CHECK(igraph_vector_bool_init(&visited, n));
1223 IGRAPH_FINALLY(igraph_vector_bool_destroy, &visited);
1224
1225 IGRAPH_CHECK(igraph_vector_int_init(&disc, n));
1226 IGRAPH_FINALLY(igraph_vector_int_destroy, &disc);
1227
1228 IGRAPH_CHECK(igraph_vector_int_init(&low, n));
1229 IGRAPH_FINALLY(igraph_vector_int_destroy, &low);
1230
1231 IGRAPH_CHECK(igraph_vector_int_init(&incoming_edge, n));
1232 IGRAPH_FINALLY(igraph_vector_int_destroy, &incoming_edge);
1233 for (i = 0; i < n; ++i) {
1234 VECTOR(incoming_edge)[i] = -1;
1235 }
1236
1237 igraph_vector_clear(bridges);
1238
1239 time = 0;
1240 for (i = 0; i < n; ++i)
1241 if (! VECTOR(visited)[i]) {
1242 IGRAPH_CHECK(igraph_i_bridges_rec(graph, &il, i, &time, bridges, &visited, &disc, &low, &incoming_edge));
1243 }
1244
1245 igraph_vector_int_destroy(&incoming_edge);
1246 igraph_vector_int_destroy(&low);
1247 igraph_vector_int_destroy(&disc);
1248 igraph_vector_bool_destroy(&visited);
1249 igraph_inclist_destroy(&il);
1250 IGRAPH_FINALLY_CLEAN(5);
1251
1252 return IGRAPH_SUCCESS;
1253 }
1254