Kruskal ML

(* utilidades *)

fun create [] = []
        | create (x::y) = (x,x)::(create y);

fun pertenece a [] = false
        | pertenece a (b::c) = if a = b then true else pertenece a c;

exception nopepuntoexe;

(* implementacion del union find *)

fun findAux x [] z = raise nopepuntoexe
        | findAux x ((a,b)::c) z = if x = a andalso a = b then b else if x = a then findAux b z z else findAux x c z;

fun find x a = findAux x a a;

fun unionAux x y [] rest k = raise nopepuntoexe
        | unionAux x y ((a,b)::c) rest k = if k = a then rest@((a,x)::c) else unionAux x y c (rest@[(a,b)]) k;

fun union x y a = unionAux x y a [] (find y a);

(* funciones para ordenar *)

fun menores (a,b,x) [] = []
        | menores (a,b,x) ((c,d,y)::ys) = if y <= x then (c,d,y)::menores (a,b,x) ys else menores (a,b,x) ys;

fun mayores (a,b,x) [] = []
        | mayores (a,b,x) ((c,d,y)::ys) = if y > x then (c,d,y)::mayores (a,b,x) ys else mayores (a,b,x) ys;

fun qs [] = []
        | qs ((a,b,x)::xs) = qs (menores (a,b,x) xs) @ [(a,b,x)] @ qs (mayores (a,b,x) xs);

(* funciones para generar la lista de nodos *)

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));

fun clash [] = []
        | clash ((a,b,c)::d) = [a,b]@(clash d);

fun listaNodos g = listaNodosAux (clash g);

(* kruskal *)

fun kruskalAux [] UFlist MSP = MSP
        | kruskalAux ((a,b,c)::d) UFlist MSP = if (find a UFlist) <> (find b UFlist) (* no hay ciclo *)
                                                then kruskalAux d (union a b UFlist) ((a,b,c)::MSP) (* se agrega la arista al MSP *)
                                                else kruskalAux d UFlist MSP; (* se ignora *)

fun kruskal g = kruskalAux (qs g) (create (listaNodos g)) []; (* le pasas la lista ordenada, la lista para el union-find y una lista vacía para guardar el msp *)

(* tests *)

kruskal [(1,2,3), (1,3,4), (2,3,99), (3,4,5), (1,4,50), (4,5,1)];
kruskal [(1,2,1), (1,3,1), (2,4,2), (2,1,0), (2,3,2), (2,4,0), (3,2,1), (4,3,1), (4,1,0)];