From 5725987c8dfd55d4ee0282f0a37779e06052f3c6 Mon Sep 17 00:00:00 2001 From: Loic Guegan Date: Sun, 24 Feb 2019 10:30:57 +0100 Subject: Re-organize code --- union-find/quick-find.lisp | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) create mode 100644 union-find/quick-find.lisp (limited to 'union-find/quick-find.lisp') diff --git a/union-find/quick-find.lisp b/union-find/quick-find.lisp new file mode 100644 index 0000000..936c647 --- /dev/null +++ b/union-find/quick-find.lisp @@ -0,0 +1,38 @@ +;;;; 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 + +(in-package :com.lisp-algo.union-find) + +;;; Base functions + +(defun qf-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 qf-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 qf-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 qf-nunion (network n1 n2) + "A destructive version of union_" + `(setq ,network (union ,network ,n1 ,n2))) + + + -- cgit v1.2.3