ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 18 Sep 2020 05:39:43 +0200Time/Space Requirements of Graph.spanning_trees()https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/ Hello, I'm working on finding the number of a certain kind of spanning tree of a graph, and doing the Dodecahedron graph as an example. My naive algorithm for doing this iterates through all of its 5000000 or so spanning trees and runs a linear time (in graph size) algorithm on each spanning tree. The size of this problem seems just possible with my home computer, but Sage's builtin Graph.spanning_trees() is using too much RAM. Beyond this, I am unsure if the running time is reasonable once the RAM problem is fixed.
Do you know where I can find documentation discussing the implementation of this function? I imagine there could be a lazy version of this algorithm that makes the problem reasonable.Thu, 17 Sep 2020 08:27:11 +0200https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/Comment by tmonteil for <p>Hello, I'm working on finding the number of a certain kind of spanning tree of a graph, and doing the Dodecahedron graph as an example. My naive algorithm for doing this iterates through all of its 5000000 or so spanning trees and runs a linear time (in graph size) algorithm on each spanning tree. The size of this problem seems just possible with my home computer, but Sage's builtin Graph.spanning_trees() is using too much RAM. Beyond this, I am unsure if the running time is reasonable once the RAM problem is fixed.</p>
<p>Do you know where I can find documentation discussing the implementation of this function? I imagine there could be a lazy version of this algorithm that makes the problem reasonable.</p>
https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/?comment=53478#post-id-53478Just a side suggestion regarding your problem: you should try use the symmetries of the dodecahedron to avoid useless work when iterating over suc large objects.Thu, 17 Sep 2020 10:19:39 +0200https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/?comment=53478#post-id-53478Comment by BurnsidesLlama for <p>Hello, I'm working on finding the number of a certain kind of spanning tree of a graph, and doing the Dodecahedron graph as an example. My naive algorithm for doing this iterates through all of its 5000000 or so spanning trees and runs a linear time (in graph size) algorithm on each spanning tree. The size of this problem seems just possible with my home computer, but Sage's builtin Graph.spanning_trees() is using too much RAM. Beyond this, I am unsure if the running time is reasonable once the RAM problem is fixed.</p>
<p>Do you know where I can find documentation discussing the implementation of this function? I imagine there could be a lazy version of this algorithm that makes the problem reasonable.</p>
https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/?comment=53483#post-id-53483@tmonteil I had a similar thought using symmetries, where we somehow find representatives of each orbit of spanning trees (in the sense of the symmetries of the dodecahedron as a group action on the set of spanning trees), and somehow find the size of each orbit. I don't know how to do this efficiently though, as it seems I need to consider every spanning tree before I can find a representative of each orbit.Fri, 18 Sep 2020 05:39:43 +0200https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/?comment=53483#post-id-53483Answer by slelievre for <p>Hello, I'm working on finding the number of a certain kind of spanning tree of a graph, and doing the Dodecahedron graph as an example. My naive algorithm for doing this iterates through all of its 5000000 or so spanning trees and runs a linear time (in graph size) algorithm on each spanning tree. The size of this problem seems just possible with my home computer, but Sage's builtin Graph.spanning_trees() is using too much RAM. Beyond this, I am unsure if the running time is reasonable once the RAM problem is fixed.</p>
<p>Do you know where I can find documentation discussing the implementation of this function? I imagine there could be a lazy version of this algorithm that makes the problem reasonable.</p>
https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/?answer=53477#post-id-53477Making the `spanning_trees` method return an iterator rather than a list is the object of
- [Sage Trac ticket 30470: Make spanning_trees an iterator](https://trac.sagemath.org/ticket/30470)
which was merged in Sage 9.2.beta12.
Install Sage 9.2.beta12 or later to try it out.Thu, 17 Sep 2020 10:01:15 +0200https://ask.sagemath.org/question/53474/timespace-requirements-of-graphspanning_trees/?answer=53477#post-id-53477