udacity eulerian path

euler.rkt

#lang racket

(define (can-have-eulerian-path? adj-hash)
  (define vertex-counts (map (λ (adjs) (length adjs)) (hash-values adj-hash)))
  (or (andmap even? vertex-counts)
      (= 2 (length (filter odd? vertex-counts)))))

(define (find-eulerian-path edges)
  (define adj-hash (build-adj-hash edges))
  (if (not (can-have-eulerian-path? adj-hash)) #f
      (let* ([verticies (hash-keys adj-hash)]
             [odd-verticies (filter (λ (v) (odd? (length (hash-ref adj-hash v)))) verticies)]
             [start-vertex (if (empty? odd-verticies) (first (first edges)) (first odd-verticies))])
        (define (seek-path remaining path current)
          (if (empty? remaining) (cons current path)
              (let ([edges-from-current (filter (λ (e) (member current e)) remaining)])
                ; (displayln  (format "~a: ~a" current remaining))
                (if (empty? edges-from-current) #f
                    (for/or ([e edges-from-current])
                      (seek-path (remove e remaining) (cons current path) (if (= (first e) current) (second e) (first e))))
                    )))) 
        (seek-path edges '() start-vertex)
        )))
        
        
(define test-graph-1 '((0 1) (1 2) (2 3) (3 0)))

(define test-graph-2
 '((0 1) (1 5) (1 7) (4 5)
  (4 8) (1 6) (3 7) (5 9)
  (2 4) (0 4) (2 5) (3 6) (8 9))) 
  

(define test-graph-3
  '((1 13) (1 6) (6 11) (3 13)
    (8 13) (0 6) (8 9)(5 9) (2 6) (6 10) (7 9)
    (1 12) (4 12) (5 14) (0 1)  (2 3) (4 11) (6 9)
    (7 14)  (10 13)
    ))
   
(define test-graph-4
  '((8 16) (8 18) (16 17) (18 19)
    (3 17) (13 17) (5 13)(3 4) (0 18) (3 14) (11 14)
    (1 8) (1 9) (4 12) (2 19)(1 10) (7 9) (13 15)
    (6 12) (0 1) (2 11) (3 18) (5 6) (7 15) (8 13) (10 17)
    ))