Random timeout in generic_graph

[tobiasdiez]

 src/bin/sage -t --warn-long 5.0 --random-seed=43052931192782388436004615366240964420 src/sage/graphs/generic_graph.py
Error: /usr/share/miniconda/envs/sage-dev/lib/python3.12/site-packages/cysignals/signals.cpython-312-x86_64-linux-gnu.so(+0x8ecc)[0x7f8c45ba9ecc]
/usr/share/miniconda/envs/sage-dev/lib/python3.12/site-packages/cysignals/signals.cpython-312-x86_64-linux-gnu.so(+0x8f99)[0x7f8c45ba9f99]
/usr/share/miniconda/envs/sage-dev/lib/python3.12/site-packages/cysignals/signals.cpython-312-x86_64-linux-gnu.so(+0xb8e6)[0x7f8c45bac8e6]
/lib/x86_64-linux-gnu/libc.so.6(+0x45330)[0x7f8c46245330]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x3239d)[0x7f8bdb77e39d]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x358b2)[0x7f8bdb7818b2]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x3001a)[0x7f8bdb77c01a]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x2d348)[0x7f8bdb779348]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x38e12)[0x7f8bdb784e12]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(glp_factorize+0xdf)[0x7f8bdb78a70f]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x39579)[0x7f8bdb785579]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(glp_simplex+0x5ab)[0x7f8bdb785c5b]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x44fa9)[0x7f8bdb790fa9]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x485b8)[0x7f8bdb7945b8]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(+0x3c244)[0x7f8bdb788244]
/usr/share/miniconda/envs/sage-dev/lib/libglpk.so.40(glp_intopt+0x830)[0x7f8bdb788f80]
/usr/share/miniconda/envs/sage-dev/lib/python3.12/site-packages/sage/numerical/backends/glpk_backend.cpython-312-x86_64-linux-gnu.so(+0x3a8e0)[0x7f8bdb86c8e0]
/usr/share/miniconda/envs/sage-dev/lib/python3.12/site-packages/sage/numerical/mip.cpython-312-x86_64-linux-gnu.so(+0x1d9a1)[0x7f8bdd8109a1]
python3(PyObject_Vectorcall+0x2e)[0x5619a920cdde]
python3(+0x112b23)[0x5619a910db23]
python3(PyEval_EvalCode+0xa1)[0x5619a92ab1a1]
python3(+0x2cc97c)[0x5619a92c797c]
python3(+0x11337b)[0x5619a910e37b]
python3(_PyObject_FastCallDictTstate+0x292)[0x5619a91fcc12]
python3(_PyObject_Call_Prepend+0x69)[0x5619a9225639]
python3(+0x2f70cb)[0x5619a92f20cb]
python3(_PyObject_MakeTpCall+0x2cc)[0x5619a91fa17c]
python3(+0x112b23)[0x5619a910db23]
python3(_PyObject_FastCallDictTstate+0x1ee)[0x5619a91fcb6e]
python3(+0x22a21c)[0x5619a922521c]
python3(_PyObject_MakeTpCall+0x294)[0x5619a91fa144]
python3(+0x112b23)[0x5619a910db23]
python3(PyEval_EvalCode+0xa1)[0x5619a92ab1a1]
python3(+0x2ea8ca)[0x5619a92e58ca]
python3(+0x2e5585)[0x5619a92e0585]
python3(+0x2e2620)[0x5619a92dd620]
python3(_PyRun_SimpleFileObject+0x1ce)[0x5619a92dd2be]
python3(_PyRun_AnyFileObject+0x44)[0x5619a92dcfe4]
python3(Py_RunMain+0x3a2)[0x5619a92d9eb2]
python3(Py_BytesMain+0x37)[0x5619a9295247]
/lib/x86_64-linux-gnu/libc.so.6(+0x2a1ca)[0x7f8c4622a1ca]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0x8b)[0x7f8c4622a28b]
python3(+0x29a0ed)[0x5619a92950ed]
------------------------------------------------------------------------
Attaching gdb to process id 41459.
Cannot find gdb installed
GDB is not installed.
Install gdb for enhanced tracebacks.
------------------------------------------------------------------------

https://github.com/sagemath/sage/actions/runs/18336258633/job/52221001109?pr=40923#step:15:6173
Ubuntu

[dcoudert]

Indeed, I can reproduce on my laptop.
However, I'm unable to identify the corresponding doctest. Do we have a verbose mode for doctests to help identifying the issue ?

[dcoudert]

ok, using ./sage -t --warn-long 5.0 --debug --random-seed=43052931192782388436004615366240964420 src/sage/graphs/generic_graph.py I can get the line after crtl-c.

The corresponding doctest is

File "src/sage/graphs/generic_graph.py", line 7460, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    trees = g.edge_disjoint_spanning_trees(k, algorithm='MILP')

For undirected graphs, we have a fast combinatorial algorithm (Roskind-Tarjan). A solution is to make it the only algorithm for undirected graphs. The MILP solution sometimes fails with glpk.

For directed graphs, the algorithm by Gabow has not yet been implemented (it is very difficult). So we have currently no other solution than a MILP formulation.

[orlitzky]

See also:

• generic_graph.py test timeout on aarch64 #34575
• Graph method edge_disjoint_spanning_trees() can hang #38831

We really need to replace GLPK with something like https://github.com/ERGO-Code/HiGHS. The GLPK project is essentially dead and it's very far from the state of the art.

[dcoudert]

I fully agree that we should replace glpk with a modern and more reliable solver like HIGHS.
We need someone to lead this task.

[orlitzky]

I fully agree that we should replace glpk with a modern and more reliable solver like HIGHS. We need someone to lead this task.

@cxzhong has started on this in #41105

[vincentmacri]

Another random seed that is giving me this same error, in case someone wants another test case.

--random-seed=24396435591607895684798352901827735493