Prüfer Encoding/Decoding of a Tree in Common Lisp

Description of the problem:

Given a tree, or a simple graph, the standard way of describing it is giving the set of vertices and edges. However, there are myriad different ways of encoding a tree. Pruefer encoding is one of them. Today, I am going to write two functions: one to write the Prüfer code of a given tree as a list of edges, and another to write a list of edges from a Prüfer code.

The algorithm

The encoding algorithm is pretty simple:

Function Encode:
Input: A tree T as a list of edges
Output: An ordered list rs of vertices with repetitions
Begin
  Let rs be the empty list
  While T contains two or more vertices do
     Find the leaf x (vertex of degree 1) in T with the minimal label
     Let y be the other end of the edge connected to x
     Remove x and the edge xy connected to x from T
     Append y to rs
  End
  Return rs
End

Let me show how this works over an example: Let T be the tree

0 -- 1 -- 2 -- 3 -- 4
     |         |
     5         6

In the first pass we pick 0 but add 1 to the Prüfer code, and we remove the edge 01. In the second pass, 4 is the smallest label and we add 3 to the code before we remove 43. Next is 5, we add 1 again and remove 15. Next is 1, we add 2 to the code and remove the edge 12. Next is 2, we add 3 to the code and remove the edge 23. And then we stop since we only have two vertices 3 and 6. The Prüfer code for the tree above is 13123.

The decoding algorithm is a little more complex

Function Decode:
Input: An ordered list rs of vertices with repetitions
Output: A tree T as a list of edges
Begin
  Let n be length(rs)
  Do
      Let x be the first element of the list rs
      Let y be the vertex with the minimal label
        that does not appear in rs
      Add the edge xy to T
      Remove x from rs
      Append y to the end of rs
  Until T contains n edges
  Let x and y be the only vertices not in rs
  Add xy to T
  Return T
End

Let us decode the code we obtained above: The code was 13123 and n is set to 5. In the first pass x is 1, and y is 0. So, we add the edge 01 to T. The code is now 31230. In the next pass x is 3, y is 4. We add 34 to T and the code becomes 12304. Next, we get x is 1, y is 5 and we add 15 to T while the code is updated to 23045. Then x is 2, y is 1, the code becomes 30451 and we add 12 to T. In the final pass x is 3, y is 2 and we add 23 to T while the code becomes 04512. The only two vertices that are not in the code are 3 and 6. So T is given by the list of edges: 01, 34, 15, 12, 23, 36.

An implementation in common lisp

Before we write the code for the encoding part, I am going to need few utility functions for graph related calculations. I got hooked on to the following macro from clojure:

(defmacro ->> (x &rest forms)
  (dolist (f forms x)
    (if (listp f)
        (setf x (append f (list x)))
        (setf x (list f x)))))

->>

The macro makes the code below more readable. Next,

(defun neighbors (G x)
  "Returns the set of neighbors of a vertex x in G."
  (remove x
          (->> G
               (remove-if-not (lambda (ys) (member x ys)))
               (reduce (lambda (us vs) (append us (remove x vs)))))))

(defun degree (G x)
  "Returns the degree of a vertex x in G."
  (length (neighbors G x)))

(defun vertices (G)
  "Returns the set of vertices of a graph G."
  (remove-duplicates (reduce #'append G)))

(defun delete-vertex (G x)
  "Deletes a vertex x all edges adjacent to x from G."
  (remove-if (lambda (edge) (member x edge)) G))

NEIGHBORS
DEGREE
VERTICES
DELETE-VERTEX

Now that we are done with generic graph operations, let us move on to the specific function we need. First is for finding the leaf with minimal label.

(defun min-leaf (G)
  "Find the leaf in G with the minimal label."
  (->> (vertices G)
       (remove-if-not (lambda (y) (= 1 (degree G y))))
       (reduce #'min)))

MIN-LEAF

Now, we can implement the encoding function as follows:

(defun prufer-encode (G &optional xs)
  "Returns the Prüfer encoding of a tree given as a list of edges."
  (if (= 1 (length G))
      (nreverse xs)
      (let* ((x (min-leaf G))
             (y (car (neighbors G x))))
        (prufer-encode (delete-vertex G x) (cons y xs)))))

PRUFER-ENCODE

Let us test:

(prufer-encode '((0 1) (1 2) (2 3) (3 4) (1 5) (3 6)))

(1 3 1 2 3)

The decode function strangely is more straightforward to implement:

(defun prufer-decode (xs)
  "Returns the tree as a list of edges from a given Prüfer code."
  (let* ((n (+ 2 (length xs)))
         (ys (loop for i from 0 below n collect i)))
    (labels ((helper (code k G)
               (let ((zs (sort (set-difference ys (remove-duplicates code)) #'<)))
                 (if (= k 2)
                     (append G (list zs))
                     (helper (append (cdr code) (list (car zs)))
                             (1- k)
                             (append G (list (list (car code) (car zs)))))))))
      (helper xs n nil))))

PRUFER-DECODE

And we test it:

(prufer-decode '(1 3 1 2 3))

((1 0) (3 4) (1 5) (2 1) (3 2) (3 6))

Now, let me test the algorithm on a larger random tree:

(defun random-tree (n)
   (loop for i from 1 below n 
         collect (list (random i) i)))

(defun straighten (G)
   (mapcar (lambda (xs) (sort xs #'<)) G))

RANDOM-TREE
STRAIGHTEN

OK. I am going to test the algorithm on a random tree on 50 vertices: The code below should return nil:

(defvar G (straighten (random-tree 50)))
(set-difference G (straighten (prufer-decode (prufer-encode G))) :test #'equal)

G
NIL