graph_parcours.ml

let sommets_exemple = [0;1;2;3;4;5;6;7;8;9] ;;
let arcs_exemple = [(0,1);(1,3);(0,2);(2,3);(3,5);(3,4);(4,2);(4,7);(6,4);(6,7);(7,8);(7,9);(8,9)] ;;

type graphe_1 = bool array array ;;
type graphe_2 = int list array ;;

(* 1.1 *)

let construction_1 sommets arcs =
	let n = (List.length sommets) in
	let arr = Array.make_matrix n n false in
	let rec aux l = match l with
		| [] -> () 
		| ((a, b)::tl) -> begin
			arr.(a).(b) <- true;
			aux tl
		end
	in
	aux arcs;
	arr;;

let sommets_exemple = [0;1;2;3;4;5;6;7;8;9] ;;
let arcs_exemple = [(0,1);(1,3);(0,2);(2,3);(3,5);(3,4);(4,2)
;(4,7);(6,4);(6,7);(7,8);(7,9);(8,9)] ;;

let res = construction_1 sommets_exemple arcs_exemple;;

(* 1.2 *)

List.iter (fun x -> Printf.printf "%d," x) @@ List.filter (fun x -> x<10) [2; 3; 54];;

(*

let construction_2 sommets arcs =
	let n = (List.length sommets) in
	let arr = Array.make n 0 in
	let aux sommet = match sommet with 
		| [] -> []
		| (a::b)::tl ->List.filter (fun (a::b) -> a = arc) arcs;
	let rec aux l = match l with
		| [] -> () 
		| ((a, b)::tl) -> begin
			arr.(a).(b) <- true;
			aux tl
		end
	in
	aux arcs;
	arr;;
*)

let construction_2 list list_c = 
	let taille_l = List.length(list) in 
	let (mat:graphe_2) = Array.make taille_l [] in 
		let rec aux list = match list with 
			| [] -> ()
			| (a,b)::tl -> begin
				mat.(a) <- b::mat.(a);
				aux tl
				end
		in
	aux list_c;
mat;;


let g1 = construction_2 sommets_exemple arcs_exemple;;


let rec appartient a l = match l with
	| [] -> false
	| hd::tl when hd = a -> true
	| hd::tl -> appartient a tl
	;;
(* 
let rec retourne l = match l with
	| [] -> []
	| hd::tl -> (retourne tl) @ [hd]
	;; *)

let retourne l =
	let rec aux l_1 l_2 =
		match l_1 with
			| [] -> l_2
			| hd::tl -> aux tl (hd::l_2)
		in
	aux l [];;

let rec range n = match n with
	| 0 -> []
	| _ -> n::(range (n-1));;

print_string "\n";;

let rec bfs (g:graphe_2) liste_vu liste_a_voir = 
	match liste_a_voir with
	| [] -> liste_vu
	| s::reste -> 
		begin
			if appartient s liste_vu then
				bfs g liste_vu reste
			else
				let voisins = g.(s) in
				bfs g (s::liste_vu) (reste @ voisins)
		end
	;;

let parcours (g:graphe_2) s = retourne @@ bfs g [] [s];;
let res2 = parcours g1 3;;

print_string "\n==parcours==\n";;

List.iter (Printf.printf "%d, ") res2;;

print_string "\n====\n"


let rec liste_num ls n = match ls with
	| [] -> []
	| hd::tl -> (hd, n)::(liste_num tl n)
;;


let rec appartient_couple e ls = match ls with
	| [] -> false
	| (a, n)::tl when a = e -> true
	| hd::tl -> appartient_couple e tl
;;

(* 
let map_list item =
	(string_of_int (snd item))
;; 


List.iter (Printf.printf "%s, ") @@ List.map map_list @@ liste_num [43; 54; 2] 3;;
*)

let rec bfs_distance (g:graphe_2) liste_vu liste_a_voir dist = 
	match liste_a_voir with
	| [] -> liste_vu
	| s::reste -> 
		begin
			if appartient_couple s liste_vu then
				bfs_distance g liste_vu reste (dist+1)
			else
				(* Traitement *)
				let voisins = liste_num (g.(fst(s))) dist in
				bfs_distance g (s::liste_vu) (reste @ voisins) (dist+1)
		end
	;;


let parcours_distance (g:graphe_2) s =
	retourne @@ bfs_distance g [] [(s, 0)] 0;;

print_string "\n===parcours_distance===\n";;

parcours_distance g1 3;;



(* 
let chemin g d a =
	;; *)