Search code examples
graphclojuretreetraversal

Nested map to sequence of tuples representing edges in Clojure

How might one go about expressing the following transformation in idiomatic Clojure?

(def m
     {:a {:b {:c nil
              :d nil}
          :e nil}})


(map->edges m) ; =>


([:a :b] [:b :c] [:b :d] [:e nil] [:d nil] [:a :e] [:e nil])

I don't care about the order in which vectors appear in the result, so either depth-first or breath-first search strategies are fine.

Solution

  • You can express this fairly concisely using for and tree-seq:

    (defn map->edges [m]
  (for [entry m
        [x m] (tree-seq some? val entry)
        y (or (keys m) [m])]
    [x y]))

    Example:

    (map->edges m)
;;=> ([:a :b] [:a :e] [:b :c] [:b :d] [:c nil] [:d nil] [:e nil])