load "Intset";

type node = int;

type nodes = Intset.intset;

datatype edge = EDGE of node * node;

datatype graph = GRAPH of nodes * nodes * nodes * edge list;

datatype pathTestResult = SUCCESS | NOENTRY | NOEXIT | NOEDGE;

fun getNodes(GRAPH(nodes, _, _, _)) = nodes;

fun getStarts(GRAPH(_, starts, _, _)) = starts;

fun getFins(GRAPH(_, _, fins, _)) = fins;

fun getEdges(GRAPH(_, _, _, edges)) = edges;

fun checkStarts(GRAPH(nodes, starts, _, _)) = Intset.isSubset(starts, nodes);

fun checkFins(GRAPH(nodes, _, fins, _)) = Intset.isSubset(fins, nodes);

fun checkSelfEdges(GRAPH(_, _, _, edges)) =
    not (List.exists (fn EDGE(a, b) => (a = b)) edges);

fun checkImpossibleEdges(GRAPH(nodes, _, _, edges)) =
    List.all (fn EDGE(a, b) => (Intset.member(nodes, a) andalso
                                         Intset.member(nodes, b))) edges;

fun  count([], _) = 0
    | count(x::xs, e) =
        if (e = x) then 1 + count(xs, e)
        else count(xs, e);

fun checkDupEdges(GRAPH(_, _, _, edges)) =
    List.all (fn e => (count(edges, e) = 1)) edges;

fun checkEdges(g) =
    checkSelfEdges(g) andalso checkDupEdges(g) andalso checkImpossibleEdges(g);

fun checkNodes(g) = checkStarts(g) andalso checkFins(g);

fun checkGraph(g) = checkEdges(g) andalso checkNodes(g);

fun addNode(GRAPH(nodes, starts, fins, edges), n) =
    GRAPH(Intset.add(nodes, n), starts, fins, edges);

fun addStartNode(GRAPH(nodes, starts, fins, edges), n) =
    GRAPH(Intset.add(nodes, n), Intset.add(starts, n), fins, edges);

fun addFinNode(GRAPH(nodes, starts, fins, edges), n) =
    GRAPH(Intset.add(nodes, n), starts, Intset.add(fins, n), edges);

fun addStartFinNode(GRAPH(nodes, starts, fins, edges), n) =
    GRAPH(Intset.add(nodes, n), Intset.add(starts, n), Intset.add(fins, n), edges);

fun addEdge(g as GRAPH(nodes, starts, fins, edges), e) =
    let
        val testResult = GRAPH(nodes, starts, fins, e::edges)
        val OK = checkEdges(testResult)
    in
        if OK then testResult else g
    end;

fun  testPath'(g as GRAPH(_, _, fins, _), [n]) =
        if Intset.member(fins, n) then SUCCESS else NOEXIT
    | testPath'(g as GRAPH(_, _, _, edges), n::ns) =
        if (List.exists (fn EDGE(a, b) => ((a = n) andalso (b = hd(ns)))) edges) then
            testPath'(g, ns)
        else NOEDGE;

fun  testPath(_, []) = NOENTRY
    | testPath(g as GRAPH(_, starts, _, _), n::ns) =
        if (Intset.member(starts, n)) then testPath'(g, n::ns) else NOENTRY;

fun  getNextNodes'([]) = []
    | getNextNodes'(EDGE(_, e)::es) = e::getNextNodes'(es);

fun getNextNodes(GRAPH(_, _, _, edges), n) =
    getNextNodes'(List.filter (fn EDGE(a, _) => (n = a)) edges);

fun reach'(g, n, s, d) =
    let
        val nextNodesList = getNextNodes(g, n)
        val nextNodes = Intset.addList(Intset.empty, nextNodesList)
    in
        Intset.member(nextNodes, s) orelse
        List.exists (fn m => ((not (Intset.member(d, m))) andalso
                                     reach'(g, m, s, Intset.add(d, n)))) nextNodesList
    end;

fun reach(g, n, s) = reach'(g, n, s, Intset.empty);

fun hasCycleOnNode(g, n) = reach(g, n, n);

fun hasCycle(g as GRAPH(nodes, _, _, _)) =
    List.exists (fn n => hasCycleOnNode(g, n)) (Intset.listItems(nodes));

fun  shortestPath'(x::[]) = x
    | shortestPath'(x::xs) =
    let val shortest = shortestPath'(xs)
    in
        if (List.length(x) < List.length(shortest)) then x
        else shortest
    end;

fun  removeEdges([], _) = []
    | removeEdges((e as EDGE(a, b))::es, n) =
        if ((n = a) orelse (n = b)) then removeEdges(es, n)
        else e::removeEdges(es, n);

fun removeNode(GRAPH(nodes, starts, fins, edges), n) =
    GRAPH(Intset.delete(nodes, n),
            (if (Intset.member(starts, n)) then Intset.delete(starts, n) else starts),
            (if (Intset.member(fins, n)) then Intset.delete(fins, n) else fins),
            removeEdges(edges, n));

fun shortestPath(g, n, s) =
    let
        val g' = removeNode(g, n)
        val nextNodesList = getNextNodes(g, n)
        val nextNodes = Intset.addList(Intset.empty, nextNodesList)
        val candList =  List.filter (fn c => reach(g', c, s)) nextNodesList
        val candPaths = List.map (fn c => shortestPath(g', c, s)) candList
    in
        if (Intset.member(nextNodes, s)) then [n, s]
        else n::shortestPath'(candPaths)
    end;

val g = GRAPH(Intset.empty, Intset.empty, Intset.empty, []);

val g = addNode(g, 2);
val g = addNode(g, 3);
val g = addNode(g, 4);

val g = addStartNode(g, 1);
val g = addFinNode(g, 5);

val g = addEdge(g, EDGE(1, 2));
val g = addEdge(g, EDGE(1, 3));
val g = addEdge(g, EDGE(2, 3));
val g = addEdge(g, EDGE(2, 4));
val g = addEdge(g, EDGE(3, 1));
val g = addEdge(g, EDGE(3, 4));
val g = addEdge(g, EDGE(4, 5));

(1, shortestPath(g, 1, 5));
(2, shortestPath(g, 2, 5));
(3, shortestPath(g, 3, 5));
(4, shortestPath(g, 4, 5));