Info_MPSI/MP/JALLAT_kurska2.ml

type 'a poids = Poids of 'a | Infini;;

let g = [|
  [|Infini; Poids(9); Infini; Poids(5); Infini; Infini; Infini|];
  [|Poids(7); Infini; Poids(8); Poids(9); Poids(7); Infini; Infini|];
  [|Infini; Poids(8); Infini; Infini; Poids(5); Infini; Infini|];
  [|Poids(5); Poids(9); Infini; Infini; Poids(15); Poids(6); Infini|];
  [|Infini; Poids(7); Poids(5); Poids(15); Infini; Poids(8); Poids(9)|];
  [|Infini; Infini; Infini; Poids(6); Poids(8); Infini; Poids(11)|];
  [|Infini; Infini; Infini; Infini; Poids(9); Poids(11); Infini|];
|];;

(* Žcrire plut™t Poids 9 que Poids(9) , comme on Žcrit plut™t f x que f(x) *)

let rec insere i x l =
  match l with
  | [] -> [i]
  | t::q -> if x > t then i :: l else t :: (insere i x q)
;;

(* myst�re ... i sera l'ar�te et x le poids, merci pour les explications ! *)
(* tu compares x et t , x et t sont donc de m�me type *)

let liste_triee_arrete w =
  let l = ref [] and n = Array.length w.(0) in
  for i = 0 to n - 2 do
    for j = i + 1 to (n - 1) do
      if w.(i).(j) <> Infini then
        match w.(i).(j) with
        | Poids(p) -> (l := insere (i, j) p !l)
        | Infini -> ()
      else ()
    done;
  done;
  !l
;;

(* mauvaise orientation : une liste, tu proposes une fonction rŽcursive et tu Žvites les rŽfŽrences de listes *)
(* tu tries par ordre dŽcroissant, non ? *)
(* la fonction insere oblige (i,j) et p ˆ �tre de m�me type, c'est pour �a que w doit etre de type (int*int) ... *)
(* l'alternative et le filtrage, un peu redondant ... *)

let n = Array.length g.(0);;

let composantes = Array.make n 0;;
(* tous les sommets sont dans la composante connexe du sommet 0 ? *)

let aretes = liste_triee_arrete g;;

let aux i j t =
  let ci = composantes.(i) and cj = composantes.(j) in
  match ci = cj with
  | true -> ()
  | false ->
    t := (i, j) :: !t;
    for k = 0 to n - 1 do
      if composantes.(k) = cj then composantes.(k) <- ci;
    done
;;

(* t a une valeur avant l'appel ˆ aux, il est modifiŽ pendant aux et il reprend sa valeur initiale apr�s aux,
la structure d'une rŽfŽrence n'est pas la m�me chose qu'un mutable  *)
(* la fonction aux devrait renvoyer t *)

let rec kaux1 w aretes t =
  match aretes with
  | [] -> t
  | a::aq -> let (i, j) = a in aux i j t; kaux1 w aq t
;;

(* recursivitŽ terminale en appelant kaux1 avant (aux i j t) ˆ la place de t *)

let kruskal1 w =
  let aretes = liste_triee_arrete w in
  let t = ref [] in
  kaux1 w aretes t;
  !t
;;

(* tu corriges, tu testes et je regarde la suite apr�s et avec des commentaires *)

(* Seconde partie *)
(*une fonction chemin w u v, qui renvoie true s'il existe un chemin entre u et v*)
let chemin w u v =
  let n = Array.length w in
  let rec aux i =
    match i = n with
    | true -> false
    | false ->
        match w.(u).(i) with
        | Infini -> aux (i+1)
        | Poids(p) ->
            match w.(i).(v) with
            | Infini -> aux (i+1)
            | Poids(q) -> true
  in aux 0
;;


let kruskal2 w =
  let n = Array.length w in
  let rec aux i =
    match i = n with
    | true -> []
    | false ->
        match w.(i) with
        | [] -> aux (i+1)
        | t::q ->
            match chemin w t i with
            | true -> (t, i) :: (aux (i+1))
            | false -> aux (i+1)
  in aux 0
;;