Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/Todd-Coxeter/include/CosetEnumerator.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: CosetEnumerator.h,v 1.6 2000/03/03 04:18:34 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1996 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 //
00008 // Contents: Definition of class PermutationRepresentation, CosetEnumerator.
00009 //
00010 // Principal Author: Alexey Myasnikov
00011 //
00012 // Status: Useable
00013 //
00014 // Usage:
00015 //
00016 // Revision History:
00017 //
00018 //
00019 
00020 
00021 #ifndef _COSET_ENUMERATOR_H_
00022 #define _COSET_ENUMERATOR_H_
00023 
00024 #include "CosetTables.h"
00025 #include "FPGroup.h"
00026 
00027 // ------------------------- PermutationRepresentation --------------//
00028 class PermutationRepresentation {
00029 public:  
00030   PermutationRepresentation():permTable(NULL), numberOfGens(0) { }
00031 
00032   PermutationRepresentation(const PermutationRepresentation& p);
00033   
00034   ~PermutationRepresentation() { 
00035     if (permTable)
00036       delete [] permTable;
00037   }
00038   
00039   PermutationRepresentation& operator = ( const PermutationRepresentation& p);
00040 
00041   void printOn(const VectorOf<Chars>& n, ostream& ostr)const;
00042   // prints permutations : x1 = (1 2 5) (7 8) ...
00043   // n - names of generators Xi
00044 
00045   Word representativeOf(const Word& )const;
00046   //returns a representative of w
00047 
00048   const VectorOf<Word>& getRepresentatives()const{
00049     return representatives;
00050   }
00051   // returns vector of representatives
00052 
00053   bool isEmpty()const { return  permTable == NULL;}
00054 
00055   /////////////////////////////////////////////////////////////////////////
00056   //                                                                     //
00057   // IPC tools:                                                          //
00058   //                                                                     //
00059   /////////////////////////////////////////////////////////////////////////
00060 
00061   friend ostream& operator < (ostream& ostr,
00062                               const PermutationRepresentation& PR )
00063   {
00064     ostr < PR.numberOfGens;
00065     ostr < PR.representatives;
00066     for (int i=0;i<PR.numberOfGens;i++)
00067       ostr < PR.permTable[i];
00068     return ostr;
00069   }
00070   
00071   friend istream& operator > ( istream& istr, PermutationRepresentation& PR)
00072   {
00073     istr > PR.numberOfGens;
00074     istr > PR.representatives;
00075     if (PR.permTable)
00076       delete [] PR.permTable;
00077     PR.permTable = new ListOf< VectorOf<int> >[PR.numberOfGens];
00078     for (int i=0;i<PR.numberOfGens;i++)
00079       istr > PR.permTable[i];    
00080     return istr;
00081   }
00082  
00083 private:
00084   friend class CosetEnumerator;
00085   PermutationRepresentation(int numOfGens):
00086     numberOfGens(numOfGens),
00087     permTable(new ListOf< VectorOf<int> >[numOfGens])   
00088     {}
00089 
00090   void addCycle(int g,const VectorOf<int>& v);
00091   
00092   void setRepresentatives(const VectorOf<Word>& r){
00093     if (r.length()==0)
00094       error("void setRepresentatives(const VectorOf<Word>& r) : "
00095             "wrong parameter");
00096     representatives = r;
00097   }
00098 
00099   int searchNext(const Generator& g,int coset)const;
00100 
00101   ListOf< VectorOf<int> >* permTable;    
00102   int numberOfGens;
00103   VectorOf<Word> representatives;
00104 };
00105 
00106 // ------------------------- CosetEnumerator --------------//
00107 
00108 class CosetEnumerator {
00109 public:
00110 
00111   // First constructors check for group(subgroup) be infinite
00112   // if so happens, than no coset enumeration proceeded, and
00113   // no representatives are built. So before asking for
00114   // representaties or permutations check order(index) be
00115   // more than 0.
00116 
00117   CosetEnumerator(const FPGroup& group); 
00118   // Constructor for order of a group problem
00119   CosetEnumerator(const FPGroup& group,const VectorOf<Word>& subgroup);
00120   // Constructor for index of a subgroup problem
00121 
00122 
00123   ~CosetEnumerator();
00124   /////////////////////////////////////////////////////////////////////// 
00125   //                                                                   //
00126   // Methods                                                           //
00127   //                                                                   //
00128   ///////////////////////////////////////////////////////////////////////
00129 
00130   int enumerate();
00131   // Returns a order of the group, or index of the subgroup
00132   // in the group. It depends of which constructor was called
00133   
00134   const VectorOf<Word> schreierRepresentatives()const{
00135     if (schreierRepres.length() == 0)
00136       error("const VectorOf<Word> schreierRepresentatives()const :"
00137             "cosets have to be enumerated first.");
00138     return schreierRepres;
00139   }
00140   // Returns Schreier representatives. makeRepresentatives() has to be
00141   // called before.
00142 
00143   const PermutationRepresentation& permutationRepresentation()const{
00144     return thePermutationRepresentation;
00145   }
00146   // Returns Schreier representatives. makeRepresentatives() has to be
00147   // called before.
00148 
00149   /////////////////////////////////////////////////////////////////////// 
00150   //                                                                   //
00151   // Operators                                                         //
00152   //                                                                   //
00153   ///////////////////////////////////////////////////////////////////////
00154   
00155 
00156 private:
00157   bool addCoset(int coset_num);
00158   // Adds a new coset to tables
00159   void  iterateTables( );
00160   // Filles tables
00161   void removeCollisions( );
00162   // removes current collisions, which exist in
00163   // set of relations
00164   bool infinite()const;
00165   // True if an abelianization of the group is infinite
00166   CosetEnumerator(const CosetEnumerator& );
00167   // Copy constructor is not allowed
00168   void makeRepresentatives(); 
00169   // fills schreierRepres vector, with Schreier representatives
00170   void makePermutations();
00171 
00172   CosetRelationsSet theRelationSet;
00173   // set of the ralations. It`s unique
00174   CosetTable** tables;
00175   // array of all coset tables
00176   FPGroup theGroup;
00177   VectorOf<Word> theSubgroup;
00178   // Generators of the subgroup (if exists)
00179   int theOrder;
00180   // computed order of the group or index of the subgroup
00181   bool haveFastSolution;
00182   // True if have fast sulution (I made some 
00183   //fast checks in constructors)
00184   int numberOfGroupRelators;
00185   // Number of tables made for group relators
00186   int numberOfTables;
00187   // Number of tables 
00188   VectorOf<Integer> cosetNumbers;
00189   VectorOf<Word> schreierRepres;
00190   PermutationRepresentation thePermutationRepresentation;
00191   BTree<int,int> cosets2repres;
00192 
00193 };
00194 #endif
00195 
00196 
00197 
00198 
00199 
00200 
00201 
00202 
00203 
00204 
00205 
00206 
00207 
00208 
00209 
00210 
00211 
00212 
00213 
00214 
00215 
00216 
00217 
00218 
00219 
00220 
00221 
00222 
00223 
00224 
00225 
00226 
00227 
00228 
00229 
00230 
00231 
00232 
00233 
00234 
00235 
00236 
00237 
00238 
00239 
00240 
00241 
00242 
00243 
00244 
00245 
00246 
00247 
00248 
00249 
00250 
00251 
00252 
00253 
00254 
00255 
00256 
00257 

Generated at Tue Jun 19 09:49:43 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001