title: Enumerate graphs under edge and symmetry constraints
body: <p>I would like to create the set of all directed graphs with <em>n</em> vertices where each vertex has <em>k</em> direct successors and <em>k</em> direct predecessors. <em>n</em> and <em>k</em> won't be that large, rather around <em>n</em> = 8 and <em>k</em> = 3. The set includes cyclic and acyclic graphs. Each graph in turn will serve as a template for sampling a large number of weighted graphs.</p>
  
  <p>My interest is in the role of topology motifs so I don't want to sample weights for any two graphs that are symmetric to each other, where <em>symmetry</em> means that no permutation of vertices exists in one graph that transforms it into the other. </p>
  
  <p>A naive solution would be to consider the 2 ^ (<em>n</em> * (<em>n</em> - 1)) adjacency matrices and eliminate all those (most of them) for which direct successor or predecessor constraints are violated. For <em>n</em> = 8, that's still few enough bits to represent and simply enumerate each matrix comfortably inside a <code>uint64_t</code>.</p>
  
  <p>Keeping track of row counts and column counts would be another improvement, but the real bottleneck will be adding the graph to the result set, at which point we need to test for symmetry against each other graph that's already in the set. For <em>n</em> = 8 that would be already more than 40,000 permutations per insert operation.</p>
  
  <p>Could anyone refer me to an algorithm that I could read up on that can do all this in a smarter way? Is there a graph library for C, C++, Java, or Python that already implements such a comprehensive graph generator? Is there a repository where someone has already "tabulated" all graphs for reasonable <em>n</em> and <em>k</em>?</p>