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

Michael Kiermaier michael.kiermaier at uni-bayreuth.de
Tue Nov 28 00:19:52 EST 2006


Hello Brandan,

many thanks for your answer.

I look forward to your new version of nauty.


I already guessed that the multigraph-generator is not what I am looking for.

The graph transformation for graphs with multiedges you describe is very
interesting, I didn't think about this possibility.
Depending on the exact problem one can choose either this transformation
or the tranformation of introducing a new node for each multiedge.

Could you give me a hint where I can find more about the O(n sqrt(log
M))-transformation you mentioned?

Thanks,

~michael


Am Mo, 27.11.2006, 07:53, schrieb Brendan McKay:
>

> 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