[Nauty] Generating reduced graphs only?

[Brendan McKay]

* Gunnar Brinkmann <Gunnar.Brinkmann at UGent.be> [050209 20:04]:
> 
> > Suppose that for various computations, I am only interested in REDUCED
> > graphs - that is, no two vertices can have identical neighbourhoods...
> >
> > Obviously I can generate everything and then throw away those with
> > vertices with identical neighbourhoods at the end...  equally clearly,
> > I wish to do better than this, by pruning (using geng's "prune"
> > facility) those that will necessarily end up as not reduced.
> >
> > If I am aiming at n vertices, then at the final step, the n-1 vertex
> > graph can have two vertices with identical neighbourhoods, provided the
> > final step makes the final vertex adjacent to just one of those two.
> > However, it can't have THREE vertices with identical neighbourhoods
> > because then no matter what I do, the final step will leave two of them
> > identical...
> >
> > Similarly when I have n-i vertices, I cannot have more than 2^i
> > vertices with identical neighbourhoods...
> >
> > But can I do better?
 
I think Gunnar is correct that you can't save much.  The only 
exception would be if you have some other parameters set so that
non-reduced graphs are a much larger fraction.  Since the test
for reduced-ness is very fast (use sorting), I'd try using the
PREPRUNE feature to test canditates at the output level before
isomorph reduction is done.  That's in case the isomorph
reduction is slower on average.

Brendan.