(* topological-sort.ml *)
(* S. Tanimoto, 5 June 2003 *)

(* Create a sample graph  *)

val mathPrereqs = [
 ("algebra", "trig"),
 ("trig", "calculus"),
 ("algebra", "geometry"),
 ("algebra", "matrices"),
 ("calculus", "analysis"),
 ("logic", "theorem-proving"),
 ("algebra", "combinatorics"),
 ("arithmetic", "algebra"),
 ("matrices", "operations-research"),
 ("calculus", "operations-research")];

fun insert (elt, []) = [elt] |
    insert (elt, h::t) = if elt = h then h::t else h::insert(elt, t);

fun makeListOfElements [] = [] |
    makeListOfElements ((c1,c2)::rest) = 
     insert (c1, insert (c2, makeListOfElements rest));

fun noPrereqs (course, []) = true |
    noPrereqs (course, (c1, c2)::rest) = if (course = c2) then false else
      noPrereqs (course, rest);
   
fun removeAsPrereq (course, []) = [] |
    removeAsPrereq (course, (c1, c2)::rest) = if (course = c1) then
       removeAsPrereq (course, rest) else
       (c1, c2)::removeAsPrereq(course, rest);

(* Find an element with no prerequisites *)

fun findEltWithNoPrereqs(elts, prereqs, failVal) =
  if elts = [] then failVal else
  if noPrereqs(hd(elts), prereqs) then hd(elts)
  else findEltWithNoPrereqs(tl(elts), prereqs, failVal);

fun remove(elt, []) = [] |
    remove(elt, h::t) = if elt = h then t else
    h::remove(elt, t);

(* Now for the topo sort alg...
   Find the first element of list of remaining elements that
   has no prerequisites.
   cons it onto a list obtained by making a recursive call
     to the topo sort function using
       a shorted list of remaining elements and
       a shorted list of prerequisites.
*)

fun toposort ([], prereqs) = [] |
    toposort (elts, []) = elts |
    toposort (elts, prereqs) =
      let val c1 = findEltWithNoPrereqs (elts, prereqs, "fail")
          in
          if (c1 = "fail") then ["fail"] else
          (c1::toposort(remove(c1, elts), 
                        removeAsPrereq(c1, prereqs) ) )
          end

val e = findEltWithNoPrereqs (makeListOfElements(mathPrereqs), mathPrereqs, "fail");

fun topologicalSort(preReqs) =
  toposort( makeListOfElements(preReqs), preReqs);

val answer = topologicalSort(mathPrereqs);