Two vertices u
and v
belong to the same strongly connected
component if and only if there exists a path from u
to v
and there exists a path from v
to u
.
This is computed in linear time (Tarjan's algorithm).
var g = new HashDigraph[Int]
g.add_arc(1, 2)
g.add_arc(2, 3)
g.add_arc(3, 1)
g.add_arc(3, 4)
g.add_arc(4, 5)
g.add_arc(5, 6)
g.add_arc(6, 5)
assert g.strongly_connected_components.number_of_subsets == 3
# Returns the strongly connected components of this digraph.
#
# Two vertices `u` and `v` belong to the same strongly connected
# component if and only if there exists a path from `u` to `v`
# and there exists a path from `v` to `u`.
#
# This is computed in linear time (Tarjan's algorithm).
#
# ~~~
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# g.add_arc(3, 1)
# g.add_arc(3, 4)
# g.add_arc(4, 5)
# g.add_arc(5, 6)
# g.add_arc(6, 5)
# assert g.strongly_connected_components.number_of_subsets == 3
# ~~~
fun strongly_connected_components: DisjointSet[V]
do
var tarjanAlgorithm = new TarjanAlgorithm[V](self)
return tarjanAlgorithm.strongly_connected_components
end
lib/graph/digraph.nit:590,2--613,4