[Nauty] Multigraphs..
Gordon Royle
gordon at csse.uwa.edu.au
Wed Sep 22 14:13:02 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
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
More information about the Nauty
mailing list