[Nauty-list] vertex-invariants

[Brendan McKay]

Hi Fatih,

Thanks for your interesting mail.

* Mr Fatih Demirkale <fatih.demirkale at uqconnect.edu.au> [120823 16:11]:
>
> I realized that the input minsize is not used in getbigcells
> function. Is line 439 in nautinv.c suppose to be
> "if (cell2 >= cell1 + minsize) "?

Actually it is supposed to be
   if (cell2 >= cell1 + minsize - 1)

The good news is that the error does not invalidate the correctness
of any of the invariants. Fixing the error makes some of the
invariants slightly faster, and changes the values of invariants
celltrips and cellquins very slightly. Invariant refinvar (only in
nauty 2.5) changes value significantly.

Many thanks for finding this error.

> I wonder what is the motivation for using XOR ^ operator in
> celltrips (similarly in cellquads and cellquins). I know this is
> done to get "the number of vertices adjacent to an odd number of
> {v, v1, v2}". Is this done specifically for the bipartite graphs
> derived from block designs? As far I understand, it is wanted
> that the vertices are assigned with different codes as much as
> possible, and wt = FUZZ1(pc); gets different values if pc +=
> POPCOUNT(sw); gets different values mod 4. Is this correct?

This invariant was inspired by the "profile" used for distinguishing
the rows and columns of Hadamard matrices. The "odd" originates from
the fact that a product of some +1s and -1s depends on the parity of
the number of -1s.

However, if you want to work on actual Hadamard matrices, it is a
lot more efficient to compute the profile from the matrices
before they are converted to graphs.

> Lastly, could you please explain why the values in "fuzz1[] =
> {037541,061532,005257,026416};" are used?

In many places I want to compute a hash value that depends on a
set of integers {x[1],...,x[k]}. The elements of the set arrive in
an unpredictable order and there might be very many of them, but
the value of the hash function must be independent of the order.
Moreover, it must distinguish between different sets quite often.

An example hash function would be f([x]) = x[1] + ... + x[k], but in
practice it would very often have the same value for different sets.
A better version that I used for a while is
   f([x]) = (x[1]^c) + ... + (x[k]^c)
where c is some constant, but that failed to distinguish different
sets too often too.  So I introduced the idea of using a different
c according to the value of x[i] mod 4, and that worked much better.
I just made up the four constants (the values in fuzz1[]).  It's a
long time since I experimented with alternatives so it could be
that there is something better.

Cheers, Brendan.

> Many thanks,
>
> Fatih

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list