Homework 9b
MUST BE DONE SOLO
Due Date Thu at 9:00pm (Week 9)
Purpose Practice with graphs
Exercises
(define-struct graph [nodes neighbors]) (define AGraph (signature [GraphOf [ListOf Symbol] (Symbol -> [ListOf Symbol])])) ; and represents the nodes and edges in a graph. ; All symbols that represent nodes are assumed to be unique ; All symbols returned by (graph-neighbors _) will also be unique ; All symbols returned by (graph-neighbors _) are assumed to be in nodes
Exercise 1 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 2 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.
Exercise 3 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.
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 4 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 5 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 6 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.