Also yours explodes if given a circular dependency. There is no way around
throwing an exception, but it is always nice not to have stack overflows in
your code:
(def graph
{"a" {:dependencies ["b" "d"]}
"b" {:dependencies ["c" "e"]}
"c" {:dependencies ["d" "e"]}
"d" {:dependencies ["c"]}
"e" {:dependencies []}})
(resolve-dep graph "c") => java.lang.StackOverflowError
On Sunday, June 9, 2013 10:30:51 AM UTC+2, Casper Clausen wrote:
>
> 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 clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
