;; file:  hw3pr3.rkt
;; submission site id/login:
;; time spent:
;; other comments?

#lang racket
(require htdp/testing)
(require racket/trace)

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

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Graphs for testing
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;; This graph makes it clearer how graphs are created:
(define TinyGraph 
  (add-edge (make-edge 'a 'b 1) 
            (add-edge (make-edge 'b 'a 1)
                      (make-empty-graph))))

; identical result to BigGraph 
(define BigGraphVerbose 
  (add-edge (make-edge 'a 'b 1)
  (add-edge (make-edge 'b 'c 1) 
  (add-edge (make-edge 'c 'd 1) 
  (add-edge (make-edge 'd 'e 1)
  (add-edge (make-edge 'c 'f 1) 
  (add-edge (make-edge 'e 'g 1) 
  (add-edge (make-edge 'e 'h 1) 
  (add-edge (make-edge 'f 'x 1) 
  (add-edge (make-edge 'x 'y 1) 
  (add-edge (make-edge 'y 'z 1) 
  (add-edge (make-edge 'z 'b 1) 
  (make-empty-graph)))))))))))))


(define BigGraph
  (foldr add-edge 
         (make-empty-graph) 
         (map make-edge 
              '(a b c d c e e f x y z)
              '(b c d e f g h x y z b)
              '(1 1 1 1 1 1 1 1 1 1 1))))
         
(define Graph2 
    (foldr add-edge 
         (make-empty-graph)
         (map make-edge
              '(e   a  e  a  a  a  b  b  d  b   c  c)
              '(b   b  a  c  d  e  c  d  e  e   d  e)
              '(100 25 42 7  13 15 10 5  2  100 1  7))))          

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Define additional graphs here:




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 2
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (gchildren N node G)
  0)

; provided tests
(check-expect (gchildren 0 'a BigGraph) '(a))
(check-expect (gchildren 1 'a BigGraph) '(b))
(check-expect (gchildren 2 'a BigGraph) '(c))

;; these tests use sortsym to avoid ambiguity in node order...
(define (sym<? s1 s2) (string<? (symbol->string s1) (symbol->string s2)))
(define (sortsym L) (sort L sym<?)) ;; will sort a list of symbols

(check-expect (sortsym (gchildren 1 'c BigGraph)) '(d f))
(check-expect (sortsym (gchildren 2 'c BigGraph)) '(e x))
(check-expect (sortsym (gchildren 3 'a BigGraph)) '(d f))
(check-expect (sortsym (gchildren 3 'c BigGraph)) '(g h y))

; additional tests

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 3
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; No path in the assignment will have combined weight more than worstCost
(define worstCost 42000000)

(define (min-dist a b G)
  0)

; provided tests
(check-expect (min-dist 'a 'e Graph2) 10)
(check-expect (min-dist 'e 'b Graph2) 67)
(check-expect (min-dist 'd 'd Graph2) 0)
(check-expect (min-dist 'f 'a Graph2) worstCost)

; additional tests