Opened 10 years ago
Closed 10 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)
Change History (14)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 10 years ago by
- 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 10 years ago by
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: ↓ 6 Changed 10 years ago by
- 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 10 years ago by
- Status changed from needs_review to needs_work
Change to needs_work
comment:6 in reply to: ↑ 4 Changed 10 years ago by
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 10 years ago by
comment:7 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:8 Changed 10 years ago by
- 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 10 years ago by
- 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 10 years ago by
comment:10 Changed 10 years ago by
- Status changed from needs_work to needs_review
This very basic patch should solve the problem.
comment:11 Changed 10 years ago by
- Reviewers changed from David Coudert to David Coudert, Jeroen Demeyer
- Status changed from needs_review to positive_review
comment:12 Changed 10 years ago by
- Merged in set to sage-5.0.beta10
- Resolution set to fixed
- Status changed from positive_review to closed
Oh, and the example reported by Joro was :
Nathann