Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Prüfer Sequence algorithm
(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.
(into {} (for [[k value] (dissoc g (first v))] [k (disj value (first v))]))
(concat p [(last (last v))])))
; 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment