id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
12355 Bug in Graph.girth ncohen jason, ncohen, rlm "Funny thing. The function is finding the correct answer, but does not know when to stop, and can be lead (for instance on the example given in [1]) to replace a best answer of 3 by a 4.
I am not satisfied with this patch, because the ""right way"" would be to use a goto to leave two loops at once. Yeah, goto are useful sometimes. So instead I added a ""if"" to leave the second loop. This could have been solved differently, for instance by replacing ``best = depth*2`` by ``best = min(best, 2*depth)``, but I thought more sensible to avoid reading the graph structure as much as possible, which is much harder than testing an easy constraint.
Well. It was a funny one. And I really could have used a GOTO statement there `:-)`
Nathann
[1] http://ask.sagemath.org/question/1075/bug-in-graphgirth-in-472" defect closed major sage-5.0 graph theory fixed jason sage-5.0.beta10 Nathann Cohen David Coudert, Jeroen Demeyer N/A