00001
00002
00003
00004
00005
00006
00007
00008
00009 #ifndef _ThRightNormalForm_h_
00010 #define _ThRightNormalForm_h_
00011
00012 #include "tuples.h"
00013 #include "Permutation.h"
00014
00015 #include "vector"
00016 #include "list"
00017 using namespace std;
00018
00019
00020 class BraidGroup;
00021 class Word;
00022
00023
00024
00025
00026
00027
00029
00030 class ThRightNormalForm
00031 {
00032 public:
00034
00039 typedef triple< int , int , list< Permutation > > NF;
00040
00042
00043
00044
00046
00047 public:
00048
00050
00054 ThRightNormalForm( int rank=0 ) :
00055 theRank( rank ) ,
00056 theOmegaPower( 0 ) ,
00057 theDecomposition( ) { }
00058
00059
00061
00065 ThRightNormalForm( int rank , int p , const list< Permutation >& d ) :
00066 theRank( rank ),
00067 theOmegaPower( p ) ,
00068 theDecomposition( d ) { }
00069
00071 ThRightNormalForm( const NF& tr ) :
00072 theRank( tr.first ),
00073 theOmegaPower( tr.second ) ,
00074 theDecomposition( tr.third ) { }
00075
00077 ThRightNormalForm( const BraidGroup& G , const Word& w );
00078
00079
00080 ThRightNormalForm& operator = ( const NF& tr ) {
00081 theRank = tr.first;
00082 theOmegaPower = tr.second;
00083 theDecomposition = tr.third;
00084 return *this;
00085 }
00086
00088
00089
00090
00092 public:
00093
00095 operator NF( ) const {
00096 return NF( theRank , theOmegaPower , theDecomposition );
00097 }
00098
00100 bool operator == ( const ThRightNormalForm& rep ) const {
00101 return
00102 theRank==rep.theRank &&
00103 theOmegaPower==rep.theOmegaPower &&
00104 theDecomposition==rep.theDecomposition;
00105 }
00106
00108 bool operator != ( const ThRightNormalForm& rep ) const {
00109 return
00110 theRank!=rep.theRank ||
00111 theOmegaPower!=rep.theOmegaPower ||
00112 theDecomposition!=rep.theDecomposition;
00113 }
00114
00116 bool operator < ( const ThRightNormalForm& rep ) const {
00117 if( theRank<rep.theRank )
00118 return true;
00119 if( theRank>rep.theRank )
00120 return false;
00121 if( theOmegaPower<rep.theOmegaPower )
00122 return true;
00123 if( theOmegaPower>rep.theOmegaPower )
00124 return false;
00125 return theDecomposition<rep.theDecomposition;
00126 }
00127
00128
00129 ThRightNormalForm operator - ( ) const {
00130 return inverse( );
00131 }
00132
00134 ThRightNormalForm operator * ( const ThRightNormalForm& rep ) const {
00135 return multiply( rep );
00136 }
00137
00139 ThRightNormalForm& operator *= ( const ThRightNormalForm& rep ) {
00140 *this = multiply( rep );
00141 return *this;
00142 }
00143
00145
00146
00147
00149
00150 public:
00151
00153 inline int getRank ( ) const { return theRank; }
00155 inline int getPower( ) const { return theOmegaPower; }
00157 inline const list< Permutation >& getDecomposition( ) const { return theDecomposition; }
00158
00160 static Permutation getHalfTwistPermutation( int theIndex ) {
00161 Permutation result( theIndex );
00162 for( int i=0 ; i<theIndex ; ++i )
00163 result[i] = theIndex-i-1;
00164 return result;
00165 }
00166
00168 bool isTrivial( ) const {
00169 return theOmegaPower==0 && theDecomposition.size( )==0;
00170 }
00171
00173
00177 Word getWord( ) const;
00179
00185 Word getShortWord( ) const;
00186
00188
00193 pair<bool,ThRightNormalForm>
00194 areConjugate( const ThRightNormalForm& rep ) const;
00195
00197
00200 static void adjustDecomposition( int rank , int& power , list<Permutation>& decomp );
00201
00203
00209 void adjust( ) {
00210 adjustDecomposition( theRank , theOmegaPower , theDecomposition );
00211 }
00212
00214
00218 set<ThRightNormalForm> computeNormalizer( ) const;
00219
00221
00224 ThRightNormalForm
00225 findSSSRepresentative( ThRightNormalForm& conjugator ) const;
00226 ThRightNormalForm findSSSRepresentative( ) const {
00227 return findSSSRepresentative( theRank , *this ).first;
00228 }
00229
00230
00232
00236 static pair<NF,ThRightNormalForm> cycle( const NF& rep );
00238
00242 static pair<NF,ThRightNormalForm> decycle( const NF& rep );
00243
00244
00246
00247
00248
00250 public:
00251
00253 inline void setPower( int p ) { theOmegaPower = p; }
00255 inline void setDecomposition( const list< Permutation >& d ) { theDecomposition = d; }
00256
00258
00259
00260
00262 private:
00263
00265 NF inverse( ) const;
00267 NF multiply( const ThRightNormalForm& rep ) const;
00268
00270 static pair<NF,ThRightNormalForm>
00271 findSSSRepresentative( int rank , const NF& rep );
00272
00273 enum transformationResult { TWO_MULTIPLIERS , ONE_MULTIPLIER , NO_CHANGE };
00274 static transformationResult transform ( int theIndex , Permutation& p1 , Permutation& p2 );
00275
00276 static set<Permutation> getSimpleConjugators( int rank , const NF& rep );
00277
00278 static set<Permutation> getSimpleSummitConjugators( int rank , const NF& rep );
00279
00280 static pair<bool,ThRightNormalForm>
00281 sssConstructionIteration( int rank ,
00282 map< NF , NF >& sss_new1 ,
00283 map< NF , NF >& sss_checked1 ,
00284 const map< NF , NF >& sss_new2 ,
00285 const map< NF , NF >& sss_checked2 );
00286
00288
00289
00290
00292
00293 private:
00294
00296 int theRank;
00298 int theOmegaPower;
00300 list< Permutation > theDecomposition;
00301
00302 };
00303
00304
00305 ostream& operator << ( ostream& os, const ThRightNormalForm& nf );
00306
00307
00308
00309 #endif