Homework 11
Due Date Tuesday 11/23 at 9:00pm (Week 11)
Purpose To design more functions over graphs and practice with accumulators.
Graded Exercises
Graphs
; A {X} [Set-of X] is a [List-of X], where order does not matter and all elements are unique. ; A Graph is a (make-graph [Set-of Symbol] [Symbol -> [Set-of Symbol]]) (define-struct graph [nodes neighbors]) ; and represents the nodes and edges in a graph. ; The neighbors function is only guaranteed to work for symbols that are in the ; set of nodes, and is guaranteed to return a set of symbols that are also in ; the set of nodes (i.e. the graph is well-formed).
To get a sense of how this representation works, you should think about how to take the small examples we built in class with the previous representation, and re-express them using this representation.
Exercise 1 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 2 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 3 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.
Note on make-graph=? : By analogy, consider the function (define (make-add x) (lambda (y) (+ x y))) that takes a number and produces a function that will add its argument to the original x.
; make-graph=? : Graph -> [Graph -> Boolean] ; Takes a graph and produces a function that checks if ; its argument is graph=? to the original graph (define make-graph=? (λ (g1) (λ (g2) (graph=? g1 g2)))) ; f : Graph ... -> Graph ; Do something to g (define (f g ...) ...) (check-satisfied (f some-input-graph ...) (make-graph=? 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, 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. (To make sure you understand what collapse is supposed to do, you should first sketch out a graph before collapse and after—
in other words, it helps to first sketch/visualize the input and output graphs of a test.) Hint: A function you’ve previously designed will likely be of help here.
More Graph Manipulation
As before, when you create and manipulate graphs, always be sure to uphold the assumptions we made about graphs in our data definition.
Exercise 5 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 6 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.
Exercise 7 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 8 Design find-all-paths, which finds all possible paths between two given nodes in a graph. Assume both nodes are in the graph. You should not include cycles in your paths. 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)) ; NOTE: don't include the path A->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))
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.
Exercise 9 Design the function connected? which determines if every node in a graph can reach every other node in a graph. Hint: A function you’ve previously designed will likely be of help here.
Exercise 10 Design undirected? which determines if each edge in the graph has a matching edge going the opposite direction. Hint: A function you’ve previously designed will likely be of help here.
Extra Credit - Graph Equality: Structural
The following exercise is extra credit. Not completing it will have no negative impact on your grade.
Exercise 11 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.