Bug in Graph.girth

[ncohen]

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

[ncohen]

Oh, and the example reported by Joro was :

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

Nathann

[dcoudert]

Installation, tests, docbuild and functionality on graphs are OK.

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?

D.

[ncohen]

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?

Well, 1 if there is a loop in the graph, and 2 if there is a pair of symmetric arcs.

I hate loops, and I hate symmetric arcs. :-P

Nathann

[dcoudert]

The point is that the patch currently returns another value :(

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

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

[dcoudert]

Change to needs_work

[ncohen]

The point is that the patch currently returns another value :(

Well, "the patch" does not really return another value. The current Sage function returns another value, and this patch just fixes another bug :-P

But you are right, let us also fix that with this patch.

Nathann

[dcoudert]

Excellent! The patch passes all long tests, functionality OK for both graphs and directed graphs (with and without loops or multiple edges).

Good to go !

[jdemeyer]

A doctest needs to be fixed (the old answer was wrong):

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

[dcoudert]

This very basic patch should solve the problem.