Homework 11a🔗

Due Date Wednesday at 9:00pm (Week 11)

MUST BE DONE WITH YOUR PARTNER

Purpose More practice designing functions over graphs

Graded Exercises

Note: Some of these problems require accumulators; some require generative recursion; some can be solved structurally; and some might simply be composed of other functions. For all problems, explain which approach you’re taking, and why, and provide an accumulator statement or termination statement as appropriate.

Note: several of these functions will be aided by the appropriate use of list abstractions. If you’d like to explore a bit, you may also (require 2htdp/abstraction) and play around with some of the loop utilities that it provides. This is not required, but it might be intriguing.

More Graph Manipulation

You should again use the following testing pattern when testing some function f that outputs a graph. Check the docs for check-satisfied for more info.

; graph=?/curried : Graph -> [Graph -> Boolean]

; Curried graph=?

(define graph=?/curried (λ (g1) (λ (g2) (graph=? g1 g2))))

; f : Graph ... -> Graph

; Do something to g

(define (f g ...) ...)

(check-satisfied (f some-input-graph ...)

(graph=?/curried

some-expected-graph))

As before, when you create and manipulate graphs, always be sure to uphold the assumptions we made about graphs in our data definition.

Exercise 1 Design the function swap, which “swaps” a graph’s nodes with its edges.

More formally, if the n1th node points to the n2th node in the graph, the new graph should have a node with a name of the form 'n1->n2. If two nodes 'n1->n2 and 'n3->n4 exist in this new graph, then 'n1->n2 has an edge pointing to 'n3->n4 if and only if n2 equals n3. We use this index-based naming convention as a way to avoid any possible difficulty with potentially problematic initial node names, such as if a node were actually named something like 'a->b (or even sillier, '0->1).

For example, here is a graph and its swapped verison:

(make-graph '(a b c)

(λ (n) (cond [(symbol=? n 'a) '(b c)]

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

[(symbol=? n 'c) '(a)])))

(make-graph '(0->1 0->2 1->1 2->0)

(λ (n) (cond [(symbol=? n '0->1) '(1->1)]

[(symbol=? n '0->2) '(2->0)]

[(symbol=? n '1->1) '(1->1)]

[(symbol=? n '2->0) '(0->1 0->2)])))

Constructing the node names will be a minor challenge, since you will need to use several functions in ISL+ that we have not yet needed. One such function is string->symbol, which does exactly what its name implies: it takes a string and produces a symbol whose name is that string — (string->symbol "hello") produces 'hello. You may use other functions from ISL+ to construct the strings you’ll need.

You will find the following function helpful. Note that this is the only place in the homework any function from racket/string is allowed to be used.

(require racket/string)

; node-name->numbers : Symbol -> (list Nat Nat)

; Convert a symbol of the form 'n1->n2 to (list n1 n2)

(define (node-name->numbers s)

(map string->number (string-split (symbol->string s) "->")))

(check-expect (node-name->numbers '0->3) '(0 3))

Hint: A function you’ve previously designed will likely be of help here.

Graph Walks

Exercise 2 Design close?, which takes a graph, two nodes, and a natural number, and determines if the second node is within that many steps of the first node. Assume both nodes are in the graph.

Exercise 3 Design find-all-paths, which finds the set of all possible acyclic paths between two given nodes in a graph (i.e. all paths with no loops in them). Assume both nodes are in the graph. Some examples are illustrated below:

(define G1

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

(λ (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-all-paths G1 'C 'C) --> '((C)) ; src = dest

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

(find-all-paths G1 'A 'B) --> '((A B)) ; skip looping paths like (A B E A B)

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

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

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

(Hint: the easiest solution to this problem will produce exactly these paths in exactly this order. Your solution might produce the paths in a different order, though; the order itself is not important — though obviously the order of nodes along an individual path is important.)

Graph Properties

Use check-satisfied to test the following functions, on graphs which both do and don’t have the properties they are checking. You will have to do some slightly clever manipulation to test on graphs that don’t have the property in question, but it shouldn’t require defining a new, named function.

Extra Credit - Graph Equality: Structural

The following exercise is extra credit. Not completing it will have no negative impact on your grade.

Exercise 6 Design graph-shape=?, which determines if two graphs have the same shapes. Here, we do not care about the names of the nodes being the same. Hint: A function you’ve previously designed will likely be of help here.