ThRightNormalForm.h

Go to the documentation of this file.

// Copyright (C) 2005 Alexander Ushakov
// Contents: Definition of class ThRightNormalForm
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//

#ifndef _ThRightNormalForm_h_
#define _ThRightNormalForm_h_

#include "tuples.h"
#include "Permutation.h"

#include "vector"
#include "list"
using namespace std;


class BraidGroup;
class Word;
class ThLeftNormalForm;


//---------------------------------------------------------------------------//
//--------------------------- ThRightNormalForm -----------------------------//
//---------------------------------------------------------------------------//


class ThRightNormalForm
{
public:

  typedef triple< int , int , list< Permutation > > NF;
  
  //                                                     //
  //  Constructors:                                      //
  //                                                     //

public:
  

  ThRightNormalForm( int rank=0 ) : 
    theRank( rank ) ,
    theOmegaPower( 0 ) ,
    theDecomposition( ) { }
    
    

  ThRightNormalForm( int rank , int p , const list< Permutation >& d ) : 
    theRank( rank ),
    theOmegaPower( p ) ,
    theDecomposition( d ) { }


  ThRightNormalForm( const NF& tr ) : 
    theRank( tr.first ),
    theOmegaPower( tr.second ) ,
    theDecomposition( tr.third ) { }
    
    
  ThRightNormalForm( const BraidGroup& G , const Word& w );
  
  
  ThRightNormalForm( const Permutation& p ) {
    theRank = p.size( );
    Permutation omega = Permutation::getHalfTwistPermutation( theRank );
    if( p.isTrivial( ) ) {
      theOmegaPower = 0;
    } else if( p==omega ) {
      theOmegaPower = 1;
    } else {
      theOmegaPower = 0;
      theDecomposition.push_back( p );
    }
  }
  
  
  ThRightNormalForm& operator = ( const NF& tr ) {
    theRank = tr.first;
    theOmegaPower = tr.second;
    theDecomposition = tr.third;
    return *this;
  }
  

  //                                                     //
  //  Operators                                          //
  //                                                     //
public:


  operator NF( ) const {
    return NF( theRank , theOmegaPower , theDecomposition );
  }
  
  
  bool operator == ( const ThRightNormalForm& rep ) const {
    return 
      theRank==rep.theRank && 
      theOmegaPower==rep.theOmegaPower && 
      theDecomposition==rep.theDecomposition;
  }
  
  
  bool operator != ( const ThRightNormalForm& rep ) const {
    return 
      theRank!=rep.theRank ||
      theOmegaPower!=rep.theOmegaPower || 
      theDecomposition!=rep.theDecomposition;
  }
  
  bool operator < ( const ThRightNormalForm& rep ) const {
    if( theRank<rep.theRank )
      return true;
    if( theRank>rep.theRank )
      return false;
    if( theOmegaPower<rep.theOmegaPower )
      return true;
    if( theOmegaPower>rep.theOmegaPower )
      return false;
    return theDecomposition<rep.theDecomposition;
  }


  // Invert a normal form.  
  ThRightNormalForm operator - ( ) const {
    return inverse( );
  }
  
  ThRightNormalForm operator * ( const ThRightNormalForm& rep ) const {
    return multiply( rep );
  }
  
  ThRightNormalForm& operator *= ( const ThRightNormalForm& rep ) {
    *this = multiply( rep );
    return *this;
  }

  operator ThLeftNormalForm( ) const;

  //                                                     //
  //  Accessors:                                         //
  //                                                     //

public:
  
  inline int getRank ( ) const { return theRank; }
  inline int getPower( ) const { return theOmegaPower; }
  inline const list< Permutation >& getDecomposition( ) const { return theDecomposition; }
  

  bool isTrivial( ) const { 
    return theOmegaPower==0 && theDecomposition.size( )==0;
  }



  Word getWord( ) const;



  Word getShortWord( ) const;



  static ThRightNormalForm randomPositive( int rank , int decomp_length );



  ThRightNormalForm increaseRank( int N ) const;
  


  pair< bool , ThRightNormalForm > areConjugate( const ThRightNormalForm& rep ) const;
  


  static void adjustDecomposition( int rank , int& power , list<Permutation>& decomp );


  void adjust( ) {
    adjustDecomposition( theRank , theOmegaPower , theDecomposition );
  }


  set<ThRightNormalForm> computeCentralizer( ) const;


  
  
  //                                                     //
  //  SSS computation:                                   //
  //                                                     //
public:
  
  /*
    Function uses cyclings and decyclings to obtain a representative of SSS.
    @return a pair (R,C), where R is the result and C is a conjugator (if A is an input then \f$R = C^{-1} A C\f$)
  */
  pair< ThRightNormalForm , ThRightNormalForm > findSSSRepresentative( ) const;
  
  

  pair< ThRightNormalForm , ThRightNormalForm > cycle( ) const;
  


  pair<ThRightNormalForm,ThRightNormalForm> decycle( ) const;
  
  

  Permutation getSimpleConjugator( const Permutation& start ) const;
  
  

  set< Permutation > getSimpleConjugators( ) const;
  
  

  Permutation getSimpleSummitConjugator( const Permutation& start ) const;
  



  set< Permutation > getSimpleSummitConjugators( ) const;




  //                                                     //
  //  USS computation:                                   //
  //                                                     //
public:



  triple< ThRightNormalForm , ThRightNormalForm , int > findUSSRepresentative( ) const;

  

  triple< Permutation , bool , int > getSimpleUltraConjugator( int period , const Permutation& start );
  
  
  set< pair< Permutation , int > > getSimpleUltraConjugators( int period );
  


  set< Permutation > getTransports( const Permutation& u , int period ) const;
  
  

  Permutation getTransport( const ThRightNormalForm& B , const Permutation& u ) const;
  
  

  Permutation getPullback( const Permutation& s ) const;



  Permutation getPullback( const Permutation& u , int period ) const;



  
  //                                                     //
  //  Modifiers:                                         //
  //                                                     //
public:

  inline void setPower( int p ) { theOmegaPower = p; }
  inline void setDecomposition( const list< Permutation >& d ) { theDecomposition = d; }
  
  //                                                     //
  //  Internal functions:                                //
  //                                                     //
private:

  
  NF inverse( ) const;
  
  
  NF multiply( const ThRightNormalForm& rep ) const;
  
  
  enum transformationResult { TWO_MULTIPLIERS , ONE_MULTIPLIER , NO_CHANGE };
  static transformationResult transform ( int theIndex , Permutation& p1 , Permutation& p2 );
  

  pair< bool , ThRightNormalForm > sssConstructionIteration( map< ThRightNormalForm , ThRightNormalForm >& sss_new1 ,
                                                             map< ThRightNormalForm , ThRightNormalForm >& sss_checked1 ,
                                                             const map< ThRightNormalForm , ThRightNormalForm >& sss_new2 ,
                                                             const map< ThRightNormalForm , ThRightNormalForm >& sss_checked2 ) const;
  
  //                                                     //
  //  Data members:                                      //
  //                                                     //

private:

  int theRank;

  int theOmegaPower;

  list< Permutation > theDecomposition;
  
};


ostream& operator << ( ostream& os, const ThRightNormalForm& nf );


#endif