diff options
Diffstat (limited to 'src/quick-find.lisp')
| -rw-r--r-- | src/quick-find.lisp | 23 |
1 files changed, 15 insertions, 8 deletions
diff --git a/src/quick-find.lisp b/src/quick-find.lisp index dd371b8..21bd6d5 100644 --- a/src/quick-find.lisp +++ b/src/quick-find.lisp @@ -1,4 +1,11 @@ -;; Create network nodes +;;;; 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))) @@ -6,11 +13,6 @@ (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" @@ -21,9 +23,14 @@ (if (= (elt new-network n) v-n2) (setf (elt new-network n) v-n1))) new-network)) -;; Union consing version +;;; 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 cosing version of union_" + "A consed version of union_" `(setq ,network (union_ ,network ,n1 ,n2))) |