The Kitchen Sink and Other Oddities

Atabey Kaygun

Kruskal’s Algorithm in Common Lisp

Description of the problem

Yesterday I implemented Kruskal’s Algorithm in Clojure. Today, I’ll do it in Common Lisp.

A Common Lisp Implementation

I’ll start with a utility function. This function finds the first element in the list satisfying the given predicate.

(defun find-first (pred xs)
  (cond ((null xs) nil)
        ((funcall pred (car xs)) (car xs))
        (t (find-first pred (cdr xs)))))
FIND-FIRST

Here’s an example

(find-first #'evenp '(1 3 5 0 7 9))
0

Next, the following function checks if adding a given path to a graph creates a cycle.

(defun creates-cycle-p (path graph)
  (let ((e (find-first (lambda (x) (intersection path x)) graph)))
    (cond ((null e) nil)
          ((every (lambda (x) (member x path)) e) t)
          (t (creates-cycle-p (union path e)
                              (remove e graph :test #'equal))))))
CREATES-CYCLE-P

And, finally an implementation for Kruskal’s algorithm:

(defun kruskal (graph &optional tree)
  (if (null graph)
      tree
      (let ((e (elt graph (random (length graph)))))
         (kruskal (remove e graph :test #'equal)
                  (if (creates-cycle-p e tree)
                      tree
                      (cons e tree))))))
KRUSKAL

Let us test:

(defparameter G '((0 1) (1 2) (1 3) (2 3) (0 4) (4 5) (3 5) (0 5)))
(kruskal G)
G
((1 2) (0 4) (3 5) (0 1) (4 5))