Skip to content

Instantly share code, notes, and snippets.

@jgdavey
Created March 4, 2014 02:26
Show Gist options
  • Save jgdavey/9339165 to your computer and use it in GitHub Desktop.
Save jgdavey/9339165 to your computer and use it in GitHub Desktop.
How to get paths for map of sets?
(use 'clojure.test)
(deftest tracing-paths
(testing "trace-paths"
(is (= (trace-paths {:a nil} :a)
[[:a]]))
(is (= (trace-paths {:a #{:b}
:b nil} :a)
[[:a :b]]))
(is (= (trace-paths {:a #{:b :c}
:b nil
:c #{:b}} :a)
[[:a :c :b] [:a :b]]))
(is (= (trace-paths {:a #{:b}
:b #{:c :d}
:c #{:d}
:d nil} :a)
[[:a :b :c :d] [:a :b :d]]))))
@Chouser
Copy link

Chouser commented Mar 4, 2014

How's this? The paths fn is more general:

(defn paths
  "Returns a lazy seq of all non-looping path vectors starting with
  [<start-node>]"
  [nodes-fn path]
  (let [this-node (peek path)]
    (->> (nodes-fn this-node)
         (filter #(not-any? (fn [edge] (= edge [this-node %]))
                            (partition 2 1 path)))
         (mapcat #(paths nodes-fn (conj path %)))
         (cons path))))

(defn trace-paths [m start]
  (remove #(m (peek %)) (paths m [start])))

@jgdavey
Copy link
Author

jgdavey commented Mar 4, 2014

@Chouser Nice!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment