blob: 936c647dc2b4411c1464b163e457af34aa387611 (
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
|
;;;; 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)
;;; Base functions
(defun qf-create-network (n)
"Build a quick-find network using a dynamic vector"
(let ((nodes (make-array n :fill-pointer 0)))
(dotimes (id n)
(vector-push id nodes))
nodes))
;; Link two nodes in the network
(defun qf-union (network n1 n2)
"Link two nodes in the quick-find network. union_ represent the union operation of the Quick Find Algorithm"
(let ((v-n1 (elt network n1))
(v-n2 (elt network n2))
(new-network (copy-seq network)))
(dotimes (n (length new-network))
(if (= (elt new-network n) v-n2) (setf (elt new-network n) v-n1)))
new-network))
;;; Macro definitions
(defmacro qf-connected (network 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"
`(= (elt ,network ,n1) (elt ,network ,n2)))
(defmacro qf-nunion (network n1 n2)
"A destructive version of union_"
`(setq ,network (union ,network ,n1 ,n2)))
|
