GRAPE provides a basic interface to B.D. McKay's nauty (Version 2.2 final) package for calculating automorphism groups of (possibly vertex-coloured) graphs and for testing graph isomorphism (see Nau90). To use a function described in this chapter, which depends on nauty, GRAPE must be fully installed on a computer running UNIX (see Installing the GRAPE Package).
AutGroupGraph(
gamma )
AutGroupGraph(
gamma,
colourclasses )
The first version of this function returns the automorphism group of the
(directed) graph gamma, using nauty (this can also be accomplished
by typing AutomorphismGroup(
gamma)
). The automorphism group
Aut(gamma) of gamma is the group consisting of the permutations
of the vertices of gamma which preserve the edge-set of gamma.
In the second version, colourclasses is an ordered partition of the vertices of gamma (into colour-classes), and the subgroup of Aut(gamma) preserving this ordered partition is returned. The ordered partition should be given as a list of sets, although the last set in the list may be omitted. Note that we do not require that adjacent vertices be in different colour-classes.
gap> gamma := JohnsonGraph(4,2); rec( isGraph := true, order := 6, group := Group([ (1,4,6,3)(2,5), (2,4)(3,5) ]), schreierVector := [ -1, 2, 1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ], isSimple := true ) gap> Size(AutGroupGraph(gamma)); 48 gap> Size(AutGroupGraph(gamma,[[1,2,3],[4,5,6]])); 6 gap> Size(AutGroupGraph(gamma,[[1,6]])); 16
IsIsomorphicGraph(
gamma1,
gamma2 )
IsIsomorphicGraph(
gamma1,
gamma2,
firstunbindcanon )
This boolean function uses the nauty package to test whether graphs
gamma1 and gamma2 are isomorphic. The value true
is returned if
and only if the graphs are isomorphic (as directed, uncoloured
graphs).
The optional boolean parameter firstunbindcanon determines whether or
not the canonicalLabelling
components of both gamma1 and gamma2
are first unbound before testing isomorphism. If firstunbindcanon
is true
(the default, safe and possibly slower option) then these
components are first unbound. If firstunbindcanon is false
, then any
existing canonicalLabelling
components are used, which was the behaviour
in versions of GRAPE before 4.0. However, since canonical labellings
can depend on the version of nauty, the version of GRAPE, parameter
settings of nauty, and the compiler and computer used, you must be
sure that if firstunbindcanon=false
then the canonicalLabelling
component(s) which may already exist for gamma1 or gamma2 were created
in exactly the same environment in which you are presently computing.
See also GraphIsomorphism. For pairwise isomorphism testing of three or more graphs, see GraphIsomorphismClassRepresentatives.
gap> gamma := JohnsonGraph(7,4);; gap> delta := JohnsonGraph(7,3);; gap> IsIsomorphicGraph( gamma, delta ); true
GraphIsomorphismClassRepresentatives(
L )
GraphIsomorphismClassRepresentatives(
L,
firstunbindcanon )
Given a list L of graphs, this function uses nauty to return a list consisting of pairwise non-isomorphic elements of L, representing all the isomorphism classes of elements of L.
The optional boolean parameter firstunbindcanon determines whether
or not the canonicalLabelling
components of all elements of L
are first unbound before proceeding. If firstunbindcanon is true
(the default, safe and possibly slower option) then these components
are first unbound. If firstunbindcanon is false
, then any existing
canonicalLabelling
components of elements of L are used. However,
since canonical labellings can depend on the version of nauty, the
version of GRAPE, parameter settings of nauty, and the compiler
and computer used, you must be sure that if firstunbindcanon=false
then the canonicalLabelling
component(s) which may already exist for
elements of L were created in exactly the same environment in which
you are presently computing.
gap> A:=JohnsonGraph(5,2); rec( isGraph := true, order := 10, group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]), schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], isSimple := true ) gap> B:=JohnsonGraph(5,3); rec( isGraph := true, order := 10, group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]), schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ], representatives := [ 1 ], names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ], [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ], isSimple := true ) gap> R:=GraphIsomorphismClassRepresentatives([A,B,ComplementGraph(A)]);; gap> Length(R); 2 gap> List(R,VertexDegrees); [ [ 6 ], [ 3 ] ]
GraphIsomorphism(
gamma1,
gamma2 )
GraphIsomorphism(
gamma1,
gamma2,
firstunbindcanon )
If graphs gamma1 and gamma2 are isomorphic, then this function
uses nauty to return an isomorphism from gamma1 to gamma2. This
isomorphism will be a permutation of [1..
gamma1.order]
which maps
the edge-set of gamma1 to that of gamma2. If gamma1 and gamma2
are not isomorphic then this function returns fail
.
The optional boolean parameter firstunbindcanon determines whether or
not the canonicalLabelling
components of both gamma1 and gamma2
are first unbound before proceeding. If firstunbindcanon is true
(the default, safe and possibly slower option) then these components
are first unbound. If firstunbindcanon is false
, then any existing
canonicalLabelling
components are used. However, since canonical
labellings can depend on the version of nauty, the version of
GRAPE, parameter settings of nauty, and the compiler and computer
used, you must be sure that if firstunbindcanon=false
then the
canonicalLabelling
component(s) which may already exist for gamma1
or gamma2 were created in exactly the same environment in which you
are presently computing.
See also IsIsomorphicGraph.
gap> A:=JohnsonGraph(5,2); rec( isGraph := true, order := 10, group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]), schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], isSimple := true ) gap> B:=JohnsonGraph(5,3); rec( isGraph := true, order := 10, group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]), schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ], representatives := [ 1 ], names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ], [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ], isSimple := true ) gap> GraphIsomorphism(A,B); (3,4,7,8,6,5) gap> GraphIsomorphism(A,ComplementGraph(A)); fail
[Up] [Previous] [Next] [Index]
grape manual