DiFUB algorithm fails on some random graph
Closed this issue · 14 comments
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
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.
it was an incorrect use of method sorted.
New commits:
89c210e | trac #32095: sorted is not inplace |
Author: David Coudert
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.
Reviewer: Jonathan Kliem
If you prefer, we can use the graph6 string.
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.
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 |
Should be better this way.
Yes, that is better. It also fixes the graph in case that random graphs change at some point.
Changed branch from public/graphs/32095_fix_DiFUB_with_boost to 1d25896