Walking a tree
Good morning everyone!
I have a problem that I have been struggling with for a few days now. I
have a directed acyclic graph that I am trying to walk, and can't seem to
figure out a to prevent my walking already visited branches. Here is the
code
(def values
[{:v a :parent [b]}
{:v b :parent [c]}
{:v c :parent [d e]}
{:v d :parent [f]}
{:v e :parent [f]}
{:v f}])
As you can see, I have a vector of records, each with a value and a
vector of parents. A node can have more than zero or more parents.
a o
|
b o
|
c o
|\
d o o e
|/
f o
Here is the fruits of several attempts ...
(defn walk-tree
([values]
(letfn [(in?
[seq elm]
(some #(= elm %) seq))
(walk [already id]
(when-not (in? already id)
(when-let [n (some #(if (= id (:v %)) %) values)]
(lazy-seq
(cons (:v n)
(mapcat #(walk (conj already (:v n)) %) (:parent
n)))]
(walk #{} (:v (first values))
I was hoping to use the set as a way to record which nodes have been
visited. Unfortunately as you might be able to tell, that's not going to
work. The result of running this is
(a b c d f e f)
Notice that f gets in the list twice. One way to do it would be to make a
set out of it, but that eliminates the laziness aspect.
Can anyone point me in the right direction here?
Thanks,
Raju
--
--
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.
Re: Walking a tree
On Jul 6, 2013, at 9:33 AM, looselytyped raju.gan...@gmail.com wrote:
Good morning everyone!
I have a problem that I have been struggling with for a few days now. I have
a directed acyclic graph that I am trying to walk, and can't seem to figure
out a to prevent my walking already visited branches. Here is the code
(def values
[{:v a :parent [b]}
{:v b :parent [c]}
{:v c :parent [d e]}
{:v d :parent [f]}
{:v e :parent [f]}
{:v f}])
It sounds like what you have here is not a directed acyclic graph. In DAGs all
links
are directed and there are no cycles.
As you can see, I have a vector of records, each with a value and a vector
of parents. A node can have more than zero or more parents.
a o
|
b o
|
c o
|\
d o o e
|/
f o
You might want to look at standard graph traversal algorithms, like DFS and
BFS [1]. I'd also suggest to store links to childs instead of links to parents,
so
you don't have to traverse it backwards, though for undirected graph there's no
difference .
[1] http://en.wikipedia.org/wiki/Graph_traversal
--
ST4096-RIPE
--
--
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.
Re: Walking a tree
Give this a go:
(defn ^:private walk-tree* [all seen to-do]
(when-let [[curr others] to-do]
(if (contains? seen curr)
(recur all seen others)
(lazy-seq
(when-let [node (first (filter #(= (:v %) curr) all))]
(println node)
(cons curr
(walk-tree* all
(conj seen curr)
(concat others
(:parent node)
(defn walk-tree [all]
(walk-tree* all #{} [(- all first :v)]))
I'm still not super happy with it, but it should solve your problem. The
basic trick is to not use things like `mapcat`, as you need to keep
updating some state (the `seen` map) between calls. The approach here is to
pass work to be done and work to be ignored together. Then both can be
kept up to date in sync with each other. Your recursion becomes a bit more
explicit, too.
I hope that helps!
On 7 July 2013 00:33, looselytyped raju.gan...@gmail.com wrote:
Good morning everyone!
I have a problem that I have been struggling with for a few days now. I
have a directed acyclic graph that I am trying to walk, and can't seem to
figure out a to prevent my walking already visited branches. Here is the
code
(def values
[{:v a :parent [b]}
{:v b :parent [c]}
{:v c :parent [d e]}
{:v d :parent [f]}
{:v e :parent [f]}
{:v f}])
As you can see, I have a vector of records, each with a value and a
vector of parents. A node can have more than zero or more parents.
a o
|
b o
|
c o
|\
d o o e
|/
f o
Here is the fruits of several attempts ...
(defn walk-tree
([values]
(letfn [(in?
[seq elm]
(some #(= elm %) seq))
(walk [already id]
(when-not (in? already id)
(when-let [n (some #(if (= id (:v %)) %) values)]
(lazy-seq
(cons (:v n)
(mapcat #(walk (conj already (:v n)) %) (:parent
n)))]
(walk #{} (:v (first values))
I was hoping to use the set as a way to record which nodes have been
visited. Unfortunately as you might be able to tell, that's not going to
work. The result of running this is
(a b c d f e f)
Notice that f gets in the list twice. One way to do it would be to make
a set out of it, but that eliminates the laziness aspect.
Can anyone point me in the right direction here?
Thanks,
Raju
--
--
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.
--
--
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.
Re: Walking a tree
Dear Stanislav, Thank you. You got me going down the right path. Upon looking around for a BFS solution, I came across this blog post http://hueypetersen.com/posts/2013/06/25/graph-traversal-with-clojure/that had me going down the right direction. Which leads me to Carlo's response -- You are SO right. It was mapcat that was hurting me. Thank you all. I do appreciate this. I will keep digging, but Carlo's prompt response definitely got me past this rut. Warm regards, Raju -- -- 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.
