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).
On Mon, Mar 3, 2014 at 12:41 PM, Volker Braun <vbraun.n...@gmail.com> wrote: > AFAIK both implement the same basic algorithm. My guess is that nauty > quickly realizes that it has a huge problem and starts constructing graph > invariants in an attempt to answer it to the negative. If you were to > compare two graphs that are actually isomorphic I'm pretty sure that you > wouldn't find such a big difference. For practical applications it is of > course important to have this trick using easily-accessible graph > invariants, but its probably not that hard to implement.. > > -- > 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.
