diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/union-find/quick-find.lisp | 37 | ||||
| -rw-r--r-- | src/union-find/quick-union.lisp | 42 | ||||
| -rw-r--r-- | src/union-find/weighted-quick-union-path-compression.lisp | 59 | ||||
| -rw-r--r-- | src/union-find/weighted-quick-union.lisp | 55 |
4 files changed, 0 insertions, 193 deletions
diff --git a/src/union-find/quick-find.lisp b/src/union-find/quick-find.lisp deleted file mode 100644 index edaa7f0..0000000 --- a/src/union-find/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))) - - - diff --git a/src/union-find/quick-union.lisp b/src/union-find/quick-union.lisp deleted file mode 100644 index bf2ff3d..0000000 --- a/src/union-find/quick-union.lisp +++ /dev/null @@ -1,42 +0,0 @@ -;;;; Quick Union 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. -;;;; It is an improved version of the Quick Find algorithm -;;;; It optimize the union function - - -;;; 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)) - -(defun find-root (network node) - "Find the root of a sub-tree in the network." - (do ((id node value) - (value (elt network node) (elt network value))) - ((= id value) id))) - -(defun union_ (network n1 n2) - "Connect to sub-tree together. union represent the union operation on the Quick Union algorithm" - (let ((new-network (copy-seq network))) - (setf (elt new-network (find-root new-network n1)) - (find-root new-network n2)) - new-network)) - - -;;; Macro definitions - -(defmacro connected (network n1 n2) - "Return true if n1 and n2 are connected and nil otherwise. connection represent -the find operation on the Quick Union algorithm" - `(= (find-root ,network ,n1) (find-root ,network ,n2))) - -(defmacro nunion_ (network n1 n2) - "A destructive version of union_" - `(setf ,network (union_ ,network ,n1 ,n2))) - diff --git a/src/union-find/weighted-quick-union-path-compression.lisp b/src/union-find/weighted-quick-union-path-compression.lisp deleted file mode 100644 index 56c80b7..0000000 --- a/src/union-find/weighted-quick-union-path-compression.lisp +++ /dev/null @@ -1,59 +0,0 @@ -;;;; Weighted Quick Union Algorithm With Path Compression -;;;; This algorithm solve dynamic connectivity -;;;; problem by providing a way to find if there -;;;; is a path between two nodes in a dynamic graph. -;;;; It is an improved version of the Quick Union algorithm -;;;; by improving the way that the union-tree is constructed -;;;; The algorithm try to reduce the deepness of the tree in -;;;; order to optimize the find-root function -;;;; The path compression is ensure by the find-root function -;;;; IMPORTANT: find-root is now a destructive function ! Be aware... - -;;; Base functions - -(defun create-network (n) - "Build a quick-find network using a multi-dimensional dynamic vector:\n -1st dimension = the network\n 2nd dimension = each subtree node quantities" - (let ((network (make-array `(2 ,n) :initial-element 1))) - (dotimes (id n) - (setf (aref network 0 id) id)) - network)) - -(defun find-root (network node) - "Find the root of a sub-tree in the network. This is a destructive version of find-root that -include path compression" - (do ((id node value) - (value (aref network 0 node) (aref network 0 value))) - ((= id value) (progn (setf (aref network 0 node) id) ; Path compression - id)))) - -(defun union_ (network n1 n2) - "Connect to sub-tree together. union represent the union operation on the Quick Union algorithm" - (let ((new-network (copy-tree network))) ; Duplicate network - (let* ((n1-root (find-root new-network n1)) - (n2-root (find-root new-network n2)) - (n1-size (aref new-network 1 n1-root)) - (n2-size (aref new-network 1 n2-root))) - (if (>= n1-size n2-size) ; Check which subtree is LARGER (not deeper) - (progn (setf (aref new-network 0 n2-root) (aref new-network 0 n1-root)) ; Modify the second node - (setf (aref new-network 1 n1-root) ; Update tree larger - (+ (aref new-network 1 n1-root) (aref new-network 1 n2-root)))) - (progn (setf (aref new-network 0 n1-root) (aref new-network 0 n2-root)) ; Otherwise modify the first node - (setf (aref new-network 1 n2-root) ; Update tree larger - (+ (aref new-network 1 n2-root) (aref new-network 1 n1-root))))) - new-network))) - - -;;; Macro definitions - - -(defmacro connected (network n1 n2) - "Return true if n1 and n2 are connected and nil otherwise. connection represent -the find operation on the Quick Union algorithm" - `(= (find-root ,network ,n1) (find-root ,network ,n2))) - -(defmacro nunion_ (network n1 n2) - "A destructive version of the union function." - `(setf ,network (union_ ,network ,n1 ,n2))) - - diff --git a/src/union-find/weighted-quick-union.lisp b/src/union-find/weighted-quick-union.lisp deleted file mode 100644 index 679de80..0000000 --- a/src/union-find/weighted-quick-union.lisp +++ /dev/null @@ -1,55 +0,0 @@ -;;;; Weighted Quick Union 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. -;;;; It is an improved version of the Quick Union algorithm -;;;; by improving the way that the union-tree is constructed -;;;; The algorithm try to reduce the deepness of the tree in -;;;; order to optimize the find-root function - -;;; Base functions - -(defun create-network (n) - "Build a quick-find network using a multi-dimensional dynamic vector:\n -1st dimension = the network\n 2nd dimension = each subtree node quantities" - (let ((network (make-array `(2 ,n) :initial-element 1))) - (dotimes (id n) - (setf (aref network 0 id) id)) - network)) - -(defun find-root (network node) - "Find the root of a sub-tree in the network." - (do ((id node value) - (value (aref network 0 node) (aref network 0 value))) - ((= id value) id))) - -(defun union_ (network n1 n2) - "Connect to sub-tree together. union represent the union operation on the Quick Union algorithm" - (let ((new-network (copy-tree network))) ; Duplicate network - (let* ((n1-root (find-root new-network n1)) - (n2-root (find-root new-network n2)) - (n1-size (aref new-network 1 n1-root)) - (n2-size (aref new-network 1 n2-root))) - (if (>= n1-size n2-size) ; Check which subtree is LARGER (not deeper) - (progn (setf (aref new-network 0 n2-root) (aref new-network 0 n1-root)) ; Modify the second node - (setf (aref new-network 1 n1-root) ; Update tree larger - (+ (aref new-network 1 n1-root) (aref new-network 1 n2-root)))) - (progn (setf (aref new-network 0 n1-root) (aref new-network 0 n2-root)) ; Otherwise modify the first node - (setf (aref new-network 1 n2-root) ; Update tree larger - (+ (aref new-network 1 n2-root) (aref new-network 1 n1-root))))) - new-network))) - - -;;; Macro definitions - - -(defmacro connected (network n1 n2) - "Return true if n1 and n2 are connected and nil otherwise. connection represent -the find operation on the Quick Union algorithm" - `(= (find-root ,network ,n1) (find-root ,network ,n2))) - -(defmacro nunion_ (network n1 n2) - "A destructive version of the union function." - `(setf ,network (union_ ,network ,n1 ,n2))) - - |