# Generating lattice clusters/graphs in parallel

I'm trying to generate all graphs with n or fewer vertices that can be embedded in some lattice, eg square, triangular, Kagome. Do there exist algorithms to both enumerate and draw these graphs? What I am looking for is a technique to:

It turned out my original question was somewhat orthogonal to what I actually needed to do. Since starting with a list (E,V) and mapping it to a particular lattice is "hard", we opted to instead start off with the lattice type assumed. In this case, we specify graphs using coordinates on the lattice, so a 4-cycle on the square lattice would be: (0,0), (0,1), (1,0), (1,1). Using this representation, it's easy to add new sites to a graph (there are four possible positions, check if a site's already there). This also prevents us from generating disconnected graphs. We define two vertices as connected by an edge if they are lattice nearest-neighbours. Since we have several different meanings for "distinct" graphs (depending on the Hamiltonian we are using, it could be distinct under the dihedral group, distinct under x-reflection but not y-reflection, different adjacency lists, etc), we implemented several functions to check for different kinds of isomorphism, depending on which Hamiltonian we are using. We canonise distinct graphs using a simple lexicographic ordering scheme, which allows us to eliminate a huge number of similar graphs. To check if one graph is a subgraph of another, we check if its lattice coordinates can all be shifted by a constant vector so that the resulting list's elements can all be found in the lattice coordinates of the larger graph. Although we haven't implemented any parallelization yet, it seems likely that checking each graph for subgraphs is parallelizable (since a graph with n + 1 vertices can only have graphs of n vertices or below for subgraphs, if all the graphs are non-isomorphic), as is attempting to add sites in all possible positions for a graph and canonising the distinct graphs.