Clean project

1 files changed, 37 insertions, 0 deletions

diff --git a/src/union-find/quick-find.lisp b/src/union-find/quick-find.lisp
new file mode 100644
index 0000000..edaa7f0
--- /dev/null
+++ b/src/union-find/quick-find.lisp
@@ -0,0 +1,37 @@
+;;;; 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
+
+
+;;; 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))
+
+;; 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))
+
+;;; Macro definitions
+
+(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)))
+
+(defmacro nunion_ (network n1 n2)
+  "A destructive version of union_"
+  `(setq ,network (union_ ,network ,n1 ,n2)))
+
+
+