Dear friends,

this is to share with you what a joy it was to work with Maple on the problem of enumerating non-isomorphic graphs. This problem goes back to Polya and Harary and it is a beautiful example of Polya counting, while also being of notable simplicity, so that a high school student or an undergraduate can follow it easily.

I have worked on this problem over the years, adapting my solutions in Cocoa and Lisp as I gained insights. My first attempt used GMP for large integers and can be found here. It was quite involved and while it computed results for very large values, there was a crucial oversight in that it did not use Lovasz' formula for the cycle index of the symmetric group. Thereafter I wrote another implementation in Lisp, taking advantage of the large integers provided by that language, but still not using said formula.

Most recently I was prompted by a post at math.stackexchange.com to revisit this problem and decided to implement the best algorithm, which is the one that uses Lovasz' formula. To my suprise it only needed a few lines of code to solve the problem even for large numbers of nodes. Imagine my amazement at the power of Maple especially taking into account the effort I had needed to program the solution with Objective C and GMP (which is not to say that this combination does not have its advantages under certain circumstances). I also enjoy working with a computer algebra system that keeps syntactic complexity to a minimum, enabling users to get started quickly.

I hope that with this motivational story I may give back some of the pleasure of my experience with Maple, and perhaps convince you that expanding the group theory package to include common cycle indices and routines to substitute at specific values of the variables would be a good thing to have, so that one day, counting non-isomorphic graphs will be as easy as saying give me the cycle index of the edge permutation group of the complete graph on n nodes and substitute the values of the edges into that index. Of course if you have such a package already do post the link.

Best regards,

Marko Riedel

PS: The Maple code for the enumeration can be foundhere.