[Nauty] lexicografic ordered canonical form

[Brendan McKay]

* Joost Winne <Joost.Winne at UGent.be> [030807 16:24]:
> 
> 
> >    for each row i+1 compatible with D[i]
> >       form D[i+1]
> >       apply nauty to find the orbits of points
> >           and a canonical order of the points
> >       reject D[i+1] if point i+1 is not in the same orbit
> >           as the point which is last in the canonical order
> 
> This would mean (after calling nauty for D[i+1]) compare orbits[i+1] with
> orbits[lab[i+1]] (with getcanon true) ?

Actually orbits[i] and orbits[lab[i]].
 
Lets say that I(D) is the set of all designs isomorphic to design D.

The basic explanation: you want to make each isomorphism type I(D[i+1])
exactly once, by adding a row to some D[i].  Because we are thinking
about isomorphism types and not labelled designs, the rows are not in a
special order.  So I(D[i+1]) could in fact be made from i+1 different
smaller designs (though some of them may be the same due to rows of
D[i+1] being equivalent).  The main step in isomorph rejection is to
choose which I(D[i]) you want to make I(D[i+1]) from and reject it if
you make it in any other way.  The algorithm above says that D[i+1] must
be made from D[i+1]-row[j], where j is the row that nauty labels last
(i.e. j = lab[i].  The use of nauty ensures that if you meet another
design D isomorphic to D[i+1] then the smaller design you want to make
D from is isomorphic to the smaller design you want to make D[i+1] from.

So when you make D[i+1] you reject it if the row you just added is not
row j, or, more correctly, if the row you just added is not equivalent
to row j.

This eliminates the possibility that members of the same I(D[i+1])
are made (and accepted) from more than one D[i].  This leaves only the
possibility that several different members of I(D[i+1]) are made and
accepted from the same D[i].  It is not hard to see that this can only
happen due to automorphisms of D[i].

Cheers,
Brendan.