let matrice a n p = let v = make_vect p a in let m = make_vect n v in for i=1 to n-1 do m.(i)<-make_vect p a done; m;; let produit_matriciel pd sm zero m1 m2 = let n=vect_length m1 and p=vect_length m1.(0) and q=vect_length m2.(0) in if vect_length m2 <> p then failwith "Dimensions incompatibles." else let m=matrice zero n q in for i=0 to n-1 do for j=0 to q-1 do for k = 0 to p-1 do m.(i).(j)<- sm m.(i).(j) (pd m1.(i).(k) m2.(k).(j)); done done done; m;; (* Calcul de la somme des n premières puissances de a *) let somme_matricielle sm m1 m2 = let n=vect_length m1 and p=vect_length m1.(0) in if vect_length m2 <> n or vect_length m2.(0) <> p then failwith "Dimensions incompatibles." else let m=matrice m1.(0).(0) n p in for i=0 to n-1 do for j=0 to p-1 do m.(i).(j) <- sm m1.(i).(j) m2.(i).(j) done done; m;; let rec som_puis pd sm zero a n = if n<=0 then failwith "som_puis" else if n=1 then a else somme_matricielle sm a (produit_matriciel pd sm zero a (som_puis pd sm zero a (n-1)));; let composantes = function h -> let n=vect_length h in let v=make_vect n false and l = ref [] in for i = 0 to n-1 do if v.(i)=false then let t=ref [i] in for j = i+1 to n-1 do if h.(i).(j) && h.(j).(i) then ( t:=j::!t; v.(j)<-true) done; l:=!t::!l done; !l;; let contracte = fun g l -> let n=list_length l in let m = matrice false n n in let rec construit i = let rec cherche j r = function | [] -> raise Not_found | t::q -> if mem j t then r else cherche j (r+1) q in function | [] -> () | t::q -> for j=0 to n-1 do if g.(hd t).(j) then m.(i).(cherche j 0 l) <- true done; construit (i+1) q in construit 0 l; m;; let tri_topologique g = let h = som_puis (prefix &&) (prefix ||) false g (vect_length g) in let comp=composantes h in let gc=contracte h comp in let n =vect_length gc in let t = make_vect n false and l = ref [] in let rec elem l i = if i=0 then hd l else elem (tl l) (i-1) in let rec parcours_en_profondeur s = t.(s) <-true; for j=0 to n-1 do if gc.(s).(j) && not t.(j) then parcours_en_profondeur j; done; l:=(elem comp s)::!l; in for i = 0 to n-1 do if t.(i)=false then parcours_en_profondeur i done; rev !l;;