DCBraidReduction.h

Go to the documentation of this file.

// Contents: Classes implementing divide and conquer algorithm for braid reduction

//
// Principal Author: Alexei Miasnikov (2006)
//
// Status:
//
// Revision History:
//

#ifndef DC_BRAID_REDUCTION_H
#define DC_BRAID_REDUCTION_H

#include <list>
#include "Word.h"
#include "ShortBraidForm.h"
#include <iterator>

class Partition
{
 public:
  virtual list<int> getPartition(const Word& w )=0;
};

class Perturbation
{
 public:
  virtual Word perturb( const Word& w)=0;
};

class UniformPartition : public Partition
{
 public:
  UniformPartition(){}
  list<int> getPartition(const Word& w ){
    list<int> indices;

    int k=10;  
    int segment = int(w.length() / k);
    int last_segment = w.length() - k*int(w.length() / k);
    
    for( int i=1;i<k-1;i++)
      indices.push_back(segment*i);
    
    if (last_segment  >= segment / 2){
      indices.push_back(segment*(k-1));
      indices.push_back(segment*(k-1)+ last_segment );
    } else {
      indices.push_back(segment*(k-1) + last_segment);
    }
    return indices;
  }

};


struct CommDivider
{
  int length;
  int begin;
  int end;
  int gen;
  friend ostream& operator << (ostream& out, const CommDivider& cd){
    out << "( " << cd.length << " : " << cd.gen <<  " | " 
        << cd.begin << " , " << cd.end << " )" << flush;
    return out;
  }
};

struct lCommDivider
{
  bool operator () (const CommDivider& c1,const CommDivider& c2 ) {
    return (c1.length < c2.length);
  }
};

class MaxCommutePartition
{
 public:
  MaxCommutePartition( int n, const Word& w ): N(n-1)
    {
      findCommutParts( w );
    }
  
    const vector<CommDivider>& getPartition() const { return partition; }

 private:
  void findCommutParts( const Word& w ){
    
    
    int i=0;
    int LEN_THRESHOLD = 5;

    vector<int> positions(N+2,-1); // +2 for the left and right padding
    //vector<int> lastPos(N+2,0);
    
    for (ConstWordIterator wI=w.begin();wI!=w.end();wI++,i++){
      Generator g = *wI;
      int absg = abs(g);
      int pos = max(positions[absg],max(positions[absg-1],positions[absg+1])) + 1;
      
      if ( pos - positions[absg] > LEN_THRESHOLD) {
        if (absg > 1 && absg < N-1 ){
          CommDivider cd;
          cd.length = pos - positions[absg];
          cd.begin = positions[absg] + 1;
          cd.end = pos - 1;
          cd.gen = absg;
          partition.push_back( cd );
        }
      }

      //      lastPos[absg]   = positions[absg];
      positions[absg] = pos;
      
    }
    sort(partition.begin(),partition.end(),lCommDivider());
    copy(partition.begin(),partition.end(),ostream_iterator<CommDivider>(cout,"\n"));
  }
 private:
  int N;
  vector<CommDivider> partition;
};



//
//
//   DCBraidReduction
//
//

class DCBraidReduction
{
 public:
  DCBraidReduction(int n, Perturbation* pert, Partition* part): 
    thePerturb( pert ),
    thePartition( part ),
    N( n ) {}
  

  Word shorten( const Word& w ) const {
    Word sw = shortenBraid( N, w );
    list<int> indices = thePartition->getPartition( w );
    list<int>::const_iterator iI = indices.begin();
    int c_index = *iI;

    Word result;
    int i=0;
    for( WordIterator I=sw.begin();I!=sw.end();I++,i++){
      Word p_w;
      if ( i < c_index || iI == indices.end())
        p_w.push_back(*I);
      else {
        result *= shortenBraid(N,p_w);
        p_w = Word();
        iI++;
        c_index = *I;
      }
    }
    
    cout << result << endl;
    return result;
  }
 private:

  int N;
  Perturbation* thePerturb;
  Partition*    thePartition;
  
};



#endif