<p><pre><code>  &gt; NAUTY (and SAUCY) were good practical implementations 
  &gt; that found solutions efficiently (except for some 
  &gt; harder class of graphs, maybe).
</code></pre>
There are good practical implementations of SAT solvers as well (except degenerate cases), even though SAT is the canonical NP-Complete problem.