[Nauty-list] Custom pruning in genbg

[Brendan McKay]

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.

It seems that what you need is to add one edge at a time.

If you are dealing with comparatively small numbers of graphs
(fitting on disk for each value of e), a more brute-force approach
might be sufficient.  Given a file of the graphs with e edges,
send all the 1-edge extensions into shortg, then you get the
graphs with e+1 edges.

Brendan.

* Stephen Hartke <hartke at gmail.com> [110729 05:33]:
> Brendan,
> 
> Thanks for your response regarding the degree and the value of m!  It
> answered my questions.
> 
> Would it be possible to add a feature to geng/genbg that accepts a different
> graph as the initialization?  The program then would only search for larger
> graphs that canonically delete down to the initial graph.  The initial graph
> could be passed as a command line parameter, or maybe read from stdin.  I
> looked at the code, but it was not clear to me how to do this.
> 
> This initialization could be quite advantageous when combined with custom
> pruning procedures.  For example, I've been searching for hypergraphs with a
> given monotone property P.  I've run genbg with the pruning up to a given
> number e of edges.  However, to extend my search to e+1 edges, the program
> will redo all of the previous work.  With the initialization feature,
> geng/genbg could continue the search starting from the examples that were
> found with e edges.
> 
> Thanks!
> Stephen