lisp-algo/union-find/quick-union.lisp

;;;; Quick Union Algorithm
;;;; This algorithm solve dynamic connectivity
;;;; problem by providing a way to find if there
;;;; is a path between two nodes in a dynamic graph.
;;;; It is an improved version of the Quick Find algorithm
;;;; It optimize the union function

(in-package :com.lisp-algo.union-find)

(defclass quick-union ()
  ((nw-size
    :initarg :network-size
    :initform 10
    :accessor network-size)
   (nw
    :initarg nil
    :accessor network)))

(defmethod initialize-instance :after ((algo quick-union) &key)
  "Build a quick-find network using a dynamic vector"
  (with-slots ((n nw-size) (nw nw)) algo
  (let ((nodes (make-array n :fill-pointer 0)))
    (dotimes (id n)
      (vector-push id nodes))
    (setf nw nodes))))

(defun quick-union-find-root (network node)
  "Find the root of a sub-tree in the network."
  (do ((id node value)
       (value (elt network node) (elt network value)))
      ((= id value) id)))

(defmethod union ((algo quick-union) n1 n2)
  "Connect to sub-tree together. union represent the union operation on the Quick Union algorithm"
  (with-slots ((network nw)) algo
  (let ((new-network (copy-seq network)))
    (setf (elt new-network (quick-union-find-root new-network n1))
          (quick-union-find-root new-network n2))
    (setf network new-network))))

(defmethod connected ((algo quick-union) n1 n2)
  "Return true if n1 and n2 are connected and nil otherwise. connection represent
the find operation on the Quick Union algorithm"
  (with-slots ((network nw)) algo
  (= (quick-union-find-root network n1) (quick-union-find-root network n2))))