nauty is a program for isomorphism and automorphism of graphs. Included in the package is a simple interactive interface dreadnaut and two programs geng and genbg for generating graphs and bipartite graphs.
debian deb packages
libnauty-dev - library for computing graph automorphisms (development files)
libnauty1d - library to compute graph automorphisms and canonical labellings
nauty - command line tools to compute graph automorphisms