3 ms·
Nope, it's theoretically amazing interesting, but anyone who really wants to solve graph isomorphism would use Brendan McKay's Nauty, or one of the up-to-date i
by CJefferson 10y ago
Nope, it's theoretically amazing interesting, but anyone who really wants to solve graph isomorphism would use Brendan McKay's Nauty, or one of the up-to-date implementations (Saucy, Bliss, Hungry, Ferret).
Personal interest: I wrote Ferret, my PhD student wrote Hungry.
- bonzini 10y agoIsn't VF2 faster than Nauty?
- CJefferson 10y agoVF2 is faster than Nauty for EXTREMELY trivial problems (and many problems are extremely triial), but I've found many real-world problems where it falls off a cliff. VF2 is basically the most stupid search imaginable -- if the problem is easy it stumbles into the solution very quickly, but if any work is required it degrades into a horrible exponential search. On the other hand, Nauty is very difficult to confuse -- as it reasons about the whole graph (whereas VF2 just does local reasoning), your graph has to have global properties which make it hard, which are rare (and basically never occur in real-world graphs, unless they come from some mathematical problem).