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?
Nick Day <nicke...@gmail.com> writes:
> 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?
clojure.contrib.graph/dependency-list might be close enough for you
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.
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. :)
> 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.
> 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. :)
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+unsubscribe@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
|
