[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