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

Brendan McKay bdm at cs.anu.edu.au
Mon Nov 27 17:53:45 EST 2006


Hi Michael,

I am certainly much too slow to release new versions of nauty, but
I decided to release version 2.4 in the next week or so.  We are
going to skip version 2.3 for general release.

The multigraph generator has specs as follows:

-----------------------------------------------------------------
Usage: multig [-q] [-u|-T|-G|-A|-B] [-e#|-e#:#] [-m#] [-f#] [infile [outfile]]

 Read undirected loop-free graphs and replace their edges with multiple
  edges in all possible ways (multiplicity at least 1).
  Isomorphic multigraphs derived from the same input are suppressed.
  If the input graphs are non-isomorphic then the output graphs are also.

    -e# | -e#:#  specify a value or range of the total number of edges
                 counting multiplicities
    -m# maximum edge multiplicity (minimum is 1)
        Either -e or -m with a finite maximum must be given
    -f#  Use the group that fixes the first # vertices setwise
    -T  use a simple text output format (nv ne {v1 v2 mult})
    -G  like -T but includes group size as third item (if less than 10^10)
          The group size does not include exchange of isolated vertices.
    -A  write as the upper triangle of an adjacency matrix, row by row,
        including the diagonal, and preceded by the number of vertices
    -B  write as an integer matrix preceded by the number of rows and
        number of columns, where -f determines the number of rows
    -u  no output, just count them
    -q  suppress auxiliary information
-----------------------------------------------------------------

There is also a new planarity tester, but the main new feature is
a sparse graph data structure.  I've been testing it up to about
50 million vertices.

However, there is no native processor for multigraphs.  Here I will
describe a method that is better than the one you mention if there
are many edges.

Let G be a multigraph - think of it as a simple directed graph with
positive integer multiplicities attached to each directed edge.
Loops are ok. Write undirected edges as two directed edges.

Let n = number of vertices
    k = positive integer such that 2^k > greatest multiplicity

Now make a simple graph H with k layers, L[0],...,L[k-1] where
each layer has n vertices.  So H has n*k vertices.  Each layer
is coloured with a unique vertex colour.

Say the vertices in layer L[i] are z[i,0..n-1].

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.

Now, suppose (v,w,M) is a directed edge of G from v to w
with multiplicity M.
Write M in binary: M = sum of m[j]*2^j over j=0..k-1.
Then for all j such that m[j]=1, add the edge z[j,v]->z[j,w] to H.
Do that for each directed edge of G.

Now, H is a perfect encoding of G.  Aut(G) is the restriction of
Aut(H) to layer L[0], and the restriction is faithful.  A canonical
labelling of G is obtained by labelling the vertices of G in the same
order that the vertices of layer L[0] appear in the canonical
labelling of H.  This will be lab[0..n-1] if you gave L[0] the
first colour.

For maximum multiplicity M, the new graph has O(n log M) vertices.
It is possible to improve this to O(n sqrt(log M)) vertices, which
is theoretically best possible, but that would only be advantageous
if M was very large.

Hope that is clearer than mud.  The new manual has an example with
a picture.

Cheers,
Brendan.


* Michael Kiermaier <Michael.Kiermaier at uni-bayreuth.de> [061124 09:39]:
> Hello!
> 
> I am interested in using nauty on undirected multigraphs. I know that I
> could transform such a graph into a simple graph, but the graph would
> get much bigger then (one more node for each multiedge).
> 
> In a mail of Brandan McKay of Sept. 2004 I found:
> 
> "The next version of nauty has a generator for undirected multigraphs.
> It is written and appears to work but needs further testing before
> release."
> 
> I would like to know what the status of the mentioned generator for
> undirected multigraphs is today. Is it already released? Or are you
> still working on it?
> 
> Also, I want to know what exactly is meant by this "generator". Does it
> mean that nauty natively supports undirected multigraphs then? Or does
> it mean something completely different?
> 
> Greetings and thanks in advance,
> 
> ~michael
> 
> 
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list




More information about the Nauty mailing list