Sorry for being unclear.
I would in fact like to _create_ an adjacency list, given a start and
end key, and the candidates function I mentioned. However, I have
problems with coming up with a functional algorithm. I have a stateful
one that works, but it's very ugly.
(defn build-tree [from to m]
(let [cs (candidates from to)]
(when (seq cs)
(swap! m assoc from (vec cs)))
(doseq [c cs]
(build-tree c to m))))
user=> (let [m (atom {})]
(build-tree :a :e m)
@m)
{:a [:b] :b [:c :d] :c [:e] :d [:e]}
On 19 Aug, 18:17, Justin Kramer <jkkra...@gmail.com> wrote:
> 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 <jkkr...@gmail.com> 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 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
