Removed the need for metabang-bind

[cl-graph.git] / dev / graph-algorithms.lisp

diff --git a/dev/graph-algorithms.lisp b/dev/graph-algorithms.lisp
index 9ee37a8..3280fff 100644 (file)
--- a/dev/graph-algorithms.lisp
+++ b/dev/graph-algorithms.lisp
@@ -1,10 +1,10 @@
-(in-package metabang.graph)
+(in-package #:metabang.graph)
 
 ;;; ---------------------------------------------------------------------------
 ;;;
 ;;; ---------------------------------------------------------------------------
 
-(defstruct (vertex-datum (:conc-name "NODE-") (:type list))
+(defstruct (vertex-datum (:conc-name node-) (:type list))
   (color nil)
   (depth most-positive-fixnum)
   (parent nil))
@@ -141,15 +141,13 @@
    (collect-elements
     (make-iterator (connected-components graph) :unique t :transform #'parent))))
 
-;;; ---------------------------------------------------------------------------
-
 (defmethod find-connected-components ((graph basic-graph))
   (collect-elements
    (make-iterator (connected-components graph) :unique t :transform #'parent)
    :transform 
    (lambda (component)
      (subgraph-containing graph (element component) 
-                          most-positive-fixnum))))
+                          :depth most-positive-fixnum))))
 
 #+Alternate
 (defmethod find-connected-components ((graph basic-graph))
@@ -213,8 +211,8 @@
   (iterate-elements
    edges
    (lambda (edge)
-     (bind ((v1 (element (source-vertex edge)))
-            (v2 (element (target-vertex edge))))
+     (let ((v1 (element (source-vertex edge)))
+          (v2 (element (target-vertex edge))))
        (add-edge-between-vertexes
         graph v1 v2 :edge-class (type-of edge)
         :edge-type (if (directed-edge-p edge)
@@ -230,46 +228,6 @@
   graph)
 
 ;;; ---------------------------------------------------------------------------
-;;; for completeness 
-;;; ---------------------------------------------------------------------------
-
-(defmethod make-graph-from-vertexes ((vertex-list list))
-  (bind ((edges-to-keep nil)
-         (g (copy-template (graph (first vertex-list)))))
-        
-    (iterate-elements
-     vertex-list
-     (lambda (v)
-       (add-vertex g (element v))
-       (iterate-elements
-        (edges v)
-        (lambda (e)
-          (when (and (member (vertex-1 e) vertex-list)
-                     (member (vertex-2 e) vertex-list))
-            (pushnew e edges-to-keep :test #'eq))))))
-    
-    (iterate-elements
-     edges-to-keep
-     (lambda (e)
-       (bind ((v1 (source-vertex e))
-              (v2 (target-vertex e)))
-         ;;?? can we use copy here...
-         (add-edge-between-vertexes
-          g (element v1) (element v2)
-          :edge-type (if (directed-edge-p e)
-                       :directed
-                       :undirected)
-          :if-duplicate-do :force
-          :edge-class (type-of e)
-          :value (value e)
-          :edge-id (edge-id e)
-          :element (element e)
-          :tag (tag e)
-          :graph g
-          :color (color e)))))
-    g))
-
-;;; ---------------------------------------------------------------------------
 
 (defmethod edge-lessp-by-weight ((e1 basic-edge) (e2 basic-edge))
   (< (weight e1) (weight e2)))
@@ -282,14 +240,14 @@
 (defmethod minimum-spanning-tree ((graph basic-graph) 
                                   &key
                                   (edge-sorter #'edge-lessp-by-weight))
-  (bind ((result nil))
+  (let ((result nil))
     (iterate-vertexes 
      graph
      (lambda (v)
        (mst-make-set v)))
     
     (loop for edge in (sort (edges graph) edge-sorter) do
-          (bind ((v1 (source-vertex edge))
+          (let ((v1 (source-vertex edge))
                  (v2 (target-vertex edge)))
             
             (unless (eq (mst-find-set v1)
@@ -304,26 +262,24 @@
 
 ;;; ---------------------------------------------------------------------------
 
-#+ignore ;;; shit
+#+ignore ;;; shoot
 (defmethod minimum-spanning-tree ((vertex-list list) 
                                   &key
                                   (edge-sorter #'edge-lessp-by-weight))
-  (bind ((result nil)
+  (let ((result nil)
          (v-edges (remove-duplicates 
                    (flatten (mapcar #'edges vertex-list)) :test #'eq)))
     
     (iterate-container
      vertex-list
      (lambda (v)
-       (mst-make-set v)))
-    
-    
+       (mst-make-set v)))    
     
     (loop for edge in (sort v-edges edge-sorter) do
-          (bind ((v1 (source-vertex edge))
-                 (v2 (target-vertex edge))
-                 (v1-set (mst-find-set v1))
-                 (v2-set (mst-find-set v2)))
+          (let ((v1 (source-vertex edge))
+               (v2 (target-vertex edge))
+               (v1-set (mst-find-set v1))
+               (v2-set (mst-find-set v2)))
 
             (when (or (not v1-set)
                            (not v2-set))
@@ -352,7 +308,7 @@
 ;;; ---------------------------------------------------------------------------
 
 #+test
-(bind ((g (make-container 'graph-container)))
+(let ((g (make-container 'graph-container)))
   (add-edge-between-vertexes g :v :y :edge-type :directed)
   (add-edge-between-vertexes g :u :x :edge-type :directed)
   (add-edge-between-vertexes g :x :v :edge-type :directed)
@@ -501,7 +457,7 @@
                            (edges u)
                            :filter (lambda (e)
                                      (out-edge-for-vertex-p e u))) sorter) do
-        (bind ((v (other-vertex edge u)))
+        (let ((v (other-vertex edge u)))
           
           (unless (color edge)
             (setf (color edge) (color v)))
@@ -521,7 +477,7 @@
 ;;; ---------------------------------------------------------------------------
 
 #+test
-(bind ((g (make-container 'graph-container)))
+(let ((g (make-container 'graph-container)))
   (add-edge-between-vertexes g :v :y :edge-type :directed)
   (add-edge-between-vertexes g :u :x :edge-type :directed)
   (add-edge-between-vertexes g :x :v :edge-type :directed)
@@ -592,7 +548,7 @@
 ;;; ---------------------------------------------------------------------------
 
 (defmethod map-over-all-combinations-of-k-vertexes ((graph basic-graph) k fn)
-  (bind ((vertex-count (size graph))
+  (let* ((vertex-count (size graph))
          (symbols (make-list k :initial-element vertex-count))
          (vertexes (vertexes graph))) 
     (iterate-over-indexes 
@@ -606,7 +562,7 @@
 ;;; ---------------------------------------------------------------------------
 
 #+test
-(bind ((result nil)
+(let ((result nil)
        (g (make-container 'graph-container)))
   (add-edge-between-vertexes g :u :v :edge-type :directed)
   (add-edge-between-vertexes g :u :x :edge-type :directed)
@@ -620,7 +576,7 @@
    g
    4
    (lambda (vertex-list)
-     (bind ((graph-from-vertexes (make-graph-from-vertexes vertex-list)))
+     (let ((graph-from-vertexes (make-graph-from-vertexes vertex-list)))
        (when (mst-kruskal graph-from-vertexes #'identity-sorter)
          (push graph-from-vertexes result)))))
   result)
@@ -631,7 +587,7 @@
 ;;; ---------------------------------------------------------------------------
 
 (defmethod map-over-all-combinations-of-k-edges ((graph basic-graph) k fn)
-  (bind ((edge-count (edge-count graph))
+  (let* ((edge-count (edge-count graph))
          (symbols (make-list k :initial-element edge-count))
          (edges (edges graph))) 
     (print symbols)
@@ -646,10 +602,10 @@
 ;;; ---------------------------------------------------------------------------
 
 (defmethod map-over-all-combinations-of-k-edges ((vertex basic-vertex) k fn)
-  (bind ((edge-count (edge-count vertex))
-         (symbols (make-list k :initial-element edge-count))
-         (edges (edges vertex))) 
-    (print symbols)
+  (let* ((edge-count (edge-count vertex))
+        (symbols (make-list k :initial-element edge-count))
+        (edges (edges vertex))) 
+    ;(print symbols)
     (iterate-over-indexes 
      symbols
      (lambda (edge-indexes)