;; ------------------------------------------------------- (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)))) ;; good-graph? : Graph -> Boolean ;; Does graph g satisfy the NAME constraint? (define (good-graph? g) (local ((define names (map node-name g)) (define (good-graph-helper? g1) (cond [(empty? g1) true] [(cons? g1) (and (good-callees? (first g1) names) (good-graph-helper? (rest g1)))]))) (good-graph-helper? g))) (check-expect (good-graph? '()) true) (check-expect (good-graph? a-graph) true) (check-expect (good-graph? b-graph) false) ;; good-callees? : Node [List-of Name] -> Boolean ;; Are all of node's callees in list of names? (define (good-callees? node names) (andmap (λ (callee) (member? callee names)) (node-callees node))) (check-expect (good-callees? (make-node 'a '()) '(a b c)) true) (check-expect (good-callees? (make-node 'amy '(billy claire)) '(amy billy claire dan eli)) true) (check-expect (good-callees? (make-node 'amy '(billy amal)) '(amy billy claire dan eli)) false) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; path? : Graph Name Name -> Boolean ;; Is there a call path from a to b in graph g? ;; Assume that a and b are node-names in g (define (path? g a b) (local ((define callees-a (callee-list-of g a))) (cond [(empty? callees-a) false] [(member? b callees-a) true] ;; complex case: ;; if there is a path from any of a's callees to b, return true [else (ormap (λ (callee) (path? g callee b)) callees-a)]))) (check-expect (path? a-graph 'claire 'billy) false) (check-expect (path? a-graph 'billy 'claire) true) ;; callee-list-of : Graph Name -> [List-of Name] (define (callee-list-of g a) (node-callees (first (filter (λ (node) (symbol=? (node-name node) a)) g)))) (check-expect (callee-list-of a-graph 'amy) '(billy claire)) (check-expect (callee-list-of a-graph 'claire) '()) (check-expect (callee-list-of a-graph 'eli) '(claire))