[Nauty] Re: DAG isomorphisms for size > 7

Brendan McKay bdm at cs.anu.edu.au
Sat Feb 28 13:50:02 EST 2004


* Brian Patterson <patterbj at cs.iastate.edu> [040228 12:02]:
> Yes, I'm shooting for DAGs (completely acyclic graphs).  I didn't 
> understand the parameters I was giving directg very well - the "-T" now 
> makes a lot of sense.  But an "acyclic" option would be awesome.
> 
> I'd love to get the 20,286,025 graphs (for size 8, I assume?).  Also, 
> if there a closed-form function to return the number of directed 
> acyclic graphs of size n, I'd love to get a reference for it.
 
I added the acyclic digraphs of order 8 to
  http://cs.anu.edu.au/~bdm/data/digraphs.html
Note that the total size after expansion is more than 588 MB.

The exact number can be calculated but the formula is not so simple.
See the references at
  http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003087

Brendan.




More information about the Nauty mailing list