cl-graph icon indicating copy to clipboard operation
cl-graph copied to clipboard

In graph.lisp in-undirected-cycle-p is not correct

Open orivej opened this issue 12 years ago • 4 comments

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))

orivej avatar Mar 08 '12 15:03 orivej