Opened 3 years ago

Closed 3 years ago

#19291 closed defect (fixed)

Graph.spanning_trees does not like loops

Reported by: Stefan Owned by:
Priority: major Milestone: sage-6.9
Component: graph theory Keywords:
Cc: Merged in:
Authors: Nathann Cohen Reviewers: Stefan van Zwam
Report Upstream: N/A Work issues:
Branch: 6a86e23 (Commits) Commit: 6a86e239c68f0d66cc182a98e74f72b34df4f961
Dependencies: Stopgaps:

Description

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.

Change History (5)

comment:1 Changed 3 years ago by ncohen

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/19291
  • Commit set to 6a86e239c68f0d66cc182a98e74f72b34df4f961
  • Status changed from new to needs_review

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:

6a86e23trac #19291: Graph.spanning_trees does not like loops

comment:2 follow-up: Changed 3 years ago by Stefan

  • Reviewers set to Stefan van Zwam
  • Status changed from needs_review to positive_review

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.

comment:3 in reply to: ↑ 2 Changed 3 years ago by dcoudert

Replying to 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)

comment:4 Changed 3 years ago by ncohen

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

comment:5 Changed 3 years ago by vbraun

  • Branch changed from u/ncohen/19291 to 6a86e239c68f0d66cc182a98e74f72b34df4f961
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.