Dear GAP Forum,

Regarding the discussion on the speed problems with directed
graphs that nauty has when called from GRAPE, I would like to
first repeat my advice from an earlier email to the Forum:

With the default parameters that GRAPE gives to nauty,

AutGroupGraph(gamma) (or AutomorphismGroup(gamma))

may perform very badly when gamma is a sparse non-simple graph.
If gamma is such a graph then you should instead compute

AutGroupGraph(ComplementGraph(gamma))

to obtain the automorphism group of gamma.

Following this advice, it is *very* easy and quick to compute
the (trivial) automorphism groups of the three (current) examples
in http://www.eecs.umich.edu/~faloul/gap . Similar advice applies
for graph isomorphism testing.

The next version of GRAPE (under development) automatically gives nauty
(2.0beta5) the vertex-invariant "adjacencies" when the input graph is
not simple (this vertex-invariant had been developed by Brendan McKay
in response to problems with certain directed graphs and I should have
used it in GRAPE sooner). I tested the three examples with the
development version of GRAPE, and it too found the answer in a small
number of seconds. Similarly, isomorphism testing for non-simple graphs
will use the "adjacencies" vertex-invariant with nauty.

Regards,     
                   Leonard Soicher.