WhiteheadAutoSet.h

Go to the documentation of this file.
00001 
00002 #ifndef _WHITEHEAD_AUTO_SET_H_
00003 #define _WHITEHEAD_AUTO_SET_H_
00004 
00005 
00006 #include "Map.h"
00007 #include "Word.h"
00008 
00009 #include <ext/hash_set>
00010 //#include <ext/stl_hash_fun.h>
00011 
00012 
00013 // --------------------- structures to create a set of maps2
00015 struct compMaps
00016 {
00017   bool operator()(  Map m1,  Map m2 ) const
00018   {
00019     return (m1 == m2);
00020   }
00021 };
00022 
00023 namespace __gnu_cxx {
00024   struct map_hash
00025   {
00026     size_t operator()(Map m) const
00027     {
00028       int h = 0;
00029       const vector<Word>& is =  m.generatingImages( );
00030       for (int i=0;i<is.size();i++)
00031         h+=is[i].length();
00032       
00033       return h;
00034     }
00035   };
00036 }
00037 
00039 typedef __gnu_cxx::hash_set<Map, __gnu_cxx::map_hash, compMaps> SetOfMaps;
00040 
00041 
00043 class AutoSet
00044 {
00045  public:
00047   virtual const SetOfMaps& getSet() const = 0;
00048 };
00049 
00050 
00051 // -------------------------- NielsenAutoSet ---------------------------- //
00052 
00054 class NielsenAutoSet : public AutoSet
00055 {
00056 
00057 public:
00058 
00059   
00061   //                                                                     //
00062   // Constructors:                                                       //
00063   //                                                                     //
00065 
00067 
00072   NielsenAutoSet( int  n );
00073 
00074   ~NielsenAutoSet( ) { }
00075 
00076   
00078   //                                                                     //
00079   // Accessors:                                                          //
00080   //                                                                     //
00082 
00084 
00087   const Map& getRandomAuto()const;
00088 
00090 
00093   const SetOfMaps& getSet() const { return theSet; }
00094  private:
00095   SetOfMaps theSet;
00096   int nGens;
00097 };
00098 
00099 // -------------------------- RestrictedWhiteheadAutoSet ---------------------------- //
00100 
00101 
00103 
00111 class RestrictedWhiteheadAutoSet : public AutoSet
00112 {
00113 
00114 public:
00115 
00116   
00118   //                                                                     //
00119   // Constructors:                                                       //
00120   //                                                                     //
00122 
00123   
00125 
00131   RestrictedWhiteheadAutoSet( int n, bool use_conj = true );
00132 
00133   ~RestrictedWhiteheadAutoSet( ) { }
00134 
00135   
00137   //                                                                     //
00138   // Accessors:                                                          //
00139   //                                                                     //
00141 
00142 
00144 
00147   const Map& getRandomAuto()const;
00148   
00150 
00153   const SetOfMaps& getSet() const { return theSet; }
00154  private:
00155   SetOfMaps theSet;
00156   int nGens;
00157 };
00158 
00159 //
00160 // -------------------------- WhiteheadAutoSetType2 ---------------------------- //
00161 //
00162 
00164 
00169 class WhiteheadAutoSetType2 : public AutoSet
00170 {
00171   
00172  public:
00173   
00174   
00176   //                                                                     //
00177   // Constructors:                                                       //
00178   //                                                                     //
00180 
00182 
00188   WhiteheadAutoSetType2(  int n );
00189 
00190   ~WhiteheadAutoSetType2( );
00191 
00192   
00194   //                                                                     //
00195   // Accessors:                                                          //
00196   //                                                                     //
00198 
00199 
00201 
00204   const SetOfMaps& getSet() const { return theSet; }
00206 
00209   const Map& getRandomAuto() const;
00210   
00211 private:
00212 
00213   Map getMap(   int n, const vector<int>& tCounts, Word a );
00214   void computeSet( int n );
00215 
00217   //                                                                     //
00218   // Data Members:                                                       //
00219   //                                                                     //
00221 
00222   const static int nElemAutos = 4;
00223 
00224   SetOfMaps theSet;
00225   int nGens;
00226 
00227 };
00228 
00229 
00230 
00232 
00238 class WhiteheadMinimization
00239 {
00240  public:
00242 
00246   WhiteheadMinimization( int n ): wSet( n ) { } 
00247 
00249 
00255   bool isMinimal( const Word& w) const;
00256   
00257   
00259 
00265   Word findMinimal( const Word& w, ostream* out = NULL )const;
00266 
00268 
00271   const WhiteheadAutoSetType2& getSet() const { return wSet; }
00272 
00273  private:
00274   WhiteheadAutoSetType2 wSet;
00275 };
00276 
00277 
00278 // ---------------------------------------------------------------------------------------- //
00279 // Check if a word is reducible by a given set
00280 // ---------------------------------------------------------------------------------------- //
00281 
00282 namespace WhiteheadAutoSet
00283 {
00285 
00293   Word reduceBy( const Word& w, const SetOfMaps& theSet );
00294 };
00295 
00296 #endif
00297 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on Mon Sep 26 18:43:45 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1