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

[orivej]

trafficstars

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

[gwkkwg]

I think you're right about the issue. Can you please send me some test cases that fail with the old code and pass with the new. That way, I can augment the test suite and make sure that it doesn't regress in the future.

[orivej]

(let ((g (make-graph 'graph-container)))
  (in-undirected-cycle-p g (add-vertex g 1)))
;;; nil, previously g

(let ((g (make-graph 'graph-container)))
  (add-edge-between-vertexes g 1 2)
  (add-edge-between-vertexes g 2 3)
  (in-undirected-cycle-p g (find-vertex g 1)))
;;; nil, previously g

(let ((g (make-graph 'graph-container)))
  (add-edge-between-vertexes g 1 2)
  (add-edge-between-vertexes g 2 3)
  (add-edge-between-vertexes g 3 1)
  (in-undirected-cycle-p g (find-vertex g 1)))
;;; t, as before

(let ((g (make-graph 'graph-container :default-edge-type :directed)))
  (add-edge-between-vertexes g 1 2)
  (add-edge-between-vertexes g 2 3)
  (add-edge-between-vertexes g 3 1)
  (in-undirected-cycle-p g (find-vertex g 1)))
;;; t, previously g

(let ((g (make-graph 'graph-container)))
  (add-edge-between-vertexes g 1 2)
  (add-edge-between-vertexes g 2 1)
  (in-undirected-cycle-p g (find-vertex g 1)))
;;; t, as before, though nil seems more obvious

First two cases illustrate the necessity of the second change (“nil))”), the fourth case — that of the first change (“((in-undirected-cycle-p”, can explain why).

The fifth example is another issue. Is it so for performance considerations?

[orivej]

Why is not this issue fixed yet? May I help somehow?

[gwkkwg]

Hey there,

my apologies. I'm just really swamped.

I'll try to get to it this week.

thanks for the ping.

On May 6, 2012, at 7:00 AM, Orivej Desh wrote:

Why is not this issue fixed yet? May I help somehow?

---

Reply to this email directly or view it on GitHub: https://github.com/gwkkwg/cl-graph/issues/4#issuecomment-5534784

Gary Warren King, metabang.com Cell: (413) 559 8738 Fax: (206) 338-4052 gwkkwg on Skype * garethsan on AIM * gwking on twitter