graph-seq

graph-seq.clj

(defmacro if-first
  ([bindings then]
   `(when-first ~bindings ~then))
  ([bindings then else]
   (let [[x xs] bindings]
     `(if-let [xs# (seq ~xs)]
        (let [~x (first xs#)]
          ~then)
        ~else))))

(defn graph-seq
  ([root children-fn hops]
   (take hops (graph-seq root children-fn)))
  ([root children-fn]
   (let [step (fn step [g0 kids]
                (cons g0
                  (lazy-seq
                    (when-let [ks (seq kids)]
                      (loop [g g0, kids kids, nxt (transient [])]
                        (if-first [k kids]
                          (if (contains? g k)
                            (recur g (rest kids) nxt)
                            (let [kids2 (children-fn k)]
                              (recur
                                (assoc g k kids2)
                                (rest kids)
                                (reduce conj! nxt kids2))))
                          (step g (persistent! nxt))))))))
         children (children-fn root)]
     (step {root children} children))))

Produces a lazy sequence of graphs, step n + 1 having a graph radius one greater than step n. Doesn't redundantly backtrack over previous nodes. children-fn should take a node and return the nodes its edges point to, if any.