The Kitchen Sink and Other Oddities

Atabey Kaygun

Prüfer Encoding and Decoding of a Tree in Clojure

Description of the problem

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.

An implementation of Prüfer encoding and decoding 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/tree

First, 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-vertex

Let 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-leaf

Let 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/encode

We 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/decode

The 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