blob: 9b4e9d83e9c6250a9647a57d8ee1962968f80fb3 (
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
40
41
42
|
;;;; 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
;;; Base functions
(defun 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))
(defun 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)))
(defun union_ (network n1 n2)
"Connect to sub-tree together. union represent the union operation on the Quick Union algorithm"
(let ((new-network (copy-seq network)))
(setf (elt new-network (find-root new-network n1))
(find-root new-network n2))
new-network))
;;; Macro definitions
(defmacro connected (network n1 n2)
"Return true if n1 and n2 are connected and nil otherwise. connection represent
the find operation on the Quick Union algorithm"
`(= (find-root ,network ,n1) (find-root ,network ,n2)))
(defmacro nunion_ (network n1 n2)
"A consed version of union_"
`(setf ,network (union_ ,network ,n1 ,n2)))
|
