Tree from adjacency map

Question

I'm trying to make a function that builds a tree from an adjacency list of the form {node [children]}.

(def adjacency
  {nil [:a]
   :a [:b :c]
   :b [:d :e]
   :c [:f]})

which should result in

{nil {:a {:b {:d nil
              :e nil}
          :c {:f nil}}}}

However I tried, I couldn't get it to work. Recursion is a bit of a weak spot of mine, and most recursion examples I found only dealt with recursion over a list, not a tree.

Edited: Original dataset and result were unintentionally nested too deep, due to not having an editor and original source at time of posting. Sorry about that.

Answer 1

There is only one entry in every submap in adjacency. Is this necessary? And the same problem in the result tree.

I hope it would be more clear:

(def adjacency {:a [:b :c]
                :b [:d :e]
                :c [:f]})

So solution is:

(defn tree [m root]
  (letfn [(tree* [l]
            (if (contains? m l)
              {l (into {} (map tree* (m l)))}
              [l nil]))]
    (tree* root)))

Test:

(tree adjacency :a)
=> {:a {:b {:d nil
            :e nil}
        :c {:f nil}}}

Update. If you don't need the result tree as nested maps

(defn tree [m root]
  (letfn [(tree* [l]
            (if (contains? m l)
              (list l (map tree* (m l)))
              (list l nil)))]
    (tree* root)))

(tree adjacency :a)
=> (:a ((:b ((:d nil)
             (:e nil)))
        (:c ((:f nil)))))

Answer 2

I usually prefer to use clojure.walk when dealing with trees. I am assuming that the root node is first in the adjacency vector.

(use 'clojure.walk)

(def adjacency
  [{nil [:a]}
   {:a [:b :c]}
   {:b [:d :e]}
   {:c [:f]}])

(prewalk
 (fn [x]
   (if (vector? x)
     (let [[k v] x lookup (into {} adjacency)]
       [k (into {} (map (fn [kk] [kk (lookup kk)]) v))])
     x))
 (first adjacency))

Result: {nil {:a {:b {:d {}, :e {}}, :c {:f {}}}}}

NOTE: Empty child are represented as {} rather than nil, also child elements are maps rather than vector as map makes easy to navigate this tree then.