;;; ---------------------------------------------------------------------------
(defmethod make-graph ((classes list) &rest args)
- (let ((name (find-or-create-class 'basic-graph classes)))
+ (let ((name (dynamic-classes:find-or-create-class 'basic-graph classes)))
(apply #'make-instance name args)))
;;; ---------------------------------------------------------------------------
(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)
(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
thing
(lambda (vertex)
(when (eq (tag vertex) marker)
- (nilf (tag vertex))
+ (setf (tag vertex) nil)
(traverse-elements-helper vertex style marker fn)))))
;;; ---------------------------------------------------------------------------
+;; also in metatilites
+(defun graph-search-for-cl-graph (states goal-p successors combiner
+ &key (state= #'eql) old-states
+ (new-state-fn #'new-states))
+ "Find a state that satisfies goal-p. Start with states,
+ and search according to successors and combiner.
+ Don't try the same state twice."
+ (cond ((null states) nil)
+ ((funcall goal-p (first states)) (first states))
+ (t (graph-search-for-cl-graph
+ (funcall
+ combiner
+ (funcall new-state-fn states successors state= old-states)
+ (rest states))
+ goal-p successors combiner
+ :state= state=
+ :old-states (adjoin (first states) old-states
+ :test state=)
+ :new-state-fn new-state-fn))))
+
(defmethod in-cycle-p ((graph basic-graph) (start-vertex basic-vertex))
(let ((first-time? t))
(not (null
- (graph-search
+ (graph-search-for-cl-graph
(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))
&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
(assign-level graph 0)
(let ((depth 0))
(iterate-vertexes graph (lambda (vertex)
- (maxf depth (depth-level vertex))))
+ (when (> (depth-level vertex) depth)
+ (setf depth (depth-level vertex)))))
depth))
;;; ---------------------------------------------------------------------------