[Nauty-list] graph isomorphism

[Abid Muslim Malik]

Gordon, Brendan.... Thank you very much for your comments and guidance.

Regards

On Tue, Jan 20, 2009 at 8:01 AM, Brendan McKay <bdm at cs.anu.edu.au> wrote:

> 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
>



-- 
Abid M. Malik
******************************************************
"I have learned silence from the talkative, toleration from the intolerant,
and kindness from the unkind"---Gibran

"If you do not think about the future, then you can not have the one!"---
Galsworthy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20090120/ff9ee18e/attachment.html