[Nauty] Isomorphism with coloured multigraphs

[Brendan McKay]

This is correct.  Also, if one of the edge multiplicities is more common
than the others, it can remain an ordinary edge and not be turned into
a node.  This can make the resulting graph somewhat smaller.

Brendan.

* Chris Jefferson <caj at cs.york.ac.uk> [040429 19:00]:
> Parker Jones wrote:
> 
> >Chris,
> >
> >>> I'd like to check for isomorphism between coloured multigraphs.
> >>> Reading through previous posts I understand that multiple edges are
> >>> denoted by colouring/partitioning - implying it's not possible to have
> >>> colouring and multi-edges at the same time. Is this really the case?
> >>>
> >>Nope, I've done directed coloured multigraphs :)
> >>
> >>The "trick" is to have lots of colours in the generated graphs. Use some
> >>for the nodes, some for the multiple edges and (in my case) some for the
> >>directions. Assuming you make each of these sets distinct the everything
> >>should be fine :)
> >
> >
> >Thanks for the quick reply and the good news.  I'm trying to 
> >understand your approach but don't quite get it.
> >
> >Given a simple multigraph, say
> >a - b = c     with colouring red = {a} and blue = {b,c}
> >
> >I'd represent this as:
> >0: 1;
> >1: 2.
> >
> >Now suppose we define four 'colours' as follows:
> > 1 arc    red
> > 2 arcs   red
> > 1 arc    blue
> > 2 arcs   blue
> >
> >Now how can we represent the colouring and the numbers of edges?
> >
> >f=[...] ?
> >
> The way I would represent this would be as follows:
> 
> Let us  label a node 0, b node 1 and c node 2 as you've already done. 
> The way I tackle multi or coloured edges is to also replace each 
> "complex" edge with a node as follows:
> Make a new node for each arc, so call a-b node 3 and b-c node 4
> 
> Then we end up with the graph 0 - 3 - 1 - 4 - 2
> 
> Then we label the colours as:
> colour 1: red node
> colour 2: blue node
> colour 3: 1 arc edge
> colour 4: 2 arc edge
> 
> so split the nodes as f={0},{3},{4},{1,2} (thats not quite the correct 
> notation, but I'm sure you know what I mean)
> 
> Chris
> 
> 
> 
> >Alternatively, if you could post one of your directed multigraphs that 
> >would be great.
> >
> >Thanks,
> >
> >P.J.
> >
> >_________________________________________________________________
> >Surf the net and talk on the phone with Xtra JetStream @  
> >http://xtra.co.nz/jetstream
> >
> >
> >_______________________________________________
> >This is the nauty mailing list
> >Post messages to nauty-list at cs.anu.edu.au
> >nauty page: http://cs.anu.edu.au/~bdm/nauty/
> >list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list
> 
> 
> 
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list