Opened 7 years ago

Closed 7 years ago

#12355 closed defect (fixed)

Bug in Graph.girth

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: jason Merged in: sage-5.0.beta10
Authors: Nathann Cohen Reviewers: David Coudert, Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (2)

trac_12355.patch (3.1 KB) - added by ncohen 7 years ago.
trac_12355-rev.patch (609 bytes) - added by dcoudert 7 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

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

comment:2 follow-up: Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_info

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.

comment:3 in reply to: ↑ 2 Changed 7 years ago by 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

comment:4 follow-up: Changed 7 years ago by dcoudert

  • Status changed from needs_info to needs_review

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

comment:5 Changed 7 years ago by dcoudert

  • Status changed from needs_review to needs_work

Change to needs_work

comment:6 in reply to: ↑ 4 Changed 7 years ago by 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

Changed 7 years ago by ncohen

comment:7 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:8 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

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 !

comment:9 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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

Changed 7 years ago by dcoudert

comment:10 Changed 7 years ago by dcoudert

  • Status changed from needs_work to needs_review

This very basic patch should solve the problem.

comment:11 Changed 7 years ago by jdemeyer

  • Reviewers changed from David Coudert to David Coudert, Jeroen Demeyer
  • Status changed from needs_review to positive_review

comment:12 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta10
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.