[Nauty] forbidden sub-digraphs

[Sterten at aol.com]

hi Brendan,

do you think it's possible to include a "prune" in directg,
like what you did in geng ?
That would enable us to generate all S-free digraphs efficiently,
where S is any set of forbidden sub-digraphs.

OK, I could convert the digraphs in S into undirected graphs, getting T,
then run geng on T to generate all possible graphs which don't
have any of T as subgraph.
Then I can feed this list into directg and then filter the
output again, so that it not only excludes forbidden subgraphs graphs from T
but forbidden sub-digraphs from S.

But this doesn't sound very efficient, does it ?


Guenter

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20030515/76b4c319/attachment.html