(*

(1) Graph Search 1.
    A digraph G = (V,A), where V is a set of vertices and A is
    a set of directed arcs. The arc (vi,vj) is in A if there
    is a directed arc from vi to vj.

    Assume you are given the set A, and the vertices X and Y. 
    Write a function that will answer the question:
    "Is there a path from X to Y in G?".
    
    You might use dfs or bfs to answer the above question. If
    you do, then you will need to define the functions: 
    test, succ, and result.

    NOTE: 
    (a) G may contain cycles. 
    (b) dfs and bfs find ALL solutions whereas we only require 
        to test for the existance of any path from X to Y.


(2) Graph Search 2.
    Again, given digraph G = (V,A), and the vertices X and Y,
    deliver the shortest path from X to Y in G, where the
    shortest path involves least arcs in A.


(3) Maximum Clique
    Given a graph G = (V,E), where E is the set of edges in
    G. The edge (vi,vj) is in E if vertices vi and vj are
    adjacent. 

    A clique of size n is composed of n vertices in G, where every 
    pair of vertices in that clique are adjacent (a clique of size 
    n is also known as the "complete graph Kn").

    Write a function that takes the set E and delivers an
    integer result k, where k is the size of the largest clique
    in G.

*)

fun dfs [] test succ result = []
   |dfs (n::q) test succ result =
        if test n
        then (result n)::(dfs q test succ result)
        else dfs ((succ n)@q) test succ result;

(* dfs takes as arguments:
   a list of nodes that have been visited
   predicate to test if node is a leaf
   function to generate successors 
   function to interpret leaf as a result *)

fun bfs [] test succ result = []
   |bfs (n::q) test succ result =
        if test n
        then (result n)::(bfs q test succ result)
        else bfs (q@(succ n)) test succ result;

(* Note difference between dfs and bfs *)