[Nauty] vcolg output format

Sun Apr 7 11:32:39 AEST 2019

Hi Johannes,

vcolg can process a file of graphs, so the edges are needed to 
distinguish outputs from different inputs.  For each input graph, the 
edges written out will be the same as the edges read in.

If you only want to process one graph at a time, you can suppress 
writing of the edges by removing the two nested 'for' loops near the end 
of procedure trythisone().

I've added to my wish-list output that just has the number of the 
corresponding input graph rather than the full edge list.

The program has enough information to determine the multiplicity of a 
given colouring, but it is quite complicated.  The problem is that I 
don't use the full automorphism group of the graph, but only some subgroups.

Brendan.

On 6/4/19 10:00 pm, J.K.R. Bausch wrote:
> Hi Brendan,
>
> thanks a lot for your help with this so far, it's much appreciated!
>
> Coming back to vcolg: why is the edge list printed? Is it possible 
> that vcolg potentially swaps the vertex order for different colorings, 
> or will the edges for a given graph that are printed always be 
> identical for all given colorings? Or is there another reason that the 
> edge list would be necessary?
>
> And, is there a simple way to obtain the multiplicity of a given 
> coloring while enumerating them (i.e. its orbit size)? I can of course 
> take the coloring and plug that back into a nauty call. (I don't mind 
> modifying vcolg.c for that purpose).
>
> Thanks so much!
> Best,
> Johannes
>
>
>
> On 2019-01-29 03:35, Brendan McKay wrote:
>> Hi Johannes,
>>
>> I'll assume that you are referring to colourings of vertices that are
>> not necessarily
>> "proper".
>>
>> The automorphism group that preserves the colours is computed by nauty
>> and Traces.
>> Just place the colouring in the arrays lab & ptn and set
>> options.defaultptn=FALSE.
>> Chapter 6 of the manual describes it.
>>
>> For (2), this is what the program vcolg does.  Run "vcolg --help" to
>> see the options.
>> The switch -u says to just count, which is recommended first since 
>> the number of
>> distinct colourings can be vast.  (Or use the estimate (#colours)^n /
>> |Aut(G)|, which
>> is usually pretty accurate.)
>>
>> To see the colourings, use -T in place of -u.  Here are the last few
>> of the list of
>> 22913 distinct colourings of the cycle C_12 with colours 0,1,2 (vcolg 
>> -m3T):
>>
>> 12 12 2 2 2 2 2 2 2 2 2 2 0 0  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
>> 9 9 10 10 11
>> 12 12 2 2 2 2 2 2 2 2 2 2 1 0  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
>> 9 9 10 10 11
>> 12 12 2 2 2 2 2 2 2 2 2 2 1 1  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
>> 9 9 10 10 11
>> 12 12 2 2 2 2 2 2 2 2 2 2 2 0  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
>> 9 9 10 10 11
>> 12 12 2 2 2 2 2 2 2 2 2 2 2 1  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
>> 9 9 10 10 11
>> 12 12 2 2 2 2 2 2 2 2 2 2 2 2  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
>> 9 9 10 10 11
>>
>>
>> First the number of vertices and the number of edges.  Then the 
>> colours, one per
>> vertex, then the edges of the graph.
>>
>> There is no program-callable version of vcolg, though a custom output 
>> function
>> can be compiled into it.
>>
>> To make a canonical labelling of a vertex-coloured graph, define the 
>> colouring
>> as above, also set options.getcanon=TRUE and go.  However, to uniquely
>> represent the isomorphism class of a coloured graph you need to keep the
>> sizes of the colour classes as a list in the order you put them into 
>> lab&ptn
>> in addition to the canonically labelled graph.
>>
>> Brendan.
>>
>> On 27/1/19 8:31 am, J.K.R. Bausch wrote:
>> Dear all,
>>
>> I have the following question, and I'm curious whether nauty/traces 
>> can do this.
>> I'm given a graph G with a large automorphism group Aut(G).
>>
>> 1. Given a coloring c for this graph, compute the _size_ of its orbit
>> under Aut(G).
>> 2. Given a number of colors, compute all possible colorings of G, 
>> modulo Aut(G).
>>
>> Context:
>> 1. I can obviously compute all elements of the orbit myself, but that
>> would be expensive.
>> What I want is to essentially compute |Aut(G)| /
>> |StabilizerGroup(Aut(G), c)|, which should be much faster and consume
>> less memory.
>> I know how to do this in e.g. Gap, or Mathematica, but it would be
>> faster for my purposes if I could compute it without leaving C++ - so
>> is this possible with nauty/traces?
>>
>> 2. To specify what exactly I mean: I want _one_ representative per
>> disjoint orbit of all possible colorings of G.
>> Again there exists an algorithm for doing this for any permutation
>> group, see e.g.
>> https://arxiv.org/abs/1211.6261
>> Can nauty/traces generate such a list of colorings directly?
>>
>> Last but not least, I would be keen to know how performant it is to
>> compute the canonical image for a _lot_ of colorings of a particular
>> graph G.
>> Currently I simply iterate over said list and call nauty individually.
>> Does nauty somehow cache its calculation of the automorphism group? Or
>> is there a specific way to call it for this purpose?
>>
>> Thank you so much for your help!
>> Best,
>> Johannes
>>
>> PS: I asked a variant of this question on stackexchange, where I was
>> pointed to this list:
>> ://mathoverflow.net/questions/321739/nauty-traces-orbit-sizes-for-colored-graph 
>>
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au<mailto:Nauty at anu.edu.au>
>> http://mailman.anu.edu.au/mailman/listinfo/nauty
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> http://mailman.anu.edu.au/mailman/listinfo/nauty
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty