[Nauty-list] graph isomorphism
Brendan McKay
bdm at cs.anu.edu.au
Wed Jan 21 00:01:14 EST 2009
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
More information about the Nauty
mailing list