(* (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 *)