[Nauty] Can we do colored edges in nauty?

[Sterten at aol.com]

>Hello,
>
>I am very new to nauty. I have  a research that needs to use graph
>isomorphism.  However, the  problem I am working on directed multigraph
>with labeled (colored)  edges.
>
>Does nauty handle this or are there any way to  do such thing without
>adding more colored vertices to the graph  (that slows nauty, right?)?
>
>BTW, I browsed many old  messages, but couldn't find an example of how to
>define to color of  vertex.  Any hint would be great.  Thank  you.
>
>-Wutnipong
 
you can always convert the problem to a standard problem
by constructing  a new graph with more vertices but less structure
which has the same  automorphismgroup.
 
When the edges are colored with k colors then e.g. you can make
k graphs  with noncolored edges just by removing all edges with color
not equal to x  for x=1..k. 
This gives a new (directed multi-) graph with k*n  vertices
and no edges between the k components.
Then add n new vertices  and connect them to the k corresponding
vertices to identify these.
Be a  bit careful if these new vertices could be mapped
to other vertices by an  automorphism, if necessary you
have to add a further structure to  distinguish.
 
When you have a multigraph, you can treat it as a graph with
colored  edges.
A digraph can be viewed as a graph with tricolored edges.
A  vertex-colored graph can be viewed as a (uncolored) graph with
some  additional color-vertices joined to all vertices with
that color.
don't  nail me on the details, but you see the idea.
 
So, when you want to calculate the automorphismgroup,
it's sufficiant to  restrict to simple undirected uncolored
graphs. Just do some preprocessing to  convert the graph.
Hopefully a future version of Nauty can do all  that
preprocessing by itself...
 

Guenter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20050312/4dded821/attachment.html