#include <ThRightNormalForm.h>
Public Types | |
typedef triple< int, int, list< Permutation > > | NF |
Presentation of a normal form. | |
Public Member Functions | |
ThRightNormalForm (int rank=0) | |
Default constructor (rank specifies the rank of a braid group the form belongs to). | |
ThRightNormalForm (int rank, int p, const list< Permutation > &d) | |
Constructor (rank specifies the rank of a braid group the form belongs to, p - a power of a half twist, and d - a list of permutations. So the pair (p,d) is a presentation). | |
ThRightNormalForm (const NF &tr) | |
Constructor (tr specifies a presentation of the normal form). | |
ThRightNormalForm (const BraidGroup &G, const Word &w) | |
Constructs the normal form of a braid word w. | |
ThRightNormalForm & | operator= (const NF &tr) |
operator NF () const | |
Cast operator (returns a representation of a normal form). | |
bool | operator== (const ThRightNormalForm &rep) const |
Compare (check if equal). | |
bool | operator!= (const ThRightNormalForm &rep) const |
Compare (check if not equal). | |
bool | operator< (const ThRightNormalForm &rep) const |
Compare (check if less, performed componentwise). | |
ThRightNormalForm | operator- () const |
ThRightNormalForm | operator * (const ThRightNormalForm &rep) const |
Multiply two normal forms. | |
ThRightNormalForm & | operator *= (const ThRightNormalForm &rep) |
Multiply a normal form by the other on the right. | |
int | getRank () const |
Get the rank of a corresponding braid group. | |
int | getPower () const |
Get half-twist power. | |
const list< Permutation > & | getDecomposition () const |
Get a list of permutations. | |
bool | isTrivial () const |
Check if a normal form is trivial. | |
Word | getWord () const |
Computes a word represented by a normal form. | |
Word | getShortWord () const |
Computes a "shorter" word represented by a normal form. | |
pair< bool, ThRightNormalForm > | areConjugate (const ThRightNormalForm &rep) const |
Check whether two braids are conjugate. | |
void | adjust () |
Adjust a normal form. | |
set< ThRightNormalForm > | computeNormalizer () const |
Compute generators of the centralizer of an element. | |
ThRightNormalForm | findSSSRepresentative (ThRightNormalForm &conjugator) const |
Find an element of a super summit set. | |
ThRightNormalForm | findSSSRepresentative () const |
void | setPower (int p) |
Set a power of a half-twist. | |
void | setDecomposition (const list< Permutation > &d) |
Set a decomposition of a normal form (without any check of "greedy conditions"). | |
Static Public Member Functions | |
static Permutation | getHalfTwistPermutation (int theIndex) |
Construct a half-twist permutation. | |
static void | adjustDecomposition (int rank, int &power, list< Permutation > &decomp) |
Adjust a normal form. | |
static pair< NF, ThRightNormalForm > | cycle (const NF &rep) |
Cycle a normal form. | |
static pair< NF, ThRightNormalForm > | decycle (const NF &rep) |
Cycle a normal form. | |
Private Types | |
enum | transformationResult { TWO_MULTIPLIERS, ONE_MULTIPLIER, NO_CHANGE } |
Private Member Functions | |
NF | inverse () const |
(Low level function) Invert a normal form. | |
NF | multiply (const ThRightNormalForm &rep) const |
(Low level function) Multiply normal forms. | |
Static Private Member Functions | |
static pair< NF, ThRightNormalForm > | findSSSRepresentative (int rank, const NF &rep) |
(Low level function) Compute super summit set representative. | |
static transformationResult | transform (int theIndex, Permutation &p1, Permutation &p2) |
static set< Permutation > | getSimpleConjugators (int rank, const NF &rep) |
static set< Permutation > | getSimpleSummitConjugators (int rank, const NF &rep) |
static pair< bool, ThRightNormalForm > | sssConstructionIteration (int rank, map< NF, NF > &sss_new1, map< NF, NF > &sss_checked1, const map< NF, NF > &sss_new2, const map< NF, NF > &sss_checked2) |
Private Attributes | |
int | theRank |
The rank of the braid group (number of strands). | |
int | theOmegaPower |
Power of omega. | |
list< Permutation > | theDecomposition |
Sequence of permutations. |
Definition at line 30 of file ThRightNormalForm.h.
|
Presentation of a normal form. The first component specifies the rank of a braid group. The second component specifies the power of the half twist. The third component specifies the list of braid permutations. Definition at line 39 of file ThRightNormalForm.h. |
|
Definition at line 273 of file ThRightNormalForm.h. |
|
Default constructor (rank specifies the rank of a braid group the form belongs to). Default rank value is for map<...> only make sure to provide the argument for this constructor Definition at line 54 of file ThRightNormalForm.h. |
|
Constructor (rank specifies the rank of a braid group the form belongs to, p - a power of a half twist, and d - a list of permutations. So the pair (p,d) is a presentation). There is no check that the pair (p,d) defines a correct normal form representation. If you are not sure if (p,d) is correct apply static function adjustDecomposition first. Definition at line 65 of file ThRightNormalForm.h. |
|
Constructor (tr specifies a presentation of the normal form).
Definition at line 71 of file ThRightNormalForm.h. |
|
Constructs the normal form of a braid word w.
|
|
Adjust a normal form. Use this function if there is a possiblitiy that the sequence of permutations does not satisfy the "greedy conditions". Right now this might happen only after use of a constructor ThRightNormalForm (const NF &tr) or, more likely, in function setDecomposition(...). This function uses adjustDecomposition( ... ). Definition at line 209 of file ThRightNormalForm.h. References adjustDecomposition(), theDecomposition, theOmegaPower, and theRank. |
|
Adjust a normal form. Use this function if the triple of arguments does not satisfy "greedy conditions". Referenced by adjust(). |
|
Check whether two braids are conjugate. Very slow function. Checks if super summit sets of two braids contain the same element (i.e., coincide). ... and the super summit sets are typically huge even for decent parameters.
|
|
Compute generators of the centralizer of an element. Very slow function. Function computes the graph with the super summit set of the element as the vertex set. Even for a small rank of a braid group (say 10) and a short braid word (say 100) the super summit set is typically huge. |
|
Cycle a normal form.
Operation:
|
|
Cycle a normal form.
Operation:
|
|
(Low level function) Compute super summit set representative.
|
|
Definition at line 226 of file ThRightNormalForm.h. References theRank. |
|
Find an element of a super summit set. Function uses cycling and decycling to decrease the canonical length of an element. |
|
Get a list of permutations.
Definition at line 157 of file ThRightNormalForm.h. References theDecomposition. |
|
Construct a half-twist permutation.
Definition at line 160 of file ThRightNormalForm.h. |
|
Get half-twist power.
Definition at line 155 of file ThRightNormalForm.h. References theOmegaPower. |
|
Get the rank of a corresponding braid group.
Definition at line 153 of file ThRightNormalForm.h. References theRank. |
|
Computes a "shorter" word represented by a normal form. Try to use the fact that the square of a half twist generates a center. If the power of half-twist is negative then it cancel them with the other permutation braids. After that, for newly obtained permutations computes braid words and concatenates them. |
|
|
|
|
|
Computes a word represented by a normal form. For each permutation-braid computes a braid-word it represents and, finally, concatenate all the results. |
|
(Low level function) Invert a normal form.
Referenced by operator-(). |
|
Check if a normal form is trivial.
Definition at line 168 of file ThRightNormalForm.h. References theDecomposition, and theOmegaPower. |
|
(Low level function) Multiply normal forms.
Referenced by operator *(), and operator *=(). |
|
Multiply two normal forms.
Definition at line 134 of file ThRightNormalForm.h. References multiply(). |
|
Multiply a normal form by the other on the right.
Definition at line 139 of file ThRightNormalForm.h. References multiply(). |
|
Cast operator (returns a representation of a normal form).
Definition at line 95 of file ThRightNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Compare (check if not equal).
Definition at line 108 of file ThRightNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Definition at line 129 of file ThRightNormalForm.h. References inverse(). |
|
Compare (check if less, performed componentwise).
Definition at line 116 of file ThRightNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Definition at line 80 of file ThRightNormalForm.h. References triple< T1, T2, T3 >::first, triple< T1, T2, T3 >::second, theDecomposition, theOmegaPower, theRank, and triple< T1, T2, T3 >::third. |
|
Compare (check if equal).
Definition at line 100 of file ThRightNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Set a decomposition of a normal form (without any check of "greedy conditions").
Definition at line 255 of file ThRightNormalForm.h. References theDecomposition. |
|
Set a power of a half-twist.
Definition at line 253 of file ThRightNormalForm.h. References theOmegaPower. |
|
|
|
|
|
Sequence of permutations.
Definition at line 300 of file ThRightNormalForm.h. Referenced by adjust(), getDecomposition(), isTrivial(), operator NF(), operator!=(), operator<(), operator=(), operator==(), and setDecomposition(). |
|
Power of omega.
Definition at line 298 of file ThRightNormalForm.h. Referenced by adjust(), getPower(), isTrivial(), operator NF(), operator!=(), operator<(), operator=(), operator==(), and setPower(). |
|
The rank of the braid group (number of strands).
Definition at line 296 of file ThRightNormalForm.h. Referenced by adjust(), findSSSRepresentative(), getRank(), operator NF(), operator!=(), operator<(), operator=(), and operator==(). |