blob: dd371b87a462d4de4cf179a5372b49bfe8ddeb43 (
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
|
;; Create network nodes
(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))
;; Check if two nodes are connected
(defmacro 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)))
;; Link two nodes in the network
(defun 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))
;; Union consing version
(defmacro nunion_ (network n1 n2)
"A cosing version of union_"
`(setq ,network (union_ ,network ,n1 ,n2)))
|
