[Nauty] Isomorphism with coloured multigraphs

[Chris Jefferson]

Sterten at aol.com wrote:

>  
> wouldn't it be better, if Nauty would perform these conversions by itself
> and thus output a canonical member of any n*n integer matrix 
> (=multigraph) ?
>  
> also as a variation if graphs and their complements are considered 
> isomorphic
> or any permutation of the edge-counts in multigraphs.
>  
> also, groupisomorphism etc. would be just a special case and could be 
> handled
> by Nauty easily.
>  
> also, coloring the vertices is not necessary IMO, you could just
> add a new vertex for each color connect it with all vertices of that 
> color.
> To distinguish colors e.g. add a chain of that length to the color-vertex
> Not that the color-feature should be removed, but considered a special 
> feature
> and not be the default.
>  


I've done some very brief experiments with this kind of thing and I 
imagine there are other people much better informed than I am, but this 
representation of coloured graphs could make find the symmetries take 
much longer (it is always better to give more information about the 
strucutre of the graph as possible) and also you have to be very careful 
to make sure that any special structures you construct don't appear in 
the normal graph. I have spent some time converting some reasonably 
complex objects (constriant satisfaction problems) into graphs to find 
their symmetries. At first I tried to be clever and minimise my useage 
of colour until I discovered a) it makes things go slower and b) it 
would sometimes find incorrect isomorphisms.

Chris

>  
> Guenter.