Arc Forumnew | comments | leaders | submitlogin
2 points by vrk 6160 days ago | link | parent

  (= src car)
  (= trg cadr)
  (= w car:cddr)

  (def make-edges l
    (let edges (join l (map [list trg._ src._ w._] l))
      (let from [keep (fn (e) (is src.e _)) edges]
          (rfn fetch (a)
              (if (no a) nil
                  (atom a) (from a)
                  (join (from car.a) (fetch cdr.a)))))))

  ; Dijkstra's algorithm.
  (def shortest-paths (edges s) 
    (with (T (table)
           S (table)
           num [case _ nil +inf.0 _])
      (= T.s 0)
      (= S.s t)
      (trav edges.s
         [map [= (T:trg _) (min (num:T:trg _) (+ (num:T:src _) w._))] _]
         [map [= (S:trg _) t] _]
         [let next (keep no:S:trg (edges (map trg _)))
                 (let m (apply min (map num:T:trg next))
                   (self (keep [<= (num:T:trg _) m] next)))])
      T))

  (= edges (make-edges 
                '(a b 2) '(a c 3)
                '(b c 2) '(b d 1) '(b e 3) '(b f 2)
                '(c e 1)
                '(d e 2) '(d f 1)
                '(e f 2)))

  (prn (shortest-paths edges 'a))
It looks a bit unwieldy, and one could argue this is perverse use of the trav macro, but there you have it.