DiFUB algorithm fails on some random graph

[kliem]

sage -t --long --random-seed=4 src/sage/graphs/digraph.py
**********************************************************************
File "src/sage/graphs/digraph.py", line 2475, in sage.graphs.digraph.DiGraph.?
Failed example:
    d1 == d2
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of 166 in sage.graphs.digraph.DiGraph.?
    [530 tests, 1 failure, 1.70 s]

sage: set_random_seed(4)                                                                                                                                                                                                                                                       
sage: G = graphs.RandomGNP(40, 0.4).to_directed()                                                                                                                                                                                                                              
sage: G.diameter()                                                                                                                                                                                                                                                             
3
sage: d1 = G.diameter(algorithm='DiFUB', by_weight=True)                                                                                                                                                                                                                       
sage: d1                                                                                                                                                                                                                                                                       
2.0

Yet, DiFUB claims to be exact.

Component: graph theory

Keywords: diameter

Author: David Coudert

Branch/Commit: 1d25896

Reviewer: Jonathan Kliem

Issue created by migration from https://trac.sagemath.org/ticket/32095

[dcoudert]

comment:1

DiFUB is an exact algorithm, and actually the default algorithm for unweighted digraphs is DiFUB as implemented in distances_all_pairs.pyx.

Apparently there is a bug in the implementation of DiFUB with boost (base/boost_graph.pyx). I will have a look.

[dcoudert]

Branch: public/graphs/32095_fix_DiFUB_with_boost

[dcoudert]

comment:2

it was an incorrect use of method sorted.

---

New commits:

89c210e

trac #32095: sorted is not inplace

[dcoudert]

Author: David Coudert

[dcoudert]

Commit: 89c210e

[kliem]

comment:3

Ok, this is good to go. Thanks for the quick fix. One needs to be carefull with setting set_random_seed(4), but this is ok at the end of a test block. The next block will get the initial seed again.

[kliem]

Reviewer: Jonathan Kliem

[dcoudert]

comment:5

If you prefer, we can use the graph6 string.

[kliem]

comment:6

It would be nice. At the moment things are stable and the next doctest is run with the correct seed. However, this doctest needs to be always the last (involving randomness) in this block.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

1d25896

trac #32095: avoid using set_random_seed

[sagetrac-git]

Changed commit from 89c210e to 1d25896

[dcoudert]

comment:8

Should be better this way.

[kliem]

comment:9

Yes, that is better. It also fixes the graph in case that random graphs change at some point.

[vbraun]

Changed branch from public/graphs/32095_fix_DiFUB_with_boost to 1d25896