Opened 10 years ago

Closed 10 years ago

# Bug in Graph.girth

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-5.0 graph theory jason sage-5.0.beta10 Nathann Cohen David Coudert, Jeroen Demeyer N/A

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

### comment:1 Changed 10 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: ↓ 3 Changed 10 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 10 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: ↓ 6 Changed 10 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 10 years ago by dcoudert

• Status changed from needs_review to needs_work

Change to needs_work

### comment:6 in reply to: ↑ 4 Changed 10 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

### comment:7 Changed 10 years ago by ncohen

• Status changed from needs_work to needs_review

### comment:8 Changed 10 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 10 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
**********************************************************************
sage: C.girth()
Expected:
4
Got:
2
**********************************************************************
```

### comment:10 Changed 10 years ago by dcoudert

• Status changed from needs_work to needs_review

This very basic patch should solve the problem.

### comment:11 Changed 10 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 10 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.