[Nauty] lexicografic ordered canonical form
Brendan McKay
bdm at cs.anu.edu.au
Wed Aug 6 19:19:01 EST 2003
* 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.
More information about the Nauty
mailing list