;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; CS212 Spring 1999 Problem Set 4
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;; Graph type definitions and constructors

(defstruct <graph>
  (vertices <list>)
  (edges    <list>))

(defstruct <vertex>
  name)

(defstruct <edge>
  (from <vertex>)
  (to   <vertex>))

(define (find-vertex name vlist)
  (let ((v (filter (lambda (v) (eq? (get-vertex-name v) name)) vlist)))
    (if (null? v)
      #f
      (head v))))

(define (create-graph vertex-name-list edge-name-list)
  (let* ((vlist (map make-vertex vertex-name-list))
         (elist (map (lambda (e)
                       (make-edge (find-vertex (first e) vlist)
                                  (find-vertex (second e) vlist)))
                     edge-name-list)))
    (make-graph vlist elist)))


;;; Output a list of vertices or edges.

(define (display-vertices vlist)
  (map get-vertex-name vlist))

(define (display-edges elist)
  (map (lambda (e) (list (get-vertex-name (edge-from e))
                         (get-vertex-name (edge-to e))))
       elist))


;;; Convert a decimal number to a list of binary representation.
(define (decimal->binary-list n)
  (define (n->binary-list n binlist)
    (if (zero? n)
      binlist
      (n->binary-list (quotient n 2) (cons (if (even? n) 0 1) binlist))))
  (n->binary-list n empty))


;;; Set operations.

(define (remove-duplicates l)
  (define (remove-dups-t l result)
    (cond ((null? l) result)
          ((member (head l) result) (remove-dups-t (tail l) result))
          (else (remove-dups-t (tail l) (cons (head l) result)))))
  (reverse (remove-dups-t l empty)))

(define (union l1 l2)
  (remove-duplicates (append l1 l2)))

(define (intersect l1 l2)
  (define (intersect-with-l2 l result)
    (cond ((null? l)
           result)
          ((member (head l) l2)
           (intersect-with-l2 (tail l) (cons (head l) result)))
          (else
           (intersect-with-l2 (tail l) result))))
  (intersect-with-l2 l1 empty))

;;; Combine two symbols.
(define (combine-names s1 s2)
  (symbol-append s1 '- s2))