Dijkstra ML

load "Int";

fun listaNodos g = let fun clash [] = [] (* funcion para saber los nodos de un grafo *)
                           | clash ((a,b,c)::d) = [a,b]@(clash d)
                       fun eliminar [] k  = []
                           | eliminar (a::b) k = if k = a then eliminar b k else a::(eliminar b k)
                       fun listaNodosAux [] = []
                           | listaNodosAux (a::b) = a::(listaNodosAux (eliminar b a))
                   in listaNodosAux (clash g) end

fun quitarAristas [] nodo restGraph lista = (restGraph, lista) (* separar grafo en la tupla (grafo - conjunto de aristas de 'nodo', conjunto de aristas de 'nodo') *)
    | quitarAristas ((a,b,c)::d) nodo restGraph lista = if nodo = a (* nodo coincide *)
                                                            then quitarAristas d nodo restGraph ((a,b,c)::lista)
                                                            else quitarAristas d nodo ((a,b,c)::restGraph) lista;

fun push [] (w,z) = [(w,z)] (* priority queue de menor a mayor *)
    | push ((a,d)::rest) (w,z) = if z > d then (a,d)::(push rest (w,z)) else [(w,z),(a,d)]@rest;

fun pushListPlusValue [] luckingFist value = luckingFist (* push de una lista a la PQ *)
    | pushListPlusValue ((a,b,c)::d) luckingFist value = pushListPlusValue d (push luckingFist (b,c+value)) value;

fun dijkstraAux graph [] destino = valOf(Int.maxInt) (* devolver infinito *)
    | dijkstraAux graph ((x,y)::PQ) destino = if destino = x (* encontre el destino en la PQ y termina *)
                                                then y
                                                else let val (p,k) = quitarAristas graph x [] []
                                                     in dijkstraAux p (pushListPlusValue k PQ y) destino end

fun dijkstra graph origen myBool =  let fun invertGraph [] = [] (* a la funcion dijkstra se le pasa el grafo, el punto de origen y un bool que es true si el grafo es dirigido, false si no *)
                                            | invertGraph ((a,b,c)::d) = (b,a,c)::(invertGraph d)
                                        val nonDirected = if myBool then graph else graph @ (invertGraph graph)
                                        fun callNodeList [] = []
                                            | callNodeList (a::b) = (a,(dijkstraAux nonDirected [(origen,0)] a)) :: (callNodeList b)
                                    in callNodeList (listaNodos graph) end

(* tests below *)

val G = [(1,2,1), (1,3,1), (2,4,2), (3,4,3), (4,5,9)];
dijkstra G 3 false; (* false -> grafo no dirigido *)

val G = [(1,2,1), (1,3,1), (2,4,2), (3,4,3), (4,5,9)];
dijkstra G 4 true; (* true -> grafo dirigido *)

val G = [(1,2,2), (2,3,3), (3,1,1), (1,4,5), (4,5,8), (5,3,1), (3,4,1)];
dijkstra G 1 false;