[Nauty-list] Custom pruning in genbg
Brendan McKay
bdm at cs.anu.edu.au
Fri Jul 29 17:22:26 EST 2011
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
More information about the Nauty
mailing list