I'm not sure if I'm addressing your needs exactly, but if you want to turn
an adjacency list into a nested structure, here's one way:
(def adj {:a [:b] :b [:c :d] :c [:e] :d [:e]})
(defn build-tree [adj from to]
{:name from
:children (when (not= from to)
(map #(build-tree adj % to) (adj from)))})
(build-tree adj :a :e)
Here each node is a map with keys :name and :children. Leaves are nodes with
empty/nil :children. This doesn't handle cycles, of course.
Justin
On Friday, August 19, 2011 11:15:36 AM UTC-4, Ulrik Sandberg wrote:
>
> Thanks. That looks very interesting.
>
> > ;; adjacency list
> > {:a [:b] :b [:c :d] :c [:e] :d [:e]}
>
> For some reason, I have trouble constructing this recursively. I seem
> to always end up with something like this:
>
> user> (build-tree :a :e)
> (:a (:b (:c (:e)) (:d
> (:e))))
>
> (defn build-tree [from to]
> (cons from
> (for [c (candidates from to)]
> (build-tree c to))))
>
> I have a start key (:a) and an end key (:e). For each key, I can get
> candidates:
>
> user> (candidates :a :e)
> (:b)
> user> (candidates :b :e)
> (:c :d)
> user> (candidates :c :e)
> (:e)
> user> (candidates :d :e)
> (:e)
> user> (candidates :e :e)
> ()
>
>
> On 19 Aug, 16:12, Justin Kramer <[email protected]> wrote:
> > There are many ways one could model a tree/graph:
> >
> > ;; collection of edges
> > [[:a :b] [:b :c] [:b :d] [:c :e] [:d :e]]
> >
> > ;; adjacency list
> > {:a [:b] :b [:c :d] :c [:e] :d [:e]}
> >
> > If you're looking for a pre-made solution, the loom graph library
> > (https://github.com/jkk/loom) may work:
> >
> > (ns example
> > (:use [loom.graph :only [digraph]]
> > [loom.alg :only [shortest-path]]))
> >
> > (def dg (digraph {:a [:b] :b [:c :d] :c [:e] :d [:e]}))
> >
> > (shortest-path dg :a :e)
> > ; => (:a :b :c :e)
--
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
