blob: dd2c54b49e68841e198519e579fa3cbc94f7dcc0 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
;;;; Quick Find 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
(in-package :com.lisp-algo.union-find)
(defclass quick-find ()
((nw-size
:initarg :network-size
:initform 10
:accessor network-size)
(nw
:initform nil
:accessor network)))
(defmethod initialize-instance :after ((algo quick-find) &key)
;; Initialize network using dynamic vector
(let* ((nw-size (slot-value algo 'nw-size))
(nodes (make-array nw-size :fill-pointer 0)))
(dotimes (id nw-size)
(vector-push id nodes))
(setf (slot-value algo 'nw) nodes)))
(defmethod union ((algo-instance quick-find) n1 n2)
(with-slots ((nw nw)) algo-instance
(let ((v-n1 (elt nw n1))
(v-n2 (elt nw n2))
(new-network (copy-seq nw)))
(dotimes (n (length new-network))
(if (= (elt new-network n) v-n2) (setf (elt new-network n) v-n1)))
(setf nw new-network))))
(defmethod connected ((algo-instance quick-find) n1 n2)
" Return t if there is a path between n1 and n2, nil otherwise. connected represent the find operation of the Quick Find Algorithm"
(with-slots ((nw nw)) algo-instance
(= (elt nw n1) (elt nw n2))))
|
