module Make: functor (G : G) -> sig .. end
Functor providing functions to compute strongly connected components of a
graph.
val scc : Components.G.t -> int * (G.V.t -> int)
scc g computes the strongly connected components of
g.
The result is a pair
(n,f) where
n is the number of
components. Components are numbered from
0 to
n-1, and
f is a function mapping each vertex to its component
number. In particular,
f u = f v if and only if
u and
v are in the same component. Another property of the
numbering is that components are numbered in a topological
order: if there is an arc from
u to
v, then
f u >= f u
Not tail-recursive.
Complexity: O(V+E)
The function returned has complexity O(1)
val scc_array : Components.G.t -> G.V.t list array
scc_array g computes the strongly connected components of g.
Components are stored in the resulting array, indexed with a
numbering with the same properties as for scc above.
val scc_list : Components.G.t -> G.V.t list list
scc_list g computes the strongly connected components of g.
The result is a partition of the set of the vertices of g.
The n-th components is (scc_array g).(n-1).