(* gsearch-followup *)

(*        Lab 18/11/92  Follow-Up *)
(*
  Sorry I didn't make it along to the lab on Wednesday Morning
  but I have a valid excuse. My wife, Andrea, went into "established
  labour" at 10.00. Our daughter, Zoe, was born at 21.01, weighing
  in at 7lb 5.5 oz. Mother and daughter (and Dad!) are well. :*)
(*
Assume you are given a set of edges
*)
val E = [("a","b"),("a","c"),("a","d"),
         ("b","e"),
         ("c","f"),
         ("d","e"),
         ("e","f"),
         ("e","g")];

(*
Therefore E represents the set of edges in a digraph.


(And the lecturer has got his terminology screwed up, 
hasn't he? The guy can't even tell the difference 
between a graph (with edges) and a directed graph 
(digraph) (with ARCS!!!!). Oh well... these old guys,
they just forget I suppose...

(1) Write a predicate 

          fun pathp s g E = ...

    that takes as arguments a starting node s, and a
    goal node g, and a set of edges E and delivers a result true
    if there is a path from s to g in E (deliver false otherwise)

*)

(* You can use dfs, SO LONG AS THERE ARE NO LOOPS IN E.
   We have to define the test, successor, and result functions.
   dfs, as it has been defined, will find ALL nodes that satisfy
   predicate test. Therefore, we could say that there is a path
   from s to g if dfs does not deliver an empty list of solutions.
   This isn't efficient, but it will work, and will at least 
   give us a "handle" on how to proceed. *)

(* First, I will load in the source for dfs/bfs, etc *)
use "dfs";

fun succ [] v = []
   |succ ((v1,v2)::edges) v = 
    if v = v1
    then v2::(succ edges v)
    else (succ edges v);

(* Function succ takes as arguments a list of edges (where
   edges are pairs), and a vertex v. succ delivers the list of
   vertices that are adjacent to v in E. A sample call might
   then be as follows: *)

succ E "a";

fun test g v = g=v;
(* given the goal g, and a vertex/node v, is 
   v the goal? *)

fun result v = v;
(* the vertex is the result/goal *)

fun pathp s g e = let val goals = dfs [s]       (*1*)
                                      (test g)  (*2*)
                                      (succ e)  (*3*)
                                      result    (*4*)
                  in not (null goals) end;

(* Commentary
  (1) The list that is the start node.
  (2) partially applied function. 
  (3) partially applied function. This explains the order 
      that I used the arguments in succ. Clever?
  (4) nothing clever here

But, wont work with loops/cycles, and VERY inefficient. 
We could overcome this inefficiency by modifying dfs such that
it teminates when it finds a first solution. Therefore we might have a 
new version of dfs that delivers as a result a list, where that list is
a single solution, or nil. That's easy to do, and I leave it to you.
As for loops/cycles, we can use bfs, again modified such that it 
terminates on finding the 1st solution. Again, I leave it to you. *)

       
(*
(2) Write a function 

          fun path s g E = ...

    that delivers the list of edges, in order, that if traversed
    take us from s to g in E *)

(* This is MUCH easier than you might imagine. Assume that we 
have a node that is of the form (v,path) where v is a vertex
in the graph, and path is a path (sequence of vertices) in the graph that 
takes us from e to v. For example, assume we want to get from "a" to "g" in E.
Our initial node will be the list [("a",[])]. The successors of 
("a",[]) would be [("b",["a"]),("c",["a"]),("d",["a"])], and the 
successors of ("b",["a"]) would be [("e",["a","b"])]. 

The test function again is curried, such that
it takes as arguments the goal g and a node (v,path) and
delivers true if g=v (again, easy).

The result function takes a node (v,path) and delivers the path. 

Again, I leave it to you. You can use your modified version of dfs
and/or bfs (for loops/cycles) that delivers 1st solution *)



(*
(3) assume we then update E, such that *)

val E2 = E @ [("e","d")];

(* Do your functions till operate when we use E2 in place of E?*)

(* Okay? Cycles/loops, dfs versus bfs. Okay?*)

(*
(4) Enhance E such that it is a list of triples of the form
    (v1,v2,c12) where v1 is a vertex, v2 is a vertex, and 
    c12 is the cost of going from v1 to v2.
    Enhance function path such that it delivers the minimum cost
    path from s to g in E.
*)

(* Mmmm ... still not an intellectual challenge to a 4th year ml 
   programmer. Do you agree? 

   What we can do is again modify dfs/bfs. In a call
   to dfs (lets say) we have as follows:

   dfs f test succ result

   Where f is the set of nodes that we have visited, but we have not yet
   tested to see if they are goal nodes, and we have not added their 
   successors to f (ie we have not EXPANDED them). In fact, f is the
   "frontier" of the search tree. What we can do is SORT f. Therefore,
   whenever we add a node to f we can merge it into f.

   My goodness ... you've already been given the code for merge.
   Where's the challenge in this? :*)


(* PLEASE LET ME KNOW WHAT YOU THOUGHT OF THIS LAB. *)