brilliant, this has been very helpful - thanks to both for taking the
time to answer!
On Nov 12, 6: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
