[Nauty-list] Custom pruning in genbg

Stephen Hartke hartke at gmail.com
Fri Aug 5 03:38:22 EST 2011


Brendan,

Thanks for your response!

On Tue, Aug 2, 2011 at 12:58 AM, Brendan McKay <bdm at cs.anu.edu.au> wrote:

> Now I get it.  If you only need that the total output over all input graphs
> consists of all extensions of all the input graphs, that is much easier.


That's the idea exactly.


> As you say, it is restricted to cases where induced subgraphs are
> also in the class. This eliminates some of the families geng/gengbg
> can generate, such as those involving a minimum degree and
> connectivity.
>

Would it be possible to maintain connected?  It seems to me that this would
be possible if a cut vertex is never the canonical vertex to delete.  Does
geng operate in this way when generating connected graphs, or does it filter
afterward?


> Nauty doesn't always generate all the graphs up to order n in the
> process of making those of order n, but usually it makes a large
> fraction of them.


Could you please explain this a bit more?  My understanding was that all of
the smaller graphs were generated.


> So your idea could be useful in the case that
> the number of graphs (in the class) of order less than n is
> substantially larger than the number of order n.
>

For my applications, the number of graphs in the class of order less than n
is actually not that large.  However, the filtering is fairly intensive
computationally, so I want to avoid re-generating them when going to order
n.


> Implementing it doesn't seem to be too hard. The main procedure
> genextend() or spaextend() can be called with an input graph rather
> than with K1 as now. The tricky part is to get all the various data
> structures into the required states before the call. There are
> several apart from the function parameters and they are subtle.
> I'm thinking about it ;).
>

The code was not so clear to me, so I'll second the subtle part! :)

Thanks!
Stephen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20110804/6392bd7a/attachment.html 


More information about the Nauty mailing list