> < ^ Date: Fri, 20 Oct 2000 15:42:14 +0200
> < ^ From: Dmitrii Pasechnik <d.pasechnik@twi.tudelft.nl >
< ^ Subject: Re: a question on fast symmetry checking (Nauty problem?)

Dear Forum,

following up my own message, I'd like to point out that if one uses
extra option of Nauty that allows one to specify "vertex invariants" for
pre-refinement of vertex partitions, the particular graph that takes so long
to process can be done instantly.
The invariant I tried was "twopaths" - vertices are somehow
classified with respect to their second neighbourhoods.

At the moment there is no option in GRAPE to supply this extra setting
to Nauty. But working directly with Nauty (or hacking GRAPE to supply such
an option, or ask Leonard Soicher to add such an option) is easy enough.

Let me describe Nauty session that does the computation I describe.
(I hope I am forgiven for writing about this on GAP list :-))
Assume that the Nauty input from my previous post is saved in a file, called say f90.

Start dreadnaut - a Nauty interactive frontend. With GRAPE fully
installed, it would usually reside in the same place as your GAP
executable. You'll get the dreadnaut prompt >

Read the file in :
><f90

If you like, display graph:
> t
  1 :  39 51 53 60 64 70 81 83;
  2 :  23 36 38 51 62 68 69;
[etc.]

Set the vertex invariant to use:
> *=1

Refine the vertex partition
> I
89 cells; code = 3aad (twopaths worked)

Execute Nauty
> x
[fixing partition]
level 1:  89 cells; 90 orbits; 24 fixed; index 1/2
90 orbits; grpsize=1; 0 gens; 3 nodes (1 bad leaf); maxlev=2
tctotal=2
>

(the last command takes < 1 sec on a usual PC)

HTH,
Dmitrii
http://ssor.twi.tudelft.nl/~dima/

Miles-Receive-Header: reply


> < [top]