[Nauty] Re: DAG isomorphisms for size > 7

Brian Patterson patterbj at cs.iastate.edu
Sat Feb 28 11:48:02 EST 2004


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.

Thanks for your help!

Brian


On Feb 26, 2004, at 8:31 PM, Brendan McKay wrote:

> 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!
>
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list
>





More information about the Nauty mailing list