[Nauty] Multigraphs..

[Sterten at aol.com]

>I have had some success with one of two approaches for  multigraphs
>
>(1) Subdivide each multiple  edge
>
>    - if there are few multiple  edges or they have low multiplicity, then 
>this will not cause the  size to blow out too much
>    - if you have "real"  vertices of degree 2 floating around, then you 
>will have to use  the lab/ptn facility to put all added vertices into a 
>single class  to avoid then getting mixed up with real vertices
 
I assume lab/ptn means coloring the vertices.
This method gives k new  vertex for each k-multi-edge.
You could also subdivide each edge, not only  multiedges.
Then you won't need to color the vertices, (I think)
 
 >OR
>
>(2) Assign one new vertex for each  different possible multiplicity, and 
>if an edge is joined by k  edges, join both its ends to the new vertex 
>representing  "k".
 
what means: "an edge is joined by k edges" ?
what, if e.g. v->w has 2  edges, but w->v has 3 edges ?
 
 >    - use lab/ptn to put each new vertex into its  own cell to stop them 
>getting permuted (eg swapping all  double-edges with triple-edges)
>    - if there are  few different multiplicities then this will cause only 
>a small  increase in graph size
 
I looked up "line-digraph" in the meantime and this should work too
if  we collaps the sinks and sources first.
We can add one new sink and source  connect it to all other
sinks and sources, disregard the multiplicities,  create the line-digraph
then color the vertices (=former edges) by their  multiplicity.
Then get the canonical form from Nauty...but then I don't  yet
know how to convert this into a canonical form of the  original
multi-graph.
 

Now, my "canonize" program will have to read a multigraph,
transform  it for Nauty, get the canonical form from Nauty and then
transform it back  into a multigraph, which then is
considered the canonical form of the  original multigraph.
 
 
 
 
 

BTW. what can we do instead of coloring ? My other programs don't  support
colored graphs data.
Also I want to create no new arcs  v->v.
 
I did:
connect each sink to a new sink S,
then connect S to a new  path Pk with k vertices for the k colors.
then connect to each of the n  original vertices from its corresponding
color-point,
then connect the  last color-point to a new sink T. G' has n+k+2 vertices.
 
To recover the colored graph G:
search the unique sink S, find its  unique in-neighbor and make it the
last color-point.
Go down as long as  you have indegree 1 and outdegree >1 for the other
color points. As soon  as you have outdegree 0 , remove that vertex.
For the remaining n vertices,  assign the color from the unique
colorpoint connected to that vertex.
Then  remove S and the k colorpoints.
 
 
 
BTW.2 : suppose I'd like to consider colored (di)graphs as
isomorphic,  when the colors are permuted. Can Nauty do that ?
 
 
 
Guenter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20040922/13fd1dbc/attachment.html