The functions described in this section supplement the Orb package by providing methods for finding something in an orbit, with the possibility of continuing the orbit enumeration at some later point.
‣ EnumeratePosition( o, val[, onlynew] ) | ( function ) |
Returns: A positive integer or fail.
This function returns the position of the value val in the orbit o. If o is closed, then this is equivalent to doing Position(o, val). However, if o is open, then the orbit is enumerated until val is found, in which case the position of val is returned, or the enumeration ends, in which case fail is returned.
If the optional argument onlynew is present, it should be true or false. If onlynew is true, then val will only be checked against new points in o. Otherwise, every point in the o, not only the new ones, is considered.
‣ LookForInOrb( o, func, start ) | ( function ) |
Returns: false or a positive integer.
The arguments of this function should be an orbit o, a function func which gets the orbit object and a point in the orbit as arguments, and a positive integer start. The function func will be called for every point in o starting from start (inclusive) and the orbit will be enumerated until func returns true or the enumeration ends. In the former case, the position of the first point in o for which func returns true is returned, and in the latter false is returned.
gap> o:=Orb(SymmetricGroup(100), 1, OnPoints); <open Int-orbit, 1 points> gap> func:=function(o, x) return x=42; end; function( o, x ) ... end gap> LookForInOrb(o, func, 1); 42 gap> o; <open Int-orbit, 42 points>
The functions described in this section supplement the Orb package by providing methods for operations related to strongly connected components of orbits.
If any of the functions is applied to an open orbit, then the orbit is completely enumerated before any further calculation is performed. It is not possible to calculate the strongly connected components of an orbit of a semigroup acting on a set until the entire orbit has been found.
‣ OrbSCC( o ) | ( function ) |
Returns: The strongly connected components of an orbit.
If o is an orbit created by the Orb package with the option orbitgraph=true, then OrbSCC returns a set of sets of positions in o corresponding to its strongly connected components.
See also OrbSCCLookup (10.2-2) and OrbSCCTruthTable (10.2-3).
gap> S:=FullTransformationSemigroup(4);; gap> o:=LambdaOrb(S); <open orbit, 1 points with Schreier tree with log> gap> OrbSCC(o); [ [ 1 ], [ 2 ], [ 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ]
‣ OrbSCCLookup( o ) | ( function ) |
Returns: A lookup table for the strongly connected components of an orbit.
If o is an orbit created by the Orb package with the option orbitgraph=true, then OrbSCCLookup returns a lookup table for its strongly connected components. More precisely, OrbSCCLookup(o)[i] equals the index of the strongly connected component containing o[i].
See also OrbSCC (10.2-1) and OrbSCCTruthTable (10.2-3).
gap> S:=FullTransformationSemigroup(4);; gap> o:=LambdaOrb(S);; gap> OrbSCC(o); [ [ 1 ], [ 2 ], [ 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ] gap> OrbSCCLookup(o); [ 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5 ] gap> OrbSCCLookup(o)[1]; OrbSCCLookup(o)[4]; OrbSCCLookup(o)[7]; 1 3 4
‣ OrbSCCTruthTable( o ) | ( function ) |
Returns: Truth tables for strongly connected components of an orbit.
If o is an orbit created by the Orb package with the option orbitgraph=true, then OrbSCCTruthTable returns a list of boolean lists such that OrbSCCTruthTable(o)[i][j] is true if j belongs to OrbSCC(o)[i].
See also OrbSCC (10.2-1) and OrbSCCLookup (10.2-2).
gap> S:=FullTransformationSemigroup(4);; gap> o:=LambdaOrb(S);; gap> OrbSCC(o); [ [ 1 ], [ 2 ], [ 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ] gap> OrbSCCTruthTable(o); [ [ true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false ], [ false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false ], [ false, false, true, true, true, true, false, false, false, false, false, false, false, false, false, false ], [ false, false, false, false, false, false, true, true, true, true, true, true, false, false, false, false ], [ false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, true ] ]
‣ ReverseSchreierTreeOfSCC( o, i ) | ( function ) |
Returns: The reverse Schreier tree corresponding to the ith strongly connected component of an orbit.
If o is an orbit created by the Orb package with the option orbitgraph=true and action act, and i is a positive integer, then ReverseSchreierTreeOfSCC(o, i) returns a pair [ gen, pos ] of lists with Length(o) entries such that
act(o[j], o!.gens[gen[j]])=o[pos[j]].
The pair [ gen, pos ] corresponds to a tree with root OrbSCC(o)[i][1] and a path from every element of OrbSCC(o)[i] to the root.
See also OrbSCC (10.2-1), TraceSchreierTreeOfSCCBack (10.2-6), SchreierTreeOfSCC (10.2-5), and TraceSchreierTreeOfSCCForward (10.2-7).
gap> S:=Semigroup(Transformation( [ 2, 2, 1, 4, 4 ] ), > Transformation( [ 3, 3, 3, 4, 5 ] ), > Transformation( [ 5, 1, 4, 5, 5 ] ) );; gap> o:=Orb(S, [1..4], OnSets, rec(orbitgraph:=true, schreier:=true));; gap> OrbSCC(o); [ [ 1 ], [ 2 ], [ 3, 5, 6, 7, 11 ], [ 4 ], [ 8 ], [ 9 ], [ 10, 12 ] ] gap> ReverseSchreierTreeOfSCC(o, 3); [ [ ,, fail,, 2, 1, 2,,,, 1 ], [ ,, fail,, 3, 5, 3,,,, 7 ] ] gap> ReverseSchreierTreeOfSCC(o, 7); [ [ ,,,,,,,,, fail,, 3 ], [ ,,,,,,,,, fail,, 10 ] ] gap> OnSets(o[11], Generators(S)[1]); [ 1, 4 ] gap> Position(o, last); 7
‣ SchreierTreeOfSCC( o, i ) | ( function ) |
Returns: The Schreier tree corresponding to the ith strongly connected component of an orbit.
If o is an orbit created by the Orb package with the option orbitgraph=true and action act, and i is a positive integer, then SchreierTreeOfSCC(o, i) returns a pair [ gen, pos ] of lists with Length(o) entries such that
act(o[pos[j]], o!.gens[gen[j]])=o[j].
The pair [ gen, pos ] corresponds to a tree with root OrbSCC(o)[i][1] and a path from the root to every element of OrbSCC(o)[i].
See also OrbSCC (10.2-1), TraceSchreierTreeOfSCCBack (10.2-6), ReverseSchreierTreeOfSCC (10.2-4), and TraceSchreierTreeOfSCCForward (10.2-7).
gap> S:=Semigroup(Transformation( [ 2, 2, 1, 4, 4 ] ), > Transformation( [ 3, 3, 3, 4, 5 ] ), > Transformation( [ 5, 1, 4, 5, 5 ] ) );; gap> o:=Orb(S, [1..4], OnSets, rec(orbitgraph:=true, schreier:=true));; gap> OrbSCC(o); [ [ 1 ], [ 2 ], [ 3, 5, 6, 7, 11 ], [ 4 ], [ 8 ], [ 9 ], [ 10, 12 ] ] gap> SchreierTreeOfSCC(o, 3); [ [ ,, fail,, 1, 3, 1,,,, 2 ], [ ,, fail,, 7, 5, 3,,,, 6 ] ] gap> SchreierTreeOfSCC(o, 7); [ [ ,,,,,,,,, fail,, 1 ], [ ,,,,,,,,, fail,, 10 ] ] gap> OnSets(o[6], Generators(S)[2]); [ 3, 5 ] gap> Position(o, last); 11
‣ TraceSchreierTreeOfSCCBack( orb, m, nr ) | ( operation ) |
Returns: A word in the generators.
orb must be an orbit object with a Schreier tree and orbit graph, that is, the options schreier and orbitgraph must have been set to true during the creation of the orbit, m must be the number of a strongly connected component of orb, and nr must be the number of a point in the mth strongly connect component of orb.
This operation traces the result of ReverseSchreierTreeOfSCC (10.2-4) and with arguments orb and m and returns a word in the generators that maps the point with number nr to the first point in the mth strongly connected component of orb. Here, a word is a list of integers, where positive integers are numbers of generators. See also OrbSCC (10.2-1), ReverseSchreierTreeOfSCC (10.2-4), SchreierTreeOfSCC (10.2-5), and TraceSchreierTreeOfSCCForward (10.2-7).
gap> S:=Semigroup(Transformation( [ 1, 3, 4, 1 ] ), > Transformation( [ 2, 4, 1, 2 ] ), > Transformation( [ 3, 1, 1, 3 ] ), > Transformation( [ 3, 3, 4, 1 ] ) );; gap> o:=Orb(S, [1..4], OnSets, rec(orbitgraph:=true, schreier:=true));; gap> OrbSCC(o); [ [ 1 ], [ 2 ], [ 3 ], [ 4, 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ] gap> ReverseSchreierTreeOfSCC(o, 4); [ [ ,,, fail, 4, 1, 1, 3 ], [ ,,, fail, 4, 4, 4, 4 ] ] gap> TraceSchreierTreeOfSCCBack(o, 4, 7); [ 1 ] gap> TraceSchreierTreeOfSCCBack(o, 4, 8); [ 3 ]
‣ TraceSchreierTreeOfSCCForward( orb, m, nr ) | ( operation ) |
Returns: A word in the generators.
orb must be an orbit object with a Schreier tree and orbit graph, that is, the options schreier and orbitgraph must have been set to true during the creation of the orbit, m must be the number of a strongly connected component of orb, and nr must be the number of a point in the mth strongly connect component of orb.
This operation traces the result of SchreierTreeOfSCC (10.2-5) and with arguments orb and m and returns a word in the generators that maps the first point in the mth strongly connected component of orb to the point with number nr. Here, a word is a list of integers, where positive integers are numbers of generators. See also OrbSCC (10.2-1), ReverseSchreierTreeOfSCC (10.2-4), SchreierTreeOfSCC (10.2-5), and TraceSchreierTreeOfSCCBack (10.2-6).
gap> S:=Semigroup(Transformation( [ 1, 3, 4, 1 ] ), > Transformation( [ 2, 4, 1, 2 ] ), > Transformation( [ 3, 1, 1, 3 ] ), > Transformation( [ 3, 3, 4, 1 ] ) );; gap> o:=Orb(S, [1..4], OnSets, rec(orbitgraph:=true, schreier:=true));; gap> OrbSCC(o); [ [ 1 ], [ 2 ], [ 3 ], [ 4, 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ] gap> SchreierTreeOfSCC(o, 4); [ [ ,,, fail, 1, 2, 2, 4 ], [ ,,, fail, 4, 4, 6, 4 ] ] gap> TraceSchreierTreeOfSCCForward(o, 4, 8); [ 4 ] gap> TraceSchreierTreeOfSCCForward(o, 4, 7); [ 2, 2 ]
generated by GAPDoc2HTML