Carte 2D en graphe dans Sml

Question

J'ai une carte 2D en entrée d'un fichier, ligne par ligne et je veux l'enregistrer et lancer un Bfs ou Dijkstra pour trouver le chemin le plus court de Start (marqué S) à la fin (marqué comme E), quelle est la structure appropriée pour enregistrer l'information? Mon implémentation en C++ était avec un graphe, mais j'ai du mal à le faire en sml, parce que je ne peux pas lier les nœuds des deux côtés.

Answer 1

Vous pouvez le faire en utilisant des tableaux mutables. Ceci est une implémentation de matrice d'adjacence extrêmement minime utilisant un tableau de int option. La limite entre les sommets i et j est donnée par la valeur de la première ligne i et de la colonne je. Si la valeur est None alors il n'y a pas de bord et si la valeur est Some w que le bord existe et a un poids 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);; 

Ceci est en OCaml, mais les différences entre SML et OCaml sont, pour la plupart, mineur.