Yes automorphisms that pop up along the way are used to prune the search tree. That's a key feature of McKay's algorithm. Also, you are correct, checking for isomorphism of two graphs is faster than computing the canonical forms of each (this is what happens when you call G.is_isomorphic(H)), but my advice to Aleksandr is that in the case where you want to make a database, the fastest way to check if something's new is to use a hash -- and a canonical label is the first step towards getting an isomorph-invariant hash.
On Wed, Mar 5, 2014 at 2:53 AM, Dima Pasechnik <dimp...@gmail.com> wrote: > On 2014-03-04, Tom Boothby <tomas.boot...@gmail.com> wrote: >> They do implement the same basic algorithm. However, Robert worked >> from McKay's paper describing the algorithm, which was approximately >> state-of-the-art when he wrote the paper (but of course, the community >> tends to eschew optimizations as superfluous to the math, so...). >> Also, nauty has some pretty serious optimizations that Robert hasn't >> even attempted: graphs with <=32 vertices are implemented with bit >> hacks, for example... and there's the matter of the partition stack >> invariant - Robert and I came up with the best thing we could, but >> suspect that McKay's is better (but we didn't peek into his >> implementation to avoid license issues). > Do you keep track of graph automorphisms that pop up along the way? > This is potentially a huge improvement in the situation graphs do > have nontrivial automorphisms. > > Do you attempt to construct isomorphisms directly, or you rather > compute canonical forms? The latter is known to be less efficient in > practice in many cases. > > Dima > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-support+unsubscr...@googlegroups.com. > To post to this group, send email to sage-support@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-support. > For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/groups/opt_out.
