Info_MPSI/MP/JALLAT_kruskal4.ml

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

let g_ex = [|[1;3];[0;2;3;4];[1;4];[0;1;4;5];[1;2;3;5;6];[3;4;6];[4;5]|] ;;

let w_ex = [|[|Infini;Poids 7;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|]
|] ;;

(*Schema classique de tri par insertion, version recursif*)
(*Bien penser que les éléments de la liste et x sont des couples, représentant les arretes*)
let rec insertion_liste_triee (w: int poids array array) (l: 'a list) (x : 'a) : 'a list 
  = match l with
  | [] -> [x]
  | (t1,t2)::q -> if w.(x).(t1) <= w.(x).(t2) then x::l else (t1,t2)::(insertion_liste_triee w q x)
;;

let liste_triee_arrete w = 
  let n = Array.length w and l = ref [] in
  for i=0 to n-1 do
    for j=i+1 to n-1 do
      (*si l'arrete existe, alors seulement on l'insere, on va pas chercher à insérer des arretes qui n'existe pas*)
      if w.(i).(j) <> Infini then l := insertion_liste_triee w !l (i,j)
    done
  done;
  !l
;;

liste_triee_arrete w_ex;;

(*Sert à remettre toutes les composantes connexes dans le tableau représentant les composantes connexes*)
(*Est donc utilisé dès que l'on rajoute une arrête qui ne crée pas de cycle*)
let maj_composantes compo i j =
  let n = Array.length compo and ci = compo.(i) and cj = compo.(j) in
    for k=0 to n-1 do
      if compo.(k) = cj then compo.(k) <- ci
    done
;;
(*Recursive terminale, qui va checker si ça crée un cycle, puis ajouter l'arrete sinon*)
let rec kruskal1_aux compo liste_triee acc = match liste_triee with
(*Si la liste est vide, on a fini, on renvoie l'acc, structure de récursive terminale*)
| [] -> acc
(*Si la liste n'est pas vide, on va regarder si l'arrete crée un cycle*)
(*Si elle crée un cycle, on passe à l'arrete suivante*)
(*Sinon, on ajoute l'arrete à l'acc, et on met à jour les composantes connexes*)
(*On rappelle la fonction avec la liste_triee sans l'arrete ajoutée, et l'acc avec l'arrete ajoutée*)
|(t1,t2)::q -> if compo.(x) = compo.(y) then
    begin
      kruskal1_aux compo q acc
    end
  else
    begin
      maj_composantes compo x y;
      kruskal1_aux compo q ((t1,t2)::acc)
    end
;;

(*Fonction chapeau, qui va tout d'abord créer un tableau des composantes connexes, que j'ai nommé compo*)
(*cette petite function ajoute chaque point à sa propre composante connexe*)
(*puis ont ajoute récursivement les arrêtes, tout en vérifiant qu'elles ne créent pas de cycle*)
(*Travail effectué par kruskal1_aux*)
let kruskal1 (w: int poids array array) : (int * int) list =
  let n = Array.length w and compo = Array.init n (fun i -> i) in
  let liste_triee = liste_triee_arrete w in
  kruskal1_aux compo liste_triee []
;;