Ly,
The algorithm for the transitive closure is fine. It's a typical
Floyd-Warshall algorithm
// Make a random graph
let makegraph = fun n -> Array.init n (fun _ -> Array.init n (fun _ ->
Random.int(2)))
// Compute transitive closure (in place)
let transitiveClosure = fun matrix ->
let n = Array.length matrix in
for k = 0 to n - 1 do
for i = 0 to n - 1 do
for j = 0 to n - 1 do
matrix.(i).(j) <- max matrix.(i).(j) (min
matrix.(i).(k) matrix.(k).(j))
done;
done;
done
I guess that by "equivalence class" you mean strongly connected components.
There are linear algorithm (Tarjan, Gabow) that are variants of DFS (depht
first search) with bookkeeping
http://en.wikipedia.org/wiki/Strongly_connected_component
You can compute the strongly connected components directly on the
transitive closure. Notice you don't need to transpose it explicitely
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
