#lang racket
(require htdp/testing)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Weighted Edge interface
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; make-edge: creates a weighted edge from a source and destination node and a weight
;;   inputs: a source node and a desintation node
;;   output: a weighted edge edge
(define (make-edge s d w)
  (list s d w))

;; src: gets the source of an edge
;;   inputs: a weighted edge
;;   output: the source node of the edge
(define (src edge)
  (first edge))

;; dest: gets the destination of an edge
;;   inputs: a weighted edge
;;   output: the destination node of the edge
(define (dst edge)
  (second edge))

;; weight: gets the weight of an edge
;;   inputs: a weighted edge
;;   output: the edge's weight
(define (weight edge)
  (third edge))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Graph interface
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; make-empty-graph: 
;;   inputs: none
;;   output: an empty graph
(define (make-empty-graph) 
  '())

;; add-edge: adds an edge to a graph (does not check for duplicates)
;;   inputs: an edge and a graph
;;   output: a new graph that includes the given edge
(define (add-edge e G) 
  (cons e G))

;; emptyGraph?:
;;   inputs: a graph
;;   output: #t if the graph is empty; #f otherwise
(define (emptyGraph? G)
  (null? G))

;; edge-list: gets a list of edges in the graph
;;   inputs: a graph
;;   output: a list of edges in the graph
(define (edge-list G)
  G)

;; remove-edge: removes an edge from a graph
;;   inputs: an edge and a graph
;;   output: a new graph that excludes the given edge
(define (remove-edge e G)
  (remove e G))

;; here is a small graph with a cycle
(define Graph1 
    (foldr add-edge 
         (make-empty-graph)
         (map make-edge
              '(a b c d e)
              '(b c d e c)
              '(1 1 1 1 1))))

;; reachable?
;;  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 (reachable? a b G)
  (cond [(equal? a b) #t]
        [(emptyGraph? G) #f]
        [else (let* ([edges (edge-list G)]
                     [it (first edges)]
                     [subG (remove-edge it G)]
                     [lose-it (reachable? a b subG)]
                     [use-it (and (reachable? a (src it) subG) 
                                  (reachable? (dst it) b subG))])
                (or use-it lose-it))]))


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

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