Advertisement
Guest User

Untitled

a guest
Jul 24th, 2016
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.71 KB | None | 0 0
  1. type vertex = { Number: int; Edges: int list }
  2.  
  3. let graph = [
  4. { Number = 1; Edges = [11] };
  5. { Number = 2; Edges = [11] };
  6. { Number = 3; Edges = [11; 4] };
  7. { Number = 4; Edges = [3; 12] };
  8. { Number = 5; Edges = [12] };
  9. { Number = 6; Edges = [13; 7] };
  10. { Number = 7; Edges = [6; 13; 8] };
  11. { Number = 8; Edges = [7; 13; 9] };
  12. { Number = 9; Edges = [8; 10] };
  13. { Number = 10; Edges = [9; 14] };
  14. { Number = 11; Edges = [1; 2; 3; 14] };
  15. { Number = 12; Edges = [5; 13; 14] };
  16. { Number = 13; Edges = [12; 6; 7; 8; 14] };
  17. { Number = 14; Edges = [11; 12; 13; 10] };
  18. ]
  19.  
  20. let paths graph origin destination =
  21. let rec loop current visited =
  22. if current = destination
  23. then [[current]]
  24. else if List.contains current visited
  25. then []
  26. else
  27. let test elem = if elem.Number = current
  28. then Some(elem.Edges)
  29. else None
  30. let vertices = match List.tryPick test graph with
  31. | None -> []
  32. | Some(vertices) -> vertices
  33. vertices |> List.collect (fun x -> loop x (current :: visited))
  34. |> List.map (fun x -> List.append [current] x)
  35. loop origin []
  36.  
  37. paths graph 3 8
  38.  
  39. [3; 11; 14; 12; 13; 6; 7; 8]
  40. [3; 11; 14; 12; 13; 7; 8]
  41. [3; 11; 14; 12; 13; 8]
  42. [3; 11; 14; 13; 6; 7; 8]
  43. [3; 11; 14; 13; 7; 8]
  44. [3; 11; 14; 13; 8]
  45. [3; 11; 14; 10; 9; 8]
  46. [3; 4; 12; 13; 6; 7; 8]
  47. [3; 4; 12; 13; 7; 8]
  48. [3; 4; 12; 13; 8]
  49. [3; 4; 12; 13; 14; 10; 9; 8]
  50. [3; 4; 12; 14; 13; 6; 7; 8]
  51. [3; 4; 12; 14; 13; 7; 8]
  52. [3; 4; 12; 14; 13; 8]
  53. [3; 4; 12; 14; 10; 9; 8]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement