[Nauty-list] Re: Problem with graph isomorphism detection using Nauty

[Brendan McKay]

Hello Srilatha.   The only thing I would change in your procedure
is to distinguish between a label on an edge and a label on a vertex.
In your example, you put the edge labelled B into the same cell of
the partition as the vertices labelled B.  It would be better to
put the B vertices in one cell and the B edges in another cell.

If it still doesn't seem to work, please write again.

Brendan.


* srilatha inavolu <i_srilatha at yahoo.com> [060212 15:50]:
> Hi,
>    
>      I am working on a project that involves graph isomorphism. I am using nauty to generate the canonical forms and am comparing them to find out the isomorphism between the graphs.
>     I am dealing with labeled graphs i.e, the vertices and the edges have labels. Since Nauty doesn't consider edge labels, I am converting every edge into a vertex and giving the label of the edge to the vertex. Now, I am giving the initial partition to Nauty. I am partitioning the vertices into cells depending on their labels i.e, all vertices with the same label go into one cell. And I am dealing with both directed and undirected graphs. So for directed graphs, I am setting the option digraph to TRUE.
>     In order to say if two graphs are isomorphic, I first compare their canonical forms, if they match, then I compare the label array of the two graphs which is a sorted array of the labels of the vertices, only if they too match, I consider that the two graphs are isomorphic.
>     I am getting correct output for some of the graphs but for others, I am having problem. I want to know if my approach is correct(valid) for all types of graphs including multigraphs.
>     I will appreciate if you can tell me if there is something wrong with my procedure and suggest me the right approach.
>    
>   An example is attached. Please look at the example. 
>    
>   Thank you,
>     Srilatha.
> 
> 		
> ---------------------------------
> Relax. Yahoo! Mail virus scanning helps detect nasty viruses!