From d0f6e2ff9cdf4c35e99b54fa765aca7f46ed6a24 Mon Sep 17 00:00:00 2001 From: Loic GUEGAN Date: Thu, 31 Jan 2019 15:31:37 +0100 Subject: Clean project --- .gitignore | 3 ++ src/quick-find.lisp | 37 -------------- src/quick-union.lisp | 42 --------------- src/union-find/quick-find.lisp | 37 ++++++++++++++ src/union-find/quick-union.lisp | 42 +++++++++++++++ .../weighted-quick-union-path-compression.lisp | 59 ++++++++++++++++++++++ src/union-find/weighted-quick-union.lisp | 55 ++++++++++++++++++++ src/weighted-quick-union-path-compression.lisp | 59 ---------------------- src/weighted-quick-union.lisp | 55 -------------------- 9 files changed, 196 insertions(+), 193 deletions(-) delete mode 100644 src/quick-find.lisp delete mode 100644 src/quick-union.lisp create mode 100644 src/union-find/quick-find.lisp create mode 100644 src/union-find/quick-union.lisp create mode 100644 src/union-find/weighted-quick-union-path-compression.lisp create mode 100644 src/union-find/weighted-quick-union.lisp delete mode 100644 src/weighted-quick-union-path-compression.lisp delete mode 100644 src/weighted-quick-union.lisp diff --git a/.gitignore b/.gitignore index 098114e..83eef09 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,5 @@ # Exclude Emacs temporary files *~ + +# Exclude external libraries +lisp-unit.lisp 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))) - - - diff --git a/src/quick-union.lisp b/src/quick-union.lisp deleted file mode 100644 index bf2ff3d..0000000 --- a/src/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/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))) + + + diff --git a/src/union-find/quick-union.lisp b/src/union-find/quick-union.lisp new file mode 100644 index 0000000..bf2ff3d --- /dev/null +++ b/src/union-find/quick-union.lisp @@ -0,0 +1,42 @@ +;;;; 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 new file mode 100644 index 0000000..56c80b7 --- /dev/null +++ b/src/union-find/weighted-quick-union-path-compression.lisp @@ -0,0 +1,59 @@ +;;;; 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 new file mode 100644 index 0000000..679de80 --- /dev/null +++ b/src/union-find/weighted-quick-union.lisp @@ -0,0 +1,55 @@ +;;;; 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))) + + diff --git a/src/weighted-quick-union-path-compression.lisp b/src/weighted-quick-union-path-compression.lisp deleted file mode 100644 index 56c80b7..0000000 --- a/src/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/weighted-quick-union.lisp b/src/weighted-quick-union.lisp deleted file mode 100644 index 679de80..0000000 --- a/src/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))) - - -- cgit v1.2.3