[Nauty] isomorphism of graphs generated by geng

Andrew H andy_t_roo at hotmail.com
Sun Jun 26 17:25:02 EST 2005


at this stage, i'm only looking at graphs with about 10 verticies, where all 
12,000,000 can be calculated in a min or 2, so increasing the time from 1 to 
10 min wouldn't matter that much to me, as i'll only need to do it as a one 
off event, then can store the results.

Andrew

-------------------
Eagles may soar, but weasels don't get sucked into jet engines



>From: Brendan McKay <bdm at cs.anu.edu.au>
>Reply-To: nauty-list at cs.anu.edu.au
>To: nauty-list at cs.anu.edu.au
>Subject: Re: [Nauty] isomorphism of graphs generated by geng
>Date: Sat, 25 Jun 2005 17:23:06 +1000
>
>It would be possible to write a generator with that property.
>
>At the moment it adds one vertex at a time, but adding one edge
>at a time could also be done. I suspect that the efficiency would
>be reduced substantially (several times), so it comes down to how
>important the order of generation is for your application.
>
>Brendan.
>
>* Andrew H <andy_t_roo at hotmail.com> [050625 13:14]:
> > would it be possible to modify geng so that all the graphs that are 
>output
> > can be crated by adding one edge to a graph that it has already output?
> >
> > eg when generating graphs of 5 verticies you get
> >
> > $ geng 5 | listg -e
> >
> > ...
> > Graph 3, order 5.
> > 5 2
> > 2 4  3 4
> > ...
> > Graph 6, order 5.
> > 5 2
> > 1 2  3 4
> >
> > Graph 7, order 5.
> > 5 3
> > 1 3  2 4  3 4
> >
> > Graph 8, order 5.
> > 5 3
> > 0 4  1 4  2 3
> >
> > graph 7 is made by adding 1,3 to graph 3, but you can't make graph 8 - 
>but
> > 1,2 3,4 4,5 and 1,5 2,4 3,4 are isomorphic to it and can be. i'm not 
>sure
> > how the program works, but would it be possible so that the latter were
> > output instead (and likewise for the rest of the graphs)
> >
> > thanks,
> > Andrew
> >
> >
> > -------------------
> > Eagles may soar, but weasels don't get sucked into jet engines
> >
> >
> >
> > _______________________________________________
> > 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
>
>_______________________________________________
>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