graph :: TarjanAlgorithm :: defaultinit
# Computing the strongly connected components using Tarjan's algorithm
private class TarjanAlgorithm[V: Object]
# The graph whose strongly connected components will be computed
var graph: Digraph[V]
# The strongly connected components computed in Tarjan's algorithm
var sccs = new DisjointSet[V]
# An index used for Tarjan's algorithm
var index = 0
# A stack used for Tarjan's algorithm
var stack: Queue[V] = (new Array[V]).as_lifo
# A map associating with each vertex its index
var vertex_to_index = new HashMap[V, Int]
# A map associating with each vertex its ancestor in Tarjan's algorithm
var ancestor = new HashMap[V, Int]
# True if and only if the vertex is in the stack
var in_stack = new HashSet[V]
# Returns the strongly connected components of a graph
fun strongly_connected_components: DisjointSet[V]
do
for u in graph.vertices_iterator do sccs.add(u)
for v in graph.vertices_iterator do
visit(v)
end
return sccs
end
# The recursive part of Tarjan's algorithm
fun visit(u: V)
do
vertex_to_index[u] = index
ancestor[u] = index
index += 1
stack.add(u)
in_stack.add(u)
for v in graph.successors(u) do
if not vertex_to_index.keys.has(v) then
visit(v)
ancestor[u] = ancestor[u].min(ancestor[v])
else if in_stack.has(v) then
ancestor[u] = ancestor[u].min(vertex_to_index[v])
end
end
if vertex_to_index[u] == ancestor[u] then
var v
loop
v = stack.take
in_stack.remove(v)
sccs.union(u, v)
if u == v then break
end
end
end
end
lib/graph/digraph.nit:616,1--669,3