[Nauty] Isomorphism with coloured multigraphs

Chris Jefferson caj at cs.york.ac.uk
Thu Apr 29 18:51:01 EST 2004


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






More information about the Nauty mailing list