... sorry, sent too early
> You can compute the strongly connected components directly on the transitive closure. Notice you don't need to transpose it explicitely
// Strong connected components matrix form
let sccmatrix = function matrix ->
let n = Array.length matrix in
let result = Array.make_matrix n n 0 in
for i = 0 to n - 1 do
for j = 0 to n - 1 do
result.(i).(j) <- min matrix.(i).(j) matrix.(j).(i)
done;
done;
result
Now you just have to collect the results in a list of lists.
You will need to avoid generating multiple times the same component.
// Output list of lists from matrix
let output = function matrix ->
let n = Array.length matrix in
let marked = Array.make n false in
let result = ref [] in
for i = 0 to n - 1 do
if (not marked.(i)) then
begin
let component = ref [i] in
for j = i + 1 to n - 1 do
if matrix.(i).(j) = 1 then
begin
marked.(j) <- true;
component := j :: !component
end
done;
result := !component :: !result
end
done;
!result
Since the code uses for loops, it needs references to store the results.
One can do a nicer code and merge the two functions sccmatrix and output
Diego Olivier