ThRightNormalForm.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class ThRightNormalForm
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
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 //--------------------------- ThRightNormalForm -----------------------------//
00026 //---------------------------------------------------------------------------//
00027 
00029 
00030 class ThRightNormalForm
00031 {
00032 public:
00034 
00039   typedef triple< int , int , list< Permutation > > NF;
00040   
00042   //                                                     //
00043   //  Constructors:                                      //
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   // Assignment operator
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   //  Operators                                          //
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   // Invert a normal form.  
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   //  Accessors:                                         //
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   //  Modifiers:                                         //
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   //  Internal functions:                                //
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   //  Data members:                                      //
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

Generated on Mon Feb 27 22:47:04 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.4