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.Sun, 27 Jan 2019 18:01:17 +0100Why does Sage 'stall' in this graph calculation?https://ask.sagemath.org/question/45210/why-does-sage-stall-in-this-graph-calculation/I was doing a demonstration for an intro graph theory course when it suddenly took a very long time to even look through 10,000 graphs. At home I isolated the troublesome code, which is this:
sage: for g in graphs(10):
....: x=g.edges();
Removing the x=, I found something surprising, the output stalls for >3min once it gets to the following graph:
[(0, 1, None),
(0, 2, None),
(0, 3, None),
(0, 4, None),
(0, 5, None),
(0, 6, None),
(0, 7, None),
(0, 8, None),
(1, 3, None),
(2, 3, None),
(3, 4, None),
(3, 5, None),
(3, 6, None),
(3, 7, None),
(3, 8, None),
(3, 9, None)]
Moreover on CoCalc [with a free server] this issue doesn't come up; it happily works through all of the graphs on 10 vertices with no discernable pauses. (Of course it takes a while to get through all 12 million, but I can see with debug statements that it is chugging along.)
The calculation pauses at other points but for much more reasonable lengths of time (<5sec).
Any idea what is going on here?Sun, 27 Jan 2019 17:51:39 +0100https://ask.sagemath.org/question/45210/why-does-sage-stall-in-this-graph-calculation/Answer by tmonteil for <p>I was doing a demonstration for an intro graph theory course when it suddenly took a very long time to even look through 10,000 graphs. At home I isolated the troublesome code, which is this:</p>
<pre><code> sage: for g in graphs(10):
....: x=g.edges();
</code></pre>
<p>Removing the x=, I found something surprising, the output stalls for >3min once it gets to the following graph:</p>
<p>[(0, 1, None),
(0, 2, None),
(0, 3, None),
(0, 4, None),
(0, 5, None),
(0, 6, None),
(0, 7, None),
(0, 8, None),
(1, 3, None),
(2, 3, None),
(3, 4, None),
(3, 5, None),
(3, 6, None),
(3, 7, None),
(3, 8, None),
(3, 9, None)] </p>
<p>Moreover on CoCalc [with a free server] this issue doesn't come up; it happily works through all of the graphs on 10 vertices with no discernable pauses. (Of course it takes a while to get through all 12 million, but I can see with debug statements that it is chugging along.)</p>
<p>The calculation pauses at other points but for much more reasonable lengths of time (<5sec).</p>
<p>Any idea what is going on here?</p>
https://ask.sagemath.org/question/45210/why-does-sage-stall-in-this-graph-calculation/?answer=45211#post-id-45211Note that you are not iterating over all graphs on {0,...,9}, but on all *isomorphism classes of graphs*, which is a much harder task. I did not check the internals of the algorithm, but one can easily imagine that at some points, it has to backtrack (or search) a lot before finding a new graph, that was not found before.
Note that there is a faster alternative using nauty library, you can replace `graphs(10)` with `graphs.nauty_geng(10)`.Sun, 27 Jan 2019 18:01:17 +0100https://ask.sagemath.org/question/45210/why-does-sage-stall-in-this-graph-calculation/?answer=45211#post-id-45211