;; -------------------------------------------------------
(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))