[Nauty-list] Re: Problem with graph isomorphism detection using Nauty
Brendan McKay
bdm at cs.anu.edu.au
Sun Feb 12 19:13:15 EST 2006
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!
More information about the Nauty
mailing list