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