public
Last active

Prüfer Sequence algorithm

  • Download Gist
gistfile1.clj
Clojure
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
(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))

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.