#lang racket
(require htdp/testing)

;; here is a small graph with a cycle
(define Graph1 '(  (a b) (b c) (c d) (d e) (e c) ))

;; reach?
;;  inputs: a starting node a
;;          an ending  node b
;;          a graph G
;;  output: #t if b is reachable from a in G
;;          #f otherwise
;;  (a is always reachable from a)
(define (reach? a b G)
  (cond
    ( (equal? a b) #t )  ;; any node is reachable from itself 
    ( (null? G) #f )     ;; nothing else is reachable in an empty G
    ( else
      (let* ( (EDGE (first G))  ; EDGE from c to d
              (c (first EDGE))  ; c is the start of EDGE
              (d (second EDGE)) ; d is the end of EDGE
              (R (rest G)) )    ; R is the rest of G
        
        (or (reach? a b R)      ; either you LOSE IT (don't use EDGE) 
            (and (reach? a c R) ; or you USE IT (use EDGE), going from
                 (reach? d b R)))) ))) ; a->c and d->b (EDGE is c->d)



;; tests
(check-expect (reach? 'a 'a Graph1)  #t)
(check-expect (reach? 'z 'z Graph1)  #t)
(check-expect (reach? 'a 'b Graph1)  #t)
(check-expect (reach? 'a 'e Graph1)  #t)
(check-expect (reach? 'e 'd Graph1)  #t)
(check-expect (reach? 'e 'a Graph1)  #f)
(check-expect (reach? 'z 'a Graph1)  #f)

;; how did we do?
(generate-report)