[Nauty] Multigraphs..
Sterten at aol.com
Sterten at aol.com
Wed Sep 22 16:40:01 EST 2004
>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
More information about the Nauty
mailing list