[Nauty] Extending graphs by one vertex

Brendan McKay bdm at cs.anu.edu.au
Mon Oct 13 23:03:01 EST 2003


Do you really only want to add one more vertex, or are you planning to
add additional vertices recursively?   Anyway...

The distinct ways to add one more vertex to a graph G correspond to the
orbits of the automorphism group of G on the power set P of V(G).  You can
compute the automorphisms of G with one call to nauty().  The difficult
issue is of how to compute representatives of the orbits on P.

There are two methods that I use for this.  The first one is used by geng.
As each generator of Aut(G) is found, convert it into its action on P.
Then accumulate the orbits of Aut(G) on P by the usual process one uses
to find the orbits of a permutation group given a set of generators.
There are procedures in geng.c that could be adapted for this.  The
disadvantage of this method is that you need two arrays of length 2^n
(one for the converted permutation and one for the orbits) so the space
requirements start to get serious when n gets over 25 or so.  A positive
aspect of this method is that very large groups take only a little
longer than very small groups.

The second method is to store the group generators using the procedures
in the file naugroup.c (see nautyex.c for an example showing how to call
them, but I have to plead guilty to not yet properly documenting them).
This gives you a way to repeatedly compute the whole group element
by element.  Then look at every element of P and reject it unless it
is minimal under the group.  That is, reject X if g(X)<X for some g
in Aut(G), where "<" is any convenient order (such as lexigographic).
The elements of P that are not rejected are orbit representatives.
This method takes little space but the efficiency depends on the group
size.  If the group is small it is fine.  There are heuristics which
can make it run faster on average.  For example, if the definition of
"<" and the order of scanning P are defined carefully, it can be that
the g such that g(X)<X also usually rejects many sets following after X.
So you first test the last automorphism that rejected something and only
then generate the full group.

So there are two methods but neither is fine in all circumstances.
Probably there is some more sophisticated way that uses group theoretic
methods, but I don't know it.   Maybe Gunnar knows.  Whatever method you
use, if you plan to extend a great many graphs make a special case in the
code for trivial groups as that is likely to be the most common situation.

Actually this would be excellent choice for a program to add to the
gtools suite and I'm already thinking about it.

Brendan.


* Falk Hueffner <falk.hueffner at student.uni-tuebingen.de> [031013 22:28]:
> Gunnar Brinkmann <gunnar at Mathematik.Uni-Bielefeld.DE> writes:
> 
> > > I need to generate from one graph the set of graphs containing one
> > > more vertex, with all possible connections to existing vertices. The
> > > obvious method is to generate all 2^n possibilities, generate the
> > > canonical form for each and filter duplicates. Is there a better way
> > > with the nauty library?
> > 
> > Yes -- MUCH MUCH better -- and there are lots of articles about it
> > in the literature.
> > 
> >   author = 	 {G. Brinkmann},
> >   title = 	 {Isomorphism Rejection in Structure Generation Programs},
> 
> Thanks for the reference. However, I was hoping there might be some
> functionality within nauty itself, or something I could adapt with
> little effort, since this is not really that central to my research
> and I wouldn't want to spend weeks on it...
> 
> -- 
> 	Falk
> 
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list




More information about the Nauty mailing list