Assignment 20

Due Date Mon 4/3 at 11:59pm

Possible Points 37

Purpose To design more complex functions that process graphs.

Graded Exercises

Exercise 1 Design the function same-graph? that determines in two graphs are the same. The following tests should pass:

(check-expect  (same-graph? (make-graph '(a) (lambda (x) '()))

(make-graph '() (lambda (x) '())))

#false)

(check-expect (same-graph? (make-graph '(a) (lambda (x) '()))

(make-graph '(a) (lambda (x) '())))

#true)

(check-expect (same-graph? (make-graph '(b) (lambda (x) '()))

(make-graph '(a) (lambda (x) '())))

#false)

(check-expect (same-graph? (make-graph '(a b) (lambda (x) '()))

(make-graph '(b a) (lambda (x) '())))

#true)

(check-expect (same-graph? (make-graph '(a b)

(lambda (x)

(cond

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

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

(make-graph '(a b)

(lambda (x)

(cond

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

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

#false)

(check-expect (same-graph? (make-graph '(a b)

(lambda (x)

(cond

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

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

(make-graph '(b a)

(lambda (x)

(cond

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

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

#true)

Exercise 2 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)

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