[Nauty] Generating reduced graphs only?
gordon at csse.uwa.edu.au
Wed Feb 9 23:43:01 EST 2005
> 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
Indeed this is the case - I was not telling the full story to try to
focus on the part causing problems, but ended up being misleading...
What I am actually doing is trying to use geng to generate graphs whose
adjacency matrices have low rank - there are other ways of doing this
that are fairly efficient, but I want to see just how close I can get
just using geng (or some other orderly algorithm if necessary).
So, I have a prune that eliminates a branch as soon as the rank gets
The problem is that when I am generating the graphs of rank less than
(for example) 6, I end up with every graph of ORDER up to 6 with every
vertex replicated in every possible way... so that by the time the
order gets to about 11, I am generating approximately 10^5 graphs for a
few hundred reduced ones, and with each increase in order, the spurious
graphs vastly outweigh the genuine examples.
This may kill the idea of using geng for this purpose, which is a
reasonable outcome of the investigation, but I was wondering if there
was something that I was missing in terms of earlier pruning... for
example, here is a basic question for which I don't even know the
answer.. is it true that every reduced graph CAN be generated
vertex-by-vertex with only reduced graphs as intermediates? Well, this
is probably not true, but it is not immediate to me if there is a
reduced graph such that every one-vertex deletion has a duplicate...
More information about the Nauty