[Nauty] How to produce a histogram of graphs?

Noah Giansiracusa noahgian at u.washington.edu
Tue Feb 3 06:08:02 EST 2004


I am running some computer simulations in which I input Nauty a large list of graphs (up to 65,000 or so, and up to about 30 vertices per graph).  I then want to produce a histogram of the different isomorphims classes in that list.  Right now I am just having Nauty output the canonical form of all 65,000 graphs, and then I go through and sort them.  This is rather slow, since the canonical form is represented as a string.  I was wondering if it were possible to have Nauty either:

1) Output a numerical representation of each graph (i.e. the unique binary number produced by looking at the adjacency matrix of each graph), since I could then produce a binary search tree based on this number -- which is much faster than just comparing strings.

or

2) Somehow output the histogram of isomorphism classes directly.

Any suggestions?

Thanks,
Noah Giansiracusa









More information about the Nauty mailing list