[Nauty] vcolg output format

[J.K.R. Bausch]

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