[Nauty-list] graph isomorphism

[Brendan McKay]

I'll add the following to Gordon's reply:

> If the canonical labelling is the same then the graphs are isomorphic

-- provided the graphs have the same number of vertices of each colour.
You need to check that yourself.

Also, for things like DAGs, I recommend the invariant "adjacencies".
This will make the worse cases much less severe.

Brendan.


* Gordon Royle <gordon at maths.uwa.edu.au> [090120 15:27]:
> 
> On 20/01/2009, at 7:35 AM, Abid Muslim Malik wrote:
> 
> > Dear all;
> >
> > I am using the Nauty to find graph isomorphism in a problem. In the  
> > problem each node is colored. Now my questions are:
> >
> > 1) How can I insert/jeep record of each node in the graph. You have  
> > "ADDELEMENT(s,i)" function,  which adds  element i  to set s etc.  
> > But, I could not find a function which keeps a record of a  
> > particular characteristic of a given node; e.g. color. May be I am  
> > missing here. ( I am dealing with Directed Acyclic Graphs (DAGs) in  
> > compiler where each node is an instruction,  which can be store/ 
> > load, branch, floating point, fixed point instruction. I need to  
> > compare this information as well to check the isomorphism).
> 
> You need to keep track of any auxiliary information, such as vertex  
> colours, yourself...
> 
> If you want nauty to only permute vertices within colour classes then  
> you use the arrays "lab" and "ptn" to define an initial partition on  
> the vertex set.
> 
> For example, if vertices 0, 4 and 5 are "green", vertices 1 and 3 are  
> "red" and vertex 2 is "blue" then you would make sure that "lab"  
> contains
> 
> 0 4 5 1 3 2
> 
> and "ptn" contains markers to show where each colour class ends...
> 
> 1 1 0 1 0 0
> 
> Then nauty will only consider permutations that permute vertices  
> WITHIN each colour class..
> 
> >
> 
> > 2) In order to check two graphs, you have to produce canonical  
> > labelling of each graph. If they are same then they are identical.  
> > right???
> 
> If the canonical labelling is the same then the graphs are isomorphic
> 
> 
> A/Prof Gordon Royle
> gordon at maths.uwa.edu.au
> School of Mathematics & Statistics
> University of Western Australia
> 
> 
> 
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list