[Nauty] Multigraphs..

[Brendan McKay]

* Gordon Royle <gordon at csse.uwa.edu.au> [040922 14:22]:
> 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

If there are high multiplicies, use just one subdivided edge, with
the new vertex coloured by the multiplicity.  Also, if one of the
multiplicities (typically 1) is common, edges of that multiplicity
can be left unsubdivided.

> 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".
> 
> 	- 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 don't see how that works.  Suppose you have a complete graph with
a perfect matching of edges with multiplicity 2.  Then it seems your
modified graph is a complete graph joined to 2 new vertices, which
has lost the structure of the matching.

Brendan.