X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=dev%2Fgraph.lisp;h=e851b1ab2a0db1d0caaf67aba740d5ad828d5b12;hb=a6bbd850d6392387184d32ffecb83d513a76395c;hp=a8f782bc9408fd04b31bba2d338cd9e1a0c2747b;hpb=14757e858454ece368c302e921642c6933909107;p=cl-graph.git diff --git a/dev/graph.lisp b/dev/graph.lisp index a8f782b..e851b1a 100644 --- a/dev/graph.lisp +++ b/dev/graph.lisp @@ -14,7 +14,7 @@ something is putting something on the vertexes plist's |# -(in-package metabang.graph) +(in-package #:metabang.graph) ;;; --------------------------------------------------------------------------- ;;; classes @@ -222,18 +222,6 @@ something is putting something on the vertexes plist's &allow-other-keys) (remf args :edge-class) (remf args :edge-type) - - #| I removed 'em, gwk - - ;;; I added these - jjm - (remf args :vertex-test) - (remf args :vertex-key) - (remf args :edge-key) - (remf args :edge-test) - (remf args :force-new?) - -|# - (assert (or (null edge-type) (eq edge-type :directed) (eq edge-type :undirected)) nil @@ -256,7 +244,6 @@ something is putting something on the vertexes plist's :graph graph :vertex-1 vertex-1 :vertex-2 vertex-2 args)) - ;;; --------------------------------------------------------------------------- (defmethod make-graph ((graph-type symbol) &rest args &key &allow-other-keys) @@ -469,14 +456,14 @@ something is putting something on the vertexes plist's ;;; --------------------------------------------------------------------------- -(defmethod find-edge-between-vertexes ((graph basic-graph) (value-1 t) (value-2 t) - &key (error-if-not-found? t)) - (let ((v1 (find-vertex graph value-1 error-if-not-found?)) - (v2 (find-vertex graph value-2 error-if-not-found?))) - (aif (and v1 v2 (find-edge-between-vertexes graph v1 v2)) - it - (when error-if-not-found? - (error 'graph-edge-not-found-error :vertex-1 v1 :vertex-2 v2))))) +(defmethod find-edge-between-vertexes + ((graph basic-graph) (value-1 t) (value-2 t) + &key (error-if-not-found? t)) + (let* ((v1 (find-vertex graph value-1 error-if-not-found?)) + (v2 (find-vertex graph value-2 error-if-not-found?))) + (or (and v1 v2 (find-edge-between-vertexes graph v1 v2))) + (when error-if-not-found? + (error 'graph-edge-not-found-error :vertex-1 v1 :vertex-2 v2)))) ;;; --------------------------------------------------------------------------- @@ -494,6 +481,11 @@ something is putting something on the vertexes plist's (delete-item (graph-edges graph) edge) edge) + +(defmethod delete-all-edges :after ((graph basic-graph)) + (empty! (graph-edges graph)) + graph) + ;;; --------------------------------------------------------------------------- (defmethod delete-vertex ((graph basic-graph) value-or-vertex) @@ -625,12 +617,18 @@ something is putting something on the vertexes plist's (defmethod find-vertex ((graph basic-graph) (value t) &optional (error-if-not-found? t)) - (aif (find-item (graph-vertexes graph) (funcall (vertex-key graph) value)) - it - (when error-if-not-found? - (error 'graph-vertex-not-found-error :vertex value :graph graph)))) + (or (find-item (graph-vertexes graph) (funcall (vertex-key graph) value)) + (when error-if-not-found? + (error 'graph-vertex-not-found-error :vertex value :graph graph)))) -;;; --------------------------------------------------------------------------- +(defmethod find-vertex ((graph basic-graph) (vertex basic-vertex) + &optional (error-if-not-found? t)) + (cond ((eq graph (graph vertex)) + vertex) + (t + (when error-if-not-found? + (error 'graph-vertex-not-found-error + :vertex vertex :graph graph))))) (defmethod find-vertex ((edge basic-edge) (value t) &optional (error-if-not-found? t)) @@ -643,38 +641,20 @@ something is putting something on the vertexes plist's (when error-if-not-found? (error 'graph-vertex-not-found-in-edge-error :vertex value :edge edge))) -;;; --------------------------------------------------------------------------- - -(defmethod search-for-vertex ((graph basic-graph) (value t) - &key (key (vertex-key graph)) (test 'equal) - (error-if-not-found? t)) - (aif (search-for-node graph value :test test :key key) - it - (when error-if-not-found? - (error "~S not found in ~A using key ~S and test ~S" value graph key - test)))) - -;;; --------------------------------------------------------------------------- (defmethod search-for-vertex ((graph basic-graph) (vertex basic-vertex) &key (key (vertex-key graph)) (test 'equal) (error-if-not-found? t)) - (aif (search-for-node (graph-vertexes graph) vertex :test test :key key) - it - (when error-if-not-found? - (error "~A not found in ~A" vertex graph)))) + (or (search-for-node (graph-vertexes graph) vertex :test test :key key) + (when error-if-not-found? + (error "~A not found in ~A" vertex graph)))) -;;; --------------------------------------------------------------------------- -;; TODO !!! dispatch is the same as the second method above (defmethod search-for-vertex ((graph basic-graph) (vertex t) &key (key (vertex-key graph)) (test 'equal) (error-if-not-found? t)) - (aif (search-for-element (graph-vertexes graph) vertex :test test :key key) - it - (when error-if-not-found? - (error "~A not found in ~A" vertex graph)))) - -;;; --------------------------------------------------------------------------- + (or (search-for-element (graph-vertexes graph) vertex :test test :key key) + (when error-if-not-found? + (error "~A not found in ~A" vertex graph)))) (defmethod iterate-elements ((graph basic-graph) fn) (iterate-elements (graph-vertexes graph) @@ -804,16 +784,6 @@ something is putting something on the vertexes plist's ;;; --------------------------------------------------------------------------- -#+COPYING -(defmethod generate-directed-free-tree ((graph basic-graph) (root basic-vertex)) - (let ((new-graph (copy-top-level graph))) - (empty! new-graph) - (nilf (contains-undirected-edge-p new-graph)) - (neighbors-to-children new-graph root) - (values new-graph))) - -;;; --------------------------------------------------------------------------- - (defmethod generate-directed-free-tree ((graph basic-graph) root) (generate-directed-free-tree graph (find-vertex graph root))) @@ -847,7 +817,7 @@ something is putting something on the vertexes plist's (defmethod traverse-elements-helper ((thing basic-vertex) (style (eql :depth)) marker fn) (when (eq (tag thing) marker) - (nilf (tag thing)) + (setf (tag thing) nil) (iterate-children thing (lambda (vertex) @@ -859,7 +829,7 @@ something is putting something on the vertexes plist's (defmethod traverse-elements-helper ((thing basic-vertex) (style (eql :breadth)) marker fn) (when (eq (tag thing) marker) - (nilf (tag thing)) + (setf (tag thing) nil) (funcall fn thing)) (iterate-neighbors @@ -872,7 +842,7 @@ something is putting something on the vertexes plist's thing (lambda (vertex) (when (eq (tag vertex) marker) - (nilf (tag vertex)) + (setf (tag vertex) nil) (traverse-elements-helper vertex style marker fn))))) ;;; --------------------------------------------------------------------------- @@ -884,7 +854,7 @@ something is putting something on the vertexes plist's (list start-vertex) (lambda (v) (if first-time? - (nilf first-time?) + (setf first-time? nil) (eq (find-vertex graph v) start-vertex))) (lambda (v) (child-vertexes v)) @@ -907,7 +877,7 @@ something is putting something on the vertexes plist's &optional (marked (make-container 'simple-associative-container)) (previous nil)) (block do-it - (tf (item-at-1 marked current)) + (setf (item-at-1 marked current) t) (iterate-children current (lambda (child) (cond @@ -1024,48 +994,48 @@ nil gathers the entire closure(s)." (defmethod make-filtered-graph ((old-graph basic-graph) test-fn - &optional + &key (graph-completion-method nil) - (depth nil)) - (let ((new-graph - (copy-template old-graph))) - (ecase graph-completion-method - ((nil - :complete-links) - (iterate-vertexes old-graph - (lambda (vertex) - (when (funcall test-fn vertex) - (add-vertex new-graph (value vertex)))))) - ((:complete-closure-nodes-only - :complete-closure-with-links) - (let* ((old-graph-vertexes (collect-items old-graph :filter test-fn)) - (closure-vertexes - (get-transitive-closure old-graph-vertexes depth))) - (dolist (vertex closure-vertexes) - (add-vertex new-graph (copy-template vertex)))))) - - (ecase graph-completion-method + (depth nil) + (new-graph + (copy-template old-graph))) + (ecase graph-completion-method + ((nil + :complete-links) + (iterate-vertexes old-graph + (lambda (vertex) + (when (funcall test-fn vertex) + (add-vertex new-graph (value vertex)))))) + ((:complete-closure-nodes-only + :complete-closure-with-links) + (let* ((old-graph-vertexes (collect-items old-graph :filter test-fn)) + (closure-vertexes + (get-transitive-closure old-graph-vertexes depth))) + (dolist (vertex closure-vertexes) + (add-vertex new-graph (copy-template vertex)))))) + (ecase graph-completion-method ((nil :complete-closure-nodes-only) nil) ((:complete-links :complete-closure-with-links) (complete-links new-graph old-graph))) - - new-graph)) + new-graph) ;;; --------------------------------------------------------------------------- (defmethod subgraph-containing ((graph basic-graph) (vertex basic-vertex) - &optional (depth nil)) - (make-filtered-graph graph - #'(lambda (v) - (equal v vertex)) - :complete-closure-with-links - depth)) + &rest args &key (depth nil) (new-graph nil)) + (declare (ignore depth new-graph)) + (apply #'make-filtered-graph + graph + #'(lambda (v) + (equal v vertex)) + :graph-completion-method :complete-closure-with-links + args)) ;;; --------------------------------------------------------------------------- (defmethod edge-count ((graph basic-graph)) - (length (edges graph))) + (count-using #'iterate-edges nil graph)) ;;; ---------------------------------------------------------------------------