On Jul 6, 2013, at 9:33 AM, looselytyped <[email protected]> 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 "parent"s. 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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
