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 "parent"s. 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.
