[Nauty] lexicografic ordered canonical form

[Brendan McKay]

* Joost Winne <Joost.Winne at UGent.be> [030806 18:44]:
> 
> I am generating BIBD's ( 2-(v,k,l) ) designs in an orderly row by row way.
> When I reach a partially filled design upto a certain row:
> I convert the (partial filled upto a certain row) design into a bipartite
> graph and then call nauty to get the canonical form (and also the autom. group which
> I use for partial isomorphic rejection).
> I store this canonical form (in some kind of hash table) and this way I
> can see if I already saw this canonical form before.
> 
> Is there some kind of standard memory efficient design storage format
> (like graph6) any one knows about ?

I have an old format that is only good for small designs.  I didn't
advertise it because it needs improvement.  I'll send you the specs
off-line.

Going back to the designs, if you just want a particular family of small
designs there is a chance that I have them already, or maybe Gordon or
Staszek or someone else in this list has them.

I'm not sure what a "row" is in your description as some people use the
transposed incidence matrix.  I'll assume there is a row for each point
and a column for each block.  Thus, at each stage you have a partial
design D[i] formed by i rows.  You want to extend this to all possible
D[i+1] by adding one more point i+1.

So do this:

   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
   endfor

At the first stage "for each row i+1", if you only choose rows
inequivalent under the automorphisms of D[i], then the D[i+1]s
accepted by the algorithm are all nonisomorphic and you don't
need your hash table.  If you don't use the automorphisms of
D[i] completely, some isomorphs can occur but the theory says
they only occur as children of the same D[i]; so in that case
your hash table only needs to be big enough to hold the
descendants of one D[i] and you can clear it between each D[i].

In applying nauty you can use some combinatorial invariant that
partitions the rows to speed it up.  Then you only need to
consider extensions D[i+1] if point i+1 has the greatest value
of the invariant, which you can check before calling nauty.

Using the bipartite graph is not wonderfully efficient; there is
an extension to nauty in preparation that allows you to process
the design directly.

Brendan.