Informatique/SPE/OPT/TP 5/main.ml

type graphel = int list array;;

let ajoute_arete i j (g:graphel) = 
	let rec ajoute k l = match l with
		| [] -> [k]
		| h::t when h=k -> h::(ajoute k t)
		| h::t -> l in
	g.(i) <- ajoute j g.(i);
	g.(j) <- ajoute i g.(j);;

let supprime_arete i j (g:graphel) =
	let rec retire k l = match l with
		| h::t when h=k -> t
		| h::t -> h::(retire k t)
		| _ -> l in
	g.(i) <- retire j g.(i);
	g.(j) <- retire i g.(j);;

let ajoute_sommet (g:graphel) =
	let n = Array.length g in
	let g2 = Array.make (n+1) [] in
	for i = 0 to n-1 do
		g2.(i) <- g.(i)
	done;
	g2;;

let supprime_sommet i (g:graphel) = 
	let n = Array.length g in
	let g2 = Array.make (n-1) [] in
	let rec parcours l = match l with
		| [] -> []
		| h::t when h=i -> parcours t
		| h::t when h<i -> h::(parcours t)
		| h::t when h>i -> (h-1)::(parcours t) in
	for j = 0 to n-2 do
		if j < i then
			g2.(j) <- parcours g.(j)
		else
			g2.(j) <- parcours g.(j+1)
	done;
	g2;;

type graphem = int array array;;

let ajoute_aretem i j (g:graphem) = 
	g.(i).(j) <- 1;
	g.(j).(i) <- 1;;

let supprime_aretem i j (g:graphem) = 
	g.(i).(j) <- 0;
	g.(j).(i) <- 0;;

let ajoute_sommetm (g:graphem) = 
	let n = Array.length g in
	let g2 = Array.make_matrix n n 0 in
	for i = 0 to n-1 do
		for j = 0 to n-1 do
			g2.(i).(j) <- g.(i).(j)
		done
	done;
	g2;;

let supprime_sommetm k (g:graphem) = 
	let n = Array.length g in
	let g2 = Array.make_matrix (n-1) (n-1) 0 in
	for i = 0 to n-2 do
		for j = 0 to n-2 do
			let a = if i < k then i else i+1 in
			let b = if j < k then j else j+1 in
			g2.(i).(j) <- g.(a).(b)
		done
	done;
	g2;;

let conversion_lm (g:graphel) = 
	let n = Array.length g in
	let g2 = Array.make_matrix n n 0 in
	for i = 0 to n-1 do
		let ajoute j = ajoute_aretem i j g2 in
		List.map ajoute g.(i)
	done;
	g2;;

let conversion_ml (g:graphem) =
	let n = Array.length	 g in
	let g2 = Array.make n [] in
	for i = 0 to n-1 do
		for j = 0 to n-1 do
			if g.(i).(j) = 1 then
				ajoute_arete i j g2
			else ()
		done
	done;
	g2;;