;; GRAPHS ;; ------------------------------------------------------- (define-struct node (name callees)) #| The call graph: --------------- A Graph is a [List-of Node] A Node is (make-node Name [List-of Name]) A Name is a Symbol. interpretation: The Graph (list (make-node 'a (list 'b ...)) (make-node 'b (list 'a ...)) ...) specifies people (by name) and who they call (by name). NAME CONSTRAINT: all names mentioned have a node |# (define a-graph (list (make-node 'amy '(billy claire)) (make-node 'billy '(dan)) (make-node 'claire '()) (make-node 'dan '(eli)) (make-node 'eli '(claire)))) (define b-graph (list (make-node 'amy '(billy claire)) (make-node 'billy '(dan)) (make-node 'claire '(amal)) ; not a good graph! (make-node 'dan '(amy)) (make-node 'eli '(claire)))) (define c-graph (list (make-node 'amy '(billy claire)) (make-node 'billy '(dan)) (make-node 'claire '(eli)) (make-node 'dan '(amy claire)) (make-node 'eli '(claire)))) ;; good-graph? : [Listof Node] -> Boolean ;; is g a good graph? (define (good-graph? g) (local ((define names (map node-name g))) (andmap (lambda (n) (good-callees? (node-callees n) names)) g))) ;; good-callees? : [Listof Name] [Listof Name] -> Boolean ;; given a list of callees, checks if each callee ;; has a node (i.e., is in names) (define (good-callees? callees names) (andmap (lambda (callee) (member? callee names)) callees)) (check-expect (good-graph? a-graph) true) (check-expect (good-graph? b-graph) false) (check-expect (good-graph? empty) true) ;------------------------------------------------------------ ;; DESIGN path? : First attempt ;; path? : Graph Name Name -> Boolean ;; is there a path from node a to b in graph g? ;; Assume that a and b are in g ;; 1. get a's callees ;; 2. Is b in callees-a? ;; -- if yes, true ;; -- if no, recur (define (path?.v1 g a b) (local ((define callees-a (callees-of g a))) (cond [(member? b callees-a) true] [else (ormap (lambda (callee-a) (path?.v1 g callee-a b)) callees-a)]))) ;; callees-of: Graph Name -> [Listof Name] ;; given a graph g and a node name n, return callees of n (define (callees-of g a) (node-callees (first (filter (lambda (node) (symbol=? a (node-name node))) g)))) (check-expect (callees-of a-graph 'amy) '(billy claire)) (check-expect (callees-of a-graph 'billy) '(dan)) (check-expect (path?.v1 a-graph 'amy 'claire) true) (check-expect (path?.v1 a-graph 'amy 'dan) true) (check-expect (path?.v1 a-graph 'claire 'dan) false) (check-expect (path?.v1 a-graph 'billy 'claire) true) ;(check-expect (path?.v1 c-graph 'amy 'eli) true) ; does not terminate ;------------------------------------------------------------ ;; DESIGN path? ;; Strategy: remove node from graph [COMPLETE THIS VERSION YOURSELF] ;; path? : Graph Name Name -> Boolean ;; is there a path from node a to b in graph g? ;; Assume that a and b are in g ;; 2. Is b in callees-a? ;; -- if yes, true ;; -- if no, recur #;(define (path?.v2 g a b) (local ((define callees-a (callees-of g a))) (cond [(member? b callees-a) true] [else (ormap (lambda (callee-a) (path?.v2 (remove-node g a) callee-a b)) callees-a)]))) #| (check-expect (path?.v2 a-graph 'amy 'claire) true) (check-expect (path?.v2 a-graph 'amy 'dan) true) (check-expect (path?.v2 a-graph 'claire 'dan) false) (check-expect (path?.v2 a-graph 'billy 'claire) true) (check-expect (path?.v2 c-graph 'amy 'eli) true) |# ;; remove-node : Graph Name -> Graph ;; remove a from graph g (i.e. remove node for a and remove ;; a from callees of all nodes) (define (remove-node g a) ...) ;; [COMPLETE YOURSELF] #;(check-expect (remove-node c-graph 'claire) (list (make-node 'amy '(billy)) (make-node 'billy '(dan)) (make-node 'dan '(amy)) (make-node 'eli '()))) ;------------------------------------------------------------ ;; DESIGN path? ;; Strategy: Keep track of visited nodes (Accumulator) ;; path? : Graph Name Name -> Boolean ;; is there a path from node a to b in graph g? ;; Assume that a and b are in g ;; 2. Is b in callees-a? ;; -- if yes, true ;; -- if no, recur ;; TERMINATES: because with each recursive call, the list of visited ;; nodes grows, and we never add a node name to visited twice, so we (define (path?.v3 g a b) (local (;; Name [Listof Name] -> Boolean (define (path-helper? a visited) (local ((define callees-a (callees-of g a))) (cond [(member? a visited) false] ;; stop if seen a before [(member? b callees-a) true] [else (ormap (lambda (callee-a) (path-helper? callee-a (cons a visited))) callees-a)])))) (path-helper? a empty))) (check-expect (path?.v3 a-graph 'amy 'claire) true) (check-expect (path?.v3 a-graph 'amy 'dan) true) (check-expect (path?.v3 a-graph 'claire 'dan) false) (check-expect (path?.v3 a-graph 'billy 'claire) true) (check-expect (path?.v3 c-graph 'amy 'eli) true)