[Nauty-list] Using nauty for a membership test

[Arend Rensink]

Rather than comparing two graphs up to isomorphism, I want to find an isomorphic representative of a graph in a given set of graphs. This set can grow very large. The obvious way is to store the set as a hash map, where the hash key is derived from the canonical labelling of the graph. A good hash function should satisfy the following criteria:

- Few collisions (the computed keys should not coincide for distinct canonical labellings)
- Efficient computation (the computation of the keys should have low complexity)

Is this a known problem? Any ideas or pointers are very welcome!

-- 
Arend Rensink                         http://www.cs.utwente.nl/~rensink
Department of Computer Science             mailto:rensink at cs.utwente.nl
University of Twente                               tel: +31 53 489 4862
P.O. Box 217, NL-7500 AE Enschede, Netherlands     fax: +31 53 489 3247