Assignment 20

Due Date Mon 4/3 at 11:59pm

Possible Points 30

Purpose To design complex functions that process graphs and begin to use accumulators.

Graded Exercises

Exercise 1 Design reverse-edges which takes a graph and reverses the edges. The following test should pass:

(check-expect (same-graph?

(reverse-edges

(make-graph '(a b c)

(lambda (x)

(cond [(symbol=? x 'a) '(a b)]

[(symbol=? x 'b) '()]

[(symbol=? x 'c) '(b c)]))))

(make-graph '(a b c)

(lambda (x)

(cond [(symbol=? x 'a) '(a)]

[(symbol=? x 'b) '(a c)]

[(symbol=? x 'c) '(c)]))))

#true)

Code for same-graph? will be uploaded to the blog on the March 30th.

Exercise 2 Design undirected? which determines if each edge in the graph has a matching edge going the opposite direction.

Exercise 3 Design find-paths which finds all paths in the graph from one node to another. An example graph as well as informally written tests are below:

(define G1

(make-graph '(A B C D E F G)

(lambda (n)

(cond [(symbol=? n 'A) '(B E)]

[(symbol=? n 'B) '(E F)]

[(symbol=? n 'C) '(D)]

[(symbol=? n 'D) '()]

[(symbol=? n 'E) '(C F A)]

[(symbol=? n 'F) '(D G)]

[(symbol=? n 'G) '()]))))

(find-paths G1 'C 'C) -> '((C)) ; src = dest

(find-paths G1 'C 'G) -> '() ; no paths from 'C to 'G

(find-paths G1 'A 'B) -> '((A B))

(find-paths G1 'E 'G) -> '((E F G)  (E A B F G))

(find-paths G1 'B 'G) -> '((B E F G)  (B F G))

(find-paths G1 'A 'G) -> '((A B E F G) (A B F G) (A E F G))