Week 10 Set b
Due Date Thursday 11/7 at 9:00pm (Week 10)
Purpose To design functions over graphs.
Finger Exercises
Graded Exercises
; A Graph is a (make-graph [List-of Symbol] [Symbol -> [List-of Symbol]]) (define-struct graph [nodes neighbors]) ; and represents the nodes and edges in a graph. ; All of the symbols in nodes are assumed to be unique, as are the symbols in ; any list returned by neighbors, and all of the symbols returned by neighbors ; are assumed to be in nodes.
Exercise 2 Design the function neighbor-of? 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 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.
Exercise 4 Design graph=?, which determines if two graphs are equal. Keep in mind the order of nodes as well as the order of edges are unimportant, but the actual names of the nodes being the same as well as the same nodes having the same neighbors are.
Graph Manipulation
For this portion of the homework, you should 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))
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, 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 were pointing to either of the first two given nodes should now point to this new one, and the new node should point to all nodes either of the first two nodes were pointing to. Hint: A function you’ve previously designed will likely be of help here.
Exercise 6 Design reverse-edges 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, 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.