The complexity predicting the running time of this algorithm is difficult to analyze, and depends very deeply on the structure of the graph itself. With G and Pi as you have them, I'm looking at sage: g = Graph(G) sage: g.show(partition=Pi) and it seems to be moderately symmetric. Usually when this is the case, the algorithm performs best- it is a balance between enough information to narrow the search, but not so much information that that becomes a bottleneck.
I have a few questions. 1) What is the size of the automorphism group the function finally outputs, and do you suspect that it is incorrect? Most likely if the output is incorrect, you will have some subgroup of the automorphism group. If so, what size do you expect the automorphism group to be? > > I ran across a graph and partition for which it takes the search_tree > > function 6 hours on my machine to complete, and I was wondering if > > this is something to be expected, or a possible bug. I've been > > working with graphs of similar sizes to this one with no real > > problems, and in looking at the graph with the visualization > > functions, there didn't seem to be anything especially odd about it. 2) Can you give an example of a similar graph that goes quickly? > > I also profiled the search_tree function running on this graph; it > > wasn't all that illuminating, but I can post the results of that here > > too, if it would help. 3) That would probably mean more to me than to you, could you post it? -- Robert Miller --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://sage.math.washington.edu/sage/ and http://sage.scipy.org/sage/ -~----------~----~----~----~------~----~------~--~---
