Info_MPSI/MP/JALLAT_tri_topo.ml

(*Ce graphe orienté est représenté par une liste de liste, chaque liste donnant l'arrivée des arretes.*)
(*Dans cet exemple, il existe une arrete de 0 vers 1, donc dans la case 1 du tableau, il y a 0*)

let gex1 = [[];[0];[1;3];[];[3];[2;4];[];[0;1;8];[]];;

let rec tri_topo1_aux : 'a list list -> 'b list -> 'b list =
  fun g l ->
    match g with
    | [] -> l
    | a :: gs -> tri_topo1_aux gs l
;;

let tri_topological1 : 'a list list -> 'b list =
  fun g ->
    tri_topo1_aux g [];;

tri_topological1 gex1;;

(*On utilise une fonction auxiliaire pour créer le tri topologique*)
let rec dfs_aux g c i =
  match g with
  |[] -> c
  |t::gs -> if c.(t) = 'B' then dfs_aux gs c i
            else if c.(t) = 'G' then dfs_aux gs c i
            else dfs_aux gs (dfs_aux t c i) i
;;
let dfs g =
  let c = Array.make (List.length g) 'B' in
  dfs_aux g c 0;;

(*utiliser le parcours en profondeur pour créer un tri topologique*)
let tritopologique2 g =
  let c = Array.to_list(dfs g) in
  let rec aux c i =
    match c with
    |[] -> []
    |c::cs -> if c = 'B' then aux cs (i+1)
              else if c = 'G' then aux cs (i+1)
              else aux cs (i+1)
  in aux c 0;;