[Nauty] isomorphism of graphs generated by geng

Brendan McKay bdm at cs.anu.edu.au
Sat Jun 25 17:24:01 EST 2005


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




More information about the Nauty mailing list