[Nauty-list] Custom pruning in genbg

[Brendan McKay]

Hi Stephen,

Now I get it. I thought you wanted to make all extensions of an
input graph. That would be hard to do efficiently. 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.

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.

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.  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.

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 ;).

Regarding hypergraphs, I have some code written for a physics
project that is much faster than genbg in many cases. Please be
in touch about this off-list; we can decide if this code would be
useful for your project.

Cheers, Brendan.


* Stephen Hartke <hartke at gmail.com> [110802 02:29]:
> On Fri, Jul 29, 2011 at 2:22 AM, Brendan McKay <bdm at cs.anu.edu.au> wrote:
> 
> > It would be possible to make such a program, but modifying geng/genbg
> > is not the way to do it.  Those programs are designed for graph
> > classes such that removing a vertex keeps you in the class, or
> > at least the exceptions can be tested very quickly.  A class
> > whose definition includes having a certain subgraph doesn't fit.
> 
> 
> Brendan,
> 
> Thanks for response!  Unfortunately, I don't understand why modifying
> geng/genbg would not be appropriate.  Let me try to explain again.
> 
> I wish to use geng to generate graphs in a monotone family (closed under
> taking induced subgraphs) with a fixed number n of vertices.  As a toy
> example, consider generating triangle-free planar graphs with maximum degree
> 4 on 10 vertices.  geng can easily do this (using a custom pruning function
> for planarity, etc), and generate a list S of graphs.
> 
> Now suppose that I now want to generate all of the graphs on p vertices in
> the family, where p>n.  From my understanding of how geng works, it is doing
> a depth-first search, adding vertices to build graphs until it reaches the
> desired number of vertices.  If the standard geng (with custom pruning) is
> started to generate graphs with p vertices, it will re-generate all of the
> graphs with fewer vertices, including the list S of graphs with n vertices.
> It seems to me that a fair amount of computation could be saved if the tree
> search could be expanded starting with the graphs in S instead of the
> trivial graph.  geng would need to be run several times, with each graph in
> S initialized as the root of the search.  This corresponds to exploring
> descendants of those nodes of the search tree when no initialization is
> used.  I like to think of the initialization as just continuing to explore a
> search tree to generate larger objects.
> 
> Of course, we need to check that really all graphs with p vertices in the
> desired family are generated when initializing geng using S.  I think they
> are, since the canonical deletion of any such graph G with p vertices down
> to the trivial graph must pass through a graph H on n vertices in the
> family, which by definition is in S.
> 
> This approach only makes sense if the set S of graphs generated is
> reasonably small. For the applications I have in mind, this is mostly true.
> 
> I also am interested in searching for hypergraphs in certain closed
> families.  I am searching for them using genbg, thinking of the generated
> bipartite graphs as the incidence graphs of the hypergraphs.  When genbg
> adds a vertex to the second part, this corresponds to adding an edge in the
> hypergraph.  This may have been unclear in my previous message: I am always
> interested in adding vertices to graphs, and consider only families that are
> closed under taking induced subgraphs.
> 
> Does this seem a reasonable approach?  Given your experience with these
> types of computations, I would appreciate your opinion.
> 
> Thanks!
> Stephen