Yesterday I implemented Kruskal’s Algorithm in Clojure. Today, I’ll do it in Common Lisp.
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-FIRSTHere’s an example
(find-first #'evenp '(1 3 5 0 7 9))0Next, 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-PAnd, 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))))))KRUSKALLet 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))