Created
September 6, 2024 21:02
-
-
Save DanielAugusto191/74dcc87a7f40ba2908306cea49401ff4 to your computer and use it in GitHub Desktop.
Graphs and a DFS in OCaml
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| type 'a graph = | |
| | Empty | |
| | G of { | |
| la: 'a list list; | |
| size: int | |
| } | |
| let init_graph = Empty | |
| let add_node = function | |
| | Empty -> G {la = [[]]; size=1} | |
| | G { la=la; size=ns } -> G {la = la @ [[]]; size = ns} | |
| let add_edge g i j = | |
| match g with | |
| | Empty -> failwith "Empty graph" | |
| | G { la;size=ns } -> | |
| let rec edgeAdd alist idx = | |
| match alist with | |
| | [] -> [] | |
| | hd :: tl when idx = i -> (j :: hd) :: (edgeAdd tl (idx+1)) | |
| | hd :: tl when idx = j -> (i :: hd) :: (edgeAdd tl (idx+1)) | |
| | hd :: tl -> hd :: edgeAdd tl (idx + 1) | |
| in | |
| G { la = (edgeAdd la 0) ; size=ns};; | |
| let print_g g = | |
| match g with | |
| | Empty -> print_endline "Empty\n" | |
| | G {la;size=_} -> | |
| let rec print la idx = | |
| match la with | |
| | [] -> print_endline "\n" | |
| | hd :: tl -> | |
| let rec pList l = | |
| match l with | |
| | [] -> () | |
| | ini :: tail -> | |
| begin | |
| match tail with | |
| | [] -> Printf.printf "%d" ini | |
| | _ -> Printf.printf "%d " ini; | |
| pList tail; | |
| end | |
| in | |
| begin | |
| Printf.printf "%d -> [" idx; | |
| pList hd; | |
| print_endline "]"; | |
| print tl (idx + 1); | |
| end | |
| in | |
| print la 0;; | |
| let rec wasVisit vis x = | |
| match vis with | |
| | [] -> false | |
| | hd :: _ when hd = x -> true | |
| | _ :: tl -> wasVisit tl x | |
| let rec dfs g x vis= | |
| Printf.printf "In node: %d\n" x; | |
| match g with | |
| | Empty -> vis | |
| | G {la;size=_} -> | |
| let rec helper k i = | |
| match k with | |
| | [] -> vis | |
| | hd :: _ when i = x -> | |
| let rec dnow li vis= | |
| match li with | |
| | [] -> vis | |
| | hd :: tl when (not (wasVisit vis hd)) -> begin | |
| let vis = dfs g hd (hd::vis) in | |
| dnow tl vis; | |
| end | |
| | _ :: tl -> | |
| dnow tl vis | |
| in dnow hd vis; | |
| | _ :: tl -> helper tl (i+1) | |
| in helper la 0 | |
| let a = init_graph;; | |
| let a = add_node a;; | |
| let a = add_node a;; | |
| let a = add_node a;; | |
| let a = add_node a;; | |
| let a = add_node a;; | |
| let a = add_node a;; | |
| let a = add_edge a 0 4;; | |
| let a = add_edge a 0 2;; | |
| let a = add_edge a 1 4;; | |
| let a = add_edge a 1 3;; | |
| let a = add_edge a 3 4;; | |
| let a = add_edge a 3 5;; | |
| let b = print_g a;; | |
| let d = dfs a 0 [0];; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment