Bug in edge disjoint spanning trees
Closed this issue · 69 comments
Timeout when creating edge disjoint spanning trees:
sage: dig6_string = r'[E_S?_hKIH@eos[BSg???Q@FShGC?hTHUGM?IPug?'
sage: dig6_string += r'JOEYCdOzdkQGo@ADA@AAg?GAQW?'
sage: dig6_string += r'[aIaSwHYcD@qQb@Dd?\hJTI@OHlJ_?C_OEIKoeCR@_BC?Q?'
sage: dig6_string += r'?YBFosqITEA?IvCU_'
sage: G = DiGraph(dig6_string)
sage: G.edge_connectivity(5)
5
sage: G.edge_disjoint_spanning_trees(5) # timeout
This contradicts a doctest in src/sage/graphs/generic_graph.py.
Depends on #32911
Component: graph theory
Keywords: spanning trees
Author: David Coudert
Branch: e23edfc
Reviewer: Travis Scrimshaw
Issue created by migration from https://trac.sagemath.org/ticket/32169
Description changed:
---
+++
@@ -11,4 +11,6 @@
sage: G.edge_disjoint_spanning_trees(5) # timeout
```
+This contradicts a doctest in `src/sage/graphs/generic_graph.py`.
+
Also I'm getting a bunch of Deprecation warning, when parsing the `dig6_string`: `DeprecationWarning: invalid escape sequence \h`.I get the answer very quickly with cplex and in a few seconds with coin. However, with glpk it takes ages (although it gets quickly the right LP bound).
sage: %time G.edge_disjoint_spanning_trees(5, solver='Cplex')
CPU times: user 2.74 s, sys: 67.5 ms, total: 2.81 s
Wall time: 663 ms
[Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices]
sage: %time G.edge_disjoint_spanning_trees(5, solver='Coin')
CPU times: user 3.52 s, sys: 76.7 ms, total: 3.6 s
Wall time: 3.61 s
[Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices]
Concerning the \h, if I replace it in the string with \\h, then I don't get the warning anymore. Not sure how to fix this issue.
Another option for the \h (which I think is better) would be to use raw strings (put an 'r' before each of them, or before the one that is giving an error, at least). As I understand it, dig6 strings can include any visible ascii character, including a backslash.
Description changed:
---
+++
@@ -1,10 +1,10 @@
Timeout when creating edge disjoint spanning trees:
```
-sage: dig6_string = '[E_S?_hKIH@eos[BSg???Q@FShGC?hTHUGM?IPug?'
-sage: dig6_string += 'JOEYCdOzdkQGo@ADA@AAg?GAQW?'
-sage: dig6_string += '[aIaSwHYcD@qQb@Dd?\hJTI@OHlJ_?C_OEIKoeCR@_BC?Q?'
-sage: dig6_string += '?YBFosqITEA?IvCU_'
+sage: dig6_string = r'[E_S?_hKIH@eos[BSg???Q@FShGC?hTHUGM?IPug?'
+sage: dig6_string += r'JOEYCdOzdkQGo@ADA@AAg?GAQW?'
+sage: dig6_string += r'[aIaSwHYcD@qQb@Dd?\hJTI@OHlJ_?C_OEIKoeCR@_BC?Q?'
+sage: dig6_string += r'?YBFosqITEA?IvCU_'
sage: G = DiGraph(dig6_string)
sage: G.edge_connectivity(5)
5
@@ -12,5 +12,3 @@
```
This contradicts a doctest in `src/sage/graphs/generic_graph.py`.
-
-Also I'm getting a bunch of Deprecation warning, when parsing the `dig6_string`: `DeprecationWarning: invalid escape sequence \h`.Replying to @DaveWitteMorris:
Another option for the
\h(which I think is better) would be to use raw strings (put an 'r' before each of them, or before the one that is giving an error, at least). As I understand it, dig6 strings can include any visible ascii character, including a backslash.
Thanks for the info. So this was a usage error from my side. I fixed the description.
The current method is based on integer linear programming and is very slow.
For undirected graphs, we can try to implement one of the existing polynomial time algorithm such as the one described in https://doi.org/10.1287/moor.10.4.701. I don't know yet if there is a simpler algorithms.
I don't know the algorithms for directed graphs.
Branch: public/graphs/32169_new_ILP
At first, I propose an alternative ILP formulation based on the Miller-Tucker-Zemlin subtour elimination constraints to replace the current formulation which is based on the maximum average degree. I obtain the solution for the reported digraph with glpk in 1.4s on a macbook air.
sage: d6 = r'[E_S?_hKIH@eos[BSg???Q@FShGC?hTHUGM?IPug?JOEYCdOzdkQGo@ADA@AAg?GAQW?[aIaSwHYcD@qQb@Dd?\hJTI@OHlJ_?C_OEIKoeCR@_BC?Q??YBFosqITEA?IvCU_'
sage: G = DiGraph(d6)
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Cplex')
CPU times: user 4.83 s, sys: 97.1 ms, total: 4.93 s
Wall time: 825 ms
sage: F
[Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices,
Digraph on 28 vertices]
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Coin')
CPU times: user 2.3 s, sys: 65.2 ms, total: 2.37 s
Wall time: 2.38 s
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='GLPK')
CPU times: user 1.36 s, sys: 7.96 ms, total: 1.36 s
Wall time: 1.37 s
Of course, it would be better to implement the polynomial time algorithms.
New commits:
76ce723 | trac #32169: new ILP formulation |
Author: David Coudert
Branch pushed to git repo; I updated commit sha1. New commits:
047afda | trac #32169: enforce equality in the number of incoming edges |
I get slightly better running time when I force equality for the number of incoming edges.
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Cplex')
CPU times: user 2.2 s, sys: 84.2 ms, total: 2.28 s
Wall time: 506 ms
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Coin')
CPU times: user 2.36 s, sys: 53.2 ms, total: 2.41 s
Wall time: 2.44 s
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='GLPK')
CPU times: user 1.22 s, sys: 8.05 ms, total: 1.22 s
Wall time: 1.23 s
However, if I remove the constraint ensuring that each vertex is incident to a selected edge, the program is way slower to solve.
Do you want to keep trying to improve the speed on this ticket or go with this current version and work on further improvements later?
I prefer to work on further improvements later. I had a look at a paper from Roskind and Tarjan for undirected graphs and it is already quite involved (I don't know if better / simpler algorithms have been proposed since 1985) and I have not seen any proposal for directed graphs yet.
Okay, LGTM.
Reviewer: Travis Scrimshaw
With this ticket our claim is still way above that what sage can do. For those three graphs with 12 vertices, this ticket fails:
sage: g1 = DiGraph(r'KAGBiSahR?D?Hw@jFDbLyTWAE')
sage: g2 = DiGraph(r'KW?ACPRIJh_AKPCk_KAORC`Bw')
sage: g3 = DiGraph(r'KOOB?R?@G_IGc_U}`NEMjE@CE')
Even worse, it seems to work find on the develop branch. However, on the develop branch I'm getting UnboundedLocalError, because classes are referenced before assignment.
Anyway, while this resolved the one particular case I reported, it seems to have created various other problems.
E.g.
g = DiGraph(r'SKwrQo`?DpS?hP@OaOYABAYP`OO[_JekGGPI?O_?bKG?IB?B@[BDGiKBCQMGoTp?GGC_')
is resolved now, but didn't work before.
Can you be more specific on the errors you get ? I can try to improve the formulation, and with more time to implement the polynomial time algorithms.
Branch pushed to git repo; I updated commit sha1. New commits:
2171ac4 | trac #32169: add strengthening constraints |
I added some strengthening constraints to speed up the resolution of the problem. Is it better now ?
Whenever I say a graph g is not working, I mean that:
sage: k = G.edge_connectivity(5)
sage: G.edge_disjoint_spanning_trees(k)
does not terminate in reasonable time.
Before this ticket, there was an UnboundedLocalError, whenever k was 0.
Branch pushed to git repo; I updated commit sha1. New commits:
3d53da3 | trac #32169: small cases |
added some tests to deal with small cases (k=0 or 1, n=0).
+ edges = p.get_values(edge)
+ for (e, c), val in edges.items():
+ if val == 1:
+ classes[c].add_edge(e)
see #32197.
Replying to @dcoudert:
I added some strengthening constraints to speed up the resolution of the problem. Is it better now ?
It seems to be an improvement. It takes way longer until I find a DiGraph with 12 vertices that does not work. And those do work in up to 40 seconds.
sage: g1 = DiGraph(r'KO_@OThwDWWCSAMOj_tCIa`DA')
sage: g2 = DiGraph(r'KGGdZEaQEOyEBZU?DO@O`wKBk')
sage: g3 = DiGraph(r'KH?cpUuwpp{AOH^SAEEDaWCbW')
sage: g4 = DiGraph(r'K?IJHENIUh[_ODPCD_@Tr{Wxg')
There is more. This is how I find them:
sage: def foo(n):
....: try:
....: alarm(20)
....: g = digraphs.RandomDirectedGNP(n, .3)
....: k = Integer(g.edge_connectivity())
....: arborescences = g.edge_disjoint_spanning_trees(k)
....: except AlarmInterrupt:
....: print(g.dig6_string())
....: finally:
....: cancel_alarm()
....:
sage: while True:
....: foo(12)
With the new formulation and glpk, I get the solution for g1, g2, g3 in less than 1s and for g4 in 5s. I'm on a Intel MacBook air.
But for sure it would be much better to get a proper implementation of the polynomial time algorithms.
I have rebased the branch on #32197 (hope I did it correctly...) and now use the integrality_tolerance.
Last 10 new commits:
cf16293 | MixedIntegerLinearProgram.get_values: Fix up for tolerance=None |
5a74113 | MixedIntegerLinearProgram._backend_variable_value: Add docstring |
aa4eed5 | MixedIntegerLinearProgram._backend_variable_value*: Add docstrings, examples |
00b34aa | trac #32197: review commit |
db83853 | trac #32197: another review commit |
b9f5f57 | trac #32169: new ILP formulation |
497b3dc | trac #32169: enforce equality in the number of incoming edges |
85bceee | trac #32169: add strengthening constraints |
ea3eb3f | trac #32169: small cases |
f977bfe | trac #32169: use convert and integrality_tolerance |
Changed branch from public/graphs/32169_new_ILP to public/graphs/32169_new_ILP_v2
The use of get_values looks fine. I have not looked at the details of the formulation used
The proposed formulation is clearly not best possible. The constraints I have used have been proposed for solving tsp, steiner tree, and simple path problems in graphs with negative weight cycles.We can certainly do better, but I'm not aware of the good formulations for this problem.
For undirected graphs, I plan to implement a polynomial time algorithm (e.g., Roskind-Tarjan). It will take some time.
This seems to be an improvement. However, there are still examples of very slow graphs with 12 vertices (one minute) and things get worse with more vertices, e.g.
sage: g = DiGraph(r'KAGHM`U`acCqHKEPmH@IHQdOy')
I don't know if this can be improved at all. I'm just stating this.
sage: g = Graph(r'M_IkGr`_QCwWDk?E?')
sage: g
Graph on 14 vertices
sage: k = Integer(g.edge_connectivity()) // 2
sage: %time trees = g.edge_disjoint_spanning_trees(k)
CPU times: user 11.7 s, sys: 18.2 ms, total: 11.7 s
Wall time: 11.7 s
Hence we lower the number of vertices in
||2609cb5||edge disjoint spanning tree not as fast as claimed, see #32169||
in #29935.
I now have an implementation of the Roskind-Tarjan algorithm for finding minimum-cost edge-disjoint spanning trees in undirected simple graphs.
However, I don't have any code for directed graphs (and I have not found any reference yet).
Which solution do you prefer:
- remove the ILP for undirected graphs and replace it with my code
- keep the ILP and add new code.
Note that the ILP is not needed if only for comparison purpose. I can add a method to check the validity of the solution.
Since the ILP part is going to have to stay (at least for now) for the directed graphs, I propose we keep it so there is more uniformity between directed and undirected graphs. Plus I always like having comparison options.
I have added the Roskind-Tarjan algorithm for undirected graphs.
test with graphs.RandomGNP(50, .4) and cplex, I get:
sage: g = Graph('qeOuOHJ?Ua?hkiwmAFDuDh|]ICoCrNTNKCLBmE]JH?s~{\\??mRR@sF_Ox@mUo|jAoh_A[]gh?@I}nGNRLUSNME]I{`kE@Q?eM?o\\^JOKpBcGbr_LCSGCpPPOo?CixnJ_
....: _ekpG@T[A^fEikLaAPcOhWqS_IWROGhB\\TiCaexPXrQHZBxjREuapmPPXIIccRVRMwHq}FR?G?Gqs?')
sage: k = Integer(g.edge_connectivity()) // 2
sage: k
7
sage: %time g.edge_disjoint_spanning_trees(k, algorithm="MILP")
CPU times: user 19.4 s, sys: 918 ms, total: 20.3 s
Wall time: 3.81 s
[Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices]
sage: %time g.edge_disjoint_spanning_trees(k, algorithm="Roskind-Tarjan")
CPU times: user 113 ms, sys: 1.98 ms, total: 115 ms
Wall time: 115 ms
[Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices,
Graph on 50 vertices]
I'm still looking for an algorithm for directed graphs. Any pointer is more than welcome (please avoid papers saying that "the argument directly translates to an efficient algorithm"...).
Branch pushed to git repo; I updated commit sha1. New commits:
8d42f68 | trac #32169: small issue |
may be EmptySetError could be loaded at module level since it is used in several methods ?
Perhaps this paper will help. It claims to provide "a simple algorithm which does find k disjoint branchings, if they exist, in polynomial time".
Robert Endre Tarjan
A good algorithm for edge-disjoint branching
Information Processing Letters
Volume 3, Issue 2, November 1974, Pages 51-53
https://doi.org/10.1016/0020-0190(74)90024-6
(When a branching is rooted at a single vertex, I think it is a directed tree that is rooted at that vertex.)
Actually, the good ones seems to be
- Harold N. Gabow: A Matroid Approach to Finding Edge Connectivity and Packing Arborescences. J. Comput. Syst. Sci. 50(2): 259-273 (1995) https://doi.org/10.1006/jcss.1995.1022
- Loukas Georgiadis, Dionysios Kefallinos, Luigi Laura, Nikos Parotsidis: An Experimental Study of Algorithms for Computing the Edge Connectivity of a Directed Graph. ALENEX 2021: 85-97 https://epubs.siam.org/doi/10.1137/1.9781611976472.7
It seems that the algorithm of Gabow is not so hard to implement (but not easy).If I understand well, the algorithm computes k-spanning-trees assuming (k-1) spanning trees are given as input (the trees might be modified). So it's incremental. Several steps are similar to the Roskind-Tarjan algorithms I implemented for undirected graphs. I will give it a try asap.
If you agree, I propose to move the code of the Roskind-Tarjan algorithm to a separate ticket. This way, it might be reviewed and possibly added to sagemath soon.
I'm working on the Gabow algorithm. Lukas Georgiadis kindly seeded me some C code, and I'm currently writing a Cython version. It requires careful checking, test and a lot of comments. It's a long and not easy code, so it takes time.
Changed branch from public/graphs/32169_new_ILP_v2 to public/graphs/32169_v3
FYI: thanks to the Loukas Georgiadis and his co-authors (see #comment:37), I now have a working implementation of the algorithm of Gabow for computing the edge connectivity of a digraph. They gave me a pure C code that I turned into an easier to read Cython code. It still lacks comments and doctests...
I'm still working on the second part of the paper of Gabow for extracting the k-edge-disjoint spanning trees (not obvious). I will not push code before it's done as I may have to refactor some parts of the first algorithm that are also used in the second part.
No problem. Just let me know when you're ready for a review.
Replying to @dcoudert:
FYI: thanks to the Loukas Georgiadis and his co-authors (see #comment:37), I now have a working implementation of the algorithm of Gabow for computing the edge connectivity of a digraph. They gave me a pure C code that I turned into an easier to read Cython code. It still lacks comments and doctests...
This is now #33839.
Then positive review.
Changed branch from public/graphs/32169_v3 to e23edfc
This makes the test suite hang with certain random seeds:
sage -t --long --random-seed=226966935809951887489348852629671397336 /usr/lib/python3.10/site-packages/sage/graphs/generic_graph.py
Timed out
**********************************************************************
Tests run before process (pid=581821) timed out:
[...]
sage: trees = g.edge_disjoint_spanning_trees(k, algorithm="MILP") ## line 6579 ##
------------------------------------------------------------------------
/usr/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x76fd)[0x7fdff2caa6fd]
/usr/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x77bc)[0x7fdff2caa7bc]
/usr/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0xa4e2)[0x7fdff2cad4e2]
/usr/lib/libc.so.6(+0x3e8e0)[0x7fdff42788e0]
/usr/lib/libglpk.so.40(glp_get_mat_col+0x4b)[0x7fdf7d591dfb]
/usr/lib/libglpk.so.40(glp_eval_tab_row+0x198)[0x7fdf7d5b3328]
/usr/lib/libglpk.so.40(+0x43ed5)[0x7fdf7d5b7ed5]
/usr/lib/libglpk.so.40(+0x49950)[0x7fdf7d5bd950]
/usr/lib/libglpk.so.40(+0x3be63)[0x7fdf7d5afe63]
/usr/lib/libglpk.so.40(glp_intopt+0xd2c)[0x7fdf7d5b108c]
/usr/lib/python3.10/site-packages/sage/numerical/backends/glpk_backend.cpython-310-x86_64-linux-gnu.so(+0x1f618)[0x7fdf7d6be618]
/usr/lib/python3.10/site-packages/sage/numerical/mip.cpython-310-x86_64-linux-gnu.so(+0x2bc83)[0x7fdf84e5ac83]
/usr/lib/libpython3.10.so.1.0(+0x154be1)[0x7fdff459bbe1]
/usr/lib/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x2ab)[0x7fdff45954bb]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x5aaf)[0x7fdff4590b9f]
/usr/lib/libpython3.10.so.1.0(+0x1603f6)[0x7fdff45a73f6]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x149a)[0x7fdff458c58a]
/usr/lib/libpython3.10.so.1.0(+0x143080)[0x7fdff458a080]
/usr/lib/libpython3.10.so.1.0(PyEval_EvalCode+0x94)[0x7fdff463cbb4]
/usr/lib/libpython3.10.so.1.0(+0x1fb9cb)[0x7fdff46429cb]
/usr/lib/libpython3.10.so.1.0(+0x15528f)[0x7fdff459c28f]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x346)[0x7fdff458b436]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyObject_FastCallDictTstate+0xdb)[0x7fdff45947ab]
/usr/lib/libpython3.10.so.1.0(_PyObject_Call_Prepend+0x6d)[0x7fdff45a4c5d]
/usr/lib/libpython3.10.so.1.0(+0x22d462)[0x7fdff4674462]
/usr/lib/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x2ab)[0x7fdff45954bb]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x5164)[0x7fdff4590254]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(+0x1603f6)[0x7fdff45a73f6]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x149a)[0x7fdff458c58a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyObject_FastCallDictTstate+0xdb)[0x7fdff45947ab]
/usr/lib/libpython3.10.so.1.0(+0x15d08d)[0x7fdff45a408d]
/usr/lib/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x283)[0x7fdff4595493]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x5164)[0x7fdff4590254]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x4ebf)[0x7fdff458ffaf]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x4ebf)[0x7fdff458ffaf]
/usr/lib/libpython3.10.so.1.0(+0x1603f6)[0x7fdff45a73f6]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x4ebf)[0x7fdff458ffaf]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(+0x143080)[0x7fdff458a080]
/usr/lib/libpython3.10.so.1.0(PyEval_EvalCode+0x94)[0x7fdff463cbb4]
/usr/lib/libpython3.10.so.1.0(+0x205103)[0x7fdff464c103]
/usr/lib/libpython3.10.so.1.0(+0x200a9a)[0x7fdff4647a9a]
/usr/lib/libpython3.10.so.1.0(+0xa183c)[0x7fdff44e883c]
/usr/lib/libpython3.10.so.1.0(_PyRun_SimpleFileObject+0x3cc)[0x7fdff44e84ed]
/usr/lib/libpython3.10.so.1.0(_PyRun_AnyFileObject+0x89)[0x7fdff44e8ea0]
/usr/lib/libpython3.10.so.1.0(Py_RunMain+0x3dd)[0x7fdff46586fd]
/usr/lib/libpython3.10.so.1.0(Py_BytesMain+0x3b)[0x7fdff462e19b]
/usr/lib/libc.so.6(+0x29290)[0x7fdff4263290]
/usr/lib/libc.so.6(__libc_start_main+0x8a)[0x7fdff426334a]
/usr/bin/python(_start+0x25)[0x5642f4693045]
------------------------------------------------------------------------
Changed commit from e23edfc to none
outch :(
This is for
g = Graph(']sLa{AZZs?fCoOOPAqJaO_byp|e?w[U@cObCktCSsAO]b{cndeJIT`G~dcaXWEBwUk_kLar@sg')
It's a too hard instance for this formulation with GLPK.
I see 2 solutions here: use a much smaller instance (10 nodes ?) or deprecate the ILP formulation. We have the polynomial time Roskind-Tarjan algorithm for undirected graphs and we should soon have an algorithm for directed graphs (GSoC project).
I would make the number of nodes for the test smaller as it is less invasive of a fix.
This bug has roared its ugly head again. Observed on Gentoo x86_64 Linux, Sage 9.8.beta7, with system-installed glpk-5.0-r1. What's even more disturbing is that doing G.edge_disjoint_spanning_trees(5,solver='ppl') does not seem to terminate either.
and after I installed Coin (used one from the system, coinor-cbc-2.10.5), I get
a multithreading-related crash:
....: sage: G.edge_connectivity()
python3: CbcModel.cpp:16173: int CbcModel::doOneNode(CbcModel*, CbcNode*&, CbcNode*&): Assertion `masterThread_' failed.
------------------------------------------------------------------------
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x7dfb)[0x7f4f7b4f6dfb]
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x7ea8)[0x7f4f7b4f6ea8]
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0xa1ed)[0x7f4f7b4f91ed]
/lib64/libc.so.6(+0x37950)[0x7f4f89103950]
/lib64/libc.so.6(+0x8342c)[0x7f4f8914f42c]
/lib64/libc.so.6(gsignal+0x12)[0x7f4f891038b2]
/lib64/libc.so.6(abort+0xd7)[0x7f4f890ee471]
/lib64/libc.so.6(+0x22395)[0x7f4f890ee395]
/lib64/libc.so.6(+0x30b92)[0x7f4f890fcb92]
/usr/lib64/libCbc.so.3(_ZN8CbcModel9doOneNodeEPS_RP7CbcNodeS3_+0x3055)[0x7f4e253859f5]
/usr/lib64/libCbc.so.3(_ZN8CbcModel14branchAndBoundEi+0x320c)[0x7f4e25388e5c]
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage_numerical_backends_coin/coin_backend.cpython-310-x86_64-linux-gnu.so(+0x21c05)[0x7f4e2540cc05]
/mnt/opt/Sage/sage-dev/src/sage/numerical/mip.cpython-310-x86_64-linux-gnu.so(+0x1a30f)[0x7f4e2a14a30f]
/usr/lib64/libpython3.10.so.1.0(+0x110fa3)[0x7f4f893abfa3]
/mnt/opt/Sage/sage-dev/src/sage/graphs/connectivity.cpython-310-x86_64-linux-gnu.so(+0x1012f)[0x7f4e2ad2112f]
/mnt/opt/Sage/sage-dev/src/sage/graphs/connectivity.cpython-310-x86_64-linux-gnu.so(+0x40cff)[0x7f4e2ad51cff]
/mnt/opt/Sage/sage-dev/src/sage/graphs/connectivity.cpython-310-x86_64-linux-gnu.so(+0x4622f)[0x7f4e2ad5722f]
/usr/lib64/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x90)[0x7f4f89362180]
/usr/lib64/libpython3.10.so.1.0(+0xc9db2)[0x7f4f89364db2]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0xa11f)[0x7f4f8930a68f]
/usr/lib64/libpython3.10.so.1.0(PyEval_EvalCode+0xcd)[0x7f4f8945c20d]
/usr/lib64/libpython3.10.so.1.0(+0x1ba021)[0x7f4f89455021]
/usr/lib64/libpython3.10.so.1.0(+0x111738)[0x7f4f893ac738]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x75b2)[0x7f4f89307b22]
/usr/lib64/libpython3.10.so.1.0(+0xdc82b)[0x7f4f8937782b]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x9829)[0x7f4f89309d99]
/usr/lib64/libpython3.10.so.1.0(+0xdc82b)[0x7f4f8937782b]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x9829)[0x7f4f89309d99]
/usr/lib64/libpython3.10.so.1.0(+0xdd53b)[0x7f4f8937853b]
/usr/lib64/libpython3.10.so.1.0(+0xd1208)[0x7f4f8936c208]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x75b2)[0x7f4f89307b22]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(+0xc9d78)[0x7f4f89364d78]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7645)[0x7f4f89307bb5]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(PyEval_EvalCode+0xcd)[0x7f4f8945c20d]
/usr/lib64/libpython3.10.so.1.0(+0x2071e9)[0x7f4f894a21e9]
/usr/lib64/libpython3.10.so.1.0(_PyRun_SimpleFileObject+0x164)[0x7f4f894a33e4]
/usr/lib64/libpython3.10.so.1.0(_PyRun_AnyFileObject+0x3c)[0x7f4f894a3a3c]
/usr/lib64/libpython3.10.so.1.0(Py_RunMain+0x7e8)[0x7f4f894c3fd8]
/usr/lib64/libpython3.10.so.1.0(Py_BytesMain+0x5a)[0x7f4f894c458a]
/lib64/libc.so.6(+0x2334a)[0x7f4f890ef34a]
/lib64/libc.so.6(__libc_start_main+0x7c)[0x7f4f890ef3fc]
python3(_start+0x21)[0x55de6f9c7081]
------------------------------------------------------------------------
Attaching gdb to process id 8887.
^CTraceback (most recent call last):
File "/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/bin/cysignals-CSI", line 225, in <module>
main(args)
File "/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/bin/cysignals-CSI", line 174, in main
trace = run_gdb(args.pid, not args.nocolor)
File "/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/bin/cysignals-CSI", line 98, in run_gdb
stdout, stderr = cmd.communicate(gdb_commands(pid, color))
File "/usr/lib/python3.10/subprocess.py", line 1154, in communicate
stdout, stderr = self._communicate(input, endtime, timeout)
File "/usr/lib/python3.10/subprocess.py", line 2005, in _communicate
ready = selector.select(timeout)
File "/usr/lib/python3.10/selectors.py", line 416, in select
fd_event_list = self._selector.poll(timeout)
KeyboardInterrupt
With Sage's supplied cbc, it works, including G.edge_disjoint_spanning_trees(5,solver='Coin')
It's a known problem that sage_numerical_backends_coin does not work properly with newer, distribution-provided COIN installations; see #30644
The way forward with COIN is via CVXpy as middleware - #34251 (needs review)
Unfortunately I'm currently too busy to work on the implementation of the combinatorial algorithm of Gabow but it's in my plan for the next months. It's a long and complex algorithm.