I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ vertices. How can I do this?
More precisely, I want an algorithm that will generate a sequence of undirected graphs $G_1,G_2,\dots,G_k$, with the following property: for every undirected graph $G$ on $n$ vertices, there exists an index $i$ such that $G$ is isomorphic to $G_i$. I would like the algorithm to be as efficient as possible; in other words, the metric I care about is the running time to generate and iterate through this list of graphs. A secondary goal is that it would be nice if the algorithm is not too complex to implement.
Notice that I need to have at least one graph from each isomorphism class, but it's OK if the algorithm produces more than one instance. In particular, it's OK if the output sequence includes two isomorphic graphs, if this helps make it easier to find such an algorithm or enables more efficient algorithms, as long as it covers all possible graphs.
My application is as follows: I have a program that I want to test on all graphs of size $n$. I know that if two graphs are isomorphic, my program will behave the same on both (it will either be correct on both, or incorrect on both), so it suffices to enumerate at least one representative from each isomorphism class, and then test the program on those inputs. In my application, $n$ is fairly small.
Some candidate algorithms I have considered:
I could enumerate all possible adjacency matrices, i.e., all symmetric $n\times n$ 0-or-1 matrices that have all 0's on the diagonals. However, this requires enumerating $2^{n(n-1)/2}$ matrices. Many of those matrices will represent isomorphic graphs, so this seems like it is wasting a lot of effort.
I could enumerate all possible adjacency matrices, and for each, test whether it is isomorphic to any of the graphs I've previously output; if it is not isomorphic to anything output before, output it. This would greatly shorten the output list, but it still requires at least $2^{n(n-1)/2}$ steps of computation (even if we assume the graph isomorphism check is super-fast), so it's not much better by my metric.
It's possible to enumerate a subset of adjacency matrices. In particular, if $G$ is a graph on $n$ vertices $V=\{v_1,\dots,v_n\}$, without loss of generality I can assume that the vertices are arranged so that $\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$. In other words, every graph is isomorphic to one where the vertices are arranged in order of non-decreasing degree. So, it suffices to enumerate only the adjacency matrices that have this property. I don't know exactly how many such adjacency matrices there are, but it is many fewer than $2^{n(n-1)/2}$, and they can be enumerated with much fewer than $2^{n(n-1)/2}$ steps of computation. However, this still leaves a lot of redundancy: many isomorphism classes will still be covered many times, so I doubt this is optimal.
Can we do better? If I understand correctly, there are approximately $2^{n(n-1)/2}/n!$ equivalence classes of non-isomorphic graphs. Can we find an algorithm whose running time is better than the above algorithms? How close can we get to the $\sim 2^{n(n-1)/2}/n!$ lower bound? I care primarily about tractability for small $n$ (say, $n=5$ or $n=8$ or so; small enough that one could plausibly run such an algorithm to completion), not so much about the asymptotics for large $n$.
Related: Constructing inequivalent binary matrices (though unfortunately that one does not seem to have received a valid answer).
