Graph.spanning_trees does not like loops

[sagetrac-Stefan]

G = Graph({0:{0:'a', 1:'b'}, 1:{2: 'c'}, 2:{0: 'e'}}, loops=True)
S = G.spanning_trees()

goes "boom" (recursion depth exceeded). It also destroys G in the process, which shouldn't happen, I think.

Component: graph theory

Author: Nathann Cohen

Branch/Commit: 6a86e23

Reviewer: Stefan van Zwam

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

[nathanncohen]

Branch: u/ncohen/19291

[nathanncohen]

comment:1

Here is a fix. By the way, if you need this function for some hard computations know that there is room for much improvement in there.

Nathann

---

New commits:

6a86e23

trac #19291: Graph.spanning_trees does not like loops

[nathanncohen]

Commit: 6a86e23

[nathanncohen]

Author: Nathann Cohen

[sagetrac-Stefan]

Reviewer: Stefan van Zwam

[sagetrac-Stefan]

comment:2

I was just exploring some graph methods, I don't actually need to use it for now.

Your change forces a copy of the graph to be made regardless of whether there are loops. That's definitely safer than what happened before, but could be costly in terms of memory for big graphs. Still, I prefer the corresponding increase in safety of the code, so I will approve.

[dcoudert]

comment:3

Replying to @sagetrac-Stefan:

but could be costly in terms of memory for big graphs.

Well, considering such running time, it is likely that no one will use this method for "big graphs".

sage: g = graphs.GridGraph([2,2,2])
sage: %timeit g.spanning_trees()
10 loops, best of 3: 99.4 ms per loop
sage: g = graphs.GridGraph([2,2,3])
sage: %timeit g.spanning_trees()
1 loops, best of 3: 13.4 s per loop
sage: g.order(),g.size()
(12, 20)

[nathanncohen]

comment:4

Yeah, precisely. Stefan: to answer your question, I did not mind adding a graph copy to this method because, well, given the way it is written, the amount of wasted time is so high that this copy makes no difference. If you ever need this method "seriously", it will have to be reimplemented.

Nathann

[vbraun]

Changed branch from u/ncohen/19291 to 6a86e23