cl-graph
cl-graph copied to clipboard
In graph.lisp in-undirected-cycle-p is not correct
Sometimes it returns the vector returned by #'iterate-children. Return from the recursive call is not dealt with correctly. (Iteration should continue when return is nil and stop when it is t.) Here is a fixed version:
(defmethod in-undirected-cycle-p
((graph basic-graph) (current basic-vertex)
&optional (marked (make-container 'simple-associative-container))
(previous nil))
(block do-it
(setf (item-at-1 marked current) t)
(iterate-children current
(lambda (child)
(cond
((eq child previous) nil)
((item-at-1 marked child) (return-from do-it t))
((in-undirected-cycle-p graph child marked current)
(return-from do-it t)))))
nil))