Ask Your Question

Why does Sage 'stall' in this graph calculation?

asked 2019-01-27 10:51:39 -0500

aleph_two gravatar image

updated 2019-06-10 11:07:27 -0500

slelievre gravatar image

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?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2019-01-27 11:01:17 -0500

tmonteil gravatar image

updated 2019-01-27 13:15:08 -0500

Note 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).

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2019-01-27 10:51:39 -0500

Seen: 136 times

Last updated: Jun 10