Hi Diego,
Thank you very much.
>>You will need to avoid generating multiple times the same component.
Here is the code:
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) = true && matrix.(j).(i) = true then*
begin
marked.(j) <- true;
component := j :: !component
end
done;
result := !component :: !result
end
done;
!result ;;
Ly
On 2 November 2011 01:55, Diego Olivier Fernandez Pons <[email protected]
> wrote:
> ... 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
>
--
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
