datatype 'a graph = Vertex of 'a * (((int ref) * ('a graph ref)) list);

fun getAll G =
    let
        val visited = ref [];

        fun been g = List.exists (fn x => g = x) (!visited)

        fun helper (g as ref (Vertex(_, l))) =
            let
                val nodes = map (fn (lbl, x) => x) l;
            in
                visited := g :: (!visited);
                List.app (fn x => if (been x) then () else helper x) nodes
            end
    in
        helper G;
        !visited
    end;

fun hasCycles G =
    List.exists
        (fn (g as ref (Vertex(_, l))) =>
            let
                val nodes = List.map (fn (_, x) => x) l
            in
                List.exists
                (fn node =>
                        List.exists
                            (fn x => x = g)
                            (getAll node)
                )
                nodes
            end
        )
        (getAll G);


exception NoPath;

fun pathFromToInSteps graph (source, destination, required_steps)=
    let
        fun findNode G src =
            case (List.find (fn (ref (Vertex(lbl, _))) => lbl = src) (getAll G)) of
                    NONE => raise NoPath
                |   SOME(g) => g;

        fun getTo (ref (Vertex(lbl, l))) (dst, steps) =
            let
                fun helper [] = raise NoPath
                |   helper ((ref i, g) :: gs) =
                        i + (getTo g (dst, steps - 1))
                            handle NoPath => helper gs;
            in
                if steps < 0 then
                    raise NoPath
                else
                    if lbl = dst andalso steps = 0 then
                        0
                    else
                        helper l
            end;
    in
        getTo (findNode graph source) (destination, required_steps)
    end;

fun incrementEdges (inc, label : string) G =
    let
        val total = ref 0;
        fun handleNode (ref (Vertex(_, l))) =
            List.app
                (fn (len, ref (Vertex(lbl, _))) =>
                        if lbl = label then (
                                len := !len + inc;
                                total := !total + inc
                            )
                        else
                            ()
                    )
                l
    in
        List.app handleNode (getAll G);
        !total
    end;

fun pathFromToUnder25 (label1, label2) graph =
    let
        fun findNode G src = valOf(List.find (fn (ref (Vertex(lbl, _))) => lbl = src) (getAll G));

        fun getTo (ref (Vertex(lbl, l))) dst limit =
            let
                fun helper [] = false
                |   helper ((ref i, g) :: gs) = (getTo g dst (limit - i)) orelse (helper gs)
            in
                if limit <= 0 then
                    false
                else
                    if lbl = dst then
                        true
                    else
                        helper l
            end;
    in
        (getTo (findNode graph label1) label2 25) orelse (getTo (findNode graph label2) label1 25)
            handle Option => false
    end;