all-paths.clj

;;Computes all possible paths through a graph (DAG)
;;assumes the graph is a DAG
;; Clojure

(defn all-paths [g]
  (let [walk (fn walk [g seen n]
               (cond
                (empty? (g n)) seen
                :else (mapcat (fn [m]
                       (walk g (conj seen m) m)) (g n))))]
    (walk g [:u1] :u1)))

;;example
(all-paths {:u1 [:u2 :u3] :u2 [:u4] :u3 [:u4 :u6] :u4 [:u5] :u6 [:u5 :u7]})
;;(:u1 :u2 :u4 :u5 :u1 :u3 :u4 :u5 :u1 :u3 :u6 :u5 :u1 :u3 :u6 :u7)