diff options
| author | Loic GUEGAN <loic.guegan@yahoo.fr> | 2019-01-27 20:29:42 +0100 |
|---|---|---|
| committer | Loic GUEGAN <loic.guegan@yahoo.fr> | 2019-01-27 20:29:42 +0100 |
| commit | 2dfdbfbb498d0584a8147279464039c49bea515a (patch) | |
| tree | e4f757e812a7a895f4efa5a5d059562817d2c1c3 /src/quick-find.lisp | |
| parent | 30765ae30d516eda228447408b59be03712f5b17 (diff) | |
Update comments
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))) |
