Just for the fun of writing it: (defn topological-sort [x] (mapcat #(for [[k v] % :when (empty? v)] k) (take-while seq (iterate #(into {} (for [[k v] % :when (seq v)] [k (mapcat % v)])) x))))
user=> (topological-sort {1 [2 3] 2 [3] 3 []}) (3 2 1) Note that it's not the same algorithm as Jon's and it doesn't detect cycles. Christophe On Thu, Nov 12, 2009 at 7:06 AM, John Harrop <jharrop...@gmail.com> wrote: > On Wed, Nov 11, 2009 at 2:04 PM, Nick Day <nicke...@gmail.com> wrote: >> >> Hi, >> >> I've been trying to implement a topological sort and have been >> struggling a bit. I have a map of symbol vs collection of symbols >> like: >> >> {a [b c], b [c], c [nil]} >> >> which can be read as 'a' depends on 'b' and 'c', 'b' depends on 'c' >> and 'c' doesn't depend on anything. I've been trying to write >> something that returns a collection of the dependencies in order (c, >> b, a) but so far I've only been able to do it using a ref to store >> intermediate output of the sorting. I was wondering if anyone has >> already done something similar? > > You mean pure functionally? > First, I'd represent no dependencies as an empty vector rather than a vector > with a single nil in it. > Then, consider how you get the first few entries: you find all the nodes > with no dependencies. > How do you get the next few? The nodes whose only dependencies are nodes you > already have. > This suggests the algorithm: > (defn find-a-node [deps already-have-nodes] > (some (fn [[k v]] (if (empty? (remove already-have-nodes v)) k)) deps)) > This will return a key from deps whose corresponding value contains no > objects not in the set already-have-nodes. > Next, we just need to apply it repeatedly until it comes up empty: > (defn order-nodes [deps] > (loop [deps deps already-have-nodes #{} output []] > (if (empty? deps) > output > (if-let [item (find-a-node deps already-have-nodes)] > (recur > (dissoc deps item) > (conj already-have-nodes item) > (conj output item)) > (throw (Exception. "Circular dependency.")))))) > This seems to work: > user=> (order-nodes {1 [2 3] 2 [3] 3 []}) > [3 2 1] > user=> (order-nodes {1 [2 3] 2 [3] 3 [2]}) > #<CompilerException java.lang.Exception: Circular dependency. > (NO_SOURCE_FILE:0)> > No refs, atoms, or other mutable state, or cheating using Java mutable > objects or set-var-root!, etc.; rewriting the above with iterate, reduce, or > similar instead of loop/recur is left as an exercise for the reader. :) > > -- > 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 -- Professional: http://cgrand.net/ (fr) On Clojure: http://clj-me.cgrand.net/ (en) -- 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