[Nauty] Multigraphs

[Brendan McKay]

* Stephan Winkler <stephan.winkler at yale.edu> [040205 07:53]:
> 
> Is there a possibility to compute canonical labellings for multigraphs 
> (graphs with multiple edges between pairs of vertices) using nauty? If 
> this cannot be done directly, as suggested by the documentation, are 
> there ways to encode multigraphs appropriately by [coloured] simple 
> graphs, which may then be analyzed using nauty?
> 
> 
> For example, if there are n > 1 edges between two vertices x and y, we 
> could model this by a single edge annotated by n. Can we represent 
> this in nauty by introducing a new vertex between x and y and 
> assigning it colour n?

As Falk said in his reply, yes this is a valid method.

In case most edges have multiplicity 1, you could save space by
not using a new vertex for those edges.

There are also other ways to encode multigraphs as vertex-coloured
simple graphs that can take less space if there are many edges.
 
> Will future versions of nauty handle multigraphs? Are there any other 
> software packages available that efficiently compute canonical 
> labellings for multigraphs? Any help is greatly appreciated,

There are two versions at the prototype stage.  One handles graphs
or digraphs with coloured edges.  It uses a sparse data structure
so it will also improve handling for very large sparse simple graphs.
Another prototype is for arbitrary matrices with isomorphism
defined by arbitrary row and column permutations.  That could be
used for multigraphs too.

Brendan.