Enumerating Graphs with Self-Loops

Question

Brendan McKay has already done the work for finding all non-isomorphic graphs of n variables that can be found here (under Simple Graphs): http://cs.anu.edu.au/~bdm/data/graphs.html

I believe this was done using polya enumeration, which I understand the basics of. I would like to expand on this, and allow self loops in these graphs. So, i'd like to find all non-ismorphic graphs of n variables, including self loops. This will be directly used for another part of my code and provide a massive optimization. I'm just not quite sure how to go about it.

To be clear, Brendan Mckay's files give all non ismorphic graphs, ie in edge notation,

1-2 1-3

is a graph with an edge between vertex 1 and 2, and 1 and 3. I want this list to also include self loops, ie:

1-2 1-3 1-1

or

1-2 1-3 1-1 2-2

I want the minimum number of graphs, so all non-ismorphic ones. How can I go about finding them, hopefully using the data Brendan McKay has available for simple graphs?

Answer 1

First of all, you should observe that if two graphs are not isomorphic, then these graphs with some additional self loops are not isomorphic.

If you need this during programming and size of graphs is small, I would generate for each non iso graph all possible self loop graphs.

Easiest thing to do is to add additional node, and every node with self loop will be connected with given node. (instead of having loop) Using nauty you can check if any two are isomorphic. You can additionally speed up things if you observe that if two loop encoded versions are iso, then they have to have same number of connections with "special" node.