Submit the code files as graphs.ss and graphs.pl. Your analysis should be submitted as graphs.txt.
This assignment is subject to clarifications but the overall task will not change. You may assume all input is valid, please document your input assumptions in a comment.
Use #lang scheme to define the language in your scheme source file. This will let you work on the lab computers, if you wish to do so. Your Scheme will be evaluated with drracket/mzscheme on mathlab. Your Prolog will be evaluated with swipl on mathlab.
For this assignment, you may work with a partner, or you may work on your own. If you choose to work with a partner, submit one assignment from one of your accounts. Include both partners' names and IDs in a header comment. You are expected to colaborate with your partner but not with other students, although you may discuss syntax and general approach with others.
Attempt to use clear style. Your code should be lightly commented. Include a header with your name and UTorID, and that of your partner, if you have one. Make use of tail recursion and higher order functions wherever possible in Scheme. (if a b (if c d)) and similar nested ifs should use cond. In Prolog, do not use singleton variables, and a rule like: g(A,B):-A=B. should be written g(A,A). Style rules you've learned in previous courses still apply.
Please let me know of any ambiguities in this assignment specification as soon as possible.
Graphs, Paths, and Cycles(48)
Graphs are fundamental data structures that we use for many purposes in computer science. An (undirected) graph is made up of vertices (or nodes), and edges which connect a pair of vertices. While graphs can be directed, for the purposes of this question, our graphs will be undirected, the edges have no associated direction.
We can use Scheme and Prolog lists to represent a graph. We will describe a graph
with a pair: a number, which is the number of vertices in the graph, and a list of
pairs of numbers, which represent the edges of the graph. The edges are always in increasing order
within the pair, and the pairs sorted in increasing
order.
This graph would be represented as the list:
'(5 ((1 2)(2 3)(3 4)(3 5)(4 5)))
in Scheme. The Prolog representation has the same structure, but uses Prolog syntax:
graph(5, [[1,2],[2,3],[3,4],[3,5],[4,5]]).
Your task is to write a set of functions to analyze and manipulate graphs. You may search for algorithms and you should use any algorithms you have learned from previous courses. You may also discuss graph algorithms with others in the course, or anyone else. You may not search for code, and should not share your code with anyone but your partner.
Question 1 - Paths(18)
There is a path between two vertices if there is a series of edges that you can use to travel between them. For example, between vertices 1 and 3 above, there is a path made up of the edges (1 2) and (2 3), written ((1 2)(2 3)). A path may not include repeated vertices.
Write two functions: in Scheme, a predicate path?, which takes a graph and two numbers indicating
vertices, which returns true iff there is a path between them.:
(path? '(5 ((1 2)(2 3)(3 4)(3 5)(4 5))) 1 5)
#t
(path? '(5 ((1 2)(3 4)(3 5)(4 5))) 1 5)
#f
In Prolog, write a query path(+G, +V1, +V2) which succeeds iff there is a path in graph G between
vertices V1 and V2.
path(graph(5, [[1,2],[2,3],[3,4],[3,5],[4,5]]), 1 5).
true.
path(graph(5, [[1,2],[3,4],[3,5],[4,5]]), 1 5).
false.
Question 2 - Cycles(18)
A graph has a cycle if there is a path from a vertex back to itself, without using the same edge twice. A cycle does not have any repeated vertices along this path. In the example graph, there is one cycle, (3 4)(4 5)(5 3).In Scheme, write a function that returns a list representing a cycle, or the empty list if the graph is acyclic (has no cycles). If the graph has multiple cycles, you should return the first one in numeric order.
(cycle '(5 ((1 2)(2 3)(3 4)(3 5)(4 5))))
((3 4)(4 5)(3 5))
(cycle '(5 ((1 2)(2 3)(3 4)(4 5))))
()
(please note examples corrected from original)
Similarly, write a cycle detecter predicate in prolog, cycle(+G, ?C) in which C is unified to a list representing the first cycle in graph G, or the empty list [] if there is no cycle.