CODEWITHSUNDEEP
graphsmlsmlnj
orfeas
orfeas

Reputation: 1

2D map to graph in Sml

I have a 2D map as input from a file ,line by line and I want to save it and run a Bfs or Dijkstra to find the shortest path from Start (marked as S ) to end (marked as E),what's the proper structure to save the information? My implementation in c++ was with a graph,but I find it hard to do so in sml,because I can't link the nodes both ways.

Upvotes: 0

Views: 218

Answers (1)

Justin Raymond
Justin Raymond

Reputation: 3558

You can do it using mutable arrays. This is an extremely minimal adjacency matrix implementation using an array of array of int option. The edge between vertex i and j is given by the value in the ith row and jth column. If the value is None then there is no edge and if the value is Some w than the edge exists and has weight w.

let is_some opt =
  match opt with
  | None -> false
  | _ -> true;;

let unwrap opt =
  match opt with
  | None -> raise (Failure "unwrapped None")
  | Some x -> x;;

let add_edge g u v w =
  let us = Array.get g u in
  Array.set us v (Some w);;

let get_edge g u v =
  let us = Array.get g u in
  Array.get us v;;

let make_graph vertices =
  Array.make_matrix vertices vertices None;;

let neighbors g u =
  Array.get g u |>
  Array.to_list |>
  List.filter is_some |>
  List.mapi (fun i o -> (i, unwrap o));;


let g = make_graph 4;;
add_edge g 0 1 2;;
add_edge g 0 2 3;;
add_edge g 0 3 5;;
add_edge g 1 2 7;;
add_edge g 1 3 11;;
add_edge g 2 3 13;;
add_edge g 3 0 17;;
List.iter (fun (v, e) -> Printf.printf "0-(%i)->%i\n" e v) (neighbors g 0);;

This is in OCaml, but the differences between SML and OCaml are, for the most part, minor.

Upvotes: 1

Related Questions