[Nauty] How to apply automorphisms?
Brendan McKay
bdm at cs.anu.edu.au
Thu Jul 29 13:16:01 EST 2004
Hi, I'm not sure exactly what you are asking.
Suppose we have graphs G and H. By applying nauty to each of
G and H we can find an isomorphism phi from G to H. We can also
find the orbits of Aut(G) and Aut(H) - these are given by the
parameter orbits[]. Then there is an isomorphism from G to H
that maps g in G onto h in H iff phi(g) lies in the same orbit
of Aut(H) as h lies in.
This means it is very efficient to ask this question for many g and h
once nauty has been called separately for G and H. In case you only
want to ask this question for a single g in G and h in H, you can
use the method that Guenter suggested. Call nauty for G with an
initial colouring (partition) [ g | everything else] and call nauty
for H with initial colouring (partition) [ h | everything else].
Then there is an isomorphism mapping g onto h iff the canonical
graphs are the same.
Brendan.
* Aisha Fenton <aishafenton at mac.com> [040728 21:01]:
> Hi,
> I'm currently using nauty to test a pair of graphs for an isomorphism.
> However, now I have a requirement that once nauty has found a canonic
> labeling for two isomorphic graphs (G, H) I want to test if vertices v
> in V(G) are ever mapped to y in V(H) under some automorphism.
>
> That is, I have vertex boundary defined on each G and H. Once I have
> found that G and H are isomorphic, I want to see if the boundary on G
> is mappable to H (for some automorphism)
>
> From the documentation the only way I could see was to parse the
> automorphism output file, and then try each cycle - since I'm dealing
> with hundreds of thousands of graphs, this method seemed like it
> wouldn't be fast enough for me.
>
> Also a newbie question. I'm not that versed in group theory, so I'd
> really appreciate it if someone could give me a quick run down of how
> I'm to interrupt the output automorphisms (I only need to know if
> vertex x ever maps to vertex y). From my very basic group theory
> knowledge, I was expecting the examples in the documentation of the
> output automorphisms, to contain something like a rotation cycle
> (01,2,3,4,5,6), but they don't?
>
>
> Thanks heaps,
> Aisha
>
>
>
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list
More information about the Nauty
mailing list