  
  [1X7 [33X[0;0YHomomorphisms[133X[101X
  
  
  [1X7.1 [33X[0;0YActing on digraphs[133X[101X
  
  [1X7.1-1 OnDigraphs[101X
  
  [33X[1;0Y[29X[2XOnDigraphs[102X( [3Xdigraph[103X, [3Xperm[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XOnDigraphs[102X( [3Xdigraph[103X, [3Xtrans[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA digraph.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is  a digraph, and the second argument [3Xperm[103X is a [13Xpermutation[113X of
  the  vertices  of [3Xdigraph[103X, then this operation returns a digraph constructed
  by  relabelling  the vertices of [3Xdigraph[103X according to [3Xperm[103X. Note that for an
  automorphism [10Xf[110X of a digraph, we have [10XOnDigraphs([3Xdigraph[103X[10X, f) = [110X[3Xdigraph[103X.[133X
  
  [33X[0;0YIf the second argument is a [13Xtransformation[113X [3Xtrans[103X of the vertices of [3Xdigraph[103X,
  then this operation returns a digraph constructed by transforming the source
  and  range  of  each  edge  according to [3Xtrans[103X. Thus a vertex which does not
  appear  in  the image of [3Xtrans[103X will be isolated in the returned digraph, and
  the  returned  digraph may contain multiple edges, even if [3Xdigraph[103X does not.
  If  [3Xtrans[103X  is  mathematically  a permutation, then the result coincides with
  [10XOnDigraphs([3Xdigraph[103X[10X, AsPermutation([3Xtrans[103X[10X))[110X.[133X
  
  [33X[0;0YNote:  [10XOnDigraphs[110X for a digraph and a permutation or transformation can also
  be used via the [10X\^[110X operator.[133X
  
  [33X[0;0YThe  [2XDigraphVertexLabels[102X  ([14X5.1-12[114X)  of  [3Xdigraph[103X  will not be retained in the
  returned digraph.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  belongs  to  [2XIsMutableDigraph[102X  ([14X3.1-2[114X), then relabelling of the
  vertices   is   performed   directly  on  [3Xdigraph[103X.  If  [3Xdigraph[103X  belongs  to
  [2XIsImmutableDigraph[102X  ([14X3.1-3[114X),  an immutable copy of [3Xdigraph[103X with the vertices
  relabelled is returned.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := Digraph([[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]);[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 11 edges>[128X[104X
    [4X[25Xgap>[125X [27Xnew := OnDigraphs(D, (1, 2));[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 11 edges>[128X[104X
    [4X[25Xgap>[125X [27XOutNeighbours(new);[127X[104X
    [4X[28X[ [ 2, 3, 5 ], [ 3 ], [ 2 ], [ 2, 1, 4 ], [ 1, 3, 5 ] ][128X[104X
    [4X[25Xgap>[125X [27XD := Digraph([[2], [], [2]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 2 edges>[128X[104X
    [4X[25Xgap>[125X [27Xt := Transformation([1, 2, 1]);;[127X[104X
    [4X[25Xgap>[125X [27Xnew := OnDigraphs(D, t);[127X[104X
    [4X[28X<immutable multidigraph with 3 vertices, 2 edges>[128X[104X
    [4X[25Xgap>[125X [27XOutNeighbours(new);[127X[104X
    [4X[28X[ [ 2, 2 ], [  ], [  ] ][128X[104X
    [4X[25Xgap>[125X [27XForAll(DigraphEdges(D),[127X[104X
    [4X[25X>[125X [27X e -> IsDigraphEdge(new, [e[1] ^ t, e[2] ^ t]));[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.1-2 \^[101X
  
  [33X[1;0Y[29X[2X\^[102X( [3Xdigraph[103X, [3XpermOrTrans[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA digraph.[133X
  
  [33X[0;0YThe   [10X^[110X   operator   acts  on  digraphs  with  either  a  permutation  or  a
  transformation. For a digraph [3Xdigraph[103X and a permutation [3Xperm[103X, [10Xdigraph ^ perm[110X
  gives  the  same  result  as  [10XOnDigraphs(digraph,  perm)[110X  —  a digraph whose
  vertices have been relabelled according to the permutation.[133X
  
  [33X[0;0YSimilarly,  if the second argument is a transformation [3Xtrans[103X, then [10Xdigraph ^
  trans[110X  calls  [10XOnDigraphs(digraph,  trans)[110X. This allows a simple way to apply
  vertex relabelling or transformations directly using the [10X^[110X symbol.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := CycleDigraph(5);[127X[104X
    [4X[28X<immutable cycle digraph with 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xp := (1, 5)(2, 4);;[127X[104X
    [4X[25Xgap>[125X [27XD ^ p = DigraphReverse(D);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(D, p) = D ^ p;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xidp := ();;[127X[104X
    [4X[25Xgap>[125X [27XD ^ idp = D;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xq := (1, 2, 3, 4, 5);;[127X[104X
    [4X[25Xgap>[125X [27X(D ^ q) ^ (q ^ -1) = D;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xt := Transformation([2, 3, 4, 5, 1]);;[127X[104X
    [4X[25Xgap>[125X [27XD ^ t = OnDigraphs(D, t);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xidt := Transformation([1, 2, 3, 4, 5]);;[127X[104X
    [4X[25Xgap>[125X [27XD ^ idt = D;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XM := DigraphMutableCopy(D);;[127X[104X
    [4X[25Xgap>[125X [27XM ^ p = OnDigraphs(M, p);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.1-3 OnMultiDigraphs[101X
  
  [33X[1;0Y[29X[2XOnMultiDigraphs[102X( [3Xdigraph[103X, [3Xpair[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XOnMultiDigraphs[102X( [3Xdigraph[103X, [3Xperm1[103X, [3Xperm2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA digraph.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is a digraph, and [3Xpair[103X is a pair consisting of a permutation of
  the  vertices and a permutation of the edges of [3Xdigraph[103X, then this operation
  returns  a  digraph  constructed  by  relabelling  the vertices and edges of
  [3Xdigraph[103X according to [3Xperm[1][103X and [3Xperm[2][103X, respectively.[133X
  
  [33X[0;0YIn  its  second  form,  [10XOnMultiDigraphs[110X  returns a digraph with vertices and
  edges permuted by [3Xperm1[103X and [3Xperm2[103X, respectively.[133X
  
  [33X[0;0YNote  that  [10XOnDigraphs([3Xdigraph[103X[10X,  perm)=OnMultiDigraphs([3Xdigraph[103X[10X,  [perm, ()])[110X
  where  [10Xperm[110X  is  a  permutation  of the vertices of [3Xdigraph[103X. If you are only
  interested in the action of a permutation on the vertices of a digraph, then
  you  can  use  [10XOnDigraphs[110X  instead of [10XOnMultiDigraphs[110X. If [3Xdigraph[103X belongs to
  [2XIsMutableDigraph[102X  ([14X3.1-2[114X),  then  relabelling  of  the vertices is performed
  directly  on  [3Xdigraph[103X.  If [3Xdigraph[103X belongs to [2XIsImmutableDigraph[102X ([14X3.1-3[114X), an
  immutable copy of [3Xdigraph[103X with the vertices relabelled is returned.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD1 := Digraph([[127X[104X
    [4X[25X>[125X [27X[3, 6, 3], [], [3], [9, 10], [9], [],  [], [10, 4, 10], [], []]);[127X[104X
    [4X[28X<immutable multidigraph with 10 vertices, 10 edges>[128X[104X
    [4X[25Xgap>[125X [27Xp := BlissCanonicalLabelling(D1);[127X[104X
    [4X[28X[ (1,7)(3,6)(4,10)(5,9), () ][128X[104X
    [4X[25Xgap>[125X [27XD2 := OnMultiDigraphs(D1, p);[127X[104X
    [4X[28X<immutable multidigraph with 10 vertices, 10 edges>[128X[104X
    [4X[25Xgap>[125X [27XOutNeighbours(D2);[127X[104X
    [4X[28X[ [  ], [  ], [  ], [  ], [  ], [ 6 ], [ 6, 3, 6 ], [ 4, 10, 4 ], [128X[104X
    [4X[28X  [ 5 ], [ 5, 4 ] ][128X[104X
  [4X[32X[104X
  
  [1X7.1-4 OnTuplesDigraphs[101X
  
  [33X[1;0Y[29X[2XOnTuplesDigraphs[102X( [3Xlist[103X, [3Xperm[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XOnSetsDigraphs[102X( [3Xlist[103X, [3Xperm[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list or set of digraphs.[133X
  
  [33X[0;0YIf  [3Xlist[103X is a list of digraphs, and [3Xperm[103X is a [13Xpermutation[113X of the vertices of
  the  digraphs  in [3Xlist[103X, then [2XOnTuplesDigraphs[102X returns a new list constructed
  by applying [3Xperm[103X via [2XOnDigraphs[102X ([14X7.1-1[114X) to a copy (with the same mutability)
  of each entry of [3Xlist[103X in turn.[133X
  
  [33X[0;0YMore   precisely,   [10XOnTuplesDigraphs([3Xlist[103X[10X,[3Xperm[103X[10X)[110X   is   a   list   of  length
  [10XLength([3Xlist[103X[10X)[110X, whose [10Xi[110X-th entry is [10XOnDigraphs(DigraphCopy([3Xlist[103X[10X[i]), [3Xperm[103X[10X)[110X.[133X
  
  [33X[0;0YIf  [3Xlist[103X  is  moreover  a  [5XGAP[105X set (i.e. a duplicate-free sorted list), then
  [2XOnSetsDigraphs[102X  returns  the  sorted  output  of  [2XOnTuplesDigraphs[102X, which is
  therefore again a set.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xlist := [CycleDigraph(IsMutableDigraph, 6),[127X[104X
    [4X[25X>[125X [27X            DigraphReverse(CycleDigraph(6))];[127X[104X
    [4X[28X[ <mutable digraph with 6 vertices, 6 edges>, [128X[104X
    [4X[28X  <immutable digraph with 6 vertices, 6 edges> ][128X[104X
    [4X[25Xgap>[125X [27Xp := (1, 6)(2, 5)(3, 4);;[127X[104X
    [4X[25Xgap>[125X [27Xresult_tuples := OnTuplesDigraphs(list, p);[127X[104X
    [4X[28X[ <mutable digraph with 6 vertices, 6 edges>, [128X[104X
    [4X[28X  <immutable digraph with 6 vertices, 6 edges> ][128X[104X
    [4X[25Xgap>[125X [27Xresult_tuples[2] = OnDigraphs(list[2], p);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xresult_tuples = list;[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xresult_tuples = Reversed(list);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xresult_sets := OnSetsDigraphs(list, p);[127X[104X
    [4X[28X[ <immutable digraph with 6 vertices, 6 edges>, [128X[104X
    [4X[28X  <mutable digraph with 6 vertices, 6 edges> ][128X[104X
    [4X[25Xgap>[125X [27Xresult_sets = list;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  
  [1X7.2 [33X[0;0YIsomorphisms and canonical labellings[133X[101X
  
  [33X[0;0YFrom  version 0.11.0 of [5XDigraphs[105X it is possible to use either [5Xbliss[105X or [5Xnauty[105X
  (via   [5XNautyTracesInterface[105X)   to   calculate   canonical   labellings   and
  automorphism  groups  of  digraphs;  see  [JK07] and [MP14] for more details
  about [5Xbliss[105X and [5Xnauty[105X, respectively.[133X
  
  [1X7.2-1 DigraphsUseNauty[101X
  
  [33X[1;0Y[29X[2XDigraphsUseNauty[102X(  ) [32X function[133X
  [33X[1;0Y[29X[2XDigraphsUseBliss[102X(  ) [32X function[133X
  [6XReturns:[106X  [33X[0;10YNothing.[133X
  
  [33X[0;0YThese functions can be used to specify whether [5Xnauty[105X or [5Xbliss[105X should be used
  by default by [5XDigraphs[105X. If [5XNautyTracesInterface[105X is not available, then these
  functions  do  nothing.  Otherwise,  by  calling [10XDigraphsUseNauty[110X subsequent
  computations will default to using [5Xnauty[105X rather than [5Xbliss[105X, where possible.[133X
  
  [33X[0;0YYou can call these functions at any point in a [5XGAP[105X session, as many times as
  you  like,  it  is  guaranteed that existing digraphs remain valid, and that
  comparison   of   existing   digraphs   and   newly   created  digraphs  via
  [2XIsIsomorphicDigraph[102X       ([14X7.2-15[114X),       [2XIsIsomorphicDigraph[102X      ([14X7.2-16[114X),
  [2XIsomorphismDigraphs[102X  ([14X7.2-17[114X),  and  [2XIsomorphismDigraphs[102X  ([14X7.2-18[114X)  are also
  valid.[133X
  
  [33X[0;0YIt  is also possible to compute the automorphism group of a specific digraph
  using   both  [5Xnauty[105X  and  [5Xbliss[105X  using  [2XNautyAutomorphismGroup[102X  ([14X7.2-4[114X)  and
  [2XBlissAutomorphismGroup[102X ([14X7.2-3[114X), respectively.[133X
  
  [1X7.2-2 AutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XAutomorphismGroup[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA permutation group.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is  a  digraph,  then  this  attribute  contains  the  group of
  automorphisms  of [3Xdigraph[103X. An [13Xautomorphism[113X of [3Xdigraph[103X is an isomorphism from
  [3Xdigraph[103X  to  itself.  See  [2XIsomorphismDigraphs[102X ([14X7.2-17[114X) for more information
  about isomorphisms of digraphs.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X is not a multidigraph then the automorphism group is returned as
  a group of permutations on the set of vertices of [3Xdigraph[103X.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X is a multidigraph then the automorphism group is returned as the
  direct  product of a group of permutations on the set of vertices of [3Xdigraph[103X
  with  a  group  of permutations on the set of edges of [3Xdigraph[103X. These groups
  can  be  accessed using [2XProjection[102X ([14XReference: Projection for a domain and a
  positive integer[114X) on the returned group.[133X
  
  [33X[0;0YBy  default,  the  automorphism group is found using [5Xbliss[105X by Tommi Junttila
  and  Petteri  Kaski.  If  [5XNautyTracesInterface[105X  is  available, then [5Xnauty[105X by
  Brendan    Mckay   and   Adolfo   Piperno   can   be   used   instead;   see
  [2XBlissAutomorphismGroup[102X      ([14X7.2-3[114X),     [2XNautyAutomorphismGroup[102X     ([14X7.2-4[114X),
  [2XDigraphsUseBliss[102X ([14X7.2-1[114X), and [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [33X[0;0YIf  the argument [3Xdigraph[103X is mutable, then the return value of this attribute
  is recomputed every time it is called.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xjohnson := DigraphFromGraph6String("E}lw");[127X[104X
    [4X[28X<immutable symmetric digraph with 6 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27XG := AutomorphismGroup(johnson);[127X[104X
    [4X[28XGroup([ (3,4), (2,3)(4,5), (1,2)(5,6) ])[128X[104X
    [4X[25Xgap>[125X [27Xcycle := CycleDigraph(9);[127X[104X
    [4X[28X<immutable cycle digraph with 9 vertices>[128X[104X
    [4X[25Xgap>[125X [27XG := AutomorphismGroup(cycle);[127X[104X
    [4X[28XGroup([ (1,2,3,4,5,6,7,8,9) ])[128X[104X
    [4X[25Xgap>[125X [27XIsCyclic(G) and Size(G) = 9;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.2-3 BlissAutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XBlissAutomorphismGroup[102X( [3Xdigraph[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XBlissAutomorphismGroup[102X( [3Xdigraph[103X, [3Xvertex_colours[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XBlissAutomorphismGroup[102X( [3Xdigraph[103X, [3Xvertex_colours[103X, [3Xedge_colours[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA permutation group.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is  a  digraph,  then  this  attribute  contains  the  group of
  automorphisms  of  [3Xdigraph[103X  as  calculated using [5Xbliss[105X by Tommi Junttila and
  Petteri Kaski.[133X
  
  [33X[0;0YThe  attribute  [2XAutomorphismGroup[102X  ([14X7.2-2[114X)  and  operation [2XAutomorphismGroup[102X
  ([14X7.2-5[114X)    returns   the   value   of   either   [10XBlissAutomorphismGroup[110X   or
  [2XNautyAutomorphismGroup[102X ([14X7.2-4[114X). These groups are, of course, equal but their
  generating sets may differ.[133X
  
  [33X[0;0YThe    attribute    [2XAutomorphismGroup[102X   ([14X7.2-6[114X)   returns   the   value   of
  [10XBlissAutomorphismGroup[110X  as  it is not implemented for [5Xnauty[105X The requirements
  for the optional arguments [3Xvertex_colours[103X and [3Xedge_colours[103X are documented in
  [2XAutomorphismGroup[102X   ([14X7.2-6[114X).   See   also   [2XDigraphsUseBliss[102X   ([14X7.2-1[114X),  and
  [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [33X[0;0YIf  the argument [3Xdigraph[103X is mutable, then the return value of this attribute
  is recomputed every time it is called.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := BlissAutomorphismGroup(JohnsonDigraph(5, 2));;[127X[104X
    [4X[25Xgap>[125X [27XIsSymmetricGroup(G);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XSize(G);[127X[104X
    [4X[28X120[128X[104X
  [4X[32X[104X
  
  [1X7.2-4 NautyAutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XNautyAutomorphismGroup[102X( [3Xdigraph[103X[, [3Xvert_colours[103X] ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA permutation group.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is  a  digraph,  then  this  attribute  contains  the  group of
  automorphisms  of  [3Xdigraph[103X  as  calculated  using [5Xnauty[105X by Brendan Mckay and
  Adolfo  Piperno  via  [5XNautyTracesInterface[105X.  The attribute [2XAutomorphismGroup[102X
  ([14X7.2-2[114X)  and operation [2XAutomorphismGroup[102X ([14X7.2-5[114X) returns the value of either
  [10XNautyAutomorphismGroup[110X  or [2XBlissAutomorphismGroup[102X ([14X7.2-3[114X). These groups are,
  of course, equal but their generating sets may differ.[133X
  
  [33X[0;0YSee also [2XDigraphsUseBliss[102X ([14X7.2-1[114X), and [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [33X[0;0YIf  the argument [3Xdigraph[103X is mutable, then the return value of this attribute
  is recomputed every time it is called.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XNautyAutomorphismGroup(JohnsonDigraph(5, 2));[127X[104X
    [4X[28XGroup([ (3,4)(6,7)(8,9), (2,3)(5,6)(9,10), (2,5)(3,6)(4,7),[128X[104X
    [4X[28X (1,2)(6,8)(7,9) ])[128X[104X
  [4X[32X[104X
  
  [1X7.2-5 AutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XAutomorphismGroup[102X( [3Xdigraph[103X, [3Xvert_colours[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA permutation group.[133X
  
  [33X[0;0YThis operation computes the automorphism group of a vertex-coloured digraph.
  A vertex-coloured digraph can be specified by its underlying digraph [3Xdigraph[103X
  and  its colouring [3Xvert_colours[103X. Let [10Xn[110X be the number of vertices of [3Xdigraph[103X.
  The colouring [3Xvert_colours[103X may have one of the following two forms:[133X
  
  [30X    [33X[0;6Ya list of [10Xn[110X integers, where [3Xvert_colours[103X[10X[i][110X is the colour of vertex [10Xi[110X,
        using the colours [10X[1 .. m][110X for some [10Xm <= n[110X; or[133X
  
  [30X    [33X[0;6Ya    list    of    non-empty    disjoint    lists   whose   union   is
        [10XDigraphVertices([3Xdigraph[103X[10X)[110X, such that [3Xvert_colours[103X[10X[i][110X is the list of all
        vertices with colour [10Xi[110X.[133X
  
  [33X[0;0YThe  [13Xautomorphism  group[113X  of  a  coloured  digraph  [3Xdigraph[103X  with  colouring
  [3Xvert_colours[103X  is  the group consisting of its automorphisms; an [13Xautomorphism[113X
  of  [3Xdigraph[103X  is  an isomorphism of coloured digraphs from [3Xdigraph[103X to itself.
  This group is equal to the subgroup of [10XAutomorphismGroup([3Xdigraph[103X[10X)[110X consisting
  of   those   automorphisms   that   preserve   the  colouring  specified  by
  [3Xvert_colours[103X.  See  [2XAutomorphismGroup[102X  ([14X7.2-2[114X),  and see [2XIsomorphismDigraphs[102X
  ([14X7.2-18[114X) for more information about isomorphisms of coloured digraphs.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X is not a multidigraph then the automorphism group is returned as
  a group of permutations on the set of vertices of [3Xdigraph[103X.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X is a multidigraph then the automorphism group is returned as the
  direct  product of a group of permutations on the set of vertices of [3Xdigraph[103X
  with  a  group  of permutations on the set of edges of [3Xdigraph[103X. These groups
  can  be  accessed using [2XProjection[102X ([14XReference: Projection for a domain and a
  positive integer[114X) on the returned group.[133X
  
  [33X[0;0YBy  default,  the  automorphism group is found using [5Xbliss[105X by Tommi Junttila
  and  Petteri  Kaski.  If  [5XNautyTracesInterface[105X  is  available, then [5Xnauty[105X by
  Brendan    Mckay   and   Adolfo   Piperno   can   be   used   instead;   see
  [2XBlissAutomorphismGroup[102X      ([14X7.2-3[114X),     [2XNautyAutomorphismGroup[102X     ([14X7.2-4[114X),
  [2XDigraphsUseBliss[102X ([14X7.2-1[114X), and [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xcycle := CycleDigraph(9);[127X[104X
    [4X[28X<immutable cycle digraph with 9 vertices>[128X[104X
    [4X[25Xgap>[125X [27XG := AutomorphismGroup(cycle);;[127X[104X
    [4X[25Xgap>[125X [27XIsCyclic(G) and Size(G) = 9;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xcolours := [[1, 4, 7], [2, 5, 8], [3, 6, 9]];;[127X[104X
    [4X[25Xgap>[125X [27XH := AutomorphismGroup(cycle, colours);;[127X[104X
    [4X[25Xgap>[125X [27XSize(H);[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XH = AutomorphismGroup(cycle, [1, 2, 3, 1, 2, 3, 1, 2, 3]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XH = SubgroupByProperty(G, p -> OnTuplesSets(colours, p) = colours);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsTrivial(AutomorphismGroup(cycle, [1, 1, 2, 2, 2, 2, 2, 2, 2]));[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.2-6 AutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XAutomorphismGroup[102X( [3Xdigraph[103X, [3Xvert_colours[103X, [3Xedge_colours[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA permutation group.[133X
  
  [33X[0;0YThis   operation  computes  the  automorphism  group  of  a  vertex-  and/or
  edge-coloured digraph. A coloured digraph can be specified by its underlying
  digraph  [3Xdigraph[103X  and  colourings  [3Xvert_colours[103X,  [3Xedge_colours[103X. Let [10Xn[110X be the
  number of vertices of [3Xdigraph[103X. The colourings must have the following forms:[133X
  
  [30X    [33X[0;6Y[3Xvert_colours[103X   must   be   [9Xfail[109X   or  a  list  of  [10Xn[110X  integers,  where
        [3Xvert_colours[103X[10X[i][110X  is the colour of vertex [10Xi[110X, using the colours [10X[1 .. m][110X
        for some [10Xm <= n[110X;[133X
  
  [30X    [33X[0;6Y[3Xedge_colours[103X must be [9Xfail[109X or a list of [10Xn[110X lists of integers of the same
        shape  as  [10XOutNeighbours(digraph)[110X,  where  [3Xedge_colours[103X[10X[i][j][110X  is  the
        colour  of the edge [10XOutNeighbours(digraph)[i][j][110X, using the colours [10X[1
        .. k][110X for some [10Xk <= n[110X;[133X
  
  [33X[0;0YGiving  [3Xvert_colours[103X  [[3Xedge_colours[103X]  as  [10Xfail[110X  is equivalent to setting all
  vertices [edges] to be the same colour.[133X
  
  [33X[0;0YUnlike  [2XAutomorphismGroup[102X ([14X7.2-2[114X), it is possible to obtain the automorphism
  group of an edge-coloured multidigraph (see [2XIsMultiDigraph[102X ([14X6.2-11[114X)) when no
  two  edges  share the same source, range, and colour. The [13Xautomorphism group[113X
  of  a  vertex/edge-coloured  digraph  [3Xdigraph[103X  with colouring [3Xc[103X is the group
  consisting   of   its   vertex/edge-colour   preserving   automorphisms;  an
  [13Xautomorphism[113X  of  [3Xdigraph[103X is an isomorphism of vertex/edge-coloured digraphs
  from   [3Xdigraph[103X   to   itself.  This  group  is  equal  to  the  subgroup  of
  [10XAutomorphismGroup([3Xdigraph[103X[10X)[110X  consisting  of those automorphisms that preserve
  the  colouring  specified by [3Xcolours[103X. See [2XAutomorphismGroup[102X ([14X7.2-2[114X), and see
  [2XIsomorphismDigraphs[102X  ([14X7.2-18[114X)  for  more  information  about isomorphisms of
  coloured digraphs.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X is not a multidigraph then the automorphism group is returned as
  a group of permutations on the set of vertices of [3Xdigraph[103X.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X is a multidigraph then the automorphism group is returned as the
  direct  product of a group of permutations on the set of vertices of [3Xdigraph[103X
  with  a  group  of permutations on the set of edges of [3Xdigraph[103X. These groups
  can  be  accessed using [2XProjection[102X ([14XReference: Projection for a domain and a
  positive integer[114X) on the returned group.[133X
  
  [33X[0;0YBy  default,  the  automorphism group is found using [5Xbliss[105X by Tommi Junttila
  and  Petteri  Kaski.  If  [5XNautyTracesInterface[105X  is  available, then [5Xnauty[105X by
  Brendan    Mckay   and   Adolfo   Piperno   can   be   used   instead;   see
  [2XBlissAutomorphismGroup[102X      ([14X7.2-3[114X),     [2XNautyAutomorphismGroup[102X     ([14X7.2-4[114X),
  [2XDigraphsUseBliss[102X ([14X7.2-1[114X), and [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xcycle := CycleDigraph(12);[127X[104X
    [4X[28X<immutable cycle digraph with 12 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xvert_colours := List([1 .. 12], x -> x mod 3 + 1);;[127X[104X
    [4X[25Xgap>[125X [27Xedge_colours := List([1 .. 12], x -> [x mod 2 + 1]);;[127X[104X
    [4X[25Xgap>[125X [27XSize(AutomorphismGroup(cycle));[127X[104X
    [4X[28X12[128X[104X
    [4X[25Xgap>[125X [27XSize(AutomorphismGroup(cycle, vert_colours));[127X[104X
    [4X[28X4[128X[104X
    [4X[25Xgap>[125X [27XSize(AutomorphismGroup(cycle, fail, edge_colours));[127X[104X
    [4X[28X6[128X[104X
    [4X[25Xgap>[125X [27XSize(AutomorphismGroup(cycle, vert_colours, edge_colours));[127X[104X
    [4X[28X2[128X[104X
    [4X[25Xgap>[125X [27XIsTrivial(AutomorphismGroup(cycle,[127X[104X
    [4X[25X>[125X [27Xvert_colours, List([1 .. 12], x -> [x mod 4 + 1])));[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.2-7 BlissCanonicalLabelling[101X
  
  [33X[1;0Y[29X[2XBlissCanonicalLabelling[102X( [3Xdigraph[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XNautyCanonicalLabelling[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA permutation, or a list of two permutations.[133X
  
  [33X[0;0YA  function [22Xρ[122X that maps a digraph to a digraph is a [13Xcanonical representative
  map[113X if the following two conditions hold for all digraphs [22XG[122X and [22XH[122X:[133X
  
  [30X    [33X[0;6Y[22Xρ(G)[122X and [22XG[122X are isomorphic as digraphs; and[133X
  
  [30X    [33X[0;6Y[22Xρ(G)=ρ(H)[122X if and only if [22XG[122X and [22XH[122X are isomorphic as digraphs.[133X
  
  [33X[0;0YA  [13Xcanonical  labelling[113X of a digraph [22XG[122X (under [22Xρ[122X) is an isomorphism of [22XG[122X onto
  its  [13Xcanonical  representative[113X,  [22Xρ(G)[122X.  See [2XIsomorphismDigraphs[102X ([14X7.2-17[114X) for
  more information about isomorphisms of digraphs.[133X
  
  [33X[0;0Y[10XBlissCanonicalLabelling[110X returns a canonical labelling of the digraph [3Xdigraph[103X
  found    using    [5Xbliss[105X    by    Tommi    Junttila    and   Petteri   Kaski.
  [10XNautyCanonicalLabelling[110X returns a canonical labelling of the digraph [3Xdigraph[103X
  found  using  [5Xnauty[105X  by  Brendan  McKay  and  Adolfo  Piperno. Note that the
  canonical  labellings  returned  by [5Xbliss[105X and [5Xnauty[105X are not usually the same
  (and may depend of the version used).[133X
  
  [33X[0;0Y[10XBlissCanonicalLabelling[110X  can  only  be  computed  if [3Xdigraph[103X has no multiple
  edges; see [2XIsMultiDigraph[102X ([14X6.2-11[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xdigraph1 := DigraphFromDiSparse6String(".ImNS_AiB?qRN");[127X[104X
    [4X[28X<immutable digraph with 10 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27XBlissCanonicalLabelling(digraph1);[127X[104X
    [4X[28X(1,9,5,7)(3,6,4,10)[128X[104X
    [4X[25Xgap>[125X [27Xp := (1, 2, 7, 5)(3, 9)(6, 10, 8);;[127X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := OnDigraphs(digraph1, p);[127X[104X
    [4X[28X<immutable digraph with 10 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27Xdigraph1 = digraph2;[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(digraph1, BlissCanonicalLabelling(digraph1)) =[127X[104X
    [4X[25X>[125X [27X   OnDigraphs(digraph2, BlissCanonicalLabelling(digraph2));[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.2-8 BlissCanonicalLabelling[101X
  
  [33X[1;0Y[29X[2XBlissCanonicalLabelling[102X( [3Xdigraph[103X, [3Xcolours[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XNautyCanonicalLabelling[102X( [3Xdigraph[103X, [3Xcolours[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA permutation.[133X
  
  [33X[0;0YA  function  [22Xρ[122X  that  maps  a  coloured  digraph  to a coloured digraph is a
  [13Xcanonical  representative  map[113X  if the following two conditions hold for all
  coloured digraphs [22XG[122X and [22XH[122X:[133X
  
  [30X    [33X[0;6Y[22Xρ(G)[122X and [22XG[122X are isomorphic as coloured digraphs; and[133X
  
  [30X    [33X[0;6Y[22Xρ(G)=ρ(H)[122X if and only if [22XG[122X and [22XH[122X are isomorphic as coloured digraphs.[133X
  
  [33X[0;0YA [13Xcanonical labelling[113X of a coloured digraph [22XG[122X (under [22Xρ[122X) is an isomorphism of
  [22XG[122X  onto its [13Xcanonical representative[113X, [22Xρ(G)[122X. See [2XIsomorphismDigraphs[102X ([14X7.2-18[114X)
  for more information about isomorphisms of coloured digraphs.[133X
  
  [33X[0;0YA  coloured  digraph  can be specified by its underlying digraph [3Xdigraph[103X and
  its  colouring  [3Xcolours[103X.  Let  [10Xn[110X  be  the number of vertices of [3Xdigraph[103X. The
  colouring [3Xcolours[103X may have one of the following two forms:[133X
  
  [30X    [33X[0;6Ya  list  of  [10Xn[110X  integers,  where [3Xcolours[103X[10X[i][110X is the colour of vertex [10Xi[110X,
        using the colours [10X[1 .. m][110X for some [10Xm <= n[110X; or[133X
  
  [30X    [33X[0;6Ya    list    of    non-empty    disjoint    lists   whose   union   is
        [10XDigraphVertices([3Xdigraph[103X[10X)[110X,  such  that  [3Xcolours[103X[10X[i][110X  is  the list of all
        vertices with colour [10Xi[110X.[133X
  
  [33X[0;0YIf    [3Xdigraph[103X    and    [3Xcolours[103X    together   form   a   coloured   digraph,
  [10XBlissCanonicalLabelling[110X returns a canonical labelling of the digraph [3Xdigraph[103X
  found   using   [5Xbliss[105X  by  Tommi  Junttila  and  Petteri  Kaski.  Similarly,
  [10XNautyCanonicalLabelling[110X returns a canonical labelling of the digraph [3Xdigraph[103X
  found  using  [5Xnauty[105X  by  Brendan  McKay  and  Adolfo  Piperno. Note that the
  canonical  labellings  returned  by [5Xbliss[105X and [5Xnauty[105X are not usually the same
  (and may depend of the version used).[133X
  
  [33X[0;0Y[10XBlissCanonicalLabelling[110X  can  only  be  computed  if [3Xdigraph[103X has no multiple
  edges;  see  [2XIsMultiDigraph[102X  ([14X6.2-11[114X). The canonical labelling of [3Xdigraph[103X is
  given  as  a  permutation  of  its vertices. The canonical representative of
  [3Xdigraph[103X  can  be created from [3Xdigraph[103X and its canonical labelling [10Xp[110X by using
  the operation [2XOnDigraphs[102X ([14X7.1-1[114X):[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(digraph, p);[127X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  colouring  of the canonical representative can easily be constructed. A
  vertex  [10Xv[110X  (in [3Xdigraph[103X) has colour [10Xi[110X if and only if the vertex [10Xv ^ p[110X (in the
  canonical  representative)  has  colour [10Xi[110X, where [10Xp[110X is the permutation of the
  canonical  labelling that acts on the vertices of [3Xdigraph[103X. In particular, if
  [3Xcolours[103X  has  the  first form that is described above, then the colouring of
  the canonical representative is given by:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XList(DigraphVertices(digraph), i -> colours[i / p]);[127X[104X
  [4X[32X[104X
  
  [33X[0;0YOn  the other hand, if [3Xcolours[103X has the second form above, then the canonical
  representative has colouring:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XOnTuplesSets(colours, p);[127X[104X
  [4X[32X[104X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xdigraph := DigraphFromDiSparse6String(".ImNS_AiB?qRN");[127X[104X
    [4X[28X<immutable digraph with 10 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27Xcolours := [[1, 2, 8, 9, 10], [3, 4, 5, 6, 7]];;[127X[104X
    [4X[25Xgap>[125X [27Xp := BlissCanonicalLabelling(digraph, colours);[127X[104X
    [4X[28X(1,5,8,4,10,3,9)(6,7)[128X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(digraph, p);[127X[104X
    [4X[28X<immutable digraph with 10 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27XOnTuplesSets(colours, p);[127X[104X
    [4X[28X[ [ 1, 2, 3, 4, 5 ], [ 6, 7, 8, 9, 10 ] ][128X[104X
    [4X[25Xgap>[125X [27Xcolours := [1, 1, 1, 1, 2, 3, 1, 3, 2, 1];;[127X[104X
    [4X[25Xgap>[125X [27Xp := BlissCanonicalLabelling(digraph, colours);[127X[104X
    [4X[28X(1,6,9,7)(3,4,5,8,10)[128X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(digraph, p);[127X[104X
    [4X[28X<immutable digraph with 10 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27XList(DigraphVertices(digraph), i -> colours[i / p]);[127X[104X
    [4X[28X[ 1, 1, 1, 1, 1, 1, 2, 2, 3, 3 ][128X[104X
  [4X[32X[104X
  
  [1X7.2-9 BlissCanonicalDigraph[101X
  
  [33X[1;0Y[29X[2XBlissCanonicalDigraph[102X( [3Xdigraph[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XNautyCanonicalDigraph[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA digraph.[133X
  
  [33X[0;0YThe  attribute  [10XBlissCanonicalLabelling[110X returns the canonical representative
  found  by  applying [2XBlissCanonicalLabelling[102X ([14X7.2-7[114X). The digraph returned is
  canonical in the sense that[133X
  
  [30X    [33X[0;6Y[10XBlissCanonicalDigraph([3Xdigraph[103X[10X)[110X and [3Xdigraph[103X are isomorphic as digraphs;
        and[133X
  
  [30X    [33X[0;6YIf    [10Xgr[110X   is   any   digraph   then   [10XBlissCanonicalDigraph(gr)[110X   and
        [10XBlissCanonicalDigraph([3Xdigraph[103X[10X)[110X are equal if and only if [10Xgr[110X and [3Xdigraph[103X
        are isomorphic as digraphs.[133X
  
  [33X[0;0YAnalogously,  the  attribute  [10XNautyCanonicalLabelling[110X  returns the canonical
  representative found by applying [2XNautyCanonicalLabelling[102X ([14X7.2-7[114X).[133X
  
  [33X[0;0YIf  the argument [3Xdigraph[103X is mutable, then the return value of this attribute
  is recomputed every time it is called.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xdigraph := Digraph([[1], [2, 3], [3], [1, 2, 3]]);[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 7 edges>[128X[104X
    [4X[25Xgap>[125X [27Xcanon := BlissCanonicalDigraph(digraph);[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 7 edges>[128X[104X
    [4X[25Xgap>[125X [27XOutNeighbours(canon);[127X[104X
    [4X[28X[ [ 1 ], [ 2 ], [ 3, 2 ], [ 1, 3, 2 ] ][128X[104X
  [4X[32X[104X
  
  [1X7.2-10 DigraphGroup[101X
  
  [33X[1;0Y[29X[2XDigraphGroup[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA permutation group.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is  immutable  and  was  created  knowing  a  subgroup  of  its
  automorphism group, then this group is stored in the attribute [10XDigraphGroup[110X.
  If  [3Xdigraph[103X  is  mutable,  or  was  not  created  knowing  a subgroup of its
  automorphism  group, then [10XDigraphGroup[110X returns the entire automorphism group
  of  [3Xdigraph[103X. Note that if [3Xdigraph[103X is mutable, then the automorphism group is
  recomputed every time this function is called.[133X
  
  [33X[0;0YNote  that  certain  other  constructor  operations  such  as  [2XCayleyDigraph[102X
  ([14X3.1-12[114X),  [2XBipartiteDoubleDigraph[102X  ([14X3.3-44[114X), and [2XDoubleDigraph[102X ([14X3.3-43[114X), may
  not  require  a  group  as  one  of  the  arguments,  but  use  the standard
  constructor  method  using a group, and hence set the [10XDigraphGroup[110X attribute
  for the resulting digraph.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xn := 4;;[127X[104X
    [4X[25Xgap>[125X [27Xadj := function(x, y)[127X[104X
    [4X[25X>[125X [27X     return (((x - y) mod n) = 1) or (((x - y) mod n) = n - 1);[127X[104X
    [4X[25X>[125X [27X   end;;[127X[104X
    [4X[25Xgap>[125X [27Xgroup := CyclicGroup(IsPermGroup, n);[127X[104X
    [4X[28XGroup([ (1,2,3,4) ])[128X[104X
    [4X[25Xgap>[125X [27XD := Digraph(IsMutableDigraph, group, [1 .. n], \^, adj);[127X[104X
    [4X[28X<mutable digraph with 4 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27XHasDigraphGroup(D);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XDigraphGroup(D);[127X[104X
    [4X[28XGroup([ (2,4), (1,2)(3,4) ])[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(D);[127X[104X
    [4X[28XGroup([ (2,4), (1,2)(3,4) ])[128X[104X
    [4X[25Xgap>[125X [27XD := Digraph(group, [1 .. n], \^, adj);[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27XHasDigraphGroup(D);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XDigraphGroup(D);[127X[104X
    [4X[28XGroup([ (1,2,3,4) ])[128X[104X
    [4X[25Xgap>[125X [27XD := DoubleDigraph(D);[127X[104X
    [4X[28X<immutable digraph with 8 vertices, 32 edges>[128X[104X
    [4X[25Xgap>[125X [27XHasDigraphGroup(D);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XDigraphGroup(D);[127X[104X
    [4X[28XGroup([ (1,2,3,4)(5,6,7,8), (1,5)(2,6)(3,7)(4,8) ])[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(D) =[127X[104X
    [4X[25X>[125X [27XGroup([(6, 8), (5, 7), (4, 6), (3, 5), (2, 4),[127X[104X
    [4X[25X>[125X [27X       (1, 2)(3, 4)(5, 6)(7, 8)]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XD := Digraph([[2, 3], [], []]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 2 edges>[128X[104X
    [4X[25Xgap>[125X [27XHasDigraphGroup(D);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XHasAutomorphismGroup(D);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XDigraphGroup(D);[127X[104X
    [4X[28XGroup([ (2,3) ])[128X[104X
    [4X[25Xgap>[125X [27XHasAutomorphismGroup(D);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xgroup := DihedralGroup(8);[127X[104X
    [4X[28X<pc group of size 8 with 3 generators>[128X[104X
    [4X[25Xgap>[125X [27XD := CayleyDigraph(group);[127X[104X
    [4X[28X<immutable digraph with 8 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27XHasDigraphGroup(D);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfGroup(DigraphGroup(D));[127X[104X
    [4X[28X[ (1,2)(3,5)(4,6)(7,8), (1,7,4,3)(2,5,6,8), (1,4)(2,6)(3,7)(5,8) ][128X[104X
  [4X[32X[104X
  
  [1X7.2-11 DigraphOrbits[101X
  
  [33X[1;0Y[29X[2XDigraphOrbits[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YAn immutable list of lists of integers.[133X
  
  [33X[0;0Y[10XDigraphOrbits[110X  returns the orbits of the action of the [2XDigraphGroup[102X ([14X7.2-10[114X)
  on the set of vertices of [3Xdigraph[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := Group([(2, 3)(7, 8, 9), (1, 2, 3)(4, 5, 6)(8, 9)]);;[127X[104X
    [4X[25Xgap>[125X [27XD := EdgeOrbitsDigraph(G, [1, 2]);[127X[104X
    [4X[28X<immutable digraph with 9 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphOrbits(D);[127X[104X
    [4X[28X[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ][128X[104X
    [4X[25Xgap>[125X [27XD := DigraphMutableCopy(D);[127X[104X
    [4X[28X<mutable digraph with 9 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphOrbits(D);[127X[104X
    [4X[28X[ [ 1, 2, 3 ], [ 4, 5, 6, 7, 8, 9 ] ][128X[104X
  [4X[32X[104X
  
  [1X7.2-12 DigraphOrbitReps[101X
  
  [33X[1;0Y[29X[2XDigraphOrbitReps[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YAn immutable list of integers.[133X
  
  [33X[0;0Y[10XDigraphOrbitReps[110X  returns  a  list of orbit representatives of the action of
  the [2XDigraphGroup[102X ([14X7.2-10[114X) on the set of vertices of [3Xdigraph[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := CayleyDigraph(AlternatingGroup(4));[127X[104X
    [4X[28X<immutable digraph with 12 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphOrbitReps(D);[127X[104X
    [4X[28X[ 1 ][128X[104X
    [4X[25Xgap>[125X [27XD := DigraphMutableCopy(D);[127X[104X
    [4X[28X<mutable digraph with 12 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphOrbitReps(D);[127X[104X
    [4X[28X[ 1 ][128X[104X
    [4X[25Xgap>[125X [27XD := DigraphFromDigraph6String("&IGO??S?`?_@?a?CK?O");[127X[104X
    [4X[28X<immutable digraph with 10 vertices, 14 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphOrbitReps(D);[127X[104X
    [4X[28X[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ][128X[104X
    [4X[25Xgap>[125X [27XDigraphOrbitReps(DigraphMutableCopy(D));[127X[104X
    [4X[28X[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ][128X[104X
  [4X[32X[104X
  
  [1X7.2-13 DigraphSchreierVector[101X
  
  [33X[1;0Y[29X[2XDigraphSchreierVector[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YAn immutable list of integers.[133X
  
  [33X[0;0Y[10XDigraphSchreierVector[110X returns the so-called [13XSchreier vector[113X of the action of
  the  [2XDigraphGroup[102X  ([14X7.2-10[114X)  on the set of vertices of [3Xdigraph[103X. The Schreier
  vector  is  a  list  [10Xsch[110X  of integers with length [10XDigraphNrVertices([3Xdigraph[103X[10X)[110X
  where:[133X
  
  [8X[10Xsch[i] < 0:[110X[8X[108X
        [33X[0;6Yimplies     that     [10Xi[110X     is     an    orbit    representative    and
        [10XDigraphOrbitReps([3Xdigraph[103X[10X)[-sch[i]] = i[110X.[133X
  
  [8X[10Xsch[i] > 0:[110X[8X[108X
        [33X[0;6Yimplies  that  [10Xi  /  gens[sch[i]][110X  is  one step closer to the root (or
        representative)   of  the  tree,  where  [10Xgens[110X  is  the  generators  of
        [10XDigraphGroup([3Xdigraph[103X[10X)[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xn := 4;;[127X[104X
    [4X[25Xgap>[125X [27Xadj := function(x, y)[127X[104X
    [4X[25X>[125X [27X     return (((x - y) mod n) = 1) or (((x - y) mod n) = n - 1);[127X[104X
    [4X[25X>[125X [27X   end;;[127X[104X
    [4X[25Xgap>[125X [27Xgroup := CyclicGroup(IsPermGroup, n);[127X[104X
    [4X[28XGroup([ (1,2,3,4) ])[128X[104X
    [4X[25Xgap>[125X [27XD := Digraph(IsMutableDigraph, group, [1 .. n], \^, adj);[127X[104X
    [4X[28X<mutable digraph with 4 vertices, 8 edges>[128X[104X
    [4X[25Xgap>[125X [27Xsch := DigraphSchreierVector(D);[127X[104X
    [4X[28X[ -1, 2, 2, 1 ][128X[104X
    [4X[25Xgap>[125X [27XD := CayleyDigraph(AlternatingGroup(4));[127X[104X
    [4X[28X<immutable digraph with 12 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27Xsch := DigraphSchreierVector(D);[127X[104X
    [4X[28X[ -1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 1 ][128X[104X
    [4X[25Xgap>[125X [27XDigraphOrbitReps(D);[127X[104X
    [4X[28X[ 1 ][128X[104X
    [4X[25Xgap>[125X [27Xgens := GeneratorsOfGroup(DigraphGroup(D));[127X[104X
    [4X[28X[ (1,7,5)(2,10,9)(3,4,11)(6,8,12), (1,3,2)(4,5,6)(7,9,8)(10,11,12) ][128X[104X
    [4X[25Xgap>[125X [27X10 / gens[sch[10]];[127X[104X
    [4X[28X2[128X[104X
    [4X[25Xgap>[125X [27X7 / gens[sch[7]];[127X[104X
    [4X[28X1[128X[104X
    [4X[25Xgap>[125X [27X5 / gens[sch[5]];[127X[104X
    [4X[28X7[128X[104X
  [4X[32X[104X
  
  [1X7.2-14 DigraphStabilizer[101X
  
  [33X[1;0Y[29X[2XDigraphStabilizer[102X( [3Xdigraph[103X, [3Xv[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA permutation group.[133X
  
  [33X[0;0Y[10XDigraphStabilizer[110X returns the stabilizer of the vertex [3Xv[103X under of the action
  of the [2XDigraphGroup[102X ([14X7.2-10[114X) on the set of vertices of [3Xdigraph[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := DigraphFromDigraph6String("&GYHPQgWTIIPW");[127X[104X
    [4X[28X<immutable digraph with 8 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphStabilizer(D, 8);[127X[104X
    [4X[28XGroup(())[128X[104X
    [4X[25Xgap>[125X [27XDigraphStabilizer(D, 2);[127X[104X
    [4X[28XGroup(())[128X[104X
    [4X[25Xgap>[125X [27XD := DigraphMutableCopy(D);[127X[104X
    [4X[28X<mutable digraph with 8 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphStabilizer(D, 8);[127X[104X
    [4X[28XGroup(())[128X[104X
    [4X[25Xgap>[125X [27XDigraphStabilizer(D, 2);[127X[104X
    [4X[28XGroup(())[128X[104X
  [4X[32X[104X
  
  [1X7.2-15 IsIsomorphicDigraph[101X
  
  [33X[1;0Y[29X[2XIsIsomorphicDigraph[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0YThis  operation returns [9Xtrue[109X if there exists an isomorphism from the digraph
  [3Xdigraph1[103X  to the digraph [3Xdigraph2[103X. See [2XIsomorphismDigraphs[102X ([14X7.2-17[114X) for more
  information about isomorphisms of digraphs.[133X
  
  [33X[0;0YBy  default,  an  isomorphism is found using the canonical labellings of the
  digraphs  obtained  from  [5Xbliss[105X  by  Tommi  Junttila  and  Petteri Kaski. If
  [5XNautyTracesInterface[105X  is  available,  then [5Xnauty[105X by Brendan Mckay and Adolfo
  Piperno   can   be   used   instead;   see   [2XDigraphsUseBliss[102X  ([14X7.2-1[114X),  and
  [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xdigraph1 := CycleDigraph(4);[127X[104X
    [4X[28X<immutable cycle digraph with 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := CycleDigraph(5);[127X[104X
    [4X[28X<immutable cycle digraph with 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XIsIsomorphicDigraph(digraph1, digraph2);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := DigraphReverse(digraph1);[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 4 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsIsomorphicDigraph(digraph1, digraph2);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xdigraph1 := Digraph([[3], [], []]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 1 edge>[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := Digraph([[], [], [2]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 1 edge>[128X[104X
    [4X[25Xgap>[125X [27XIsIsomorphicDigraph(digraph1, digraph2);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.2-16 IsIsomorphicDigraph[101X
  
  [33X[1;0Y[29X[2XIsIsomorphicDigraph[102X( [3Xdigraph1[103X, [3Xdigraph2[103X, [3Xcolours1[103X, [3Xcolours2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0YThis  operation  tests  for  isomorphism  of  coloured  digraphs. A coloured
  digraph  can  be  specified  by  its  underlying  digraph  [3Xdigraph1[103X  and its
  colouring  [3Xcolours1[103X.  Let  [10Xn[110X  be  the  number  of  vertices of [3Xdigraph1[103X. The
  colouring [3Xcolours1[103X may have one of the following two forms:[133X
  
  [30X    [33X[0;6Ya  list  of  [10Xn[110X  integers,  where [3Xcolours[103X[10X[i][110X is the colour of vertex [10Xi[110X,
        using the colours [10X[1 .. m][110X for some [10Xm <= n[110X; or[133X
  
  [30X    [33X[0;6Ya    list    of    non-empty    disjoint    lists   whose   union   is
        [10XDigraphVertices([3Xdigraph[103X[10X)[110X,  such  that  [3Xcolours[103X[10X[i][110X  is  the list of all
        vertices with colour [10Xi[110X.[133X
  
  [33X[0;0YIf  [3Xdigraph1[103X  and [3Xdigraph2[103X are digraphs without multiple edges, and [3Xcolours1[103X
  and  [3Xcolours2[103X  are  colourings  of [3Xdigraph1[103X and [3Xdigraph2[103X, respectively, then
  this operation returns [9Xtrue[109X if there exists an isomorphism between these two
  coloured  digraphs.  See  [2XIsomorphismDigraphs[102X  ([14X7.2-18[114X) for more information
  about isomorphisms of coloured digraphs.[133X
  
  [33X[0;0YBy  default,  an  isomorphism is found using the canonical labellings of the
  digraphs  obtained  from  [5Xbliss[105X  by  Tommi  Junttila  and  Petteri Kaski. If
  [5XNautyTracesInterface[105X  is  available,  then [5Xnauty[105X by Brendan Mckay and Adolfo
  Piperno   can   be   used   instead;   see   [2XDigraphsUseBliss[102X  ([14X7.2-1[114X),  and
  [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xdigraph1 := ChainDigraph(4);[127X[104X
    [4X[28X<immutable chain digraph with 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := ChainDigraph(3);[127X[104X
    [4X[28X<immutable chain digraph with 3 vertices>[128X[104X
    [4X[25Xgap>[125X [27XIsIsomorphicDigraph(digraph1, digraph2,[127X[104X
    [4X[25X>[125X [27X [[1, 4], [2, 3]], [[1, 2], [3]]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := DigraphReverse(digraph1);[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 3 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsIsomorphicDigraph(digraph1, digraph2,[127X[104X
    [4X[25X>[125X [27X [1, 1, 1, 1], [1, 1, 1, 1]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsIsomorphicDigraph(digraph1, digraph2,[127X[104X
    [4X[25X>[125X [27X [1, 2, 2, 1], [1, 2, 2, 1]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsIsomorphicDigraph(digraph1, digraph2,[127X[104X
    [4X[25X>[125X [27X [1, 1, 2, 2], [1, 1, 2, 2]);[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X7.2-17 IsomorphismDigraphs[101X
  
  [33X[1;0Y[29X[2XIsomorphismDigraphs[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA permutation, or a pair of permutations, or [9Xfail[109X.[133X
  
  [33X[0;0YThis  operation  returns  an  isomorphism  between the digraphs [3Xdigraph1[103X and
  [3Xdigraph2[103X if one exists, else this operation returns [9Xfail[109X.[133X
  
  [33X[0;0YAn  [13Xisomorphism[113X from a digraph [3Xdigraph1[103X to a digraph [3Xdigraph2[103X is a bijection
  [10Xp[110X  from  the  vertices  of  [3Xdigraph1[103X  to  the  vertices of [3Xdigraph2[103X with the
  following  property: for all vertices [10Xi[110X and [10Xj[110X of [3Xdigraph1[103X, [10X[i, j][110X is an edge
  of [3Xdigraph1[103X if and only if [10X[i ^ p, j ^ p][110X is an edge of [3Xdigraph2[103X.[133X
  
  [33X[0;0YIf  there  exists  such an isomorphism, then this operation returns one. The
  form of this isomorphism is a permutation [10Xp[110X of the vertices of [3Xdigraph1[103X such
  that[133X
  
  [33X[0;0Y[10XOnDigraphs([3Xdigraph1[103X[10X,  p)  =  digraph2[110X.  By  default, an isomorphism is found
  using  the canonical labellings of the digraphs obtained from [5Xbliss[105X by Tommi
  Junttila and Petteri Kaski. If [5XNautyTracesInterface[105X is available, then [5Xnauty[105X
  by   Brendan   Mckay   and   Adolfo   Piperno   can  be  used  instead;  see
  [2XDigraphsUseBliss[102X ([14X7.2-1[114X), and [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xdigraph1 := CycleDigraph(4);[127X[104X
    [4X[28X<immutable cycle digraph with 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := CycleDigraph(5);[127X[104X
    [4X[28X<immutable cycle digraph with 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XIsomorphismDigraphs(digraph1, digraph2);[127X[104X
    [4X[28Xfail[128X[104X
    [4X[25Xgap>[125X [27Xdigraph1 := CompleteBipartiteDigraph(10, 5);[127X[104X
    [4X[28X<immutable complete bipartite digraph with bicomponent sizes 10 and 5>[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := CompleteBipartiteDigraph(5, 10);[127X[104X
    [4X[28X<immutable complete bipartite digraph with bicomponent sizes 5 and 10>[128X[104X
    [4X[25Xgap>[125X [27Xp := IsomorphismDigraphs(digraph1, digraph2);[127X[104X
    [4X[28X(1,6,11)(2,7,12)(3,8,13)(4,9,14)(5,10,15)[128X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(digraph1, p) = digraph2;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.2-18 IsomorphismDigraphs[101X
  
  [33X[1;0Y[29X[2XIsomorphismDigraphs[102X( [3Xdigraph1[103X, [3Xdigraph2[103X, [3Xcolours1[103X, [3Xcolours2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA permutation, or [9Xfail[109X.[133X
  
  [33X[0;0YThis  operation  searches  for  an  isomorphism between coloured digraphs. A
  coloured digraph can be specified by its underlying digraph [3Xdigraph1[103X and its
  colouring  [3Xcolours1[103X.  Let  [10Xn[110X  be  the  number  of  vertices of [3Xdigraph1[103X. The
  colouring [3Xcolours1[103X may have one of the following two forms:[133X
  
  [30X    [33X[0;6Ya  list  of  [10Xn[110X  integers,  where [3Xcolours[103X[10X[i][110X is the colour of vertex [10Xi[110X,
        using the colours [10X[1 .. m][110X for some [10Xm <= n[110X; or[133X
  
  [30X    [33X[0;6Ya    list    of    non-empty    disjoint    lists   whose   union   is
        [10XDigraphVertices([3Xdigraph[103X[10X)[110X,  such  that  [3Xcolours[103X[10X[i][110X  is  the list of all
        vertices with colour [10Xi[110X.[133X
  
  [33X[0;0YAn  [13Xisomorphism[113X  between  coloured  digraphs  is  an isomorphism between the
  underlying  digraphs  that preserves the colourings. See [2XIsomorphismDigraphs[102X
  ([14X7.2-17[114X)   for   more  information  about  isomorphisms  of  digraphs.  More
  precisely,  let  [10Xf[110X  be  an isomorphism of digraphs from the digraph [3Xdigraph1[103X
  (with colouring [3Xcolours1[103X) to the digraph [3Xdigraph2[103X (with colouring [3Xcolours2[103X),
  and let [10Xp[110X be the permutation of the vertices of [3Xdigraph1[103X that corresponds to
  [10Xf[110X.  Then  [10Xf[110X preserves the colourings of [3Xdigraph1[103X and [3Xdigraph2[103X – and hence is
  an  isomorphism  of coloured digraphs – if [10X[3Xcolours1[103X[10X[i] = [3Xcolours2[103X[10X[i ^ p][110X for
  all vertices [10Xi[110X in [3Xdigraph1[103X.[133X
  
  [33X[0;0YThis  operation  returns  such an isomorphism if one exists, else it returns
  [9Xfail[109X.[133X
  
  [33X[0;0YBy  default,  an  isomorphism is found using the canonical labellings of the
  digraphs  obtained  from  [5Xbliss[105X  by  Tommi  Junttila  and  Petteri Kaski. If
  [5XNautyTracesInterface[105X  is  available,  then [5Xnauty[105X by Brendan Mckay and Adolfo
  Piperno   can   be   used   instead;   see   [2XDigraphsUseBliss[102X  ([14X7.2-1[114X),  and
  [2XDigraphsUseNauty[102X ([14X7.2-1[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xdigraph1 := ChainDigraph(4);[127X[104X
    [4X[28X<immutable chain digraph with 4 vertices>[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := ChainDigraph(3);[127X[104X
    [4X[28X<immutable chain digraph with 3 vertices>[128X[104X
    [4X[25Xgap>[125X [27XIsomorphismDigraphs(digraph1, digraph2,[127X[104X
    [4X[25X>[125X [27X [[1, 4], [2, 3]], [[1, 2], [3]]);[127X[104X
    [4X[28Xfail[128X[104X
    [4X[25Xgap>[125X [27Xdigraph2 := DigraphReverse(digraph1);[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 3 edges>[128X[104X
    [4X[25Xgap>[125X [27Xcolours1 := [1, 1, 1, 1];;[127X[104X
    [4X[25Xgap>[125X [27Xcolours2 := [1, 1, 1, 1];;[127X[104X
    [4X[25Xgap>[125X [27Xp := IsomorphismDigraphs(digraph1, digraph2, colours1, colours2);[127X[104X
    [4X[28X(1,4)(2,3)[128X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(digraph1, p) = digraph2;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XList(DigraphVertices(digraph1), i -> colours1[i ^ p]) = colours2;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xcolours1 := [1, 1, 2, 2];;[127X[104X
    [4X[25Xgap>[125X [27Xcolours2 := [2, 2, 1, 1];;[127X[104X
    [4X[25Xgap>[125X [27Xp := IsomorphismDigraphs(digraph1, digraph2, colours1, colours2);[127X[104X
    [4X[28X(1,4)(2,3)[128X[104X
    [4X[25Xgap>[125X [27XOnDigraphs(digraph1, p) = digraph2;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XList(DigraphVertices(digraph1), i -> colours1[i ^ p]) = colours2;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsomorphismDigraphs(digraph1, digraph2,[127X[104X
    [4X[25X>[125X [27X [1, 1, 2, 2], [1, 1, 2, 2]);[127X[104X
    [4X[28Xfail[128X[104X
  [4X[32X[104X
  
  [1X7.2-19 RepresentativeOutNeighbours[101X
  
  [33X[1;0Y[29X[2XRepresentativeOutNeighbours[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YAn immutable list of lists.[133X
  
  [33X[0;0YThis  function returns the list [10Xout[110X of [13Xout-neighbours[113X of each representative
  of  the  orbits  of the action of [2XDigraphGroup[102X ([14X7.2-10[114X) on the vertex set of
  the digraph [3Xdigraph[103X.[133X
  
  [33X[0;0YMore  specifically,  if  [10Xreps[110X  is  the list of orbit representatives, then a
  vertex  [10Xj[110X  appears  in  [10Xout[i][110X  each  time  there exists an edge with source
  [10Xreps[i][110X and range [10Xj[110X in [3Xdigraph[103X.[133X
  
  [33X[0;0YIf [2XDigraphGroup[102X ([14X7.2-10[114X) is trivial, then [2XOutNeighbours[102X ([14X5.2-6[114X) is returned.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := Digraph([[127X[104X
    [4X[25X>[125X [27X [2, 1, 3, 4, 5], [3, 5], [2], [1, 2, 3, 5], [1, 2, 3, 4]]);[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 16 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphGroup(D);[127X[104X
    [4X[28XGroup(())[128X[104X
    [4X[25Xgap>[125X [27XRepresentativeOutNeighbours(D);[127X[104X
    [4X[28X[ [ 2, 1, 3, 4, 5 ], [ 3, 5 ], [ 2 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 4 ] ][128X[104X
    [4X[25Xgap>[125X [27XD := Digraph(IsMutableDigraph, [[127X[104X
    [4X[25X>[125X [27X [2, 1, 3, 4, 5], [3, 5], [2], [1, 2, 3, 5], [1, 2, 3, 4]]);[127X[104X
    [4X[28X<mutable digraph with 5 vertices, 16 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphGroup(D);[127X[104X
    [4X[28XGroup(())[128X[104X
    [4X[25Xgap>[125X [27XRepresentativeOutNeighbours(D);[127X[104X
    [4X[28X[ [ 2, 1, 3, 4, 5 ], [ 3, 5 ], [ 2 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 4 ] ][128X[104X
    [4X[25Xgap>[125X [27XD := DigraphFromDigraph6String("&GYHPQgWTIIPW");[127X[104X
    [4X[28X<immutable digraph with 8 vertices, 24 edges>[128X[104X
    [4X[25Xgap>[125X [27XG := DigraphGroup(D);;[127X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfGroup(G);[127X[104X
    [4X[28X[ (1,2)(3,4)(5,6)(7,8), (1,3,2,4)(5,7,6,8), (1,5)(2,6)(3,8)(4,7) ][128X[104X
    [4X[25Xgap>[125X [27XSet(RepresentativeOutNeighbours(D), Set);[127X[104X
    [4X[28X[ [ 2, 3, 5 ] ][128X[104X
  [4X[32X[104X
  
  [1X7.2-20 IsDigraphIsomorphism[101X
  
  [33X[1;0Y[29X[2XIsDigraphIsomorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphIsomorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X, [3Xcol1[103X, [3Xcol2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphAutomorphism[102X( [3Xdigraph[103X, [3Xx[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphAutomorphism[102X( [3Xdigraph[103X, [3Xx[103X, [3Xcol[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0Y[10XIsDigraphIsomorphism[110X  returns [9Xtrue[109X if the permutation or transformation [3Xx[103X is
  an isomorphism from the digraph [3Xsrc[103X to the digraph [3Xran[103X.[133X
  
  [33X[0;0Y[10XIsDigraphAutomorphism[110X returns [9Xtrue[109X if the permutation or transformation [3Xx[103X is
  an automorphism of the digraph [3Xdigraph[103X.[133X
  
  [33X[0;0YA  permutation or transformation [3Xx[103X is an [13Xisomorphism[113X from a digraph [3Xsrc[103X to a
  digraph [3Xran[103X if the following hold:[133X
  
  [30X    [33X[0;6Y[3Xx[103X is a bijection from the vertices of [3Xsrc[103X to those of [3Xran[103X;[133X
  
  [30X    [33X[0;6Y[10X[u  ^  [3Xx[103X[10X, v ^ [3Xx[103X[10X][110X is an edge of [3Xran[103X if and only if [10X[u, v][110X is an edge of
        [3Xsrc[103X; and[133X
  
  [30X    [33X[0;6Y[3Xx[103X fixes every [10Xi[110X which is not a vertex of [3Xsrc[103X.[133X
  
  [33X[0;0YSee also [2XAutomorphismGroup[102X ([14X7.2-2[114X).[133X
  
  [33X[0;0YIf  [3Xcol1[103X  and  [3Xcol2[103X,  or  [3Xcol[103X,  are  given,  then they must represent vertex
  colourings;  see  [2XAutomorphismGroup[102X  ([14X7.2-5[114X)  for details of the permissible
  values  for  these  arguments.  The  homomorphism  must  then  also have the
  property:[133X
  
  [30X    [33X[0;6Y[10Xcol1[i]   =   col2[i   ^   x][110X   for   all   vertices  [10Xi[110X  of  [3Xsrc[103X,  for
        [10XIsDigraphIsomorphism[110X.[133X
  
  [30X    [33X[0;6Y[10Xcol[i]   =   col[i   ^   x][110X   for  all  vertices  [10Xi[110X  of  [3Xdigraph[103X,  for
        [10XIsDigraphAutomorphism[110X.[133X
  
  [33X[0;0YFor  some  digraphs,  it  can be faster to use [10XIsDigraphAutomorphism[110X than to
  test membership in the automorphism group of [3Xdigraph[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xsrc := Digraph([[1], [1, 2], [1, 3]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphAutomorphism(src, (1, 2, 3));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphAutomorphism(src, (2, 3));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphAutomorphism(src, (2, 3), [2, 1, 1]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphAutomorphism(src, (2, 3), [2, 2, 1]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphAutomorphism(src, (2, 3)(4, 5));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphAutomorphism(src, (1, 4));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphAutomorphism(src, ());[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xran := Digraph([[2, 1], [2], [2, 3]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphIsomorphism(src, ran, (1, 2));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphIsomorphism(ran, src, (1, 2));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphIsomorphism(ran, src, (1, 2));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphIsomorphism(src, Digraph([[3], [1, 3], [2]]), (1, 2, 3));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphIsomorphism(src, ran, (1, 2), [1, 2, 3], [2, 1, 3]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphIsomorphism(src, ran, (1, 2), [1, 2, 2], [2, 1, 3]);[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X7.2-21 IsDigraphColouring[101X
  
  [33X[1;0Y[29X[2XIsDigraphColouring[102X( [3Xdigraph[103X, [3Xlist[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphColouring[102X( [3Xdigraph[103X, [3Xt[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0YThe  operation  [10XIsDigraphColouring[110X  verifies  whether  or  not the list [3Xlist[103X
  describes a proper colouring of the digraph [3Xdigraph[103X.[133X
  
  [33X[0;0YA  list  [3Xlist[103X  describes  a  [13Xproper  colouring[113X  of a digraph [3Xdigraph[103X if [3Xlist[103X
  consists  of  positive  integers,  the  length  of [3Xlist[103X equals the number of
  vertices  in  [3Xdigraph[103X,  and  for any vertices [10Xu, v[110X of [3Xdigraph[103X if [10Xu[110X and [10Xv[110X are
  adjacent, then [10X[3Xlist[103X[10X[u] >< [3Xlist[103X[10X[v][110X.[133X
  
  [33X[0;0YA  transformation  [3Xt[103X  describes  a proper colouring of a digraph [3Xdigraph[103X, if
  [10XImageListOfTransformation([3Xt[103X[10X,   DigraphNrVertices([3Xdigraph[103X[10X))[110X   is   a   proper
  colouring of [3Xdigraph[103X.[133X
  
  [33X[0;0YSee also [2XIsDigraphHomomorphism[102X ([14X7.3-10[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := JohnsonDigraph(5, 3);[127X[104X
    [4X[28X<immutable symmetric digraph with 10 vertices, 60 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphColouring(D, [1, 2, 3, 3, 2, 1, 4, 5, 6, 7]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphColouring(D, [1, 2, 3, 3, 2, 1, 2, 5, 6, 7]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphColouring(D, [1, 2, 3, 3, 2, 1, 2, 5, 6, -1]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphColouring(D, [1, 2, 3]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphColouring(D, IdentityTransformation);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.2-22 MaximalCommonSubdigraph[101X
  
  [33X[1;0Y[29X[2XMaximalCommonSubdigraph[102X( [3XD1[103X, [3XD2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list containing a digraph and two transformations.[133X
  
  [33X[0;0YIf    [3XD1[103X    and    [3XD2[103X    are   digraphs   without   multiple   edges,   then
  [10XMaximalCommonSubdigraph[110X  returns  a  maximal  common subgraph [10XM[110X of [3XD1[103X and [3XD2[103X
  with  the  maximum  number  of vertices. So [10XM[110X is a digraph which embeds into
  both  [3XD1[103X  and [3XD2[103X and has the largest number of vertices among such digraphs.
  It  returns  a list [10X[M, t1, t2][110X where [10XM[110X is the maximal common subdigraph and
  [10Xt1, t2[110X are transformations embedding [10XM[110X into [3XD1[103X and [3XD2[103X respectively.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XMaximalCommonSubdigraph(PetersenGraph(), CompleteDigraph(10));[127X[104X
    [4X[28X[ <immutable digraph with 2 vertices, 2 edges>,[128X[104X
    [4X[28X  IdentityTransformation, IdentityTransformation ][128X[104X
    [4X[25Xgap>[125X [27XMaximalCommonSubdigraph(PetersenGraph(),[127X[104X
    [4X[25X>[125X [27XDigraphSymmetricClosure(CycleDigraph(5)));[127X[104X
    [4X[28X[ <immutable digraph with 5 vertices, 10 edges>,[128X[104X
    [4X[28X  IdentityTransformation, IdentityTransformation ][128X[104X
    [4X[25Xgap>[125X [27XMaximalCommonSubdigraph(NullDigraph(0), CompleteDigraph(10));[127X[104X
    [4X[28X[ <immutable empty digraph with 0 vertices>, IdentityTransformation,[128X[104X
    [4X[28X  IdentityTransformation ][128X[104X
  [4X[32X[104X
  
  [1X7.2-23 MinimalCommonSuperdigraph[101X
  
  [33X[1;0Y[29X[2XMinimalCommonSuperdigraph[102X( [3XD1[103X, [3XD2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list containing a digraph and two transformations.[133X
  
  [33X[0;0YIf    [3XD1[103X    and    [3XD2[103X    are   digraphs   without   multiple   edges,   then
  [10XMinimalCommonSuperdigraph[110X  returns a minimal common superdigraph [10XM[110X of [3XD1[103X and
  [3XD2[103X with the minimum number of vertices. So [10XM[110X is a digraph into which both [3XD1[103X
  and [3XD2[103X embed and has the smallest number of vertices among such digraphs. It
  returns  a  list  [10X[M, t1, t2][110X where [10XM[110X is the minimal common superdigraph and
  [10Xt1, t2[110X are transformations embedding [3XD1[103X and [3XD2[103X respectively into [10XM[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XMinimalCommonSuperdigraph(PetersenGraph(), CompleteDigraph(10));[127X[104X
    [4X[28X[ <immutable digraph with 18 vertices, 118 edges>,[128X[104X
    [4X[28X  IdentityTransformation,[128X[104X
    [4X[28X  Transformation( [ 1, 2, 11, 12, 13, 14, 15, 16, 17, 18, 11, 12, 13,[128X[104X
    [4X[28X      14, 15, 16, 17, 18 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XMinimalCommonSuperdigraph(PetersenGraph(),[127X[104X
    [4X[25X>[125X [27XDigraphSymmetricClosure(CycleDigraph(5)));[127X[104X
    [4X[28X[ <immutable digraph with 10 vertices, 30 edges>,[128X[104X
    [4X[28X  IdentityTransformation, IdentityTransformation ][128X[104X
    [4X[25Xgap>[125X [27XMinimalCommonSuperdigraph(NullDigraph(0), CompleteDigraph(10));[127X[104X
    [4X[28X[ <immutable digraph with 10 vertices, 90 edges>,[128X[104X
    [4X[28X  IdentityTransformation, IdentityTransformation ][128X[104X
  [4X[32X[104X
  
  [1X7.2-24 DigraphColourRefinement[101X
  
  [33X[1;0Y[29X[2XDigraphColourRefinement[102X( [3Xdigraph[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list of integers.[133X
  
  [33X[0;0YColour  refinement  is  a  method  of colouring a digraph such that it has a
  'stable  colouring'.  That is, for a colour, every node with that colour has
  an identical configuration of coloured neighbours. This means that all nodes
  with  the  same  colour  have  equal  numbers  of neighbours of each colour.
  [10XDigraphColourRefinement[110X  considers the out-neighbours and in-neighbours of a
  node  separately,  meaning  the nodes of a certain colour must have an equal
  number   of   out-neighbours   of  each  colour,  and  an  equal  number  of
  in-neighbours of each colour.[133X
  
  [33X[0;0Y[10XDigraphColourRefinement[110X  returns  the colouring as a list where the value at
  the  ith  position  is  the  colour  of  node i. The time complexity of this
  algorithm is [22XO(n^2 log n)[122X.[133X
  
  [33X[0;0YBecause  the  labels of the vertices are not used in any capacity during the
  refinement  process (i.e. to determine which cells to refine), the colouring
  produced  is  canonical.  This  means that for two isomorphic digraphs, they
  would  produce  the  same colouring. Identical colourings do not necessarily
  prove  that  two digraphs are isomorphic, but non-identical colourings would
  prove  that  they  aren't.  While  the colouring produced for two isomorphic
  digraphs  will be identical, the output of [10XDigraphColourRefinement[110X will not,
  as  the  list  produced is ordered by vertex labels. This is demonstrated in
  the examples below.[133X
  
  [33X[0;0YSee also [2XDigraphColouring[102X ([14X7.3-15[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := Digraph([[3], [], [1, 9], [], [10], [7, 8, 9], [6, 8],[127X[104X
    [4X[25X>[125X [27X[6, 7], [3, 6, 10], [5, 9]]);;[127X[104X
    [4X[25Xgap>[125X [27XDigraphColourRefinement(D);[127X[104X
    [4X[28X[ 2, 1, 4, 1, 2, 5, 3, 3, 6, 4 ][128X[104X
    [4X[25Xgap>[125X [27XD2 := Digraph([[6, 7], [], [8, 9], [], [10], [1, 7, 9], [6, 1],[127X[104X
    [4X[25X>[125X [27X[3], [3, 6, 10], [5, 9]]);;[127X[104X
    [4X[25Xgap>[125X [27XDigraphColourRefinement(D2);[127X[104X
    [4X[28X[ 3, 1, 4, 1, 2, 5, 3, 2, 6, 4 ][128X[104X
    [4X[25Xgap>[125X [27XDigraphColourRefinement(Digraph([[], [1], [1], [1]]));[127X[104X
    [4X[28X[ 1, 2, 2, 2 ][128X[104X
  [4X[32X[104X
  
  
  [1X7.3 [33X[0;0YHomomorphisms of digraphs[133X[101X
  
  [33X[0;0YThe  following  methods  exist to find homomorphisms between digraphs. If an
  argument  to one of these methods is a digraph with multiple edges, then the
  multiplicity  of  edges will be ignored in order to perform the calculation;
  the digraph will be treated as if it has no multiple edges.[133X
  
  [1X7.3-1 HomomorphismDigraphsFinder[101X
  
  [33X[1;0Y[29X[2XHomomorphismDigraphsFinder[102X( [3XD1[103X, [3XD2[103X, [3Xhook[103X, [3Xuser_param[103X, [3Xmax_results[103X, [3Xhint[103X, [3Xinjective[103X, [3Ximage[103X, [3Xpartial_map[103X, [3Xcolors1[103X, [3Xcolors2[103X[, [3Xorder[103X, [3Xaut_grp[103X] ) [32X function[133X
  [6XReturns:[106X  [33X[0;10YThe argument [3Xuser_param[103X.[133X
  
  [33X[0;0YThis  function  finds  homomorphisms  from  the digraph [3XD1[103X to the digraph [3XD2[103X
  subject to the conditions imposed by the other arguments as described below.[133X
  
  [33X[0;0YIf  [10Xf[110X  and  [10Xg[110X  are homomorphisms found by [10XHomomorphismDigraphsFinder[110X, then [10Xf[110X
  cannot  be  obtained from [10Xg[110X by right multiplying by an automorphism of [3XD2[103X in
  [3Xaut_grp[103X.[133X
  
  [8X[3Xhook[103X[8X[108X
        [33X[0;6YThis argument should be a function or [9Xfail[109X.[133X
  
        [33X[0;6YIf [3Xhook[103X is a function, then it must have two arguments [3Xuser_param[103X (see
        below)  and  a  transformation  [10Xt[110X. The function [10X[3Xhook[103X[10X([3Xuser_param[103X[10X, t)[110X is
        called    every    time   a   new   homomorphism   [10Xt[110X   is   found   by
        [10XHomomorphismDigraphsFinder[110X.   If   the  function  returns  [9Xtrue[109X,  then
        [10XHomomorphismDigraphsFinder[110X   stops  and  does  not  find  any  further
        homomorphisms. This feature might be useful if you are searching for a
        homomorphism that satisfies some condition that you cannot specify via
        the other arguments to [10XHomomorphismDigraphsFinder[110X.[133X
  
        [33X[0;6YIf  [3Xhook[103X  is  [9Xfail[109X,  then a default function is used which simply adds
        every   new   homomorphism   found  by  [10XHomomorphismDigraphsFinder[110X  to
        [3Xuser_param[103X, which must be a mutable list in this case.[133X
  
  [8X[3Xuser_param[103X[8X[108X
        [33X[0;6YIf  [3Xhook[103X  is  a  function,  then [3Xuser_param[103X can be any [5XGAP[105X object. The
        object  [3Xuser_param[103X is used as the first argument of the function [3Xhook[103X.
        For  example,  [3Xuser_param[103X  might  be  a  transformation semigroup, and
        [10X[3Xhook[103X[10X([3Xuser_param[103X[10X,  t)[110X  might  set  [3Xuser_param[103X  to  be  the  closure  of
        [3Xuser_param[103X and [10Xt[110X.[133X
  
        [33X[0;6YIf  the  value of [3Xhook[103X is [9Xfail[109X, then the value of [3Xuser_param[103X must be a
        mutable list.[133X
  
  [8X[3Xmax_results[103X[8X[108X
        [33X[0;6YThis   argument   should   be   a   positive   integer   or  [9Xinfinity[109X.
        [10XHomomorphismDigraphsFinder[110X  will return after it has found [3Xmax_results[103X
        homomorphisms or the search is complete, whichever happens first.[133X
  
  [8X[3Xhint[103X[8X[108X
        [33X[0;6YThis argument should be a positive integer or [9Xfail[109X.[133X
  
        [33X[0;6YIf  [3Xhint[103X is a positive integer, then only homorphisms of rank [3Xhint[103X are
        found.[133X
  
        [33X[0;6YIf  [3Xhint[103X  is  [9Xfail[109X,  then  no  restriction  is  put  on  the  rank  of
        homomorphisms found.[133X
  
  [8X[3Xinjective[103X[8X[108X
        [33X[0;6YThis  argument  should be [10X0[110X, [10X1[110X, or [10X2[110X. If it is [10X2[110X, then only embeddings
        are  found,  if  it is [10X1[110X, then only injective homomorphisms are found,
        and if it is [10X0[110X there are no restrictions imposed by this argument.[133X
  
        [33X[0;6YFor backwards compatibility, [3Xinjective[103X can also be [9Xfalse[109X or [9Xtrue[109X which
        correspond  to the values [10X0[110X and [10X1[110X described in the previous paragraph,
        respectively.[133X
  
  [8X[3Ximage[103X[8X[108X
        [33X[0;6YThis  argument  should  be  a  subset of the vertices of the graph [3XD2[103X.
        [10XHomomorphismDigraphsFinder[110X  only  finds  homomorphisms  from [3XD1[103X to the
        subgraph of [3XD2[103X induced by the vertices [3Ximage[103X.[133X
  
        [33X[0;6YThe  returned  homomorphisms  (if any) are still "up to the action" of
        the group specified by [3Xaut_grp[103X (which is the entire automorphism group
        by  default).  This might generate unexpected results. For example, if
        [3XD1[103X  has  automorphism group where one orbit consists of, say, [10X1[110X and [10X2[110X,
        then    [10XHomomorphismDigraphsFinder[110X   will   only   attempt   to   find
        homomorphisms  mapping  [10X1[110X to [10X1[110X, and if there are no such homomorphisms
        with  image set equal to [3Ximage[103X, then no homomorphisms will be returned
        (even  if  there  is  a homomorphism from [3XD1[103X to [3XD2[103X mapping [10X1[110X to [10X2[110X). To
        ensure  that  that [12Xall[112X homomorphisms with image set equal to [3Ximage[103X are
        considered  it  is  necessary  for the last argument [3Xaut_grp[103X to be the
        trivial permutation group.[133X
  
  [8X[3Xpartial_map[103X[8X[108X
        [33X[0;6YThis  argument  should be a partial map from [3XD1[103X to [3XD2[103X, that is, a (not
        necessarily  dense)  list  of  vertices of the digraph [3XD2[103X of length no
        greater    than    the    number   vertices   in   the   digraph   [3XD1[103X.
        [10XHomomorphismDigraphsFinder[110X    only   finds   homomorphisms   extending
        [3Xpartial_map[103X (if any).[133X
  
  [8X[3Xcolors1[103X[8X[108X
        [33X[0;6YThis should be a list representing possible colours of vertices in the
        digraph   [3XD1[103X;   see  [2XAutomorphismGroup[102X  ([14X7.2-5[114X)  for  details  of  the
        permissible values for this argument.[133X
  
  [8X[3Xcolors2[103X[8X[108X
        [33X[0;6YThis should be a list representing possible colours of vertices in the
        digraph   [3XD2[103X;   see  [2XAutomorphismGroup[102X  ([14X7.2-5[114X)  for  details  of  the
        permissible values for this argument.[133X
  
  [8X[3Xorder[103X[8X[108X
        [33X[0;6YThe  optional  argument  [3Xorder[103X  specifies the order the vertices in [3XD1[103X
        appear  in  the  search for homomorphisms. The value of this parameter
        can  have  a  large impact on the runtime of the function. It seems in
        many    cases   to   be   a   good   idea   for   this   to   be   the
        [2XDigraphWelshPowellOrder[102X  ([14X7.3-17[114X),  i.e. vertices ordered from highest
        to lowest degree.[133X
  
  [8X[3Xaut_grp[103X[8X[108X
        [33X[0;6YThe optional argument [3Xaut_grp[103X should be a subgroup of the automorphism
        group  of  [3XD2[103X.  This  function  returns  unique representatives of the
        homomorphisms  found  up  to  right multiplication by [3Xaut_grp[103X. If this
        argument  is  not specific, it defaults to the full automorphism group
        of [3XD2[103X, which may be costly to calculate.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := ChainDigraph(10);[127X[104X
    [4X[28X<immutable chain digraph with 10 vertices>[128X[104X
    [4X[25Xgap>[125X [27XD := DigraphSymmetricClosure(D);[127X[104X
    [4X[28X<immutable symmetric digraph with 10 vertices, 18 edges>[128X[104X
    [4X[25Xgap>[125X [27XHomomorphismDigraphsFinder(D, D, fail, [], infinity, 2, 0,[127X[104X
    [4X[25X>[125X [27X[3, 4], [], fail, fail);[127X[104X
    [4X[28X#I  WARNING you are trying to find homomorphisms by specifying a subset[128X[104X
    [4X[28Xof the vertices of the target digraph. This might lead to unexpected[128X[104X
    [4X[28Xresults! If this happens, try passing Group(()) as the last argument.[128X[104X
    [4X[28XPlease see the documentation of HomomorphismDigraphsFinder for details.[128X[104X
    [4X[28X[ Transformation( [ 3, 4, 3, 4, 3, 4, 3, 4, 3, 4 ] ),[128X[104X
    [4X[28X  Transformation( [ 4, 3, 4, 3, 4, 3, 4, 3, 4, 3 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XD2 := CompleteDigraph(6);;[127X[104X
    [4X[25Xgap>[125X [27XHomomorphismDigraphsFinder(D, D2, fail, [], 1, fail, 0,[127X[104X
    [4X[25X>[125X [27X[1 .. 6], [1, 2, 1], fail, fail);[127X[104X
    [4X[28X[ Transformation( [ 1, 2, 1, 3, 4, 5, 6, 1, 2, 1 ] ) ][128X[104X
    [4X[25Xgap>[125X [27Xfunc := function(user_param, t)[127X[104X
    [4X[25X>[125X [27XAdd(user_param, t * user_param[1]);[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XHomomorphismDigraphsFinder(D, D2, func, [Transformation([2, 2])],[127X[104X
    [4X[25X>[125X [27X3, fail, 0, [1 .. 6], [1, 2, 1], fail, fail);[127X[104X
    [4X[28X[ Transformation( [ 2, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 2, 2, 3, 4, 5, 6, 2, 2, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 2, 2, 3, 4, 5, 6, 2, 2, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 2, 2, 3, 4, 5, 6, 2, 2, 4 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XHomomorphismDigraphsFinder(NullDigraph(2), NullDigraph(3), fail,[127X[104X
    [4X[25X>[125X [27X[], infinity, fail, 1, [1, 2, 3], fail, fail, fail, fail,[127X[104X
    [4X[25X>[125X [27XGroup(()));[127X[104X
    [4X[28X[ IdentityTransformation, Transformation( [ 1, 3, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 1 ] ), Transformation( [ 2, 3, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 1, 3 ] ), Transformation( [ 3, 2, 3 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XHomomorphismDigraphsFinder(NullDigraph(2), NullDigraph(3), fail,[127X[104X
    [4X[25X>[125X [27X[], infinity, fail, 1, [1, 2, 3], fail, fail, fail, fail,[127X[104X
    [4X[25X>[125X [27XGroup((1, 2)));[127X[104X
    [4X[28X[ IdentityTransformation, Transformation( [ 1, 3, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 1, 3 ] ) ][128X[104X
  [4X[32X[104X
  
  [1X7.3-2 DigraphHomomorphism[101X
  
  [33X[1;0Y[29X[2XDigraphHomomorphism[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA transformation, or [9Xfail[109X.[133X
  
  [33X[0;0YA homomorphism from [3Xdigraph1[103X to [3Xdigraph2[103X is a mapping from the vertex set of
  [3Xdigraph1[103X  to  a  subset of the vertices of [3Xdigraph2[103X, such that every pair of
  vertices  [10X[i,j][110X which has an edge [10Xi->j[110X is mapped to a pair of vertices [10X[a,b][110X
  which  has an edge [10Xa->b[110X. Note that non-adjacent vertices can still be mapped
  to adjacent vertices.[133X
  
  [33X[0;0Y[10XDigraphHomomorphism[110X  returns  a  single  homomorphism  between  [3Xdigraph1[103X and
  [3Xdigraph2[103X if it exists, otherwise it returns [9Xfail[109X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr1 := ChainDigraph(3);;[127X[104X
    [4X[25Xgap>[125X [27Xgr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]);[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphHomomorphism(gr1, gr1);[127X[104X
    [4X[28XIdentityTransformation[128X[104X
    [4X[25Xgap>[125X [27Xmap := DigraphHomomorphism(gr1, gr2);[127X[104X
    [4X[28XTransformation( [ 3, 1, 5, 4, 5 ] )[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphHomomorphism(gr1, gr2, map);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.3-3 HomomorphismsDigraphs[101X
  
  [33X[1;0Y[29X[2XHomomorphismsDigraphs[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XHomomorphismsDigraphsRepresentatives[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list of transformations.[133X
  
  [33X[0;0Y[10XHomomorphismsDigraphsRepresentatives[110X finds every [2XDigraphHomomorphism[102X ([14X7.3-2[114X)
  between  [3Xdigraph1[103X  and [3Xdigraph2[103X, up to right multiplication by an element of
  the   [2XAutomorphismGroup[102X   ([14X7.2-2[114X)   of   [3Xdigraph2[103X.  In  other  words,  every
  homomorphism  [10Xf[110X  between  [3Xdigraph1[103X  and  [3Xdigraph2[103X  can  be  written  as  the
  composition    [10Xf    =    g    *    x[110X,    where    [10Xg[110X    is    one    of   the
  [10XHomomorphismsDigraphsRepresentatives[110X and [10Xx[110X is an automorphism of [3Xdigraph2[103X.[133X
  
  [33X[0;0Y[10XHomomorphismsDigraphs[110X   returns   all  homomorphisms  between  [3Xdigraph1[103X  and
  [3Xdigraph2[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr1 := ChainDigraph(3);;[127X[104X
    [4X[25Xgap>[125X [27Xgr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]);[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XHomomorphismsDigraphs(gr1, gr2);[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 1 ] ), Transformation( [ 1, 3, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 1, 5, 4, 4, 5 ] ), Transformation( [ 2, 2, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 1, 3 ] ), Transformation( [ 3, 1, 5, 4, 5 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 3, 1 ] ), Transformation( [ 3, 3, 3 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XHomomorphismsDigraphsRepresentatives(gr1, CompleteDigraph(3));[127X[104X
    [4X[28X[ Transformation( [ 2, 1 ] ), Transformation( [ 2, 1, 2 ] ) ][128X[104X
  [4X[32X[104X
  
  [1X7.3-4 DigraphMonomorphism[101X
  
  [33X[1;0Y[29X[2XDigraphMonomorphism[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA transformation, or [9Xfail[109X.[133X
  
  [33X[0;0Y[10XDigraphMonomorphism[110X  returns  a single [13Xinjective[113X [2XDigraphHomomorphism[102X ([14X7.3-2[114X)
  between [3Xdigraph1[103X and [3Xdigraph2[103X if one exists, otherwise it returns [9Xfail[109X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr1 := ChainDigraph(3);;[127X[104X
    [4X[25Xgap>[125X [27Xgr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]);[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphMonomorphism(gr1, gr1);[127X[104X
    [4X[28XIdentityTransformation[128X[104X
    [4X[25Xgap>[125X [27XDigraphMonomorphism(gr1, gr2);[127X[104X
    [4X[28XTransformation( [ 3, 1, 5, 4, 5 ] )[128X[104X
  [4X[32X[104X
  
  [1X7.3-5 MonomorphismsDigraphs[101X
  
  [33X[1;0Y[29X[2XMonomorphismsDigraphs[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XMonomorphismsDigraphsRepresentatives[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list of transformations.[133X
  
  [33X[0;0YThese  operations  behave  the  same  as  [2XHomomorphismsDigraphs[102X  ([14X7.3-3[114X) and
  [2XHomomorphismsDigraphsRepresentatives[102X   ([14X7.3-3[114X),   except  they  only  return
  [13Xinjective[113X homomorphisms.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr1 := ChainDigraph(3);;[127X[104X
    [4X[25Xgap>[125X [27Xgr2 := Digraph([[3, 5], [2], [3, 1], [], [4]]);[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XMonomorphismsDigraphs(gr1, gr2);[127X[104X
    [4X[28X[ Transformation( [ 1, 5, 4, 4, 5 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 1, 5, 4, 5 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XMonomorphismsDigraphsRepresentatives(gr1, CompleteDigraph(3));[127X[104X
    [4X[28X[ Transformation( [ 2, 1 ] ) ][128X[104X
  [4X[32X[104X
  
  [1X7.3-6 DigraphEpimorphism[101X
  
  [33X[1;0Y[29X[2XDigraphEpimorphism[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA transformation, or [9Xfail[109X.[133X
  
  [33X[0;0Y[10XDigraphEpimorphism[110X  returns  a single [13Xsurjective[113X [2XDigraphHomomorphism[102X ([14X7.3-2[114X)
  between [3Xdigraph1[103X and [3Xdigraph2[103X if one exists, otherwise it returns [9Xfail[109X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr1 := DigraphReverse(ChainDigraph(4));[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 3 edges>[128X[104X
    [4X[25Xgap>[125X [27Xgr2 := DigraphRemoveEdge(CompleteDigraph(3), [1, 2]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphEpimorphism(gr2, gr1);[127X[104X
    [4X[28Xfail[128X[104X
    [4X[25Xgap>[125X [27XDigraphEpimorphism(gr1, gr2);[127X[104X
    [4X[28XTransformation( [ 3, 1, 2, 3 ] )[128X[104X
  [4X[32X[104X
  
  [1X7.3-7 EpimorphismsDigraphs[101X
  
  [33X[1;0Y[29X[2XEpimorphismsDigraphs[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XEpimorphismsDigraphsRepresentatives[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list of transformations.[133X
  
  [33X[0;0YThese  operations  behave  the  same  as  [2XHomomorphismsDigraphs[102X  ([14X7.3-3[114X) and
  [2XHomomorphismsDigraphsRepresentatives[102X   ([14X7.3-3[114X),   except  they  only  return
  [13Xsurjective[113X homomorphisms.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr1 := DigraphReverse(ChainDigraph(4));[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 3 edges>[128X[104X
    [4X[25Xgap>[125X [27Xgr2 := DigraphSymmetricClosure(CycleDigraph(3));[127X[104X
    [4X[28X<immutable symmetric digraph with 3 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XEpimorphismsDigraphsRepresentatives(gr1, gr2);[127X[104X
    [4X[28X[ Transformation( [ 3, 1, 2, 1 ] ), Transformation( [ 3, 1, 2, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 1, 2, 3 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XEpimorphismsDigraphs(gr1, gr2);[127X[104X
    [4X[28X[ Transformation( [ 1, 2, 1, 3 ] ), Transformation( [ 1, 2, 3, 1 ] ),[128X[104X
    [4X[28X  Transformation( [ 1, 2, 3, 2 ] ), Transformation( [ 1, 3, 1, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 1, 3, 2, 1 ] ), Transformation( [ 1, 3, 2, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 1, 2, 3 ] ), Transformation( [ 2, 1, 3, 1 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 1, 3, 2 ] ), Transformation( [ 2, 3, 1, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 3, 1, 3 ] ), Transformation( [ 2, 3, 2, 1 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 1, 2, 1 ] ), Transformation( [ 3, 1, 2, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 1, 3, 2 ] ), Transformation( [ 3, 2, 1, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 2, 1, 3 ] ), Transformation( [ 3, 2, 3, 1 ] ) ][128X[104X
  [4X[32X[104X
  
  [1X7.3-8 DigraphEmbedding[101X
  
  [33X[1;0Y[29X[2XDigraphEmbedding[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA transformation, or [9Xfail[109X.[133X
  
  [33X[0;0YAn  embedding  of  a  digraph  [3Xdigraph1[103X  into  another digraph [3Xdigraph2[103X is a
  [2XDigraphMonomorphism[102X   ([14X7.3-4[114X)  from  [3Xdigraph1[103X  to  [3Xdigraph2[103X  which  has  the
  additional property that a pair of vertices [10X[i, j][110X which have no edge [10Xi -> j[110X
  in  [3Xdigraph1[103X are mapped to a pair of vertices [10X[a, b][110X which have no edge [10Xa->b[110X
  in [3Xdigraph2[103X.[133X
  
  [33X[0;0YIn  other  words,  an  embedding  [10Xt[110X  is  an isomorphism from [3Xdigraph1[103X to the
  [2XInducedSubdigraph[102X ([14X3.3-3[114X) of [3Xdigraph2[103X on the image of [10Xt[110X.[133X
  
  [33X[0;0Y[10XDigraphEmbedding[110X  returns  a  single  embedding  if one exists, otherwise it
  returns [9Xfail[109X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr := ChainDigraph(3);[127X[104X
    [4X[28X<immutable chain digraph with 3 vertices>[128X[104X
    [4X[25Xgap>[125X [27XDigraphEmbedding(gr, CompleteDigraph(4));[127X[104X
    [4X[28Xfail[128X[104X
    [4X[25Xgap>[125X [27XDigraphEmbedding(gr, Digraph([[3], [1, 4], [1], [3]]));[127X[104X
    [4X[28XTransformation( [ 2, 4, 3, 4 ] )[128X[104X
  [4X[32X[104X
  
  [1X7.3-9 EmbeddingsDigraphs[101X
  
  [33X[1;0Y[29X[2XEmbeddingsDigraphs[102X( [3XD1[103X, [3XD2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XEmbeddingsDigraphsRepresentatives[102X( [3XD1[103X, [3XD2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list of transformations.[133X
  
  [33X[0;0YThese  operations  behave  the  same  as  [2XHomomorphismsDigraphs[102X  ([14X7.3-3[114X) and
  [2XHomomorphismsDigraphsRepresentatives[102X   ([14X7.3-3[114X),   except  they  only  return
  embeddings of [3XD1[103X into [3XD2[103X.[133X
  
  [33X[0;0YSee also [2XIsDigraphEmbedding[102X ([14X7.3-11[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD1 := NullDigraph(2);[127X[104X
    [4X[28X<immutable empty digraph with 2 vertices>[128X[104X
    [4X[25Xgap>[125X [27XD2 := CycleDigraph(5);[127X[104X
    [4X[28X<immutable cycle digraph with 5 vertices>[128X[104X
    [4X[25Xgap>[125X [27XEmbeddingsDigraphsRepresentatives(D1, D2);[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 3 ] ), Transformation( [ 1, 4, 3, 4 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XEmbeddingsDigraphs(D1, D2);[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 3 ] ), Transformation( [ 1, 4, 3, 4 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 4, 4, 5, 1 ] ),[128X[104X
    [4X[28X  Transformation( [ 2, 5, 4, 5, 1 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 1, 5, 1, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 5, 5, 1, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 4, 1, 1, 2, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 4, 2, 1, 2, 3 ] ),[128X[104X
    [4X[28X  Transformation( [ 5, 2, 2, 3, 4 ] ),[128X[104X
    [4X[28X  Transformation( [ 5, 3, 2, 3, 4 ] ) ][128X[104X
  [4X[32X[104X
  
  [1X7.3-10 IsDigraphHomomorphism[101X
  
  [33X[1;0Y[29X[2XIsDigraphHomomorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphHomomorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X, [3Xcol1[103X, [3Xcol2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphEpimorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphEpimorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X, [3Xcol1[103X, [3Xcol2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphMonomorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphMonomorphism[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X, [3Xcol1[103X, [3Xcol2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphEndomorphism[102X( [3Xdigraph[103X, [3Xx[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphEndomorphism[102X( [3Xdigraph[103X, [3Xx[103X, [3Xcol[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0Y[10XIsDigraphHomomorphism[110X returns [9Xtrue[109X if the permutation or transformation [3Xx[103X is
  a homomorphism from the digraph [3Xsrc[103X to the digraph [3Xran[103X.[133X
  
  [33X[0;0Y[10XIsDigraphEpimorphism[110X  returns [9Xtrue[109X if the permutation or transformation [3Xx[103X is
  a surjective homomorphism from the digraph [3Xsrc[103X to the digraph [3Xran[103X.[133X
  
  [33X[0;0Y[10XIsDigraphMonomorphism[110X returns [9Xtrue[109X if the permutation or transformation [3Xx[103X is
  an injective homomorphism from the digraph [3Xsrc[103X to the digraph [3Xran[103X.[133X
  
  [33X[0;0Y[10XIsDigraphEndomorphism[110X returns [9Xtrue[109X if the permutation or transformation [3Xx[103X is
  an endomorphism of the digraph [3Xdigraph[103X.[133X
  
  [33X[0;0YA  permutation or transformation [3Xx[103X is a [13Xhomomorphism[113X from a digraph [3Xsrc[103X to a
  digraph [3Xran[103X if the following hold:[133X
  
  [30X    [33X[0;6Y[10X[u  ^  [3Xx[103X[10X,  v ^ [3Xx[103X[10X][110X is an edge of [3Xran[103X whenever [10X[u, v][110X is an edge of [3Xsrc[103X;
        and[133X
  
  [30X    [33X[0;6Y[3Xx[103X  maps  the  vertices of [3Xsrc[103X to a subset of the vertices of [3Xran[103X, i.e.
        [10XIsSubset(DigraphVertices([3Xran[103X[10X),   OnSets(DigraphVertices([3Xsrc[103X[10X),  [3Xx[103X[10X))[110X  is
        [9Xtrue[109X.[133X
  
  [33X[0;0YNote  that  if [10Xi[110X is any integer greater than [10XDigraphNrVertice([3Xsrc[103X[10X)[110X, then the
  action  of  [3Xx[103X  on  [10Xi[110X is ignored by this function. One consequence of this is
  that  distinct  transformations  or  permutations  might  represent the same
  homomorphism. For example, if [3Xsrc[103X and [3Xran[103X are [10XCycleDigraph(2)[110X, then both the
  permutations [10X(1, 2)[110X and [10X(1, 2)(3, 4)[110X represent the same automorphism of [3Xsrc[103X.[133X
  
  [33X[0;0YSee also [2XGeneratorsOfEndomorphismMonoid[102X ([14X7.3-14[114X).[133X
  
  [33X[0;0YIf  [3Xcol1[103X  and  [3Xcol2[103X,  or  [3Xcol[103X,  are  given,  then they must represent vertex
  colourings;  see  [2XAutomorphismGroup[102X  ([14X7.2-5[114X)  for details of the permissible
  values  for  these  argument.  The  homomorphism  must  then  also  have the
  property:[133X
  
  [30X    [33X[0;6Y[10Xcol[i]  =  col[i  ^  x][110X  for all vertices [10Xi[110X of [3Xdigraph[103X, in the case of
        [10XIsDigraphEndomorphism[110X.[133X
  
  [30X    [33X[0;6Y[10Xcol1[i]  =  col2[i ^ x][110X for all vertices [10Xi[110X of [3Xsrc[103X, in the cases of the
        other operations.[133X
  
  [33X[0;0YSee also [2XDigraphsRespectsColouring[102X ([14X7.3-13[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xsrc := Digraph([[1], [1, 2], [1, 3]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27Xran := Digraph([[1], [1, 2]]);[127X[104X
    [4X[28X<immutable digraph with 2 vertices, 3 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphHomomorphism(src, ran, Transformation([1, 2, 2]));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphHomomorphism(src, ran, Transformation([2, 1, 2]));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphHomomorphism(src, ran, Transformation([3, 3, 3]));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphHomomorphism(src, src, Transformation([3, 3, 3]));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphHomomorphism(src, ran, Transformation([1, 2, 2]),[127X[104X
    [4X[25X>[125X [27X                         [1, 2, 2], [1, 2]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphHomomorphism(src, ran, Transformation([1, 2, 2]),[127X[104X
    [4X[25X>[125X [27X                         [2, 1, 1], [1, 2]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEndomorphism(src, Transformation([3, 3, 3]));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEndomorphism(src, Transformation([3, 3, 3]), [1, 1, 1]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEndomorphism(src, Transformation([3, 3, 3]), [1, 1, 2]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEpimorphism(src, ran, Transformation([3, 3, 3]));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphMonomorphism(src, ran, Transformation([1, 2, 2]));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEpimorphism(src, ran, Transformation([1, 2, 2]));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphMonomorphism(ran, src, ());[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X7.3-11 IsDigraphEmbedding[101X
  
  [33X[1;0Y[29X[2XIsDigraphEmbedding[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsDigraphEmbedding[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X, [3Xcol1[103X, [3Xcol2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0Y[10XIsDigraphEmbedding[110X  returns [9Xtrue[109X if the permutation or transformation [3Xx[103X is a
  embedding  of  the  digraph  [3Xsrc[103X  into the digraph [3Xran[103X, while respecting the
  colourings [3Xcol1[103X and [3Xcol2[103X if given.[133X
  
  [33X[0;0YA  permutation  or  transformation  [3Xx[103X is a [13Xembedding[113X of a digraph [3Xsrc[103X into a
  digraph [3Xran[103X if [3Xx[103X is a monomorphism from [3Xsrc[103X to [3Xran[103X and the inverse of [3Xx[103X is a
  monomorphism  from  the  subdigraph of [3Xran[103X induced by the image of [3Xx[103X to [3Xsrc[103X.
  See also [2XIsDigraphHomomorphism[102X ([14X7.3-10[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xsrc := Digraph([[1], [1, 2]]);[127X[104X
    [4X[28X<immutable digraph with 2 vertices, 3 edges>[128X[104X
    [4X[25Xgap>[125X [27Xran := Digraph([[1], [1, 2], [1, 3]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphMonomorphism(src, ran, ());[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEmbedding(src, ran, ());[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEmbedding(src, ran, (), [2, 1], [2, 1, 1]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEmbedding(src, ran, (), [2, 1], [1, 2, 1]);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xran := Digraph([[1, 2], [1, 2], [1, 3]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphMonomorphism(src, ran, IdentityTransformation);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEmbedding(src, ran, IdentityTransformation);[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X7.3-12 SubdigraphsMonomorphisms[101X
  
  [33X[1;0Y[29X[2XSubdigraphsMonomorphisms[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XSubdigraphsMonomorphismsRepresentatives[102X( [3Xdigraph1[103X, [3Xdigraph2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA list of transformations.[133X
  
  [33X[0;0YThese  operations  behave  the  same  as  [2XHomomorphismsDigraphs[102X  ([14X7.3-3[114X) and
  [2XHomomorphismsDigraphsRepresentatives[102X   ([14X7.3-3[114X),   except  they  only  return
  [13Xinjective[113X  homomorphisms  with  the following property: the (not necessarily
  induced) subdigraphs defined by the images of these monomorphisms are all of
  the  subdigraphs  of [3Xdigraph2[103X that are isomorphic to [3Xdigraph1[103X. Note that the
  subdigraphs  of  the  previous  sentence  are those obtained by applying the
  corresponding  monomorphism  to  the vertices and the edges of [3Xdigraph1[103X, and
  are  therefore  possibly strictly contained in the induced subdigraph on the
  same vertex set.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XSet(SubdigraphsMonomorphisms(CompleteBipartiteDigraph(2, 2),[127X[104X
    [4X[25X>[125X [27XCompleteDigraph(4)));[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 2 ] ), Transformation( [ 2, 3, 1 ] ),[128X[104X
    [4X[28X  Transformation( [ 3, 4, 2, 1 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XSubdigraphsMonomorphismsRepresentatives([127X[104X
    [4X[25X>[125X [27XCompleteBipartiteDigraph(2, 2), CompleteDigraph(4));[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 2 ] ) ][128X[104X
  [4X[32X[104X
  
  [1X7.3-13 DigraphsRespectsColouring[101X
  
  [33X[1;0Y[29X[2XDigraphsRespectsColouring[102X( [3Xsrc[103X, [3Xran[103X, [3Xx[103X, [3Xcol1[103X, [3Xcol2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0YThe   operation   [10XDigraphsRespectsColouring[110X  verifies  whether  or  not  the
  permutation or transformation [3Xx[103X respects the vertex colourings [3Xcol1[103X and [3Xcol2[103X
  of  the  digraphs  [3Xsrc[103X and [3Xrange[103X. That is, [10XDigraphsRespectsColouring[110X returns
  [9Xtrue[109X if and only if for all vertices [10Xi[110X of [3Xsrc[103X, [10Xcol1[i] = col2[i ^ x][110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xsrc := Digraph([[1], [1, 2]]);[127X[104X
    [4X[28X<immutable digraph with 2 vertices, 3 edges>[128X[104X
    [4X[25Xgap>[125X [27Xran := Digraph([[1], [1, 2], [1, 3]]);[127X[104X
    [4X[28X<immutable digraph with 3 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphsRespectsColouring(src, ran, (1, 2), [2, 1], [1, 2, 1]);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XDigraphsRespectsColouring(src, ran, (1, 2), [2, 1], [2, 1, 1]);[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X7.3-14 GeneratorsOfEndomorphismMonoid[101X
  
  [33X[1;0Y[29X[2XGeneratorsOfEndomorphismMonoid[102X( [3Xdigraph[103X[, [3Xcolors[103X][, [3Xlimit[103X] ) [32X function[133X
  [33X[1;0Y[29X[2XGeneratorsOfEndomorphismMonoidAttr[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA list of transformations.[133X
  
  [33X[0;0YAn  endomorphism  of  [3Xdigraph[103X  is a homomorphism [2XDigraphHomomorphism[102X ([14X7.3-2[114X)
  from  [3Xdigraph[103X  back to itself. [10XGeneratorsOfEndomorphismMonoid[110X, called with a
  single   argument,   returns   a  generating  set  for  the  monoid  of  all
  endomorphisms  of [3Xdigraph[103X. If [3Xdigraph[103X belongs to [2XIsImmutableDigraph[102X ([14X3.1-3[114X),
  then  the  value of [10XGeneratorsOfEndomorphismMonoid[110X will not be recomputed on
  future calls.[133X
  
  [33X[0;0YIf  the  [3Xcolors[103X  argument  is specified, then [10XGeneratorsOfEndomorphismMonoid[110X
  will  return  a generating set for the monoid of endomorphisms which respect
  the given colouring. The colouring [3Xcolors[103X can be in one of two forms:[133X
  
  [30X    [33X[0;6YA list of positive integers of size the number of vertices of [3Xdigraph[103X,
        where [3Xcolors[103X[10X[i][110X is the colour of vertex [10Xi[110X.[133X
  
  [30X    [33X[0;6YA  list  of  lists, such that [3Xcolors[103X[10X[i][110X is a list of all vertices with
        colour [10Xi[110X.[133X
  
  [33X[0;0YIf the [3Xlimit[103X argument is specified, then it will return only the first [3Xlimit[103X
  homomorphisms, where [3Xlimit[103X must be a positive integer or [10Xinfinity[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgr := Digraph(List([1 .. 3], x -> [1 .. 3]));;[127X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfEndomorphismMonoid(gr);[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 2 ] ), Transformation( [ 2, 1 ] ),[128X[104X
    [4X[28X  IdentityTransformation, Transformation( [ 1, 2, 1 ] ),[128X[104X
    [4X[28X  Transformation( [ 1, 2, 2 ] ), Transformation( [ 1, 1, 2 ] ),[128X[104X
    [4X[28X  Transformation( [ 1, 1, 1 ] ) ][128X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfEndomorphismMonoid(gr, 3);[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 2 ] ), Transformation( [ 2, 1 ] ),[128X[104X
    [4X[28X  IdentityTransformation ][128X[104X
    [4X[25Xgap>[125X [27Xgr := CompleteDigraph(3);;[127X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfEndomorphismMonoid(gr);[127X[104X
    [4X[28X[ Transformation( [ 2, 3, 1 ] ), Transformation( [ 2, 1 ] ),[128X[104X
    [4X[28X  IdentityTransformation ][128X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfEndomorphismMonoid(gr, [1, 2, 2]);[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ][128X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfEndomorphismMonoid(gr, [[1], [2, 3]]);[127X[104X
    [4X[28X[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ][128X[104X
  [4X[32X[104X
  
  [1X7.3-15 DigraphColouring[101X
  
  [33X[1;0Y[29X[2XDigraphColouring[102X( [3Xdigraph[103X, [3Xn[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA transformation, or [9Xfail[109X.[133X
  
  [33X[0;0YA [13Xproper colouring[113X of a digraph is a labelling of its vertices in such a way
  that  adjacent  vertices  have  different  labels. A [13Xproper [10Xn[110X-colouring[113X is a
  proper  colouring  that  uses  exactly  [10Xn[110X  colours.  Equivalently,  a proper
  ([10Xn[110X-)colouring of a digraph can be defined to be a [2XDigraphEpimorphism[102X ([14X7.3-6[114X)
  from   a   digraph   onto  the  complete  digraph  (with  [10Xn[110X  vertices);  see
  [2XCompleteDigraph[102X  ([14X3.5-13[114X).  Note  that a digraph with loops ([2XDigraphHasLoops[102X
  ([14X6.2-1[114X)) does not have a proper [10Xn[110X-colouring for any value [10Xn[110X.[133X
  
  [33X[0;0YIf   [3Xdigraph[103X   is   a   digraph  and  [3Xn[103X  is  a  non-negative  integer,  then
  [10XDigraphColouring([3Xdigraph[103X[10X,  [3Xn[103X[10X)[110X  returns  an epimorphism from [3Xdigraph[103X onto the
  complete digraph with [3Xn[103X vertices if one exists, else it returns [9Xfail[109X.[133X
  
  [33X[0;0YSee also [2XDigraphGreedyColouring[102X ([14X7.3-16[114X) and[133X
  
  [33X[0;0YNote that a digraph with at least two vertices has a 2-colouring if and only
  if it is bipartite, see [2XIsBipartiteDigraph[102X ([14X6.2-3[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XDigraphColouring(CompleteDigraph(5), 4);[127X[104X
    [4X[28Xfail[128X[104X
    [4X[25Xgap>[125X [27XDigraphColouring(ChainDigraph(10), 1);[127X[104X
    [4X[28Xfail[128X[104X
    [4X[25Xgap>[125X [27XD := ChainDigraph(10);;[127X[104X
    [4X[25Xgap>[125X [27Xt := DigraphColouring(D, 2);[127X[104X
    [4X[28XTransformation( [ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ] )[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphColouring(D, t);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XDigraphGreedyColouring(D);[127X[104X
    [4X[28XTransformation( [ 2, 1, 2, 1, 2, 1, 2, 1, 2, 1 ] )[128X[104X
  [4X[32X[104X
  
  [1X7.3-16 DigraphGreedyColouring[101X
  
  [33X[1;0Y[29X[2XDigraphGreedyColouring[102X( [3Xdigraph[103X, [3Xorder[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XDigraphGreedyColouring[102X( [3Xdigraph[103X, [3Xfunc[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XDigraphGreedyColouring[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA transformation, or [9Xfail[109X.[133X
  
  [33X[0;0YA [13Xproper colouring[113X of a digraph is a labelling of its vertices in such a way
  that adjacent vertices have different labels. Note that a digraph with loops
  ([2XDigraphHasLoops[102X ([14X6.2-1[114X)) does not have any proper colouring.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is a digraph and [3Xorder[103X is a dense list consisting of all of the
  vertices  of  [3Xdigraph[103X  (in  any  order),  then [10XDigraphGreedyColouring[110X uses a
  greedy algorithm with the specified order to obtain some proper colouring of
  [3Xdigraph[103X, which may not use the minimal number of colours.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X is a digraph and [3Xfunc[103X is a function whose argument is a digraph,
  and  that  returns  a dense list [3Xorder[103X, then [10XDigraphGreedyColouring([3Xdigraph[103X[10X,
  [3Xfunc[103X[10X)[110X returns [10XDigraphGreedyColouring([3Xdigraph[103X[10X, [3Xfunc[103X[10X([3Xdigraph[103X[10X))[110X.[133X
  
  [33X[0;0YIf  the  optional  second  argument  (either  a  list or a function), is not
  specified, then [2XDigraphWelshPowellOrder[102X ([14X7.3-17[114X) is used by default.[133X
  
  [33X[0;0YSee also [2XDigraphColouring[102X ([14X7.3-15[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XDigraphGreedyColouring(ChainDigraph(10));[127X[104X
    [4X[28XTransformation( [ 2, 1, 2, 1, 2, 1, 2, 1, 2, 1 ] )[128X[104X
    [4X[25Xgap>[125X [27XDigraphGreedyColouring(ChainDigraph(10), [1 .. 10]);[127X[104X
    [4X[28XTransformation( [ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ] )[128X[104X
  [4X[32X[104X
  
  [1X7.3-17 DigraphWelshPowellOrder[101X
  
  [33X[1;0Y[29X[2XDigraphWelshPowellOrder[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA list of the vertices.[133X
  
  [33X[0;0Y[10XDigraphWelshPowellOrder[110X returns a list of all of the vertices of the digraph
  [3Xdigraph[103X   ordered   according   to  the  sum  of  the  number  of  out-  and
  in-neighbours, from highest to lowest.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XDigraphWelshPowellOrder(Digraph([[4], [9], [9], [],[127X[104X
    [4X[25X>[125X [27X                                    [4, 6, 9], [1], [], [],[127X[104X
    [4X[25X>[125X [27X                                    [4, 5], [4, 5]]));[127X[104X
    [4X[28X[ 5, 9, 4, 1, 6, 10, 2, 3, 7, 8 ][128X[104X
  [4X[32X[104X
  
  [1X7.3-18 ChromaticNumber[101X
  
  [33X[1;0Y[29X[2XChromaticNumber[102X( [3Xdigraph[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA non-negative integer.[133X
  
  [33X[0;0YA [13Xproper colouring[113X of a digraph is a labelling of its vertices in such a way
  that adjacent vertices have different labels. Equivalently, a proper digraph
  colouring  can  be defined to be a [2XDigraphEpimorphism[102X ([14X7.3-6[114X) from a digraph
  onto a complete digraph.[133X
  
  [33X[0;0YIf  [3Xdigraph[103X  is  a  digraph without loops (see [2XDigraphHasLoops[102X ([14X6.2-1[114X), then
  [10XChromaticNumber[110X  returns the least non-negative integer [10Xn[110X such that there is
  a  proper colouring of [3Xdigraph[103X with [10Xn[110X colours. In other words, for a digraph
  with  at  least  one vertex, [10XChromaticNumber[110X returns the least number [10Xn[110X such
  that [10XDigraphColouring([3Xdigraph[103X[10X, n)[110X does not return [9Xfail[109X. See [2XDigraphColouring[102X
  ([14X7.3-15[114X).[133X
  
  [33X[0;0YIt  is  possible to select the algorithm to compute the chromatic number via
  the  use  of  value  options. The permitted algorithms and values to pass as
  options are:[133X
  
  [30X    [33X[0;6Y[10Xlawler[110X - Lawler's Algorithm [Law76][133X
  
  [30X    [33X[0;6Y[10Xbyskov[110X - Byskov's Algorithm [Bys02][133X
  
  [30X    [33X[0;6Y[10Xzykov[110X - Zykov's Algorithm [CG73][133X
  
  [30X    [33X[0;6Y[10Xchristofides[110X - Christofides's Algorithm [Wan74][133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(NullDigraph(10));[127X[104X
    [4X[28X1[128X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(CompleteDigraph(10));[127X[104X
    [4X[28X10[128X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(CompleteBipartiteDigraph(5, 5));[127X[104X
    [4X[28X2[128X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(Digraph([[], [3], [5], [2, 3], [4]]));[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(NullDigraph(0));[127X[104X
    [4X[28X0[128X[104X
    [4X[25Xgap>[125X [27XD := PetersenGraph(IsMutableDigraph);[127X[104X
    [4X[28X<mutable digraph with 10 vertices, 30 edges>[128X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(D);[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(CompleteDigraph(10) : lawler);[127X[104X
    [4X[28X10[128X[104X
    [4X[25Xgap>[125X [27XChromaticNumber(CompleteDigraph(10) : byskov);[127X[104X
    [4X[28X10[128X[104X
  [4X[32X[104X
  
  [1X7.3-19 DigraphCore[101X
  
  [33X[1;0Y[29X[2XDigraphCore[102X( [3XD[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10YA list of positive integers.[133X
  
  [33X[0;0YIf [3XD[103X is a digraph, then [10XDigraphCore[110X returns a list of vertices corresponding
  to the [10Xcore[110X of [3XD[103X. In particular, the subdigraph of [3XD[103X induced by this list is
  isomorphic to the core of [3XD[103X.[133X
  
  [33X[0;0YThe  [13Xcore[113X  of  a  digraph  [10XD[110X  is  the  minimal  subdigraph [3XC[103X of [10XD[110X which is a
  homomorphic image of [10XD[110X. The core of a digraph is unique up to isomorphism.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := DigraphSymmetricClosure(CycleDigraph(8));[127X[104X
    [4X[28X<immutable symmetric digraph with 8 vertices, 16 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphCore(D);[127X[104X
    [4X[28X[ 1, 2 ][128X[104X
    [4X[25Xgap>[125X [27XD := PetersenGraph();[127X[104X
    [4X[28X<immutable digraph with 10 vertices, 30 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphCore(D);[127X[104X
    [4X[28X[ 1 .. 10 ][128X[104X
    [4X[25Xgap>[125X [27XD := Digraph(IsMutableDigraph, [[3], [3], [4], [5], [2]]);[127X[104X
    [4X[28X<mutable digraph with 5 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27XDigraphCore(D);[127X[104X
    [4X[28X[ 2, 3, 4, 5 ][128X[104X
  [4X[32X[104X
  
  [1X7.3-20 LatticeDigraphEmbedding[101X
  
  [33X[1;0Y[29X[2XLatticeDigraphEmbedding[102X( [3XL1[103X, [3XL2[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10YA transformation, or [9Xfail[109X.[133X
  
  [33X[0;0YIf  [3XL1[103X  and  [3XL2[103X are lattice digraphs ([2XIsLatticeDigraph[102X ([14X6.4-3[114X) returns [9Xtrue[109X,
  then  [10XLatticeDigraphEmbedding[110X returns a single [13Xinjective[113X [2XDigraphHomomorphism[102X
  ([14X7.3-2[114X)  between  [3XL1[103X  and  [3XL2[103X,  with  the  property  that  it  is  a [13Xlattice
  homomorphism[113X. If no such homomorphism exists, [9Xfail[109X is returned.[133X
  
  [33X[0;0YA  [13Xlattice  homomorphism[113X  is a digraph homomorphism which respects meets and
  joins  of  every  pair  of  vertices.  Note  that  every  injective  lattice
  homomorphism  [10Xmap[110X is an embedding, in the sense that the inverse of [10Xmap[110X is a
  lattice homomorphism also.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XD := DigraphReflexiveTransitiveClosure(ChainDigraph(5));[127X[104X
    [4X[28X<immutable preorder digraph with 5 vertices, 15 edges>[128X[104X
    [4X[25Xgap>[125X [27XL1 := DigraphReflexiveTransitiveClosure(ChainDigraph(5));[127X[104X
    [4X[28X<immutable preorder digraph with 5 vertices, 15 edges>[128X[104X
    [4X[25Xgap>[125X [27XL2 := DigraphReflexiveTransitiveClosure(ChainDigraph(6));[127X[104X
    [4X[28X<immutable preorder digraph with 6 vertices, 21 edges>[128X[104X
    [4X[25Xgap>[125X [27XLatticeDigraphEmbedding(L1, L2);[127X[104X
    [4X[28XIdentityTransformation[128X[104X
    [4X[25Xgap>[125X [27XLatticeDigraphEmbedding(L2, L1);[127X[104X
    [4X[28Xfail[128X[104X
  [4X[32X[104X
  
  [1X7.3-21 IsLatticeHomomorphism[101X
  
  [33X[1;0Y[29X[2XIsLatticeHomomorphism[102X( [3XL1[103X, [3XL2[103X, [3Xmap[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsLatticeEpimorphism[102X( [3XL1[103X, [3XL2[103X, [3Xmap[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsLatticeEmbedding[102X( [3XL1[103X, [3XL2[103X, [3Xmap[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsLatticeMonomorphism[102X( [3XL1[103X, [3XL2[103X, [3Xmap[103X ) [32X operation[133X
  [33X[1;0Y[29X[2XIsLatticeEndomorphism[102X( [3XL[103X, [3Xmap[103X ) [32X operation[133X
  [6XReturns:[106X  [33X[0;10Y[9Xtrue[109X or [9Xfalse[109X.[133X
  
  [33X[0;0YEach    of    the    function    described    in    this   section   (except
  [10XIsLatticeEndomorphism[110X)   takes   a  pair  of  digraphs  [3XL1[103X  and  [3XL2[103X,  and  a
  transformation  [3Xmap[103X, returning [9Xtrue[109X if [3Xmap[103X is a [13Xlattice homomorphism[113X from [3XL1[103X
  to  [3XL2[103X,  and  [9Xfalse[109X  otherwise.  If [3XL1[103X or [3XL2[103X is not a lattice, then [9Xfalse[109X is
  returned.[133X
  
  [33X[0;0YA  transformation  or  permutation  [3Xmap[103X  is  a  [13Xlattice  homomorphism[113X if [3Xmap[103X
  respects  meets  and  joins of every pair of vertices, and [3Xmap[103X fixes every [10Xi[110X
  which is not a vertex of [3XL1[103X.[133X
  
  [33X[0;0Y[10XIsLatticeHomomorphism[110X  returns [9Xtrue[109X if the permutation or transformation [3Xmap[103X
  is a lattice homomorphism from the lattice digraph [3XL1[103X to the lattice digraph
  [3XL2[103X.[133X
  
  [33X[0;0Y[10XIsLatticeEpimorphism[110X  returns  [9Xtrue[109X if the permutation or transformation [3Xmap[103X
  is  a  surjective  lattice  homomorphism  from the lattice digraph [3XL1[103X to the
  lattice digraph [3XL2[103X.[133X
  
  [33X[0;0Y[10XIsLatticeEmbedding[110X  returns [9Xtrue[109X if the permutation or transformation [3Xmap[103X is
  an injective lattice homomorphism from the lattice digraph [3XL1[103X to the lattice
  digraph   [3XL2[103X.   The   function   [10XIsLatticeMonomorphism[110X   is   a  synonym  of
  [10XIsLatticeEmbedding[110X.[133X
  
  [33X[0;0Y[10XIsLatticeEndomorphism[110X  returns [9Xtrue[109X if the permutation or transformation [3Xmap[103X
  is an lattice endomorphism of the lattice digraph [3XL[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := Digraph([[2, 4], [3, 7], [6], [5, 7], [6], [], [6]]);[127X[104X
    [4X[28X<immutable digraph with 7 vertices, 9 edges>[128X[104X
    [4X[25Xgap>[125X [27XD := DigraphRemoveVertex(G, 7);[127X[104X
    [4X[28X<immutable digraph with 6 vertices, 6 edges>[128X[104X
    [4X[25Xgap>[125X [27XG := DigraphReflexiveTransitiveClosure(G);[127X[104X
    [4X[28X<immutable preorder digraph with 7 vertices, 22 edges>[128X[104X
    [4X[25Xgap>[125X [27XD := DigraphReflexiveTransitiveClosure(D);[127X[104X
    [4X[28X<immutable preorder digraph with 6 vertices, 17 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsDigraphEmbedding(D, G, IdentityTransformation);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsLatticeHomomorphism(D, G, IdentityTransformation);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XD := Digraph([[2, 3], [4], [4], []]);[127X[104X
    [4X[28X<immutable digraph with 4 vertices, 4 edges>[128X[104X
    [4X[25Xgap>[125X [27XG := Digraph([[2, 3], [4], [4], [5], []]);[127X[104X
    [4X[28X<immutable digraph with 5 vertices, 5 edges>[128X[104X
    [4X[25Xgap>[125X [27XD := DigraphReflexiveTransitiveClosure(D);[127X[104X
    [4X[28X<immutable preorder digraph with 4 vertices, 9 edges>[128X[104X
    [4X[25Xgap>[125X [27XG := DigraphReflexiveTransitiveClosure(G);[127X[104X
    [4X[28X<immutable preorder digraph with 5 vertices, 14 edges>[128X[104X
    [4X[25Xgap>[125X [27XIsLatticeEmbedding(D, G, IdentityTransformation);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsLatticeMonomorphism(D, G, IdentityTransformation);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xf := Transformation([1, 2, 3, 4, 4]);[127X[104X
    [4X[28XTransformation( [ 1, 2, 3, 4, 4 ] )[128X[104X
    [4X[25Xgap>[125X [27XIsLatticeEpimorphism(G, D, f);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsLatticeEndomorphism(D, (2, 3));[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
