Prüfer Sequence algorithm

gistfile1.clj

(defn prufer
  "Convert a labelled tree to a Prüfer Sequence."
  ([graph] (prufer graph []))
  ([graph prufer-sequence]
    (loop [g graph p prufer-sequence]
      (if (> (count g) 2) ; A Prüfer sequence is always of length n - 2
        ;v finds the lowest-valued leaf node
        (let [v (apply min-key first (filter #(= 1 (count (last %))) g))]
          ; Remove the label's node key and occurrences in edge sets,
          ; then push its neighbour's label onto front of Prüfer sequence p.
          (recur
            (into {} (for [[k value] (dissoc g (first v))] [k (disj value (first v))]))
            (concat p [(last (last v))])))
        p))))


; Trivial 5-vertex graph where the keys represent labels and
; values represent each node's neighbours i.e. a vertex with one neighbour is a leaf
(def g {1 #{2 3}, 2 #{1 4}, 3 #{1 5}, 5 #{3}, 4 #{2}})

(println (prufer g))