GRAPE includes B. D. McKay's nauty (Version 2.8.6) package for calculating automorphism groups of graphs and for testing graph isomorphism (see MP14). As described in Section Installing the GRAPE Package, a user may instead use their own copy of nauty/dreadnaut, or may use T. Juntilla's and P. Kaski's bliss package JK07 instead of nauty. Many functions described in this chapter make use of nauty or bliss.
For each of the functions described in this chapter, each graph parameter
may be replaced by a graph with colour-classes, which is a record having
(at least) the components graph (which should be a graph in GRAPE
format), and colourClasses, which should be an ordered partition of the
vertices of the graph, and so define colour-classes for the vertices.
This ordered partition should be given as a list of (pairwise-disjoint
non-empty) sets partitioning the vertex-set. When these functions are
called with graphs with colour-classes, then it is understood that an
automorphism of a graph with colour-classes is an automorphism of the
graph which additionally preserves the list of colour-classes (classwise),
and an isomorphism from one graph with colour-classes to a second is a
graph isomorphism from the first graph to the second which additionally
maps the first list of colour-classes to the second (classwise). The
record for a graph with colour-classes may also optionally contain the
additional components autGroup and/or canonicalLabelling, and these
are handled in an analogous way to those for a graph (such as when using
the parameter firstunbindcanon). Note that we do not require that
adjacent vertices be in different colour-classes.
AutGroupGraph( gamma )
AutGroupGraph( gamma, colourclasses )
The first version of this function returns the automorphism group of
the graph (or graph with colour-classes) gamma, using nauty
or bliss (this can also be accomplished by typing
AutomorphismGroup(gamma)). The automorphism group Aut(gamma)
of a graph gamma is the group consisting of the permutations
of the vertices of gamma which preserve the edge-set of gamma.
The automorphism group of a graph with colour-classes is the subgroup
of the automorphism group of the graph which preserves the colour-classes
(classwise).
The second version of this function is maintained only for backward compatibility. For this version gamma must be a graph, colourclasses is an ordered partition of the vertices of gamma, and the subgroup of Aut(gamma) preserving this ordered partition is returned. The ordered partition should be given as a list of (pairwise-disjoint non-empty) sets partitioning the vertices of gamma, although for backward compatibility and only in this situation, the last set in the ordered partition need not be included explicitly.
gap> gamma := JohnsonGraph(4,2); rec( adjacencies := [ [ 2, 3, 4, 5 ] ], group := Group([ (1,4,6,3)(2,5), (2,4)(3,5) ]), isGraph := true, isSimple := true, names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ], order := 6, representatives := [ 1 ], schreierVector := [ -1, 2, 1, 1, 1, 1 ] ) gap> Size(AutGroupGraph(gamma)); 48 gap> AutGroupGraph( rec(graph:=gamma,colourClasses:=[[1,2,3],[4,5,6]]) ); Group([ (2,3)(4,5), (1,2)(5,6) ]) gap> Size(AutomorphismGroup( rec(graph:=gamma,colourClasses:=[[1,6],[2,3,4,5]]) )); 16
GraphIsomorphism( gamma1, gamma2 )
GraphIsomorphism( gamma1, gamma2, firstunbindcanon )
Let gamma1 and gamma2 both be graphs or both be graphs with
colour-classes. Then this function makes use of nauty or bliss to
(try to) determine an isomorphism from gamma1 to gamma2. If gamma1
and gamma2 are isomorphic, then this function returns an isomorphism
from gamma1 to gamma2. This isomorphism will be a permutation of the
vertices of gamma1 which maps the edge-set of gamma1 onto that of
gamma2, and if gamma1 and gamma2 are graphs with colour-classes,
this isomorphism will also map the colour-class list of gamma1 to that
of gamma2 (classwise). 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 much 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 whether nauty or bliss is used, the version
of nauty or bliss used, the version of GRAPE, parameter settings
of nauty or bliss, and possibly even 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.
Please also note that a canonical labelling for a GRAPE graph is the inverse of what a canononical labelling for a graph is usually defined as (such as in bliss), in that in GRAPE, the image of a graph under the inverse of its canonical labelling is the calculated canonical version of that graph.
See also IsIsomorphicGraph.
gap> gamma := JohnsonGraph(5,3);
rec( adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ],
group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]),
isGraph := true, isSimple := true,
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 ] ],
order := 10, representatives := [ 1 ],
schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ] )
gap> delta := JohnsonGraph(5,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ],
group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]),
isGraph := true, isSimple := true,
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
[ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10,
representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1
] )
gap> GraphIsomorphism( gamma, delta );
(3,5,6,8,7,4)
gap> GraphIsomorphism(
> rec(graph:=gamma, colourClasses:=[[7],[1,2,3,4,5,6,8,9,10]]),
> rec(graph:=delta, colourClasses:=[[10],[1..9]]) );
(1,3)(2,6,5)(4,8)(7,10,9)
gap> GraphIsomorphism(
> rec(graph:=gamma, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]),
> rec(graph:=delta, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]) );
fail
IsIsomorphicGraph( gamma1, gamma2 )
IsIsomorphicGraph( gamma1, gamma2, firstunbindcanon )
Let gamma1 and gamma2 both be graphs or both be graphs with
colour-classes. Then this boolean function makes use of the nauty or
bliss package to test whether gamma1 and gamma2 are isomorphic
(as graphs or as graphs with colour-classes, respectively). The
value true is returned if and only if the graphs (or graphs with
colour-classes) are isomorphic.
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 much 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 whether nauty or bliss is used, the version
of nauty or bliss used, the version of GRAPE, parameter settings
of nauty or bliss, and possibly even 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 (or graphs with colour-classes), see GraphIsomorphismClassRepresentatives.
Please also note that a canonical labelling for a GRAPE graph is the inverse of what a canononical labelling for a graph is usually defined as (such as in bliss), in that in GRAPE, the image of a graph under the inverse of its canonical labelling is the calculated canonical version of that graph.
gap> gamma := JohnsonGraph(5,3);
rec( adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ],
group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]),
isGraph := true, isSimple := true,
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 ] ],
order := 10, representatives := [ 1 ],
schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ] )
gap> delta := JohnsonGraph(5,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ],
group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]),
isGraph := true, isSimple := true,
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
[ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10,
representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1
] )
gap> IsIsomorphicGraph( gamma, delta );
true
gap> IsIsomorphicGraph(
> rec(graph:=gamma, colourClasses:=[[7],[1,2,3,4,5,6,8,9,10]]),
> rec(graph:=delta, colourClasses:=[[10],[1..9]]) );
true
gap> IsIsomorphicGraph(
> rec(graph:=gamma, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]),
> rec(graph:=delta, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]) );
false
GraphIsomorphismClassRepresentatives( L )
GraphIsomorphismClassRepresentatives( L, firstunbindcanon )
Given a list L of graphs, or of graphs with colour-classes, this function uses nauty or bliss 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 whether nauty or bliss is
used, the version of nauty or bliss used, the version of GRAPE,
parameter settings of nauty or bliss, and possibly even the compiler
and computer used, you must be sure that if firstunbindcanon=false
then any canonicalLabelling component(s) which may already exist for
elements of L were created in exactly the same environment in which
you are presently computing.
It is assumed that the computing environment is constant throughout the execution of this function.
Please also note that a canonical labelling for a GRAPE graph is the inverse of what a canononical labelling for a graph is usually defined as (such as in bliss), in that in GRAPE, the image of a graph under the inverse of its canonical labelling is the calculated canonical version of that graph.
gap> A:=JohnsonGraph(5,3);
rec( adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ],
group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]),
isGraph := true, isSimple := true,
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 ] ],
order := 10, representatives := [ 1 ],
schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ] )
gap> B:=JohnsonGraph(5,2);
rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ],
group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]),
isGraph := true, isSimple := true,
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
[ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10,
representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1
] )
gap> R:=GraphIsomorphismClassRepresentatives([A,B,ComplementGraph(A)]);;
gap> Length(R);
2
gap> List(R,VertexDegrees);
[ [ 6 ], [ 3 ] ]
gap> R:=GraphIsomorphismClassRepresentatives(
> [ rec(graph:=gamma, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]),
> rec(graph:=delta, colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]),
> rec(graph:=ComplementGraph(gamma), colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]) ] );;
gap> Length(R);
3
[Up] [Previous] [Next] [Index]
grape manual