[Nauty] DAG isomorphisms for size > 7

[Brendan McKay]

The graphs at the end of 
   http://cs.anu.edu.au/people/bdm/data/digraphs.html
are *acyclic* digraphs, so they have no directed cycles.
However, the sequence
   ./geng -q 3 | ./directg -u -o
makes all digraphs without cycles of length 2, including the
directed triangle 0-->1-->2-->0 which is not acyclic.  That is
why it produces 7 digraphs instead of 6.

Do you want acyclic or not?

For acyclic digraphs, the next two counts are 20,286,025 and 342,493,801.
You can't make them with software I've made available.  Perhaps I can
make the 20,286,025 with existing software if you need them.  For the
342,493,801, I would need to write a new program.

I'll also think about whether directg can get an "acyclic" option.

To get useful output from directg use the -T option.  If gives the
number of vertices, the number of edges, then a list of edges.

Brendan.


* Brian Patterson <patterbj at cs.iastate.edu> [040227 12:04]:
> Hi, new guy here so sorry if this question has already been asked 
> (though I searched the archives):
> 
> What I'm interested in finding is a way to use nauty, geng, directg, 
> etc. to generate the set of all non-isomorphic graphs for graphs of 
> size greater than 7 (hopefully in a format like at the bottom of 
> http://cs.anu.edu.au/people/bdm/data/digraphs.html for sizes 2-7).  I'm 
> not a computational graph theorist but I realize going much higher than 
> 7 is probably infeasible but I'd like to go as far as I can.
> 
> In the archives, someone suggested running the command line "./geng -q 
> 6 | ./directg -u" but (1) it gives output I don't follow and (2) the 
> counts don't add up.  Even if I do "./geng -q 3 | ./directg -u -o" (to 
> allow no bidirected edges), I still get 7 graphs when there are only 6 
> isomorphism classes in http://cs.anu.edu.au/people/bdm/data/dag3.txt .
> 
> Any help with either my understanding of the theoretical picture or 
> what parameters to use on this issue would be awesome.  Thanks!