[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