4 Groupoids
  
  Many  of  the names of the functions described in this chapter have changed,
  due  to  the  introduction of magmas with objects, so the chapter is full of
  errors. A new version will be released as soon as possible.
  
  A   groupoid  is  a  (mathematical)  category  in  which  every  element  is
  invertible.  It  consists  of  a set of pieces, each of which is a connected
  groupoid.  (The  usual  terminology  is  `connected  component',  but in GAP
  `component' is used for `record component'.)
  
  A  single piece groupoid is determined by a set of objects obs and an object
  group grp. The objects of a single piece groupoid are generally chosen to be
  consecutive  negative  integers, but any suitable ordered set is acceptable,
  and  `consecutive'  is  not a requirement. The object groups will usually be
  taken  to  be  permutation  groups,  but  pc-groups  and  fp-groups are also
  supported.
  
  A group is a single piece groupoid with one object.
  
  A  groupoid is a set of one or more single piece groupoids, its single piece
  pieces,    and    is    represented   as   IsGroupoidRep,   with   attribute
  PiecesOfGroupoid.
  
  For  the  definitions of the standard properties of groupoids we refer to R.
  Brown's   book  ``Topology''  [Bro88],  recently  revised  and  reissued  as
  ``Topology and Groupoids'' [Bro06].
  
  
  4.1 Groupoids: their elements and attributes
  
  4.1-1 SinglePieceGroupoid
  
  > SinglePieceGroupoid( grp, obs ) _________________________________operation
  > Groupoid( args ) _________________________________________________function
  
  There  are  a  variety  of  constructors  for  groupoids,  with  one  or two
  parameters.  The global function Groupoid will normally find the appropriate
  one to call, the options being:
  
  --    the object group, a list of objects;
  
  --    a group being converted to a groupoid, a single object;
  
  --    a list of groupoids which have already been constructed.
  
  Methods for ViewObj, PrintObj and Display are provided for groupoids and the
  other types of object in this package. Users are advised to supply names for
  all the groups and groupoids they construct.
  
  ---------------------------  Example  ----------------------------
    
    gap> d8 := Group( (1,2,3,4), (1,3) );;
    gap> SetName( d8, "d8" );
    gap> Gd8 := SinglePieceGroupoid( d8, [-9,-8,-7] );
    Perm single piece groupoid:
    < d8, [ -9, -8, -7 ] >
    gap> c6 := Group( (5,6,7)(8,9) );;
    gap> SetName( c6, "c6" );
    gap> Gc6 := DomainWithSingleObject( c6, -6 );
    Perm SinglePiece Groupoid:
    < c6, [ -6 ] >
    gap> Gd8c6 := UnionOfPieces( [ Gd8, Gc6 ] );;
    gap> Display( Gd8c6 );
    Perm Groupoid with 2 pieces:
    < objects: [ -9, -8, -7 ]
        group: d8 = <[ (1,2,3,4), (1,3) ]> >
    < objects: [ -6 ]
        group: c6 = <[ (5,6,7)(8,9) ]> >
    gap> SetName( Gd8, "Gd8" );  SetName( Gc6, "Gc6" );  SetName( Gd8c6, "Gd8+Gc6" );
    
  ------------------------------------------------------------------
  
  4.1-2 Pieces
  
  > Pieces( gpd ) ___________________________________________________attribute
  > ObjectList( gpd ) _______________________________________________attribute
  
  When  a  groupoid  consists  of  two or more pieces, we require their object
  lists  to  be  disjoint.  The pieces are sorted by the first object in their
  object  lists,  which  must  be  disjoint.  The  list ObjectsOfGroupoid of a
  groupoid is the sorted concatenation of the objects in the pieces.
  
  ---------------------------  Example  ----------------------------
    
    gap> Pieces( Gd8c6 );
    [ Gd8, Gc6 ]
    gap> ObjectList( Gd8c6 );
    [ -9, -8, -7, -6 ]
    
  ------------------------------------------------------------------
  
  4.1-3 IsPermGroupoid
  
  > IsPermGroupoid( gpd ) ____________________________________________property
  > IsPcGroupoid( gpd ) ______________________________________________property
  > IsFpGroupoid( gpd ) ______________________________________________property
  
  A  groupoid  is  a  permutation  groupoid if all its pieces have permutation
  groups.  Most of the examples in this chapter are permutation groupoids, but
  in principle any type of group known to GAP may be used.
  
  In the following example Gf2 is an fp-groupoid, while Gq8 is a pc-groupoid.
  
  ---------------------------  Example  ----------------------------
    
    gap> f2 := FreeGroup( 2 );;
    gap> SetName( f2, "f2" );
    gap> Gf2 := Groupoid( f2, -22 );;
    gap> q8 := SmallGroup( 8, 4 );;
    gap> Gq8 := Groupoid( q8, [ -28, -27 ] );;
    gap> SetName( q8, "q8" );  SetName( Gq8, "Gq8" );
    gap> Gf2q8 := Groupoid( [ Gf2, Gq8 ] );;
    gap> [ IsFpGroupoid( Gf2 ), IsPcGroupoid( Gq8 ), IsPcGroupoid( Gf2q8 ) ];
    [ true, true, false ]
    gap> G4 := Groupoid( [ Gd8c6, Gf2, Gq8 ] );;
    gap> Display( G4 );
    Groupoid with 4 pieces:
    < objects: [ -28, -27 ]
        group: q8 = <[ f1, f2, f3 ]> >
    < objects: [ -22 ]
        group: f2 = <[ f1, f2 ]> >
    < objects: [ -9, -8, -7 ]
        group: d8 = <[ (1,2,3,4), (1,3) ]> >
    < objects: [ -6 ]
        group: c6 = <[ (5,6,7)(8,9) ]> >
    gap> G4 = Groupoid( [ Gq8, Gf2, Gd8c6 ] );
    true
    
  ------------------------------------------------------------------
  
  4.1-4 GroupoidElement
  
  > GroupoidElement( gpd, elt, tail, head ) _________________________operation
  > IsElementOfGroupoid( elt ) _______________________________________property
  > Arrow( elt ) ____________________________________________________attribute
  > Arrowtail( elt ) ________________________________________________attribute
  > Arrowhead( elt ) ________________________________________________attribute
  > Size( gpd ) _____________________________________________________attribute
  
  A  groupoid element e is a triple consisting of a group element, Arrow(e) or
  e![1];  the  tail  (source)  object,  Arrowtail(e)  or  e![2];  and the head
  (target) object, Arrowhead(e) or e![3].
  
  The  Size  of  a  groupoid is the number of its elements which, for a single
  piece  groupoid,  is the product of the size of the group with the square of
  the number of objects.
  
  Groupoid elements have a partial composition: two elements may be multiplied
  when the head of the first coincides with the tail of the second.
  
  ---------------------------  Example  ----------------------------
    
    gap> e1 := GroupoidElement( Gd8, (1,2)(3,4), -9, -8 );
    [(1,2)(3,4) : -9 -> -8]
    gap> e2 := GroupoidElement( Gd8, (1,3), -8, -7 );;
    gap> Print( [ Arrow( e2 ), Arrowtail( e2 ), Arrowhead( e2 ) ], "\n" );
    [ (1,3), -8, -7 ]
    gap> prod := e1*e2;
    [(1,2,3,4) : -9 -> -7]
    gap> e3 := GroupoidElement( Gd8, (1,3)(2,4), -7, -9 );;
    gap> cycle := prod*e3;
    [(1,4,3,2) : -9 -> -9]
    gap> cycle^2;
    [(1,3)(2,4) : -9 -> -9]
    gap> Order( cycle );
    4
    gap> cycle^e1;
    [(1,2,3,4) : -8 -> -8]
    gap> [ Size( Gd8 ), Size( Gc6 ), Size( Gd8c6 ), Size( Gf2q8 ) ];
    [ 72, 6, 78, infinity ]
    
  ------------------------------------------------------------------
  
  4.1-5 IsSinglePiece
  
  > IsSinglePiece( gpd ) _____________________________________________property
  > IsDiscrete( gpd ) ________________________________________________property
  
  The  forgetful  functor, which forgets the composition of elements, maps the
  category  of  groupoids  and their morphisms to the category of digraphs and
  their  morphisms.  Applying  this functor to a particular groupoid gives the
  underlying  digraph  of  the  groupoid.  A  groupoid  is  connected  if  its
  underlying digraph is connected (and so complete). A groupoid is discrete if
  it  is a union of groups, so that all the arcs in its underlying digraph are
  loops. It is sometimes convenient to call a groupoid element a loop when its
  tail and head are the same object.
  
  
  4.2 Subgroupoids
  
  4.2-1 SubgroupoidByPieces
  
  > SubgroupoidByPieces( gpd, obhoms ) ______________________________operation
  > Subgroupoid( args ) ______________________________________________function
  > FullSubgroupoid( gpd, obs ) _____________________________________operation
  > MaximalDiscreteSubgroupoid( gpd ) _______________________________attribute
  > DiscreteSubgroupoid( gpd, obs, sgps ) ___________________________operation
  > FullIdentitySubgroupoid( gpd ) __________________________________attribute
  > DiscreteIdentitySubgroupoid( gpd ) ______________________________attribute
  
  A  subgroupoid sgpd of gpd has as objects a subset of the objects of gpd. It
  is  wide if all the objects are included. It is full if, for any two objects
  in sgpd, the Homset is the same as in gpd. The elements of sgpd are a subset
  of  those  of gpd, closed under multiplication and with tail and head in the
  chosen object set.
  
  There  are  a  variety  of constructors for a subgroupoid of a groupoid. The
  operation  SubgroupoidByPieces is the most general. Its two parameters are a
  groupoid  and  a  list  of  pieces,  where each piece is specified as a list
  [obs,sgp],  obs  is a subset of the objects in one of the pieces of gpd, and
  sgp is a subgroup of the group in that piece.
  
  The  FullSubgroupoid  of  a  groupoid  gpd  on  a  subset obs of its objects
  contains all the elements of gpd with tail and head in obs.
  
  A   subgroupoid   is   discrete   if   it   is   a   union  of  groups.  The
  MaximalDiscreteSubgroupoid of gpd is the union of all the single-object full
  subgroupoids of gpd.
  
  An identity subgroupoid has trivial object groups, but need not be discrete.
  A single piece identity groupoid is sometimes called a tree groupoid.
  
  The global function Subgroupoid should call the appropriate operation.
  
  ---------------------------  Example  ----------------------------
    
    gap> c4d := Subgroup( d8, [ (1,2,3,4) ] );;
    gap> k4d := Subgroup( d8, [ (1,2)(3,4), (1,3)(2,4) ] );;
    gap> SetName( c4d, "c4d" );  SetName( k4d, "k4d" );
    gap> Ud8 := Subgroupoid( Gd8, [ [ k4d,[-9] ], [ c4d, [-8,-7] ] ] );;
    gap> SetName( Ud8, "Ud8" );
    gap> Display( Ud8 );
    Perm Groupoid with 2 pieces:
    < objects: [ -9 ]
        group: k4d = <[ (1,2)(3,4), (1,3)(2,4) ]> >
    < objects: [ -8, -7 ]
        group: c4d = <[ (1,2,3,4) ]> >
    gap> FullSubgroupoid( Gd8c6, [-7,-6] );
    Perm Groupoid with pieces:
    < [ -7 ], d8 >
    < [ -6 ], c6 >
    gap> DiscreteSubgroupoid( Gd8c6, [-9,-8], [ c4d, k4d ] );
    Perm Groupoid with pieces:
    < [ -9 ], c4d >
    < [ -8 ], k4d >
    gap> FullIdentitySubgroupoid( Ud8 );
    Perm Groupoid with pieces:
    < [ -9 ], id(k4d) >
    < [ -8, -7 ], id(c4d) >
    
  ------------------------------------------------------------------
  
  
  4.3 Stars, Costars and Homsets
  
  4.3-1 ObjectStar
  
  > ObjectStar( gpd, obj ) __________________________________________operation
  > ObjectCostar( gpd, obj ) ________________________________________operation
  > Homset( gpd, tail, head ) _______________________________________operation
  
  The  star  at  obj  is  the set of groupoid elements which have obj as tail,
  while  the  costar is the set of elements which have obj as head. The homset
  from  obj1  to obj2 is the set of elements with the specified tail and head,
  and  so  is  bijective  with  the elements of the group. Thus every star and
  every costar is a union of homsets.
  
  In  order  not  to  create  unneccessary long lists, these operations return
  objects  of  type  IsHomsetCosetsRep  for which an Iterator is provided. (An
  Enumerator is not yet implemented.)
  
  ---------------------------  Example  ----------------------------
    
    gap> star9 := ObjectStar( Gd8, -9 );
    <star at [ -9 ] with group d8>
    gap> for e in star9 do
    >      if ( Order( e![1] ) = 4 ) then Print( e, "\n" ); fi;
    >    od;
    [(1,4,3,2) : -9 -> -9]
    [(1,4,3,2) : -9 -> -8]
    [(1,4,3,2) : -9 -> -7]
    [(1,2,3,4) : -9 -> -9]
    [(1,2,3,4) : -9 -> -8]
    [(1,2,3,4) : -9 -> -7]
    gap> costar6 := ObjectCostar( Gc6, -6 );
    <costar at [ -6 ] with group c6>
    gap> hset78 := Homset( Ud8, -7, -8 );
    <homset -7 -> -8 with group c4d>
    gap> for e in hset78 do  Print( e, "\n" );  od;
    [() : -7 -> -8]
    [(1,3)(2,4) : -7 -> -8]
    [(1,4,3,2) : -7 -> -8]
    [(1,2,3,4) : -7 -> -8]
    
  ------------------------------------------------------------------
  
  4.3-2 IdentityElement
  
  > IdentityElement( gpd, obj ) _____________________________________operation
  
  The  identity  groupoid element 1\_{o} of gpd at object o is [e,o,o] where e
  is the identity group element in the object group. It is a left identity for
  the star and a right identity for the costar at that object.
  
  ---------------------------  Example  ----------------------------
    
    gap> i7 := IdentityElement( Gd8, -7 );;
    gap> i8 := IdentityElement( Gd8, -8 );;
    gap> L := [ i7, i8 ];;
    gap> for e in hset78 do  Add( L, i7*e*i8 = e );  od;
    gap> L;
    [ [() : -7 -> -7], [() : -8 -> -8], true, true, true, true ]
    
  ------------------------------------------------------------------
  
  
  4.4 Left, right and double cosets
  
  4.4-1 RightCoset
  
  > RightCoset( G, U, elt ) _________________________________________operation
  > RightCosetRepresentatives( G, U ) _______________________________operation
  > RightCosetsNC( G, U ) ___________________________________________operation
  > LeftCoset( G, U, elt ) __________________________________________operation
  > LeftCosetRepresentatives( G, U ) ________________________________operation
  > LeftCosetRepresentativesFromObject( G, U, obj ) _________________operation
  > LeftCosetsNC( G, U ) ____________________________________________operation
  > DoubleCoset( G, U, elt, V ) _____________________________________operation
  > DoubleCosetRepresentatives( G, U, V ) ___________________________operation
  > DoubleCosetsNC( G, U, V ) _______________________________________operation
  
  If  U  is  a  wide  subgroupoid  of  G,  the  right cosets of U in G are the
  equivalence classes of the relation on the elements of G where g1 is related
  to  g2  if  and  only  if g2 = u*g1 for some element u of U. The right coset
  containing  g is written Ug. These right cosets refine the costars of G and,
  in  particular,  U1_o  is the costar of U at o, so that (unlike groups) U is
  itself a coset only when G has a single object.
  
  The  right  coset  representatives  for  U  in  G form a list containing one
  groupoid element for each coset where, in a particular piece of U, the group
  element  chosen  is  the right coset representative of the group of U in the
  group of G.
  
  Similarly, the left cosets gU refine the stars of G, while double cosets are
  unions    of    left   cosets   and   of   right   cosets.   The   operation
  LeftCosetRepresentativesFromObject(  G,  U,  obj ) is used in Chapter 4, and
  returns only those representatives which have tail at obj.
  
  As  with stars and homsets, these cosets are implemented with representation
  IsHomsetCosetsRep  and provided with an iterator. Note that, when U has more
  than one piece, cosets may have differing lengths.
  
  ---------------------------  Example  ----------------------------
    
    gap> re2 := RightCoset( Gd8, Ud8, e2 );
    RightCoset(c4d,[(1,3) : -8 -> -7])
    gap> for x in re2 do Print( x, "\n" ); od;
    [(1,3) : -8 -> -8]
    [(1,3) : -7 -> -8]
    [(2,4) : -8 -> -8]
    [(2,4) : -7 -> -8]
    [(1,4)(2,3) : -8 -> -8]
    [(1,4)(2,3) : -7 -> -8]
    [(1,2)(3,4) : -8 -> -8]
    [(1,2)(3,4) : -7 -> -8]
    gap> rcrd8 := RightCosetRepresentatives( Gd8, Ud8 );
    [ [() : -9 -> -9], [() : -9 -> -8], [() : -9 -> -7], [(2,4) : -9 -> -9],
      [(2,4) : -9 -> -8], [(2,4) : -9 -> -7], [() : -8 -> -9], [() : -8 -> -8],
      [() : -8 -> -7], [(2,4) : -8 -> -9], [(2,4) : -8 -> -8], [(2,4) : -8 -> -7]
     ]
    gap> lcr7 := LeftCosetRepresentativesFromObject( Gd8, Ud8, -7 );
    [ [() : -7 -> -9], [(2,4) : -7 -> -9], [() : -7 -> -8], [(2,4) : -7 -> -8] ]
    
  ------------------------------------------------------------------
  
  
  4.5 Conjugation
  
  4.5-1 \^
  
  > \^( e1, e2 ) ____________________________________________________operation
  
  When  e2  = c : p -> q and e1 has group element b, the conjugate e1^e2 has a
  complicated  definition,  but  may be remembered as follows. All objects are
  fixed  except  p,q, which are interchanged. For p,q as source, multiply b on
  the  left  by  c^-1,c respectively; and for p,q as target, multiply b on the
  right by c,c^-1. This product gives the group element of the conjugate.
  
  ---------------------------  Example  ----------------------------
    
    gap> x := GroupoidElement( Gd8, (2,4), -9, -9 );; 
    gap> y := GroupoidElement( Gd8, (1,2,3,4), -8, -9 );; 
    gap> z := GroupoidElement( Gd8, (1,3)(2,4), -7, -8 );; 
    gap> Print( "\nConjugation with elements x, y, and z in Gd8:\n" );
    gap> Print( "x = ", x, ",  y = ", y, ",  z = ", z, "\n" );
    x = [(2,4) : -9 -> -9],  y = [(1,2,3,4) : -8 -> -9],  z = [(1,3) : -8 -> -8]
    gap> Print( "x^x = ", x^x, ",  x^y = ", x^y, ",  x^z = ", x^z, "\n" );
    x^x = [(2,4) : -9 -> -9],  x^y = [(1,3) : -8 -> -8],  x^z = [(2,4) : -9 -> -9]
    gap> Print( "y^x = ", y^x, ",  y^y = ", y^y, ",  y^z = ", y^z, "\n" );
    y^x = [() : -8 -> -9],  y^y = [(1,4,3,2) : -9 -> -8],  y^z = [(1,4)(2,3) : -8 -> -9]
    gap> Print( "z^x = ", z^x, ",  z^y = ", z^y, ",  z^z = ", z^z, "\n" );
    z^x = [(1,3) : -8 -> -8],  z^y = [(2,4) : -9 -> -9],  z^z = [(1,3) : -8 -> -8]
    
  ------------------------------------------------------------------
  
  More  examples  of  all  these  operations  may be found in the example file
  gpd/examples/gpd.g.