Almost 2 years ago, I looked into Prüfer encoding and decoding of a tree in common lisp. Today, I’ll write a new implementation from scratch in clojure.
You can find the pseudo-code of the algorithm in my original post. In that post, I used edge set representaion of a graph but today I am going to use adjacency list representation.
Let us start with a simple example of a tree that I used in my original post:
0 --- 1 --- 2 --- 3 --- 4
| |
| |
5 6(ns prüfer
(:use clojure.set))
(def tree {0 #{1}, 1 #{0 2 5}, 2 #{1 3}, 3 #{2 4 6}, 4 #{3}, 5 #{1}, 6 #{3}})#'user/treeFirst, I am going to need a function that remove a vertex and every edge it is incident to:
(defn remove-vertex [G v]
(->> (dissoc G v)
(map (fn [x] {(key x) (->> (val x)
(remove #{v})
(into #{}))}))
(into {})))#'prüfer/remove-vertexLet us test:
(prüfer/remove-vertex user/tree 0){1 #{2 5}, 2 #{1 3}, 3 #{4 6 2}, 4 #{3}, 5 #{1}, 6 #{3}}Next, I need a function that returns the leaf with the minimal label and its neighbor.
(defn minimal-leaf [tree]
(->> tree
(filter #(->> % val count (= 1)))
(sort #(compare (first %1) (first %2)))
first))#'prüfer/minimal-leafLet us test:
(prüfer/minimal-leaf user/tree)[0 #{1}]Next, my implementation of the Prüfer encoding:
(defn encode [tree]
(loop [graph tree code []]
(let [[v xs] (minimal-leaf graph)]
(if (= 1 (count graph))
code
(recur (remove-vertex graph v)
(conj code (first xs)))))))#'prüfer/encodeWe test:
(prüfer/encode user/tree)[1 3 1 2 3 6]Next, the decoding function:
(defn decode [code]
(let [n (count code)
vs (into #{} (range (+ 1 n)))]
(loop [xs code tree []]
(if (= n (count tree))
(->> tree
(map (fn [[x y]] {x #{y} y #{x}}))
(apply merge-with union))
(let [x (reduce min (remove (into #{} xs) vs))]
(recur (conj (into [] (rest xs)) x)
(conj tree [x (first xs)])))))))#'prüfer/decodeThe main body of the code reconstruct the tree as a lıst of edges. Then right when I need to return the value, I convert it into an adjacency list. Let us test:
(= user/tree (prüfer/decode (prüfer/encode user/tree)))true