Here is a similar algorithm I did for work a while back:
(defn- find-next-node [deps used-nodes]
(some (fn [[k v]] (if (empty? (remove used-nodes v)) k)) deps))
(defn topsort
"Takes a map of dependencies between items and performs a topological
sort.
E.g. (topsort {1 [2 3] 3 [] 2 [3]}) => [3 2 1]"
[deps]
(loop [deps deps res []]
(if (empty? deps)
res
(if-let [item (find-next-node deps (set res))]
(recur (dissoc deps item) (conj res item))
(throw (Exception. (str "A circular dependency was found: "
deps)))))))
I am not sure if it is optimal, but it does it without the atom which is a
bit nicer i think. I'm also open to input for a better way of course.
On Friday, May 31, 2013 6:33:59 PM UTC+2, Alice wrote:
>
> (def graph
> {"a" {:dependencies ["b" "d"]}
> "b" {:dependencies ["c" "e"]}
> "c" {:dependencies ["d" "e"]}
> "d" {:dependencies []}
> "e" {:dependencies []}})
>
> (defn resolve-dep
> [graph name]
> (let [resolved (atom [])
> resolved-set (atom #{})
> f (fn f [name]
> (doseq [x (:dependencies (graph name))]
> (f x))
> (when-not (@resolved-set name)
> (swap! resolved conj name)
> (swap! resolved-set conj name)))]
> (f name)
> @resolved))
>
> (resolve-dep graph "a")
> ;=> ["d" "e" "c" "b" "a"]
>
> This code works, but not sure if it's idiomatic clojure code.
> The use of atom feels like procedural than functional to me since
> there's no concurrency involved at all.
>
> Any suggestions?
>
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
