[Nauty-list] Custom pruning in genbg

[Stephen Hartke]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20110801/63815f3a/attachment.html