Re: Topological sort
user> (topological-sort {0 [1] 1 [2 3] 2 [3] 3 []})
(3 2 0 1)
!
--
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/d/optout.
Re: Topological sort
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
Re: Topological sort
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
Topological sort
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?
cheers,
Nick
--
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
Re: Topological sort
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
(use 'clojure.contrib.graph)
(dependency-list {:nodes [:a :b :c]
:neighbors {:a [:b :c]
:b [:c]}})
=[#{:c} #{:b} #{:a}]
--
jan
--
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
Re: Topological sort
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
