[Nauty-list] status of generator for undirected multigraphs?

[Brendan McKay]

* Michael Kiermaier <michael.kiermaier at uni-bayreuth.de> [061128 00:26]:
> 
> Could you give me a hint where I can find more about the O(n sqrt(log
> M))-transformation you mentioned?

First a correction.  I wrote:

> First connect the layes together with edges
>    z[i,0]--z[i,1]--z[i,2]--z[i,k-1]  for each i;  n*(k-1) edges total.
> Alternatively, make {z[i,0],z[i,1],z[i,2],z[i,k-1]} a clique; use
> whichever seems to work faster for your application.

I should have written z[0,j]--z[1,j]--...--z[k-1,j] for each j
(path method), or clique {z[0,j],z[1,j],...,z[k-1,j]} (clique
method).  Add another possibility:  edges z[0,j]--z[i,j] for
i > 0 and all j (star method).

For the O(n sqrt(log M)) construction, choose k such that
2^((k-1)^2) > max_multiplicity.

First join the layers using either the clique method or the
star method (the path method won't work).

Identify the pairs (x,y) for 1 <= x,y <= k-1 with the numbers
0..(k-1)^2-1 in any convenient way.

Now for an edge (v,w) of multiplicity M, write M in binary
  M = sum of m[j]*2^j over j=0..(k-1)^2-1.
For each j such that m[j]=1, put in the edge z[x,v]->z[y,w]
where (x,y) is the pair associated with the number j.

That's it.  Note that x=0 and y=0 are forbidden.  This rule can
be relaxed slightly, but care is needed.  It is important that
for any vertex z[0,j], the vertices z[1,j],...,z[k-1,j] are
combinatorially determined, which is not always true if x=0
and y=0 are allowed without restriction.

As I gave it, the result has directed edges even if the original
graph does not.  If you don't like that, assign (x,y) and (y,x) to
the same number, which might require increasing k.

Brendan.