Sage: Ticket #12355: Bug in Graph.girth
http://trac.sagemath.org/ticket/12355
<p>
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.
</p>
<p>
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 <tt></tt>best = depth*2<tt></tt> by <tt></tt>best = min(best, 2*depth)<tt></tt>, 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 <tt>:-)</tt>
</p>
<p>
Nathann
</p>
<p>
[1] <a class="ext-link" href="http://ask.sagemath.org/question/1075/bug-in-graphgirth-in-472"><span class="icon"></span>http://ask.sagemath.org/question/1075/bug-in-graphgirth-in-472</a>
</p>
en-usSagehttp://trac.sagemath.org/chrome/site/sage_logo_trac_v2.png
http://trac.sagemath.org/ticket/12355
Trac 1.1.1ncohenWed, 25 Jan 2012 11:29:42 GMTstatus changed
http://trac.sagemath.org/ticket/12355#comment:1
http://trac.sagemath.org/ticket/12355#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Oh, and the example reported by Joro was :
</p>
<pre class="wiki">sage: H=Graph([(0, 1), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 6), (2, 5), (3, 4), (5, 6)])
sage: H.girth()
4
sage: H.is_triangle_free()
False
</pre><p>
Nathann
</p>
TicketdcoudertSat, 17 Mar 2012 16:33:54 GMTstatus changed; reviewer set
http://trac.sagemath.org/ticket/12355#comment:2
http://trac.sagemath.org/ticket/12355#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
Installation, tests, docbuild and functionality on graphs are OK.
</p>
<p>
However, I don't understand the behavior for digraphs. What should be the correct answer for a digraph with a pair of symmetric arcs? For instance, for the digraph with arc set [(0,1),(1,0),(1,2),(2,0)], the girth is 2 or 3? and what if the digraph has loops?
</p>
<p>
D.
</p>
TicketncohenSat, 17 Mar 2012 16:35:59 GMT
http://trac.sagemath.org/ticket/12355#comment:3
http://trac.sagemath.org/ticket/12355#comment:3
<blockquote class="citation">
<p>
However, I don't understand the behavior for digraphs. What should be the correct answer for a digraph with a pair of symmetric arcs? For instance, for the digraph with arc set [(0,1),(1,0),(1,2),(2,0)], the girth is 2 or 3? and what if the digraph has loops?
</p>
</blockquote>
<p>
Well, 1 if there is a loop in the graph, and 2 if there is a pair of symmetric arcs.
</p>
<p>
I hate loops, and I hate symmetric arcs. <tt>:-P</tt>
</p>
<p>
Nathann
</p>
TicketdcoudertSat, 17 Mar 2012 16:41:41 GMTstatus changed
http://trac.sagemath.org/ticket/12355#comment:4
http://trac.sagemath.org/ticket/12355#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
The point is that the patch currently returns another value :(
</p>
<p>
For instance, the de Bruijn digraph of degree 2 and diameter 3 has both loops and pairs of symmetric arcs, but the returned value is 3...
</p>
<pre class="wiki">sage: D = digraphs.DeBruijn(2,3)
sage: D.edges(labels=None)
[('000', '000'), ('000', '001'), ('001', '010'), ('001', '011'), ('010', '100'), ('010', '101'), ('011', '110'), ('011', '111'), ('100', '000'), ('100', '001'), ('101', '010'), ('101', '011'), ('110', '100'), ('110', '101'), ('111', '110'), ('111', '111')]
sage: D.girth()
3
</pre>
TicketdcoudertSat, 17 Mar 2012 16:41:59 GMTstatus changed
http://trac.sagemath.org/ticket/12355#comment:5
http://trac.sagemath.org/ticket/12355#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Change to needs_work
</p>
TicketncohenSat, 17 Mar 2012 16:47:25 GMT
http://trac.sagemath.org/ticket/12355#comment:6
http://trac.sagemath.org/ticket/12355#comment:6
<blockquote class="citation">
<p>
The point is that the patch currently returns another value :(
</p>
</blockquote>
<p>
Well, "the patch" does not really return another value. The current Sage function returns another value, and this patch just fixes another bug <tt>:-P</tt>
</p>
<p>
But you are right, let us also fix that with this patch.
</p>
<p>
Nathann
</p>
TicketncohenSat, 17 Mar 2012 17:00:22 GMTattachment set
http://trac.sagemath.org/ticket/12355
http://trac.sagemath.org/ticket/12355
<ul>
<li><strong>attachment</strong>
set to <em>trac_12355.patch</em>
</li>
</ul>
TicketncohenSat, 17 Mar 2012 17:01:04 GMTstatus changed
http://trac.sagemath.org/ticket/12355#comment:7
http://trac.sagemath.org/ticket/12355#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketdcoudertSat, 17 Mar 2012 17:08:38 GMTstatus changed
http://trac.sagemath.org/ticket/12355#comment:8
http://trac.sagemath.org/ticket/12355#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Excellent!
The patch passes all long tests, functionality OK for both graphs and directed graphs (with and without loops or multiple edges).
</p>
<p>
Good to go !
</p>
TicketjdemeyerTue, 20 Mar 2012 20:47:34 GMTstatus changed
http://trac.sagemath.org/ticket/12355#comment:9
http://trac.sagemath.org/ticket/12355#comment:9
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
A doctest needs to be fixed (the old answer was wrong):
</p>
<pre class="wiki">sage -t -force_lib devel/sage/doc/en/constructions/graph_theory.rst
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta10/devel/sage-main/doc/en/constructions/graph_theory.rst", line 51:
sage: C.girth()
Expected:
4
Got:
2
**********************************************************************
</pre>
TicketdcoudertTue, 20 Mar 2012 21:20:22 GMTattachment set
http://trac.sagemath.org/ticket/12355
http://trac.sagemath.org/ticket/12355
<ul>
<li><strong>attachment</strong>
set to <em>trac_12355-rev.patch</em>
</li>
</ul>
TicketdcoudertTue, 20 Mar 2012 21:21:27 GMTstatus changed
http://trac.sagemath.org/ticket/12355#comment:10
http://trac.sagemath.org/ticket/12355#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
This very basic patch should solve the problem.
</p>
TicketjdemeyerWed, 21 Mar 2012 08:23:30 GMTstatus, reviewer changed
http://trac.sagemath.org/ticket/12355#comment:11
http://trac.sagemath.org/ticket/12355#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>David Coudert</em> to <em>David Coudert, Jeroen Demeyer</em>
</li>
</ul>
TicketjdemeyerFri, 23 Mar 2012 15:21:11 GMTstatus changed; resolution, merged set
http://trac.sagemath.org/ticket/12355#comment:12
http://trac.sagemath.org/ticket/12355#comment:12
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.0.beta10</em>
</li>
</ul>
Ticket