[Nauty] Canonical representations for annotated graphs

Brendan McKay bdm at cs.anu.edu.au
Wed Mar 19 13:36:01 EST 2003


* Falk Hueffner <falk.hueffner at student.uni-tuebingen.de> [030319 05:41]:
> Hi,
> 
> I have an algorithm that includes a search tree over annotated
> graphs. To recognize graphs already encountered, I want to convert
> them to a canonical form so I can look them up in a hash table.
> 
> In particular, I have
> 
> * graphs with 1 or 2 extra bits per vertex,
> * graphs with 1 or 2 extra bits per edge.
> 
> 1 extra bit per vertex can easily be modeled with a self loop. Is
> there any possibility for the other options? The graphs are rather
> small, < 32 nodes.

For annotations on the vertices, use vertex colours.  Just make
a colour for each possible value of the annotation.

The distributed version of nauty can't handle edge annotations
directly, but there are several ways to fudge it.  One way is
to subdivide edges with a new vertex and colour that new vertex
according to the edge annotation.

Brendan.




More information about the Nauty mailing list