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 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
EndLet me show how this works over an example: Let T be the tree
0 -- 1 -- 2 -- 3 -- 4
| |
5 6In 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
EndLet 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.
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-VERTEXNow 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-LEAFNow, 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-ENCODELet 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-DECODEAnd 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
STRAIGHTENOK. 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