Commits

Roma Sokolov committed 1b153c5

floyd warshall algo

Comments (0)

Files changed (1)

floyd_warshall.ml

+
+type ('a, 'b) graph = ('a, 'b) edges * 'a vertexes
+and ('a , 'b) edges = (('a * 'a) * ('b weight)) list
+and 'a vertexes = 'a list
+and 'b weight = Val of 'b | Infinity | Zero
+
+
+let gvertexes:(('a, 'b) graph -> 'a list) = snd
+let gedges:(('a, 'b) graph -> (('a * 'a) * 'b) list) = fst
+
+
+let zip = List.combine
+let unzip = List.split
+let curry f x y = f (x, y)
+let uncurry f (x, y) = f x y
+
+
+let all_pairs lst =
+  let pairs item lst = List.map (fun li -> (item, li)) lst
+  in
+    List.fold_left (fun acc item -> acc @ (pairs item lst)) [] lst
+
+let floyd_warshall graph = 
+  let vertexes = gvertexes graph in 
+  let vertex_pairs = all_pairs vertexes in
+  let edges = gedges graph in 
+  let init_d l_of_p = 
+    let rec forall lst d = match lst with
+      | ((u, v)::tail) when u == v -> 
+          let d' = ((u, v), Zero)::d in
+            forall tail d' 
+      | (uv::tail) when List.mem_assoc uv edges -> 
+          let w = List.assoc uv edges in
+          let d' = (uv, w)::d in
+            forall tail d'
+      | (uv::tail) -> 
+          let d' = (uv, Infinity)::d in
+            forall tail d'
+      | [] -> d
+    in forall l_of_p []
+  in 
+    init_d vertex_pairs
+(* *)
+
+
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.