46 lines
1.6 KiB
Common Lisp
46 lines
1.6 KiB
Common 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))))
|
|
|