Homework 10a🔗

MUST BE DONE WITH YOUR NEW PARTNERS

Due Date Tue at 9:00pm (Week 9)

Purpose Practice with graphs

Exercises

The representation is different from what we used in class. Instead of each node in the graph storing a list of the names of other nodes in the graph, here our graph has a function that computes the neighbors of a given node name. For instance, if we want to represent the graph

in class we would have represented this as

(list (list 'anne   '(billie carl))

(list 'billie '(anne))

(list 'carl   '(anne 'dave))

(list 'dave   '(carl)))

In this representation, we would instead use

(make-graph

'(anne billie carl dave) ; the names of the nodes

(lambda(name) ; a function computing the neighbors of each node

(cond [(symbol=? name 'anne)   '(billie carl)]

[(symbol=? name 'billie) '(anne)]

[(symbol=? name 'carl)   '(anne dave)]

[(symbol=? name 'dave)   '(carl)])))

Exercise 1 Make several more examples of graphs.

Graph Warmup

Exercise 2 Design the function (neighbor-of? g s1 s2) that takes a graph and two symbols and determines if the second symbol is a neighbor of the first one. Assume both symbols are in the graph.

Exercise 3 Design the function (both-neighbors s1 s2 g) that takes two symbols and a graph and returns the list of both of their neighbors, and be sure not to include any duplicates in the output. Assume both symbols are in the graph. Hint: A function you’ve previously designed will likely be of help here.

Graph Equality: Exact

Exercise 4 Design (graph=? g1 g2), which determines if two graphs are equal. Keep in mind that two nodes are the same if they are represented by the same symbol and have the same set of neighbors, and two graphs are the same if they have the same set of nodes. (Hint: how have we implemented set-equality before?)

Graph Manipulation

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

; Curried graph=?

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

; graph=?/some-expected-graph : Graph -> Boolean

(define graph=?/some-expected-graph (graph=?/curried some-expected-graph))

; This function checks whether any given graph is equal to some-expected-graph

Now we have a single-argument predicate that would work in check-satisfied...but it’s more convenient to not define this intermediate function explicitly, and just use graph=?/curried instead:

; f : Graph -> Graph

; Do something to graph g

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

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

(graph=?/curried some-expected-graph))

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

Exercise 5 Design the function (collapse s1 s2 s3 g), which takes in three nodes and a graph. The first two nodes are assumed to be in the graph, and the third is assumed not to be.

The function collapses the first two nodes into one new node, which is named by the third node. All nodes in the graph that nodes s1 or s2 as neighbors should now have the third node s3 as a neighbor. And the new node should have all the neighbors of the old nodes. Keep in mind that there should still be no duplicate nodes in any of the neighbor lists after the collapse, but nodes can have themselves as a neighbor. Hint: A function you’ve previously designed will likely be of help here.

Exercise 6 Design (reverse-edges g) which takes a graph and reverses the edges. Hint: A function you’ve previously designed will likely be of help here.

Exercise 7 Design the function (rename g los), which takes a graph and a list of symbols that is the same length of the nodes in the graph and renames the nodes in the graph to the names in the list of symbols. The nth node in the graph’s nodes should be renamed as the nth node in the given list. Assume the given list has no duplicates.