[Nauty] forbidden sub-digraphs

Brendan McKay bdm at cs.anu.edu.au
Thu May 15 18:37:01 EST 2003


* Sterten at aol.com <Sterten at aol.com> [030515 17:19]:
> 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 ?

The structure of directg is completely different from that of geng,
so pruning would not be so simple.

In the case of geng, and also genbg, each graph is made by adding a
vertex and some edges to a smaller graph.  Therefore, if some graph has
a forbidden configuration, all the larger graphs made from it can be
rejected at once.

In the case of directg, suppose the underlying undirected graph G has
e edges.  Then there are 2*e possible directed edges which are numbered
arbitrarily 0,1,...,2*e-1.  Any directed graph made from G can be
written as a boolean vector of length 2*e, where a "1" means to include
that directed edge and "0" means to not include it.  The program makes
all such vectors and applies each automorphism of the graph to them.
Only the vectors which are minimal under the group action are written
out - this implies that only one of each set of isomorphic digraphs
is written.  (This is the logical structure of the algorithm; of course
the program uses a bunch of tricks to make this run faster on average.)
With this structure it is hard to do pruning efficiently, but it may be
possible to do something that is better than just filtering the outputs.

Brendan.




More information about the Nauty mailing list