(* Problem 1 - a function startpoints(pairs,z) that produces the list of all x such that (x,z) is in the list pairs *)

fun startpoints(pairs,z)=
  let
    fun sp([],_,results) = results
      | sp((x,y)::pairs,z,results) =
          if y = z
		  then
            sp(pairs,z,x::results)
          else
            sp(pairs,z,results)
  in
    sp(pairs,z,[])
  end
;

(* Problem 2 - a function endpoints(z,pairs) that produces he list of all y such that (z,y) is in the list pairs *)

fun endpoints(z,pairs)=
  let
    fun ep([],_,results) = results
      | ep((x,y)::pairs,z,results) =
          if x = z
		  then
            ep(pairs,z,y::results)
          else
            ep(pairs,z,results)
  in
    ep(pairs,z,[])
  end
;
  
(* Problem 3 - a function allpairs(xs,ys) that produces te list of all (x,y) for x in the list xs and y in the list ys *)

fun allpairs(xs,ys)=
  let
    fun ap1(_,[],results) = results
      | ap1(v,w::ws,results)=ap1(v,ws,(v,w)::results)
    fun ap2([],_) = []
      | ap2(v::vs,ws)=ap1(v,ws,[]) @ ap2(vs,ws)
  in
    ap2(xs,ys)
  end
;

(* Problem 4 - a function addnew((x,y), pairs) where the list paitrs is expected to be complete *)

fun addnew((x,y),pairs)=
  let
    val sp=startpoints(pairs,x)
    val ep=endpoints(y,pairs)
    val ap=allpairs(x::sp,y::ep)
    fun combine(v,[]) = [v]
      | combine(v,w::ws) = if v = w then
                           w::ws
                         else
                           w::combine(v,ws)
    fun merge([],ws) = ws
      | merge(v::vs,ws) = merge(vs,combine(v,ws))
  in
    merge(ap,pairs)
  end
;
  
(* Problem 5 - a function routes(pairs) that produces a list of all (x,y) such that there is a route from x to y via the pairs *)

fun routes([])= []
  | routes((x,y)::pairs) = addnew((x,y),routes(pairs))