289:
31:
383:
of vertices that have been explored by the search but not yet assigned to a component, and calculates "low numbers" of each vertex (an index number of the highest ancestor reachable in one step from a descendant of the vertex) which it uses to determine when a set of vertices should be popped off the
416:
queries, and such algorithms are usually called reachability-based SCC algorithms. The idea of this approach is to pick a random pivot vertex and apply forward and backward reachability queries from this vertex. The two queries partition the vertex set into 4 subsets: vertices reached by both,
391:
uses a depth-first search, like Tarjan's algorithm, but with two stacks. One of the stacks is used to keep track of the vertices not yet assigned to components, while the other keeps track of the current path in the depth-first search tree. The first linear time version of this algorithm was
539:, a partition of the edges into a sequence of directed paths and cycles such that the first subgraph in the sequence is a cycle, and each subsequent subgraph is either a cycle sharing one vertex with previous subgraphs, or a path sharing its two endpoints with previous subgraphs.
440:
of the graph is small); and (2) the independence between the subtasks in the divide-and-conquer process. This algorithm performs well on real-world graphs, but does not have theoretical guarantee on the parallelism (consider if a graph has no edges, the algorithm requires
417:
either one, or none of the searches. One can show that a strongly connected component has to be contained in one of the subsets. The vertex subset reached by both searches forms a strongly connected component, and the algorithm then recurses on the other 3 subsets.
480:, the problem of adding as few edges as possible to make a graph strongly connected. When used in conjunction with the Gilbert or Erdős-Rényi models with node relabelling, the algorithm is capable of generating any strongly connected graph on
213:
in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first. In a directed graph
352:
uses two passes of depth-first search. The first, in the original graph, is used to choose the order in which the outer loop of the second depth-first search tests vertices for having been visited already and
265:
can be included in the subgraph without breaking its property of being strongly connected. The collection of strongly connected components forms a partition of the set of vertices of
136:
372:
456:) still holds. Furthermore, the queries then can be batched in a prefix-doubling manner (i.e. 1, 2, 4, 8 queries) and run simultaneously in one round. The overall
296:
is the condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.
408:
Previous linear-time algorithms are based on depth-first search which is generally considered hard to parallelize. Fleischer et al. in 2000 proposed a
400:
Although
Kosaraju's algorithm is conceptually simple, Tarjan's and the path-based algorithm require only one depth-first search rather than two.
906:
825:
388:
516:
554:. One way to prove this result is to find an ear decomposition of the underlying undirected graph and then orient each ear consistently.
432:) more than the classic algorithms. The parallelism comes from: (1) the reachability queries can be parallelized more easily (e.g. by a
122:
568:
876:
689:
649:
476:
Peter M. Maurer describes an algorithm for generating random strongly connected graphs, based on a modification of an algorithm for
477:
457:
129:
468:
reachability queries, which is probably the optimal parallelism that can be achieved using the reachability-based approach.
1005:
361:
of the original graph, and each recursive exploration finds a single new strongly connected component. It is named after
409:
1064:
178:
55:
1049:
674:
Proceedings of the
International Conference on High Performance Computing, Networking, Storage and Analysis - SC '13
598:
Nuutila, Esko; Soisalon-Soininen, Eljas (1994), "On finding the strongly connected components in a directed graph",
640:
380:
448:
Blelloch et al. in 2016 shows that if the reachability queries are applied in a random order, the cost bound of O(
748:
85:
1069:
324:
is strongly connected and every non-trivial strongly connected component contains at least one directed cycle.
437:
349:
174:
551:
305:
293:
60:
573:
563:
110:
627:
433:
234:
802:
543:
226:
are said to be strongly connected to each other if there is a path in each direction between them.
210:
70:
841:
1022:
982:
893:
765:
695:
496:
problems (systems of
Boolean variables with constraints on the values of pairs of variables): as
393:
342:
301:
170:
90:
46:
932:(1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas",
849:
Proceedings of the 28th ACM Symposium on
Parallelism in Algorithms and Architectures - SPAA '16
960:
902:
872:
821:
685:
645:
547:
536:
509:
242:
105:
1014:
972:
941:
862:
852:
813:
757:
724:
677:
631:
623:
607:
524:
493:
238:
95:
17:
1000:
782:
520:
362:
358:
258:
230:
80:
667:"On fast parallel detection of strongly connected components (SCC) in small-world graphs"
500:
showed, a 2-satisfiability instance is unsatisfiable if and only if there is a variable
635:
578:
321:
317:
202:
154:
715:(1981), "A strong-connectivity algorithm and its applications in data flow analysis",
1058:
986:
945:
929:
743:
729:
611:
376:
1003:(1939), "A theorem on graphs, with an application to a problem on traffic control",
769:
508:
and its negation are both contained in the same strongly connected component of the
712:
699:
413:
366:
162:
288:
666:
182:
150:
281:
consists of a single vertex which is not connected to itself with an edge, and
65:
817:
484:
nodes, without restriction on the kinds of structures that can be generated.
857:
681:
354:
338:
320:
it has no strongly connected subgraphs with more than one vertex, because a
75:
977:
492:
Algorithms for finding strongly connected components may be used to solve
177:
that are themselves strongly connected. It is possible to test the strong
867:
420:
The expected sequential running time of this algorithm is shown to be O(
1026:
812:, Lecture Notes in Computer Science, vol. 1800, pp. 505–511,
550:
in such a way that it becomes strongly connected, if and only if it is
379:
in 1972, performs a single pass of depth-first search. It maintains a
27:
Partition of a graph whose components are reachable from all vertices
1044:
Java implementation for computation of strongly connected components
1018:
761:
901:, Int'l Conf. Modeling, Sim. and Vis. Methods MSV'17, CSREA Press,
1043:
287:
29:
535:
A directed graph is strongly connected if and only if it has an
30:
365:, who described it (but did not publish his results) in 1978;
357:
explores them if not. The second depth-first search is on the
218:
that may not itself be strongly connected, a pair of vertices
181:
of a graph, or to find its strongly connected components, in
1046:
in the jBPT library (see
StronglyConnectedComponents class).
840:
Blelloch, Guy E.; Gu, Yan; Shun, Julian; Sun, Yihan (2016),
801:
Fleischer, Lisa K.; Hendrickson, Bruce; Pınar, Ali (2000),
515:
Strongly connected components are also used to compute the
803:"On Identifying Strongly Connected Components in Parallel"
746:(1972), "Depth-first search and linear graph algorithms",
665:
Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013),
261:
with this property: no additional edges or vertices from
345:
compute strongly connected components in linear time.
523:, according to whether or not they can be part of a
1050:
C++ implementation of
Strongly Connected Components
644:, Second Edition. MIT Press and McGraw-Hill, 2001.
842:"Parallelism in Randomized Incremental Algorithms"
497:
257:is a subgraph that is strongly connected, and is
373:Tarjan's strongly connected components algorithm
34:Graph with strongly connected components marked
660:
658:
717:Computers & Mathematics with Applications
304:to a single vertex, the resulting graph is a
130:
8:
895:Generating strongly connected random graphs
472:Generating random strongly connected graphs
137:
123:
37:
976:
963:(1958), "Coverings of bipartite graphs",
866:
856:
728:
300:If each strongly connected component is
652:. Section 22.5, pp. 552–557.
590:
45:
519:, a classification of the edges of a
389:path-based strong component algorithm
7:
928:Aspvall, Bengt; Plass, Michael F.;
810:Parallel and Distributed Processing
569:Connected component (graph theory)
498:Aspvall, Plass & Tarjan (1979)
233:of being strongly connected is an
25:
436:(BFS), and it can be fast if the
269:. A strongly connected component
789:, NJ: Prentice Hall, Ch. 25
517:Dulmage–Mendelsohn decomposition
478:strong connectivity augmentation
333:DFS-based linear-time algorithms
892:Maurer, P. M. (February 2018),
934:Information Processing Letters
600:Information Processing Letters
316:. A directed graph is acyclic
1:
1006:American Mathematical Monthly
546:, an undirected graph may be
404:Reachability-based algorithms
247:strongly connected components
167:strongly connected components
165:from every other vertex. The
946:10.1016/0020-0190(79)90002-4
730:10.1016/0898-1221(81)90008-0
612:10.1016/0020-0190(94)90047-7
251:strongly connected component
101:Strongly connected component
787:A Discipline of Programming
428:), a factor of O(log
384:stack into a new component.
369:later published it in 1981.
169:of a directed graph form a
18:Condensation (graph theory)
1086:
641:Introduction to Algorithms
86:K-connectivity certificate
749:SIAM Journal on Computing
445:) levels of recursions).
818:10.1007/3-540-45591-4_68
460:of this algorithm is log
157:, a graph is said to be
858:10.1145/2935764.2935766
682:10.1145/2503210.2503246
978:10.4153/cjm-1958-052-0
306:directed acyclic graph
297:
294:directed acyclic graph
61:Algebraic connectivity
35:
959:Dulmage, A. L. &
574:Modular decomposition
564:Clique (graph theory)
291:
33:
851:, pp. 467–478,
628:Charles E. Leiserson
434:breadth-first search
350:Kosaraju's algorithm
253:of a directed graph
235:equivalence relation
243:equivalence classes
161:if every vertex is
71:Rank (graph theory)
1065:Graph connectivity
412:approach based on
410:divide-and-conquer
394:Edsger W. Dijkstra
343:depth-first search
298:
249:. Equivalently, a
207:strongly connected
159:strongly connected
91:Pixel connectivity
47:Graph connectivity
41:Relevant topics on
36:
961:Mendelsohn, N. S.
930:Tarjan, Robert E.
908:978-1-60132-465-8
827:978-3-540-67442-9
676:, pp. 1–11,
537:ear decomposition
512:of the instance.
510:implication graph
239:induced subgraphs
147:
146:
106:Biconnected graph
16:(Redirected from
1077:
1031:
1029:
997:
991:
989:
980:
956:
950:
948:
925:
919:
918:
917:
915:
900:
889:
883:
881:
870:
860:
846:
837:
831:
830:
807:
798:
792:
790:
783:Dijkstra, Edsger
779:
773:
772:
740:
734:
733:
732:
709:
703:
702:
671:
662:
653:
632:Ronald L. Rivest
624:Thomas H. Cormen
621:
615:
614:
595:
552:2-edge-connected
544:Robbins' theorem
525:perfect matching
494:2-satisfiability
452: log
424: log
139:
132:
125:
96:Vertex separator
38:
21:
1085:
1084:
1080:
1079:
1078:
1076:
1075:
1074:
1070:Directed graphs
1055:
1054:
1040:
1035:
1034:
1019:10.2307/2303897
999:
998:
994:
958:
957:
953:
927:
926:
922:
913:
911:
909:
898:
891:
890:
886:
879:
844:
839:
838:
834:
828:
805:
800:
799:
795:
781:
780:
776:
762:10.1137/0201010
742:
741:
737:
711:
710:
706:
692:
669:
664:
663:
656:
622:
618:
597:
596:
592:
587:
560:
533:
531:Related results
521:bipartite graph
490:
474:
463:
406:
375:, published by
363:S. Rao Kosaraju
359:transpose graph
335:
330:
231:binary relation
199:
155:directed graphs
143:
81:St-connectivity
28:
23:
22:
15:
12:
11:
5:
1083:
1081:
1073:
1072:
1067:
1057:
1056:
1053:
1052:
1047:
1039:
1038:External links
1036:
1033:
1032:
1013:(5): 281–283,
1001:Robbins, H. E.
992:
951:
940:(3): 121–123,
920:
907:
884:
877:
832:
826:
793:
774:
756:(2): 146–160,
735:
704:
690:
654:
636:Clifford Stein
616:
589:
588:
586:
583:
582:
581:
579:Weak component
576:
571:
566:
559:
556:
532:
529:
527:in the graph.
489:
486:
473:
470:
461:
405:
402:
398:
397:
385:
370:
334:
331:
329:
326:
322:directed cycle
318:if and only if
209:if there is a
203:directed graph
198:
195:
145:
144:
142:
141:
134:
127:
119:
116:
115:
114:
113:
108:
103:
98:
93:
88:
83:
78:
73:
68:
63:
58:
50:
49:
43:
42:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1082:
1071:
1068:
1066:
1063:
1062:
1060:
1051:
1048:
1045:
1042:
1041:
1037:
1028:
1024:
1020:
1016:
1012:
1008:
1007:
1002:
996:
993:
988:
984:
979:
974:
970:
966:
965:Can. J. Math.
962:
955:
952:
947:
943:
939:
935:
931:
924:
921:
910:
904:
897:
896:
888:
885:
880:
878:9781450342100
874:
869:
868:1721.1/146176
864:
859:
854:
850:
843:
836:
833:
829:
823:
819:
815:
811:
804:
797:
794:
788:
784:
778:
775:
771:
767:
763:
759:
755:
751:
750:
745:
744:Tarjan, R. E.
739:
736:
731:
726:
722:
718:
714:
713:Sharir, Micha
708:
705:
701:
697:
693:
691:9781450323789
687:
683:
679:
675:
668:
661:
659:
655:
651:
650:0-262-03293-7
647:
643:
642:
637:
633:
629:
625:
620:
617:
613:
609:
605:
601:
594:
591:
584:
580:
577:
575:
572:
570:
567:
565:
562:
561:
557:
555:
553:
549:
545:
542:According to
540:
538:
530:
528:
526:
522:
518:
513:
511:
507:
503:
499:
495:
487:
485:
483:
479:
471:
469:
467:
459:
455:
451:
446:
444:
439:
435:
431:
427:
423:
418:
415:
411:
403:
401:
395:
392:published by
390:
386:
382:
378:
377:Robert Tarjan
374:
371:
368:
364:
360:
356:
351:
348:
347:
346:
344:
340:
332:
327:
325:
323:
319:
315:
311:
307:
303:
295:
290:
286:
284:
280:
276:
272:
268:
264:
260:
256:
252:
248:
244:
240:
236:
232:
227:
225:
221:
217:
212:
208:
204:
196:
194:
192:
189: +
188:
184:
180:
176:
172:
168:
164:
160:
156:
152:
140:
135:
133:
128:
126:
121:
120:
118:
117:
112:
109:
107:
104:
102:
99:
97:
94:
92:
89:
87:
84:
82:
79:
77:
74:
72:
69:
67:
64:
62:
59:
57:
54:
53:
52:
51:
48:
44:
40:
39:
32:
19:
1010:
1004:
995:
968:
964:
954:
937:
933:
923:
914:December 27,
912:, retrieved
894:
887:
848:
835:
809:
796:
786:
777:
753:
747:
738:
720:
716:
707:
673:
639:
619:
603:
599:
593:
541:
534:
514:
505:
501:
491:
488:Applications
481:
475:
465:
453:
449:
447:
442:
429:
425:
421:
419:
414:reachability
407:
399:
367:Micha Sharir
336:
313:
310:condensation
309:
299:
282:
278:
274:
270:
266:
262:
254:
250:
246:
228:
223:
219:
215:
206:
200:
190:
186:
185:(that is, Θ(
179:connectivity
166:
158:
151:mathematical
148:
100:
56:Connectivity
971:: 517–534,
606:(1): 9–14,
355:recursively
292:The yellow
285:otherwise.
283:non-trivial
245:are called
197:Definitions
193: )).
183:linear time
1059:Categories
585:References
504:such that
339:algorithms
328:Algorithms
302:contracted
273:is called
237:, and the
205:is called
153:theory of
66:Cycle rank
987:123363425
723:: 67–72,
341:based on
175:subgraphs
171:partition
163:reachable
76:SPQR tree
785:(1976),
770:16467262
558:See also
548:oriented
438:diameter
396:in 1976.
337:Several
1027:2303897
700:2156324
464:
275:trivial
259:maximal
241:of its
149:In the
1025:
985:
905:
875:
824:
768:
698:
688:
648:
634:, and
308:, the
111:Bridge
1023:JSTOR
983:S2CID
899:(PDF)
845:(PDF)
806:(PDF)
766:S2CID
696:S2CID
670:(PDF)
381:stack
277:when
173:into
916:2019
903:ISBN
873:ISBN
822:ISBN
686:ISBN
646:ISBN
458:span
387:The
229:The
222:and
211:path
1015:doi
973:doi
942:doi
863:hdl
853:doi
814:doi
758:doi
725:doi
678:doi
608:doi
312:of
1061::
1021:,
1011:46
1009:,
981:,
969:10
967:,
936:,
871:,
861:,
847:,
820:,
808:,
764:,
752:,
719:,
694:,
684:,
672:,
657:^
638:.
630:,
626:,
604:49
602:,
441:O(
201:A
1030:.
1017::
990:.
975::
949:.
944::
938:8
882:.
865::
855::
816::
791:.
760::
754:1
727::
721:7
680::
610::
506:v
502:v
482:n
466:n
462:2
454:n
450:n
443:n
430:n
426:n
422:n
314:G
279:C
271:C
267:G
263:G
255:G
224:v
220:u
216:G
191:E
187:V
138:e
131:t
124:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
