diff options
Diffstat (limited to 'src/quick-find.lisp')
| -rw-r--r-- | src/quick-find.lisp | 37 |
1 files changed, 0 insertions, 37 deletions
diff --git a/src/quick-find.lisp b/src/quick-find.lisp deleted file mode 100644 index edaa7f0..0000000 --- a/src/quick-find.lisp +++ /dev/null @@ -1,37 +0,0 @@ -;;;; 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))) - - - |
