;; 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))
   (make-node 'eli '(claire))))

;------------------------------------------------------------
;; DESIGN a program to check if a given [Listof Node] is a 
;; valid Graph

;; 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, check is each callee 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)

;------------------------------------------------------------
;; DESIGN path? which checks if there is a path from 
;; node a to node b in a given graph

;; path? : Graph Name Name -> Boolean
;; Is there a path from a to b in graph g?
;; Assume that a and b are in the graph
;; 1. get a's callees
;; 2. Is b in callees-a?
;;   -- if yes, true
;;   -- if no, recur on each of callees....
(define (path? g a b)
  ...)

;; callees-of : Graph Name -> [Listof Name]
;; retrieve calles of a in graph g
(define (callees-of g a)
  (node-callees
   (first 
    (filter (lambda (node) (symbol=? (node-name node) a)) g))))
  
;(callees-of a-graph 'amy) 

(check-expect (path a-graph 'amy 'dan) true)
(check-expect (path a-graph 'amy 'claire) true)
(check-expect (path a-graph 'claire 'dan) false)
(check-expect (path a-graph 'billy 'claire) true)