> < ^ From:

> < ^ Subject:

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 computeAutGroupGraph(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.

> < [top]