#open "graphics";;
open_graph "600x600+0-0";;
#open "printf" ;;

type graphe = {mutable s : int ; (* nb de sommets *)
			mutable a : int ; (* nb d'arètes *)
			mutable w : (int*int) -> int ; (* fn de pondération *)
			mutable l : (int list) vect ; (* listes d'adjacence *)			
			mutable ar : (int*int) vect ; (* représentation ensembliste : (debut, fin) *)
			mutable pos : int vect vect
			};;


(****************** Gestion du type graphe ************************************************)

let check_graph g =
	let a = ref 0 and b = ref true in
	if (vect_length g.l = g.s)&&(
		for i = 0 to g.s-1 do
			a:= !a + list_length g.l.(i)
		done; !a = g.a ) 
		then print_string "listes d'adjacence OK \n";
	if (vect_length g.ar = g.a)&&(
		for i = 0 to g.a -1 do
			let (d,f) = g.ar.(i) in
			b := !b&&(0<=d)&&(d<g.s)&&(0<=f)&&(f<g.s)
		done; !b)
		then print_string "ensembliste OK \n";
	if (!a=g.a) && !b && (
		let c= ref true in
		for i = 0 to g.a-1 do
			let (d,f) = g.ar.(i) in
			c := !c && (mem f g.l.(d))
		done; !c)
		then print_string "les 2 définitions correspondent \n" ;;


let ens_of_la g =
	let rec aux i u = function
		[] -> i
		|h::t -> (g.ar.(i) <- (u,h) ; aux (i+1) u t)
	in
		g.ar <- make_vect g.a (0,0) ;
		let i = ref 0 in
		for u = 0 to g.a - 1 do
			i := aux !i u g.l.(u)
		done;
	g;;

let la_of_ens g =
	for i = 0 to g.a-1 do
		let (d,f) = g.ar.(i) in
		g.l.(d) <- f::g.l.(d)
	done;
	g;;


let rand_graph s a min max =  							(* -1000 < min <= w < max <1000 *)
	let ar = make_vect a (0,0) 
	and l= make_vect s [] 
	and (d,f)= (ref (random__int s), ref (random__int s)) 
	and W = make_vect s [] 								(* W va permettre d'associer un poids aléatoire à chaque élément de l *)
	in
	for i = 0 to a-1 do
		while (mem !f l.(!d)) do
			d:= random__int s ;
			f:= random__int s 
		done;
		l.(!d) <- !f :: l.(!d) ;
		W.(!d) <- (!f, (random__int (max-min) + min)) :: W.(!d) ;
		ar.(i) <- (!d,!f) 
	done;	
	let w (u,v) =										(* comme ça w prend pas trop de place en mémoire *)
		if mem v l.(u) then assoc v W.(u)
		else max_int 
	in	
	{s=s; a=a; w=w; l=l; ar= ar ; pos = [|[||]|] }
;;



let mat_from_w g =
	let t = make_matrix g.s g.s max_int in
	for i = 0 to g.s-1 do
		for j = 0 to g.s-1 do
			t.(i).(j) <- g.w (i,j)
		done;
	done;
	t ;;
	
let w_from_mat t = function
	(u,v) -> t.(u).(v) ;;




(****************** Affichage des graphes *************************************************)


let trouver_sommet t x y gs =
	let s = ref (-1) 
	and i = ref (gs -1) 
	in
		while (!s = -1)&(!i > -1) do
			let xs = t.(!i).(0) and ys = t.(!i).(1) in
			if (xs>x-8)&(xs<x+8)&(ys>y-8)&(ys<y+8) then s := !i ;
			i := !i -1
		done;
	!s ;;


let draw_graph p g poids =			(* t stock les positions des sommets du graphe ; poids = true pour voir les poids *)
	clear_graph () ;				(* p tableau des prédecesseurs : [||] pour pas voir chemins *)
	set_color blue ;
	let chemins = not (p=[||]) 
	and t = g.pos in
	for i = 0 to g.a -1 do
		let (d,f) = g.ar.(i) in
		if chemins then
				if d = p.(f) then
					set_color green
				else set_color blue ;
		let (x1,y1,x2,y2)=(t.(d).(0), t.(d).(1), t.(f).(0), t.(f).(1)) in
		if d=f then
			draw_circle (x1+8) (y1+8) 10 
		else	
			(
			moveto x1 y1  ;
			lineto x2 y2 ;
			let y0 = (x2-x1) and x0 = (y1-y2) in 
			let n0 = int_of_float (sqrt (float_of_int(x0*x0 + y0*y0))) in
			let xo = (8*x0+1)/(2*n0) and yo = (8*y0+1)/(2*n0) 
			and xn = (10*(x2-x1)/n0) and yn = (10*(y2-y1)/n0) in
			fill_poly [|(x2-xn), (y2-yn) ;(x2-2*xn+xo),(y2-2*yn+yo) ;(x2-2*xn-xo),(y2-2*yn-yo) |]
			);		
		if d=f then
			moveto (t.(d).(0)+10) (t.(d).(1)+8)
		else
			moveto ((t.(d).(0)+2*t.(f).(0))/3 -4)				(* le numéro de l'arète est plus proche *)
		 		  ((t.(d).(1)+2*t.(f).(1))/3 -9) 	 			(* de la destination que du départ *)
		 	;
		if poids then draw_string (string_of_int (g.w (d,f)))
		else draw_string (string_of_int i)
	done ;
	for i = 0 to g.s -1 do
		set_color white ; fill_circle (t.(i).(0)) (t.(i).(1)) 9 ;
		set_color red ;  moveto (t.(i).(0)-4) (t.(i).(1)-9) ; draw_string (string_of_int i);
		set_color red ; draw_circle (t.(i).(0)) (t.(i).(1)) 9 ;
	done;;
	




let voir g p =										(* p tableau des prédecesseurs : [||] pour pas voir chemins *)
	if vect_length g.pos < g.s then
		(
		g.pos <- make_matrix g.s 2 0 ;  				(* t stock les positions des sommets du graphe *)
		for i = 0 to g.s -1 do
			g.pos.(i).(0) <- random__int 600;
			g.pos.(i).(1) <- random__int 400
		done;		
		);
		let t = g.pos in
	let modif = ref true 
	and poids = ref true in
	while !modif do
		draw_graph p g !poids ;
		let e = wait_next_event [Key_pressed;Button_down] in
		if e.button then
			(
			let x = e.mouse_x and y = e.mouse_y in
			let s= trouver_sommet t x y g.s in
			if s= -1 then ()
			else ( 
				let button = ref true in
				while !button do
					draw_graph p g !poids;
					let e = wait_next_event [Mouse_motion;Button_up] in
					t.(s).(0) <- e.mouse_x ;
					t.(s).(1) <- e.mouse_y ;
					button := e.button
				done;
				)
			)
		else
			if e.keypressed then
				if e.key = `p` then poids := not !poids
				else modif := false ;
	done;
	draw_graph p g !poids ;;
					

(* voir (rand_graph 10 20 0 10) [||] ;; *)



(****************** Sous-programmes courants **********************************************)


let init g s =
	let d = make_vect g.s max_int
	and p = make_vect g.s (-1) in
	d.(s) <- 0 ;
	(d,p) ;;


let relacher (d,p) u v w =
	if (d.(u) < max_int)&&(d.(v)> d.(u) + w(u,v)) then
		(
		d.(v) <- d.(u) + w(u,v) ;
		p.(v) <- u 
		);;



(************************** Bellman-Ford **************************************************)

let bellman_ford g s =
	let (d,p) = init g s in
	for i = 2 to g.s do
		for j = 0 to g.a-1 do
			let (u,v) = g.ar.(j) in
			relacher (d,p) u v g.w 
		done;
	done;
	for j= 0 to g.a -1 do
		let (u,v) = g.ar.(j) in
		if (d.(u)< max_int) && (d.(v)>d.(u) + g.w (u,v))
		then failwith "Il y a un circuit absorbant"
	done;
	(d,p) ;;



(******************* Sous-programmes pour Dijkstra basique ********************************)



let rec init_a_faire_basique = function
	-1 -> []
	|n -> n::init_a_faire_basique (n-1) ;;


let rec extraire_min_basique d = function
	[] -> ([],-1,max_int)
	|[h] -> ([],h,d.(h))
	|h::t -> let (f,u,m)=extraire_min_basique d t in
			if d.(h)<m then (u::f,h,d.(h))
			else (h::f,u,m) ;;


let rec relacher_liste (d,p) u w = function
	[] -> ()
	|v::l -> relacher (d,p) u v w ;
			relacher_liste (d,p) u w l ;;



(********************************** Dijkstra basique **************************************)


let dijkstra_basique g s =
	let (d,p) = init g s 
	and a_faire = ref (init_a_faire_basique (g.s-1))
	in
	while !a_faire <> [] do
		let (f,u,m) = extraire_min_basique d !a_faire in
		a_faire := f ;
		relacher_liste (d,p) u g.w g.l.(u)
	done;
	(d,p);;







(******************************************************************************************)
(******************************* Tas de Fibonacci *****************************************)
(******************************************************************************************)



type Fnoeud = {mutable cle  : int ; mutable valeur : int ;  mutable marque : bool ;
			mutable p : int ; mutable g : int ; mutable d : int ;
			mutable e : int ; mutable deg : int } ;;

type FTas = {mutable n : int ; mutable min : int ; mutable t : Fnoeud vect };;

let make_noeud () = {cle = 0 ; valeur = -1 ; marque = false ; p = -1 ; g = 0 ; d = 0 ; e = -1 ; deg = 0 };;

let make_tas () = { n = 0 ; min = 0 ; t = [|make_noeud () |] };;

let copy_noeud {cle = cle ; valeur = valeur ; marque = marque ; p = p ; g = g ; d = d ; e = e ; deg = deg } =
	{cle = cle ; valeur = valeur ; marque = marque ; p = p ; g = g ; d = d ; e = e ; deg = deg } ;;


(* {cle = cle ; valeur = valeur ; marque = marque ; p = p ; g = g ; d = d ; e = e ; deg = deg };; *)




(******************************* Dessin d'un tas ******************************************)


let draw_tas tas =
	clear_graph ();
	let rec parcours debut x y pasx pasy i =
	let {cle = cle ; valeur = valeur ; marque = marque ; p = p ; g = g ; d = d ; e = e ; deg = deg } = tas.t.(i) in
		moveto x y ;
		let noeud = ("("^string_of_int i^","^string_of_int cle^","^string_of_int valeur(*^","^string_of_int deg
					^","^string_of_int p^","^string_of_int g^","^string_of_int d *)^")")
		in
		draw_string noeud;
		let char = string_length noeud in
		if e = -1 then 
			if d=debut then x
			else 
				(
				set_color blue ;
				moveto (x+8*char) (y+9) ;
				lineto (x+8*char+pasx) (y+9);
				parcours debut (x+8*char+pasx) y pasx pasy d 
				)
		else
			(
			set_color red ;
			moveto (x+4*char) (y-1) ;
			lineto (x+4*char) (y-pasy) ;
			let xx = x in
			let x = parcours e x (y-pasy) pasx pasy e 
			in 
			if d=debut then x
			else 
				(
				set_color magenta ;
				moveto (xx+8*char) (y+9);
				lineto (x+8*char+pasx) (y+9);
				parcours debut (x+8*char+pasx) y pasx pasy d 
				)
			)
	in
	set_color black ;
	moveto 10 450 ; draw_string "(i,cle,valeur)" ;
	parcours tas.min 10 400 20 30 tas.min ;;



(************************** Sous-programmes pour extraire_min *****************************)



let inserer_racine tas (cle, valeur) =					(* insertion dans la liste des racines d'un nouvel élement *)
	if tas.n = vect_length tas.t then
		tas.t <- concat_vect tas.t (make_vect tas.n (make_noeud () ) ) ;
	tas.t.(tas.n) <- {cle = cle ; valeur = valeur ; marque = false ; p = -1 ; g = tas.min ; d = tas.t.(tas.min).d ; e = -1 ; deg = 0 };
	tas.t.(tas.t.(tas.min).d).g <- tas.n ;
	tas.t.(tas.min).d <- tas.n ;
	if cle < tas.t.(tas.min).cle then
		tas.min <- tas.n ;
	tas.n <- tas.n +1 ;;


(* sert dans boucher , consolider *)
let parcours_freres tas f i =			(* applique f à tous les indices des frères du noeud d'indice i (y compris i) *)
	let rec aux j =
		if j=i then
			f i
		else (f j ; aux tas.t.(j).d )
	in aux tas.t.(i).d ;;


(* sert dans extraire_min
utilise parcours_freres *)
let boucher tas i = 		(* bouche la ième case avec le dernier element du tableau -> modifie pas le tas si la ième case est vide *)
	if i<> (tas.n -1) then
		(
		let x = copy_noeud tas.t.(tas.n-1) in
		if (x.p <> -1)&&(tas.t.(x.p).e = tas.n -1) then tas.t.(x.p).e <- i ;
		if x.e <> -1 then 
			parcours_freres tas (function j -> (tas.t.(j).p <- i)) x.e;
		tas.t.(x.d).g <- i ;
		tas.t.(x.g).d <- i ;
		tas.t.(i) <- x ;
		if x.d=tas.n -1 then 
			(
			tas.t.(i).d <- i ;
			tas.t.(i).g <- i
			)
		);
	tas.t.(tas.n-1).valeur <- -1 ;;	(* juste pour se repérer *)
	

(* sert dans relier, extraire_min, passer_racine *)
let supprimer_freres tas x =				(* supprime x de la liste de ses frêres (attention aux enfants/parents) *)
	tas.t.(x.d).g <- x.g ;
	tas.t.(x.g).d <- x.d ;;	




(* sert dans consolider, extraire_min, couper *)
let passer_racine tas i = 		(* insere le noeud d'indice i dans la liste des racines *)
	let x = tas.t.(i) in
	if x.p <> -1 then
		(
		if tas.t.(x.p).e = i then
			if x.d = i then tas.t.(x.p).e <- -1		(* prévient le père *)
			else  tas.t.(x.p).e <- x.d ;
		tas.t.(x.p).deg <- tas.t.(x.p).deg -1 ;
		tas.t.(i).p <- -1 ;
		supprimer_freres tas x ;					(* prévient les frères *)
		tas.t.(i).g <- tas.min ;					(* insertion dans la liste des racines *)
		tas.t.(i).d <- tas.t.(tas.min).d ;	
		tas.t.(tas.t.(tas.min).d).g <- i ;
		tas.t.(tas.min).d <- i ;
		(* print_string "passer_racine utile \n" *)
		)
	(* else print_string "passer_racine inutile \n" *);;



(* sert dans relier *)
let inserer_droite tas i j =				(* insere le noeud d'indice j comme frère droit de celui d'indice i *)
	let x = tas.t.(i) 
	in
	tas.t.(j).g <- i;
	tas.t.(j).d <-	x.d ;
	tas.t.(j).p <- x.p ;
	tas.t.(x.d).g <- j ;
	tas.t.(i).d <- j ;;

	

(* sert dans consolider
utilise supprimer_freres, inserer_droite *)
let relier tas j i = 						(* x, y racines de tas *)
	supprimer_freres tas tas.t.(j) ;
	let x = tas.t.(i) in
	if x.e = -1 then
		(
		tas.t.(i).e <- j ; 
		tas.t.(j).p <- i ;
		tas.t.(j).d <- j ;
		tas.t.(j).g <- j
		)
	else
		inserer_droite tas x.e j ;
	tas.t.(i).deg <- tas.t.(i).deg +1 ;
	tas.t.(j).marque <- false ;;


(* sert dans consolider *)
let D n = int_of_float ( (log(float_of_int n)) /. (log ((1.+.sqrt 5.)/.2.)) ) +1 ;;




(***************************** consolider, extraire_min ***********************************)



(* sert dans extraire_min
utilise relier, passer_racine, d *)
let consolider tas =
	let a = make_vect (D tas.n) (-1) in
	let i = ref tas.min 
	and next = ref tas.t.(tas.min).d
	and pas_fini = ref true
	and gmin = tas.t.(tas.min).g in
	while !pas_fini do
		if !i = gmin then pas_fini := false ;
		next := tas.t.(!i).d ;
		let x = tas.t.(!i) in
		let d = ref x.deg in
		(*print_string "consolider 1 \n";*)
		while a.(!d) <> -1 do
			let j = ref a.(!d) in
			let y = tas.t.(!j) in
			if tas.t.(!i).cle > y.cle then
				(
				let k = !i in
				i := !j ; j:= k 
				);
			relier tas !j !i ;
			if tas.min = !j then tas.min <- !i ;
			a.(!d) <- -1;
			d:= !d+1 ;
		done;
		a.(!d) <- !i ;
		i:= !next
	done;
	(*print_string "concolider 2 \n" ;*)
	for i = 0 to D tas.n -1 do
		if a.(i) <> -1 then
			(
			(* print_string "consolider : " ;*)
			passer_racine tas a.(i) ; 
			if (tas.min = -1)||(tas.t.(a.(i)).cle < tas.t.(tas.min).cle) then
				tas.min <- a.(i);
			)
	done	;;
			
				



(* utilise supprimer_freres, passer_racine, boucher, consolider *)
let extraire_min tas =						(* on suppose tas non vide *)
	let z = copy_noeud tas.t.(tas.min) in
	let j = ref z.e 
	and next = ref 0 in
	for i = 1 to z.deg do					(* transfère les fils de z dans la liste des racines *)
		next := tas.t.(!j).d ;
		passer_racine tas !j ;
		j := !next
	done;
	supprimer_freres tas tas.t.(tas.min) ;					(* prévient les frères de z *)
	boucher tas tas.min ;					(* enlève z du tas *)
	if (z.e <> -1)&&(z.e<> tas.n -1) then tas.min <- z.e
		else
			if (z.d<>tas.n -1) then tas.min <- z.d ;		(* si le tas est non vide, place le pointeur min sur une autre racine *)
	tas.n <- tas.n -1 ;
	if tas.n > 0 then
		consolider tas; 
	(z.cle,z.valeur) ;;
	
	

(************************************ Tests ***********************************************)

	
	
let rand_tas n =
	let t = make_tas () in
	for i = 1 to n do
		inserer_racine t (random__int 10, random__int 10)
	done;
	t;;


let check_tas tas =
	if tas.n > vect_length tas.t then failwith "erreur tas.n \n" ;
	for i = 0 to tas.n -1 do
		if tas.t.(i).valeur = -1 then print_string ("attention : élément "^string_of_int i ^" de valeur -1 \n");
	done;
	if (tas.n < vect_length tas.t)&&(tas.t.(tas.n).valeur <> -1) then print_string ("attention : élément tas.n de valeur <> -1 \n") ;
	for i = 0 to tas.n -1 do
		let x = tas.t.(i) in
		if x.d > tas.n -1 then print_string ("erreur : frère droit de "^string_of_int i ^" hors du tableau \n" );
		if tas.t.(x.d).g <> i then print_string ("erreur : frère droit de "^string_of_int i ^" pas réciproque \n" );
		if tas.t.(x.d).p <> x.p then print_string ("erreur : frère droit de "^string_of_int i ^" n'a pas le même père \n" );
		if x.g > tas.n -1 then print_string ("erreur : frère gauche de "^string_of_int i ^" hors du tableau \n" );
		if tas.t.(x.g).d <> i then print_string ("erreur : frère gauche de "^string_of_int i ^" pas réciproque \n" );
		if tas.t.(x.g).p <> x.p then print_string ("erreur : frère gauche de "^string_of_int i ^" n'a pas le même père \n" );
		if (x.e <> -1)&&(tas.t.(x.e).p <> i) then print_string ("erreur : fils de "^string_of_int i ^" pas réciproque \n" );
		
		if x.cle < tas.t.(tas.min).cle then print_string ("erreur : clé de "^string_of_int i ^" plus petite que celle du min \n");
	done;;
	
	
	
(* let ext t = extraire_min t ; draw_tas t ; check_tas t ; t ;; *)



(******************************* Diminution d'une clé *************************************)



let couper tas i = 				
	passer_racine tas i ;
	tas.t.(i).marque <- false ;;
	
let rec coupe_cascade tas i =
	(*print_string ("cascade : "^string_of_int i ^"\n");*)
	let x = copy_noeud tas.t.(i) in
	(*print_string "cascade 2\n";*)
	if x.p <> -1 then
		(
		if not x.marque then
			(
	(*		print_string "cascade 3\n";*)
			tas.t.(i).marque <- true
			)
		else
			(
			(*print_string "cascade 4\n";*)
			couper tas i ;
			coupe_cascade tas x.p
			)
		);;


let diminuer_cle tas i k =
	let x = tas.t.(i) in
	if k > x.cle then
		failwith "erreur : nouvelle clé plus grande que la clé courante" ;
	tas.t.(i).cle <- k ;
	let p = x.p in
	if ((x.p <> -1)&&(x.cle < tas.t.(x.p).cle)) then
		(
		(*print_string "diminuer_cle 1\n";*)
		couper tas i ;
		(*print_string "diminuer_cle 2\n";*)
		coupe_cascade tas p 
		);
	(*print_string "diminuer_cle 3\n";*)
	if x.cle < tas.t.(tas.min).cle then
		tas.min <- i ;;




(******************************************************************************************)
(****************************** Application à Dijkstra ************************************)
(******************************************************************************************)




let rec init_tas_fib tas s = function
	-1 -> ()
	|n -> if n=s then inserer_racine tas (0,n) 
			else	inserer_racine tas (max_int,n) ;
		init_tas_fib tas s (n-1);;


let init_fib g s =
	let tas = make_tas ()
	and p = make_vect g.s (-1) 
	and d = make_vect g.s max_int 
	and position = make_vect g.s (-1) in
	for i = 0 to g.s -1 do
		position.(i) <- g.s - 1 - i
	done;
	init_tas_fib tas s (g.s-1) ;
	(tas,p,d,position) ;;


let extraire_min_fib tas position d = 
	let (cout, sommet) = extraire_min tas in
	d.(sommet) <- cout;
	(*print_string ("extraire_min : "^string_of_int sommet ^" cout "^string_of_int cout^"\n") ;*)
	if position.(sommet) < tas.n then position.(tas.t.(position.(sommet)).valeur) <- position.(sommet) ;
	position.(sommet) <- -1 ;
	sommet;;


let relacher_fib tas position p d u v w =
	if (d.(u) < max_int)&&(tas.t.(position.(v)).cle > d.(u) + w(u,v)) then
		(
		(*print_string ("relacher "^string_of_int v ^" "^string_of_int position.(v)^"\n");*)
		diminuer_cle tas position.(v) (d.(u) + w(u,v)) ;
		p.(v) <- u ;
		);;


let rec relacher_liste_fib tas position p d u w = function
	[] -> ()
	|v::l -> if position.(v) > -1 then relacher_fib tas position p d u v w ;
			relacher_liste_fib tas position p d u w l ;;





(********************************** Dijkstra Fibonacci ************************************)



let dijkstra_fib g s =
	let (tas,p,d,position) = init_fib g s 
	in
	while tas.n > 0 do
		let u = extraire_min_fib tas position d in
		relacher_liste_fib tas position p d u g.w g.l.(u)
	done;
	(d,p);;




(* 

let g = rand_graph 100 200 0 20 ;;
let (a1,b1) = dijkstra_fib g 0 ;;
let (a2,b2) = dijkstra_basique g 0 ;; 
(a1=a2,b1=b2);;

*)


(******************************************************************************************)
(**************************** Comparaison des temps d'éxécution ***************************)
(******************************************************************************************)

#open "sys" ;;

(*
system_command ".\ecrire.bat 10 S 15 A D";;
dijkstra_basique g 0 ;;
system_command ".\ecrire.bat f.txt 10";;
*)

chdir "c:";;
chdir "..";;
chdir "..";;
chdir "..";;
chdir "..";;
chdir "..";;
chdir "..";;
chdir "Documents and Settings";;
chdir "Jules";;
chdir "Bureau";;
chdir "tipe";;



let compare () =
	let puiss = ref 10 in
	while !puiss < 1001 do
		for s1 = 1 to 10 do
			let s = s1* !puiss in
			for a1 = 0 to s do
				let a = a1*s in
				print_string (string_of_int s^"    "^string_of_int a^"    ") ;
				let g = rand_graph s a 0 20 in
				system_command (".\ecrire.bat f"^string_of_int !puiss ^".txt "^string_of_int s ^" "^string_of_int a ^" debut ");
				for i = 0 to 9 do
					print_int i ;
					flush std_out ;
					dijkstra_basique g i ;
				done;
				system_command (".\ecrire.bat f"^string_of_int !puiss ^".txt "^string_of_int s ^" "^string_of_int a ^" milieu ");
				for i = 0 to 9 do
					print_int i ;
					flush std_out ;
					dijkstra_fib g i ;
				done;
				system_command (".\ecrire.bat f"^string_of_int !puiss ^".txt "^string_of_int s ^" "^string_of_int a ^" fin ");
				print_string "\n" ;
			done;
		done;
	puiss := !puiss *10 ;
	done;;
	
	



let compare () =
		for s1 = 1 to 40 do
			let s = 10*s1 in
			for a1 = 1 to 40 do
				let a = (a1*s*s)/40 in
				print_string (string_of_int s^"    "^string_of_int a^"    ") ;
				let g = rand_graph s a 0 20 in
				system_command (".\ecrire.bat f.txt "^string_of_int s ^" "^string_of_int a ^" debut ");
				for i = 0 to 9 do
					print_int i ;
					flush std_out ;
					dijkstra_basique g i ;
				done;
				system_command (".\ecrire.bat f.txt "^string_of_int s ^" "^string_of_int a ^" milieu ");
				for i = 0 to 9 do
					print_int i ;
					flush std_out ;
					dijkstra_fib g i ;
				done;
				system_command (".\ecrire.bat f.txt "^string_of_int s ^" "^string_of_int a ^" fin ");
				print_string "\n" ;
			done;
		done;;



let compare () =
		for s1 = 38 to 40 do
			let s = 10*s1 in
			for a1 = 1 to 40 do
				let a = (a1*s*s)/40 in
				print_string (string_of_int s^"    "^string_of_int a^"    ") ;
				let g = rand_graph s a 0 20 in
				system_command (".\ecrire.bat f.txt "^string_of_int s ^" "^string_of_int a ^" debut ");
				for i = 0 to 9 do
					print_int i ;
					flush std_out ;
					dijkstra_basique g i ;
				done;
				system_command (".\ecrire.bat f.txt "^string_of_int s ^" "^string_of_int a ^" milieu ");
				for i = 0 to 9 do
					print_int i ;
					flush std_out ;
					dijkstra_fib g i ;
				done;
				system_command (".\ecrire.bat f.txt "^string_of_int s ^" "^string_of_int a ^" fin ");
				print_string "\n" ;
			done;
		done;;





(******************************************************************************************)
(*********************************** Présentation *****************************************)
(******************************************************************************************)


let ex_ord = 
{s = 6; a = 8;
 w = w_from_mat 
 [|[|1073740823; 1073740823; 8; 1073740823; 1073740823; 8|];
   [|1073740823; 1073740823; 1073740823; 1073740823; 1073740823; 9|];
   [|1073740823; 2; 1073740823; 1073740823; 1073740823; 1073740823|];
   [|1073740823; 7; 1073740823; 1073740823; 1073740823; 1073740823|];
   [|1073740823; 9; 2; 3; 1073740823; 1073740823|];
   [|1073740823; 1073740823; 1073740823; 1073740823; 1073740823; 1073740823|]|];
  l = [|[ 2; 5]; [5]; [1]; [1]; [1; 2; 3]; []|];
  ar =
   [|4, 3; 4, 2; 0, 5; 3, 1; 0, 2; 4, 1; 1, 5; 2, 1|];
  pos =
   [|[|351; 336|]; [|283; 233|]; [|117; 336|]; [|161; 152|]; [|41; 233|];
     [|411; 234|]|]} ;;

let p = [|9;2;4;9;9;9|] ;;