[Nauty] Re: nauty-list digest, Vol 1 #116 - 3 msgs

[Brendan McKay]

* Sterten at aol.com <Sterten at aol.com> [050313 18:09]:
> 
> Hello Senlin,
> 
> the other post yesterday gave me the idea to convert  the digraph into an 
> undirected graph
> with isomorphic automorphismgroup.
> It seems that this is much faster  than using  options.digraph = TRUE
> for some graphs with large  automorphismgroup like the one which you posted.
> The program below gave answer 16777216 immediately.

Yes, this can help with digraphs sometimes. An alternative is to use
the "adjacencies" invariant, like this:

        options.mininvarlevel = 1;
        options.maxinvarlevel = 99;
        options.invarproc = adjacencies;

("99" is arbitrary).  This change also gives 16777216 immediately
with the same example.

I don't know if this example is a case, but many times someone has
shown me a digraph with can be converted to an undirected graph
directly without increasing the number of vertices.  For example,
if the digraph is a tree with all edges directed away from the root,
change it to an undirected tree with the root having a different
colour from the other vertices.  Similarly, if the digraph has
vertex set X union Y (where X and Y are disjoint) and every edge
is a directed edge from X to Y, change it to an undirected graph
with X and Y indicated by vertex colouring.  This type of thing is
not always possible, but when it is possible the improvement is
often spectactular.

Brendan.