Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

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

Open
orivej opened this Issue Mar 8, 2012 · 4 comments

Comments

Projects
None yet
2 participants

orivej commented Mar 8, 2012

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

gwkkwg commented Mar 11, 2012

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 commented Mar 11, 2012

(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 commented May 6, 2012

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

Owner

gwkkwg commented May 7, 2012

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:
#4 (comment)

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment