{"cells":[{"metadata":{"trusted":false},"cell_type":"code","source":"type graphe = int list array;;","execution_count":1,"outputs":[{"output_type":"execute_result","execution_count":1,"data":{"text/plain":"type graphe = int list array"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let graphe_vide n = Array.make n [];;","execution_count":2,"outputs":[{"output_type":"execute_result","execution_count":2,"data":{"text/plain":"val graphe_vide : int -> 'a list array = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let ajoute_arc g i j = if not (List.mem j g.(i)) then g.(i) <- j::g.(i);;","execution_count":3,"outputs":[{"output_type":"execute_result","execution_count":3,"data":{"text/plain":"val ajoute_arc : 'a list array -> int -> 'a -> unit = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let supprime_arc g i j = \n   let rec aux l1 l2 = match l1 with\n      | [] -> l2\n      | t::q -> if t=j then q@l2 else aux q (t::l2)\n    in g.(i) <- aux g.(i) [];;","execution_count":4,"outputs":[{"output_type":"execute_result","execution_count":4,"data":{"text/plain":"val supprime_arc : 'a list array -> int -> 'a -> unit = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let non_oriente g = \n   let rec aux i l = match l with\n      | [] -> true\n      | t::q -> (List.mem i g.(t))&&(aux i q) in\n   let b = ref true in\n   for i=0 to Array.length g -1 do\n      b:=(!b)&&(aux i g.(i))\n    done;\n    !b;;\n   ","execution_count":11,"outputs":[{"output_type":"execute_result","execution_count":11,"data":{"text/plain":"val non_oriente : int list array -> bool = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let transpose g = \n   let n=Array.length g in\n   let h=Array.make n [] in\n   let rec aux i l = match l with\n      |[]->()\n      |t::q-> h.(t)<-i::h.(t); aux i q in\n   for i=0 to n-1 do\n       aux i g.(i)\n    done;\n    h;;","execution_count":13,"outputs":[{"output_type":"execute_result","execution_count":13,"data":{"text/plain":"val transpose : int list array -> int list array = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let sommets_accessibles g i =\n   let b=Array.make (Array.length g) false and f = Queue.create () in\n   let rec voisins l = match l with\n      |[]->()\n      |t::q->if not(b.(t)) then begin b.(t)<-true; Queue.push t f end; voisins q in\n   Queue.push i f;\n   b.(i)<-true;\n   while not(Queue.is_empty f) do\n      let x=Queue.pop f in\n      voisins g.(x)\n    done;\n    let tab_vers_liste b = \n       let l=ref [] in\n       for i=0 to Array.length b -1 do\n          if b.(i) then l:=i::(!l)\n        done;\n        !l in\n    tab_vers_liste b;;\n      ","execution_count":14,"outputs":[{"output_type":"execute_result","execution_count":14,"data":{"text/plain":"val sommets_accessibles : int list array -> int -> int list = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let chemins g i =\n   let c= Array.make (Array.length g) [] and f=Queue.create() in\n   let rec aux l x = match l with\n      |[]->()\n      |y::q->if c.(y)=[] then begin Queue.push y f; c.(y)<-y::c.(x) end; aux q x\n    in c.(i)<-[i];\n    Queue.push i f;\n    while not(Queue.is_empty f) do\n       let x=Queue.pop f in aux g.(x) x\n    done;\n    Array.map (List.rev) c;;","execution_count":15,"outputs":[{"output_type":"execute_result","execution_count":15,"data":{"text/plain":"val chemins : int list array -> int -> int list array = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let g1=[|[1;3];[0;2];[1;3];[2;0]|];;\nchemins g1 1;;","execution_count":17,"outputs":[{"output_type":"execute_result","execution_count":17,"data":{"text/plain":"val g1 : int list array = [|[1; 3]; [0; 2]; [1; 3]; [2; 0]|]\n- : int list array = [|[1; 0]; [1]; [1; 2]; [1; 0; 3]|]"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let connexe g = Array.length g = List.length (sommets_accessibles g 0);;","execution_count":18,"outputs":[{"output_type":"execute_result","execution_count":18,"data":{"text/plain":"val connexe : int list array -> bool = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let comp_connexes g =\n   let n=Array.length g in\n   let b=Array.make n false and f = Queue.create () and liste_comp=ref[] in\n    for i=0 to n-1 do\n       if not(b.(i)) then\n          begin\n          let comp= ref [] in\n          Queue.push i f;\n          b.(i)<-true;\n          comp:=[i];\n          let rec aux l= match l with\n             |[]-> ()\n             |t::q-> if not(b.(t)) then begin b.(t)<-true; Queue.push t f; comp:=t::(!comp) end; aux q\n           in\n          while not(Queue.is_empty f) do\n             aux g.(Queue.pop f)\n            done;\n        liste_comp:=(!comp)::(!liste_comp)\n        end\n    done;\n    !liste_comp;;","execution_count":19,"outputs":[{"output_type":"execute_result","execution_count":19,"data":{"text/plain":"val comp_connexes : int list array -> int list list = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let co_accessibles g i = sommets_accessibles (transpose g) i;;","execution_count":20,"outputs":[{"output_type":"execute_result","execution_count":20,"data":{"text/plain":"val co_accessibles : int list array -> int -> int list = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let comp_fort_connexe g i = \n   let rec inter l1 l2 = match l1 with\n      |[]->[]\n      |t::q -> if List.mem t l2 then t::(inter q l2) else inter q l2\n    in inter (sommets_accessibles g i) (co_accessibles g i);;","execution_count":21,"outputs":[{"output_type":"execute_result","execution_count":21,"data":{"text/plain":"val comp_fort_connexe : int list array -> int -> int list = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let comp_fort_connexes g = let n = Array.length g in let b = Array.make n false in\n   let liste_comp = ref [] in\n   let rec aux l = match l with\n      |[]->()\n      |x::q->b.(x)<-true; aux q in\n   for i = 0 to n-1 do\n      if not b.(i) then begin\n         let l = comp_fort_connexe g i in aux l;\n         liste_comp:=l::(!liste_comp)\n        end\n    done;\n    !liste_comp","execution_count":22,"outputs":[{"output_type":"execute_result","execution_count":22,"data":{"text/plain":"val comp_fort_connexes : int list array -> int list list = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let cycle_depuis_sommet i g = \n   let b = Array.make (Array.length g) false in\n   let rec aux l = match l with\n      |[]->()\n      |t::q->if b.(t) then aux q else begin b.(t)<-true; aux(g.(t)@q)end in\n    aux g.(i);\n    b.(i);;","execution_count":25,"outputs":[{"output_type":"execute_result","execution_count":25,"data":{"text/plain":"val cycle_depuis_sommet : int -> int list array -> bool = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let cyclique g = \n   let rec aux i = \n      if i=Array.length g then false\n      else (cycle_depuis_sommet i g)||(aux (i+1)) in aux 0;;","execution_count":26,"outputs":[{"output_type":"execute_result","execution_count":26,"data":{"text/plain":"val cyclique : int list array -> bool = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"ocaml","display_name":"OCaml","language":"ocaml"}},"nbformat":4,"nbformat_minor":2}