  
  [1X6 Graphs of Groups and Groupoids[0X
  
  This package was originally designed to implement [13Xgraphs of groups[0m, a notion
  introduced by Serre in [Ser80]. It was only when this was extended to [13Xgraphs
  of  groupoids[0m  that  the  functions for groupoids, described in the previous
  chapters,  were  required.  The  methods  described here are based on Philip
  Higgins'  paper [Hig76]. For further details see Chapter 2 of [Moo01]. Since
  a graph of groups involves a directed graph, with a group associated to each
  vertex  and  arc,  we  first  define  digraphs  with  edges  weighted by the
  generators of a free group.
  
  
  [1X6.1 Digraphs[0X
  
  [1X6.1-1 FpWeightedDigraph[0m
  
  [2X> FpWeightedDigraph( [0X[3Xverts, arcs[0X[2X ) ________________________________[0Xattribute
  [2X> IsFpWeightedDigraph( [0X[3Xdig[0X[2X ) ______________________________________[0Xattribute
  [2X> InvolutoryArcs( [0X[3Xdig[0X[2X ) ___________________________________________[0Xattribute
  
  A  [13Xweighted  digraph[0m  is  a  record with two components: [13Xvertices[0m, which are
  usually  taken to be positive integers (to distinguish them from the objects
  in   a  groupoid);  and  [13Xarcs[0m,  which  take  the  form  of  3-element  lists
  [10X[weight,tail,head][0m.  The  [13Xtail[0m and [13Xhead[0m are the two vertices of the arc. The
  [13Xweight[0m  is  taken  to  be an element of a finitely presented group, so as to
  produce digraphs of type [10XIsFpWeightedDigraph[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> V1 := [ 5, 6 ];;[0X
    [4Xgap> f1 := FreeGroup( "y" );;[0X
    [4Xgap> y := f1.1;;[0X
    [4Xgap> A1 := [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ];[0X
    [4Xgap> D1 := FpWeightedDigraph( V1, A1 );[0X
    [4Xweighted digraph with vertices: [ 5, 6 ][0X
    [4Xand arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ][0X
    [4Xgap> inv1 := InvolutoryArcs( D1 );[0X
    [4X[ 2, 1 ][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  The  example  illustrates  the  fact  that  we require arcs to be defined in
  involutory pairs, as though they were inverse elements in a groupoid. We may
  in  future  decide  just to give [10X[y,5,6][0m as the data and get the function to
  construct  the  reverse edge. The attribute [10XInvolutoryArcs[0m returns a list of
  the positions of each inverse arc in the list of arcs. In the second example
  the graph is a complete digraph on three vertices.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> f3 := FreeGroup( 3, "z" );;[0X
    [4Xgap> z1 := f3.1;;  z2 := f3.2;;  z3 := f3.3;;[0X
    [4Xgap> V3 := [ 7, 8, 9 ];;[0X
    [4Xgap> A3 := [[z1,7,8],[z2,8,9],[z3,9,7],[z1^-1,8,7],[z2^-1,9,8],[z3^-1,7,9]];;[0X
    [4Xgap> D3 := FpWeightedDigraph( V3, A3 );[0X
    [4Xweighted digraph with vertices: [ 7, 8, 9 ][0X
    [4Xand arcs: [ [ z1, 7, 8 ], [ z2, 8, 9 ], [ z3, 9, 7 ], [ z1^-1, 8, 7 ],[0X
    [4X  [ z2^-1, 9, 8 ], [ z3^-1, 7, 9 ] ][0X
    [4X[gap> inv3 := InvolutoryArcs( D3 );[0X
    [4X[ 4, 5, 6, 1, 2, 3 ][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X6.2 Graphs of Groups[0X
  
  [1X6.2-1 GraphOfGroups[0m
  
  [2X> GraphOfGroups( [0X[3Xdig, gps, sgps, isos[0X[2X ) ___________________________[0Xoperation
  [2X> DigraphOfGraphOfGroups( [0X[3Xgg[0X[2X ) ____________________________________[0Xattribute
  [2X> GroupsOfGraphOfGroups( [0X[3Xgg[0X[2X ) _____________________________________[0Xattribute
  [2X> SubgroupsOfGraphOfGroups( [0X[3Xgg[0X[2X ) __________________________________[0Xattribute
  [2X> IsomorphismsOfGraphOfGroups( [0X[3Xgg[0X[2X ) _______________________________[0Xattribute
  
  A graph of groups is traditionally defined as consisting of:
  
  --    a digraph with involutory pairs of arcs;
  
  --    a [13Xvertex group[0m associated to each vertex;
  
  --    a group associated to each pair of arcs;
  
  --    an injective homomorphism from each arc group to the group at the head
        of the arc.
  
  We have found it more convenient to associate to each arc:
  
  --    a subgroup of the vertex group at the tail;
  
  --    a subgroup of the vertex group at the head;
  
  --    an isomorphism between these subgroups, such that each involutory pair
        of arcs determines inverse isomorphisms.
  
  These two viewpoints are clearly equivalent.
  
  In  this implementation we require that all subgroups are of finite index in
  the vertex groups.
  
  The four attributes provide a means of calling the four items of data in the
  construction of a graph of groups.
  
  We  shall  be representing free products with amalgamation of groups and HNN
  extensions of groups, so we take as our first example the trefoil group with
  generators  a,b and relation a^3=b^2. For this we take digraph [10XD1[0m above with
  an  infinite cyclic group at each vertex, generated by a and b respectively.
  The  two  subgroups  will  be  generated  by  a^3  and  b^2 with the obvious
  isomorphisms.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> ## free vertex group at 5[0X
    [4Xgap> fa := FreeGroup( "a" );;[0X
    [4Xgap> a := fa.1;;[0X
    [4Xgap> SetName( fa, "fa" );[0X
    [4Xgap> hy := Subgroup( fa, [a^3] );;[0X
    [4Xgap> SetName( hy, "hy" );[0X
    [4Xgap> ## free vertex group at 6[0X
    [4Xgap> fb := FreeGroup( "b" );;[0X
    [4Xgap> b := fb.1;;[0X
    [4Xgap> SetName( fb, "fb" );[0X
    [4Xgap> hybar := Subgroup( fb, [b^2] );;[0X
    [4Xgap> SetName( hybar, "hybar" );[0X
    [4Xgap> ## isomorphisms between subgroups[0X
    [4Xgap> homy := GroupHomomorphismByImagesNC( hy, hybar, [a^3], [b^2] );;[0X
    [4Xgap> homybar := GroupHomomorphismByImagesNC( hybar, hy, [b^2], [a^3] );;[0X
    [4Xgap> ## defining graph of groups G1[0X
    [4Xgap> G1 := GraphOfGroups( D1, [fa,fb], [hy,hybar], [homy,homybar] );[0X
    [4XGraph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ][0X
    [4Xgap> Display( G1 );[0X
    [4XGraph of Groups with :-[0X
    [4X    vertices: [ 5, 6 ][0X
    [4X        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ][0X
    [4X      groups: [ fa, fb ][0X
    [4X   subgroups: [ hy, hybar ][0X
    [4Xisomorphisms: [ [ [ a^3 ], [ b^2 ] ], [ [ b^2 ], [ a^3 ] ] ][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X6.2-2 IsGraphOfFpGroups[0m
  
  [2X> IsGraphOfFpGroups( [0X[3Xgg[0X[2X ) __________________________________________[0Xproperty
  [2X> IsGraphOfPcGroups( [0X[3Xgg[0X[2X ) __________________________________________[0Xproperty
  [2X> IsGraphOfPermGroups( [0X[3Xgg[0X[2X ) ________________________________________[0Xproperty
  
  This  is  a  list  of  properties  to  be  expected of a graph of groups. In
  principle  any  type  of  group  known  to [5XGAP[0m may be used as vertex groups,
  though these types are not normally mixed in a single structure.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> IsGraphOfFpGroups( G1 );[0X
    [4Xtrue[0X
    [4Xgap> IsomorphismsOfGraphOfGroups( G1 );[0X
    [4X[ [ a^3 ] -> [ b^2 ], [ b^2 ] -> [ a^3 ] ][0X
    [4X[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X6.2-3 RightTransversalsOfGraphOfGroups[0m
  
  [2X> RightTransversalsOfGraphOfGroups( [0X[3Xgg[0X[2X ) __________________________[0Xattribute
  [2X> LeftTransversalsOfGraphOfGroups( [0X[3Xgg[0X[2X ) ___________________________[0Xattribute
  
  Computation  with  graph of groups words will require, for each arc subgroup
  [10Xha[0m,  a  set  of representatives for the left cosets of [10Xha[0m in the tail vertex
  group.  As  already pointed out, we require subgroups of finite index. Since
  [5XGAP[0m  prefers  to  provide  right cosets, we obtain the right representatives
  first, and then invert them.
  
  When the vertex groups are of type [10XFpGroup[0m we shall require normal forms for
  these  groups,  so we assume that such vertex groups are provided with Knuth
  Bendix  rewriting  systems  using functions from the main [5XGAP[0m library, (e.g.
  [10XIsomorphismFpSemigroup[0m).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> RTG1 := RightTransversalsOfGraphOfGroups( G1 );[0X
    [4X[ [ <identity ...>, a, a^2 ], [ <identity ...>, b ] ][0X
    [4Xgap> LTG1 := LeftTransversalsOfGraphOfGroups( G1 );[0X
    [4X[ [ <identity ...>, a^-1, a^-2 ], [ <identity ...>, b^-1 ] ] [0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X6.3 Words in a Graph of Groups and their normal forms[0X
  
  [1X6.3-1 GraphOfGroupsWord[0m
  
  [2X> GraphOfGroupsWord( [0X[3Xgg, tv, list[0X[2X ) _______________________________[0Xoperation
  [2X> IsGraphOfGroupsWord( [0X[3Xw[0X[2X ) _________________________________________[0Xproperty
  [2X> GraphOfGroupsOfWord( [0X[3Xw[0X[2X ) ________________________________________[0Xattribute
  [2X> WordOfGraphOfGroupsWord( [0X[3Xw[0X[2X ) ____________________________________[0Xattribute
  [2X> GGTail( [0X[3Xw[0X[2X ) _____________________________________________________[0Xattribute
  [2X> GGHead( [0X[3Xw[0X[2X ) _____________________________________________________[0Xattribute
  
  If [10XG[0m is a graph of groups with underlying digraph [10XD[0m, the following groupoids
  may  be  considered. First there is the free groupoid or path groupoid on [10XD[0m.
  Since  we want each involutory pair of arcs to represent inverse elements in
  the  groupoid,  we  quotient  out  by the relations [10Xy\^{}-1 = ybar[0m to obtain
  [10XPG(D)[0m.  Secondly,  there is the discrete groupoid [10XVG(D)[0m, namely the union of
  all  the  vertex  groups. Since these two groupoids have the same object set
  (the  vertices  of  [10XD[0m) we can form [10XA(G)[0m, the free product of [10XPG(D)[0m and [10XVG(D)[0m
  amalgamated  over  the  vertices.  For  further  details  of  this universal
  groupoid  construction  see  [Moo01].  (Note  that  these  groupoids are not
  implemented in this package.)
  
  An  element  of [10XA(G)[0m is a graph of groups word which may be represented by a
  list  of  the form w = [g_1,y_1,g_2,y_2,...,g_n,y_n,g_n+1]. Here each y_i is
  an  arc  of  [10XD[0m;  the head of y_i-1 is a vertex v_i which is also the tail of
  y_i; and g_i is an element of the vertex group at v_i.
  
  The  attributes  [10XGGTail[0m and [10XGGHead[0m are [13Xtemporary[0m names for the tail and head
  of a graph of groups word, and are likely to be replaced in future versions.
  
  So  a  graph  of  groups word requires as data the graph of groups; the tail
  vertex  for  the word; and a list of arcs and group elements. We may specify
  each arc by its position in the list of arcs.
  
  In  the  following  example,  where  [10Xgw1[0m  is  a word in the trefoil graph of
  groups,  the  y_i  are  specified  by  their  positions in [10XA1[0m. Both arcs are
  traversed twice, so the resulting word is a loop at vertex 5.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> L1 := [ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ];;[0X
    [4Xgap> gw1 := GraphOfGroupsWord( G1, 5, L1 );[0X
    [4X(5)a^7.y.b^-6.y^-1.a^-11.y.b^9.y^-1.a^7(5)[0X
    [4Xgap> IsGraphOfGroupsWord( gw1 );[0X
    [4Xtrue[0X
    [4Xgap> [ GGTail(gw1), GGHead(gw1) ];[0X
    [4X[ 5, 5 ][0X
    [4Xgap> GraphOfGroupsOfWord(gw1);[0X
    [4XGraph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ][0X
    [4Xgap> WordOfGraphOfGroupsWord( gw1 );[0X
    [4X[ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X6.3-2 ReducedGraphOfGroupsWord[0m
  
  [2X> ReducedGraphOfGroupsWord( [0X[3Xw[0X[2X ) ___________________________________[0Xoperation
  [2X> IsReducedGraphOfGroupsWord( [0X[3Xw[0X[2X ) __________________________________[0Xproperty
  
  A  graph  of  groups word may be reduced in two ways, to give a normal form.
  Firstly,  if  part  of the word has the form [10X[yi, identity, yibar][0m then this
  subword  may be omitted. This is known as a length reduction. Secondly there
  are  coset  reductions. Working from the left-hand end of the word, subwords
  of  the  form [g_i,y_i,g_i+1] are replaced by [t_i,y_i,m_i(h_i)*g_i+1] where
  g_i  =  t_i*h_i  is  the  unique  factorisation  of  g_i  as  a  left  coset
  representative  times  an  element  of  the  arc  subgroup,  and  m_i is the
  isomorphism  associated  to  y_i.  Thus we may consider a coset reduction as
  passing  a  subgroup  element along an arc. The resulting normal form (if no
  length  reductions have taken place) is then [t_1,y_1,t_2,y_2,...,t_n,y_n,k]
  for  some k in the head group of y_n. For further details see Section 2.2 of
  [Moo01].
  
  The  reduction of the word [10Xgw1[0m in our example includes one length reduction.
  The four stages of the reduction are as follows:
  
  
       a^7b^{-6}a^{-11}b^9a^7 ~\mapsto~ a^{-2}b^0a^{-11}b^9a^7 ~\mapsto~
       a^{-13}b^9a^7 ~\mapsto~ a^{-1}b^{-8}b^9a^7 ~\mapsto~
       a^{-1}b^{-1}a^{10}.
  
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> nw1 := ReducedGraphOfGroupsWord( gw1 );[0X
    [4X(5)a^-1.y.b^-1.y^-1.a^10(5)[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X6.4 Free products with amalgamation and HNN extensions[0X
  
  [1X6.4-1 FreeProductWithAmalgamation[0m
  
  [2X> FreeProductWithAmalgamation( [0X[3Xgp1, gp2, iso[0X[2X ) ____________________[0Xoperation
  [2X> IsFpaGroup( [0X[3Xfpa[0X[2X ) ________________________________________________[0Xproperty
  [2X> GraphOfGroupsRewritingSystem( [0X[3Xfpa[0X[2X ) _____________________________[0Xattribute
  [2X> NormalFormGGRWS( [0X[3Xfpa, word[0X[2X ) ____________________________________[0Xattribute
  
  As we have seen with the trefoil group example, graphs of groups can be used
  to obtain a normal form for free products with amalgamation G_1 *_H G_2 when
  G_1, G_2 both have rewrite systems, and H is of finite index in both G_1 and
  G_2.
  
  When  [10Xgp1[0m  and  [10Xgp2[0m are fp-groups, the operation [10XFreeProductWithAmalgamation[0m
  constructs  the  required  fp-group.  When  the  two  groups are permutation
  groups,  the [10XIsomorphismFpGroup[0m operation is called on both [10Xgp1[0m and [10Xgp2[0m, and
  the  resulting  isomorphism  is  transported  to  one  between  the  two new
  subgroups.
  
  The  attribute  [10XGraphOfGroupsRewritingSystem[0m  of  [10Xfpa[0m is the graph of groups
  which  has  underlying  digraph  [10XD1[0m, with two vertices and two arcs; the two
  groups as vertex groups; and the specified isomorphisms on the arcs. Despite
  the  name,  graphs  of  groups  constructed in this way [13Xdo not[0m belong to the
  category  [10XIsRewritingSystem[0m.  This  anomaly  may  be  dealt  with  when time
  permits.
  
  The  example  below  shows  a  computation  in  the  the free product of the
  symmetric [10Xs3[0m and the alternating [10Xa4[0m, amalgamated over a cyclic subgroup [10Xc3[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> ## set up the first group s3 and a subgroup c3=<a1>[0X
    [4Xgap> f1 := FreeGroup( 2, "a" );;[0X
    [4Xgap> rel1 := [ f1.1^3, f1.2^2, (f1.1*f1.2)^2 ];;[0X
    [4Xgap> s3 := f1/rel1;;[0X
    [4Xgap> gs3 := GeneratorsOfGroup(s3);;[0X
    [4Xgap> SetName( s3, "s3" );[0X
    [4Xgap> a1 := gs3[1];;  a2 := gs3[2];;[0X
    [4Xgap> H1 := Subgroup(s3,[a1]);;[0X
    [4Xgap> ## then the second group a4 and subgroup c3=<b1>[0X
    [4Xgap> f2 := FreeGroup( 2, "b" );;[0X
    [4Xgap> rel2 := [ f2.1^3, f2.2^3, (f2.1*f2.2)^2 ];;[0X
    [4Xgap> a4 := f2/rel2;;[0X
    [4Xgap> ga4 := GeneratorsOfGroup(a4);;[0X
    [4Xgap> SetName( a4, "a4" );[0X
    [4Xgap> b1 := ga4[1];  b2 := ga4[2];;[0X
    [4Xgap> H2 := Subgroup(a4,[b1]);;[0X
    [4Xgap> ## form the isomorphism and the fpa group[0X
    [4Xgap> iso := GroupHomomorphismByImages(H1,H2,[a1],[b1]);;[0X
    [4Xgap> fpa := FreeProductWithAmalgamation( s3, a4, iso );[0X
    [4X<fp group on the generators [ fa1, fa2, fa3, fa4 ]>[0X
    [4Xgap> RelatorsOfFpGroup( fpa );[0X
    [4X[ fa1^3, fa2^2, fa1*fa2*fa1*fa2, fa3^3, fa4^3, fa3*fa4*fa3*fa4, fa1*fa3^-1 ][0X
    [4Xgap> gg1 := GraphOfGroupsRewritingSystem( fpa );;[0X
    [4Xgap> Display( gg1 );[0X
    [4XGraph of Groups with :-[0X
    [4X    vertices: [ 5, 6 ][0X
    [4X        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ][0X
    [4X      groups: [ s3, a4 ][0X
    [4X   subgroups: [ Group( [ a1 ] ), Group( [ b1 ] ) ][0X
    [4Xisomorphisms: [ [ [ a1 ], [ b1 ] ], [ [ b1 ], [ a1 ] ] ][0X
    [4Xgap> LeftTransversalsOfGraphOfGroups( gg1 );[0X
    [4X[ [ <identity ..>, a2^-1 ], [ <identity ..>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ] ][0X
    [4Xgap> ## choose a word in fpa and find its normal form [0X
    [4Xgap> gfpa := GeneratorsOfGraphOfGroups( fpa );;[0X
    [4Xgap> w2 := (gfpa[1]*gfpa[2]*gfpa[3]^gfpa[4])^3;[0X
    [4Xfa1*fa2*fa4^-1*fa3*fa4*fa1*fa2*fa4^-1*fa3*fa4*fa1*fa2*fa4^-1*fa3*fa4[0X
    [4Xgap> n2 := NormalFormGGRWS( fpa, w2 );[0X
    [4Xfa2*fa3*fa4^-1*fa2*fa4^-1*fa2*fa3^-1*fa4*fa3^-1[0X
    [4X[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X6.4-2 HnnExtension[0m
  
  [2X> HnnExtension( [0X[3Xgp, iso[0X[2X ) _________________________________________[0Xoperation
  [2X> IsHnnGroup( [0X[3Xhnn[0X[2X ) ________________________________________________[0Xproperty
  
  For  [13XHNN  extensions[0m, the appropriate graph of groups has underlying digraph
  with just one vertex and one pair of loops, weighted with [10XFpGroup[0m generators
  z,z^-1.  There  is  one vertex group [10XG[0m, two isomorphic subgroups [10XH1,H2[0m of [10XG[0m,
  with  the  isomorphism and its inverse on the loops. The presentation of the
  extension  has  one  more  generator  than  that of [10XG[0m and corresponds to the
  generator z.
  
  The   functions  [10XGraphOfGroupsRewritingSystem[0m  and  [10XNormalFormGGRWS[0m  may  be
  applied to hnn-groups as well as to fpa-groups.
  
  In the example we take [10XG=a4[0m and the two subgroups are cyclic groups of order
  3.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> H3 := Subgroup(a4,[b2]);;[0X
    [4Xgap> i23 := GroupHomomorphismByImages( H2, H3, [b1], [b2] );;[0X
    [4Xgap> hnn := HnnExtension( a4, i23 );[0X
    [4X<fp group on the generators [ fe1, fe2, fe3 ]> [0X
    [4Xgap> phnn := PresentationFpGroup( hnn );;[0X
    [4Xgap> TzPrint( phnn );[0X
    [4X#I  generators: [ fe1, fe2, fe3 ][0X
    [4X#I  relators:[0X
    [4X#I  1.  3  [ 1, 1, 1 ][0X
    [4X#I  2.  3  [ 2, 2, 2 ][0X
    [4X#I  3.  4  [ 1, 2, 1, 2 ][0X
    [4X#I  4.  4  [ -3, 1, 3, -2 ] [0X
    [4Xgap> gg2 := GraphOfGroupsRewritingSystem( hnn );[0X
    [4XGraph of Groups: 1 vertices; 2 arcs; groups [ a4 ][0X
    [4Xgap> LeftTransversalsOfGraphOfGroups( gg2 );[0X
    [4X[ [ <identity ...>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ],[0X
    [4X  [ <identity ...>, b1^-1, b1, b2^-1*b1 ] ][0X
    [4Xgap> gh := GeneratorsOfGroup( hnn );;[0X
    [4Xgap> w3 := (gh[1]^gh[2])*gh[3]^-1*(gh[1]*gh[3]*gh[2]^2)^2*gh[3]*gh[2];[0X
    [4Xfe2^-1*fe1*fe2*fe3^-1*fe1*fe3*fe2^2*fe1*fe3*fe2^2*fe3*fe2 [0X
    [4Xgap> n3 := NormalFormGGRWS( hnn, w3 );[0X
    [4Xfe2*fe1*fe3*fe2*fe1*fe3   [0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  Both  fpa-groups  and  hnn-groups  are  provided  with  a  record attribute,
  [10XFpaInfo(fpa)[0m   and   [10XHnnInfo(hnn)[0m   respectively,  storing  the  groups  and
  isomorphisms involved in their construction.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> fpainfo := FpaInfo( fpa );[0X
    [4Xrec( groups := [ s3, a4 ], positions := [ [ 1, 2 ], [ 3, 4 ] ],[0X
    [4X  isomorphism := [ a1 ] -> [ b1 ] )[0X
    [4Xgap> hnninfo := HnnInfo( hnn );[0X
    [4Xrec( group := a4, isomorphism := [ b1 ] -> [ b2 ] )[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X6.5 GraphsOfGroupoids and their Words[0X
  
  [1X6.5-1 GraphOfGroupoids[0m
  
  [2X> GraphOfGroupoids( [0X[3Xdig, gpds, subgpds, isos[0X[2X ) ____________________[0Xoperation
  [2X> IsGraphOfPermGroupoids( [0X[3Xgg[0X[2X ) _____________________________________[0Xproperty
  [2X> IsGraphOfFpGroupoids( [0X[3Xgg[0X[2X ) _______________________________________[0Xproperty
  [2X> GroupoidsOfGraphOfGroupoids( [0X[3Xgg[0X[2X ) _______________________________[0Xattribute
  [2X> DigraphOfGraphOfGroupoids( [0X[3Xgg[0X[2X ) _________________________________[0Xattribute
  [2X> SubgroupoidsOfGraphOfGroupoids( [0X[3Xgg[0X[2X ) ____________________________[0Xattribute
  [2X> IsomorphismsOfGraphOfGroupoids( [0X[3Xgg[0X[2X ) ____________________________[0Xattribute
  [2X> RightTransversalsOfGraphOfGroupoids( [0X[3Xgg[0X[2X ) _______________________[0Xattribute
  [2X> LefvtTransversalsOfGraphOfGroupoids( [0X[3Xgg[0X[2X ) _______________________[0Xattribute
  
  Graphs  of  groups  generalise naturally to graphs of groupoids, forming the
  class  [10XIsGraphOfGroupoids[0m.  There  is  now a groupoid at each vertex and the
  isomorphism  on  an  arc identifies wide subgroupoids at the tail and at the
  head.  Since  all  subgroupoids  are  wide,  every  groupoid  in a connected
  constituent  of  the  graph  has the same number of objects, but there is no
  requirement that the object sets are all the same.
  
  The example below generalises the trefoil group example in subsection 4.4.1,
  taking  at  each vertex of [10XD1[0m a two-object groupoid with a free group on one
  generator, and full subgroupoids with groups < a^3 > and < b^2 >.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> Gfa := SinglePieceGroupoid( [-2,-1], fa );;[0X
    [4Xgap> ofa := One( fa );;[0X
    [4Xgap> SetName( Gfa, "Gfa" );[0X
    [4Xgap> Uhy := Subgroupoid( Gfa, [ [[-2,-1], hy ] ] );;[0X
    [4Xgap> SetName( Uhy, "Uhy" );[0X
    [4Xgap> Gfb := SinglePieceGroupoid( [-4,-3], fb );;[0X
    [4Xgap> ofb := One( fb );;[0X
    [4Xgap> SetName( Gfb, "Gfb" );[0X
    [4Xgap> Uhybar := Subgroupoid( Gfb, [ [[-4,-3], hybar ] ] );;[0X
    [4Xgap> SetName( Uhybar, "Uhybar" );[0X
    [4Xgap> mory := GroupoidMappingOfSinglePieces( [0X
    [4Xgap>      Uhy, Uhybar, homy, [-4,-3], [ofb,ofb] );;[0X
    [4Xgap> morybar := GroupoidMappingOfSinglePieces( [0X
    [4Xgap>      Uhybar, Uhy, homybar, [-2,-1], [ofa,ofa] );;[0X
    [4Xgap> gg3 := GraphOfGroupoids( D1, [Gfa,Gfb], [Uhy,Uhybar], [mory,morybar] );;[0X
    [4Xgap> Display( gg3 );[0X
    [4XGraph of Groupoids with :-[0X
    [4X    vertices: [ 5, 6 ][0X
    [4X        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ][0X
    [4X   groupoids:[0X
    [4XFp single piece groupoid: Gfa[0X
    [4X  objects: [ -2, -1 ][0X
    [4X    group: fa = <[ a ]>[0X
    [4XFp single piece groupoid: Gfb[0X
    [4X  objects: [ -4, -3 ][0X
    [4X    group: fb = <[ b ]>[0X
    [4Xsubgroupoids: single piece groupoid: Uhy[0X
    [4X  objects: [ -2, -1 ][0X
    [4X    group: hy = <[ a^3 ]>[0X
    [4Xsingle piece groupoid: Uhybar[0X
    [4X  objects: [ -4, -3 ][0X
    [4X    group: hybar = <[ b^2 ]>[0X
    [4Xisomorphisms: [ groupoid mapping : Uhy -> Uhybar,[0X
    [4X  groupoid mapping : Uhybar -> Uhy ][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  [1X6.5-2 GraphOfGroupoidsWord[0m
  
  [2X> GraphOfGroupoidsWord( [0X[3Xgg, tv, list[0X[2X ) ____________________________[0Xoperation
  [2X> IsGraphOfGroupoidsWord( [0X[3Xw[0X[2X ) ______________________________________[0Xproperty
  [2X> GraphOfGroupoidsOfWord( [0X[3Xw[0X[2X ) _____________________________________[0Xattribute
  [2X> WordOfGraphOfGroupoidsWord( [0X[3Xw[0X[2X ) _________________________________[0Xattribute
  [2X> ReducedGraphOfGroupoidsWord( [0X[3Xw[0X[2X ) ________________________________[0Xoperation
  [2X> IsReducedGraphOfGroupoidsWord( [0X[3Xw[0X[2X ) _______________________________[0Xproperty
  
  Having  produced  the  graph  of  groupoids [10Xgg3[0m, we may construct left coset
  representatives; choose a graph of groupoids word; and reduce this to normal
  form. Compare the [10Xnw3[0m below with the normal form [10Xnw1[0m in subsection 4.3.2.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> f1 := GroupoidElement( Gfa, a^7, -1, -2);;[0X
    [4Xgap> f2 := GroupoidElement( Gfb, b^-6, -4, -4 );;[0X
    [4Xgap> f3 := GroupoidElement( Gfa, a^-11, -2, -1 );;[0X
    [4Xgap> f4 := GroupoidElement( Gfb, b^9, -3, -4 );;[0X
    [4Xgap> f5 := GroupoidElement( Gfa, a^7, -2, -1 );;[0X
    [4Xgap> L3 := [ f1, 1, f2, 2, f3, 1, f4, 2, f5 ];[0X
    [4X[ [a^7 : -1 -> -2], 1, [b^-6 : -4 -> -4], 2, [a^-11 : -2 -> -1], 1, [0X
    [4X  [b^9 : -3 -> -4], 2, [a^7 : -2 -> -1] ][0X
    [4Xgap> gw3 := GraphOfGroupoidsWord( gg3, 5, L3);[0X
    [4X(5)[a^7 : -1 -> -2].y.[b^-6 : -4 -> -4].y^-1.[a^-11 : -2 -> -1].y.[b^9 : [0X
    [4X-3 -> -4].y^-1.[a^7 : -2 -> -1](5)[0X
    [4Xgap> nw3 := ReducedGraphOfGroupoidsWord( gw3 );[0X
    [4X(5)[a^-1 : -1 -> -2].y.[b^-1 : -4 -> -4].y^-1.[a^10 : -2 -> -1](5)[0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  More  examples  of  these  operations  may  be  found  in  the  example file
  [11Xgpd/examples/ggraph.g[0m.
  
