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

/magnus/back_end/Subgroup/include/DecomposeInSubgroup.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: DecomposeInSubgroup.h,v 1.2 2000/03/03 04:17:07 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1998 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: 
00009 //
00010 // Principal Author: Dmitry Pechkin
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 // Bugs:
00017 //
00018 // Special Notes:
00019 //
00020 // Next implementation steps:
00021 //
00022 
00023 
00024 #ifndef _DECOMPOSE_IN_SUBGROUP_H_
00025 #define _DECOMPOSE_IN_SUBGROUP_H_
00026 
00027 
00028 #include "SubgroupGraph.h"
00029 #include "FreeGroup.h"
00030 #include "../AProducts/include/AP-fixups.h"
00031 
00032 // NOTE: Original generators of subgroup should be freely reduced.
00033 
00034 class DecomposeInSubgroupOfFreeGroup
00035 {
00036 public:
00037   
00038   DecomposeInSubgroupOfFreeGroup( const int ambientRank, 
00039                                   const VectorOf<Word>& gens );
00040   // Construct a subgroup of a free group. `gens' are given generators
00041   // of the subgroup.
00042 
00043   virtual ~DecomposeInSubgroupOfFreeGroup( ) { }
00044 
00045   virtual DecomposeInSubgroupOfFreeGroup* clone( ) const {
00046     return new DecomposeInSubgroupOfFreeGroup( *this );
00047   }
00048 
00049   int rankOfFreeGroup( ) const { return theAmbientRank; }
00050   // Returns the rank of the ambient free group.
00051 
00052   VectorOf<Word> generators( ) const { return theGenerators; }
00053   // Returns the given generators of the subgroup.
00054 
00055   const SubgroupGraph& graph() const { return theGraph; }
00056   // Returns an graph represinting the subgroup.
00057 
00058   VectorOf<Word> decomposeNielsenBasis( ) const {
00059     return nielsenInSubgroupGenerators;
00060   }
00061   // Returns a decomposition of a Nielsen basis for the subgroup
00062   // in the original subgroup generators.
00063 
00064   bool contains( const Word& w ) const { return theGraph.contains(w); }
00065   // Checks whether the subgroup contains the given word.
00066 
00067   Word decompose( const Word& w ) const;
00068   // Express the word `w' in the given subgroup generators.
00069 
00070   Trichotomy checkDecomposition( const Word& w ) const;
00071 
00072   //protected:
00073 
00074   DecomposeInSubgroupOfFreeGroup( const SubgroupGraph& G, 
00075                                   const VectorOf<Word>& gens );
00076 
00077   /////////////////////////////////////////////////////////////////////////
00078   //                                                                     //
00079   // IPC tools:                                                          //
00080   //                                                                     //
00081   /////////////////////////////////////////////////////////////////////////
00082 
00083   friend 
00084   ostream& operator<(ostream& ostr, const DecomposeInSubgroupOfFreeGroup& d) {
00085     d.write( ostr );
00086     return ostr;
00087   }
00088 
00089   friend 
00090   istream& operator>(istream& istr, DecomposeInSubgroupOfFreeGroup& d );
00091 
00092   virtual bool readPiece( istream& istr, const class Timer& timer );
00093 
00094 
00095 private:
00096   
00097   void init( );
00098 
00099 protected:
00100 
00101 
00102 
00103   VectorOf<Word> makeMapBetweenNielsens( SubgroupGraph& S, 
00104                                          const VectorOf<Word>& words ) const;
00105 
00106 
00107   // Data members:
00108 
00109   int theAmbientRank;
00110   VectorOf<Word> theGenerators;
00111 
00112 protected:
00113   SubgroupGraph theGraph;
00114   VectorOf<Word> nielsenInSubgroupGenerators;
00115 
00116   virtual void write( ostream& ostr ) const;
00117   int n;
00118 
00119 private:
00120 
00121   enum ReadingState { STOP, GENS, GRAPH, NIELSEN };
00122 
00123   // Data members:
00124   ReadingState readState;
00125 };
00126 
00127 
00128 
00129 
00130 class DecomposeInExpandingSubgroup : public DecomposeInSubgroupOfFreeGroup
00131 {
00132 public:
00133 
00134   DecomposeInExpandingSubgroup( int ambientRank,
00135                                 const VectorOf<Word>& constantSubgroup, 
00136                                 const VectorOf<Word>& expandingSubgroup );
00137   // Construct expanding subgroup of free group. `expandingGens' will be 
00138   // conjugated by some elements to expand the subgroup.
00139 
00140   DecomposeInSubgroupOfFreeGroup* clone( ) const {
00141     return (DecomposeInSubgroupOfFreeGroup *)
00142               new DecomposeInExpandingSubgroup(*this);
00143   }
00144 
00145   VectorOf<Word> constantGenerators( ) const { return theConstantGenerators; }
00146   // Returns the original constant generators of the subgroup.
00147 
00148   VectorOf<Word> expandingGenerators( ) const { return theExpandingGenerators;}
00149   // Returns the original expanding generators of the subgroup.
00150 
00151   VectorOf<Generator> expandingConjugators( ) const {
00152     return theExpandingConjugators;
00153   }
00154   // Returns a list of conjugators which are used to expand the subgroup.
00155   // When we expand the subgroup by a conjugator this one is appened
00156   // to the end of the list.
00157 
00158   void expandSubgroupByConjugation( const Generator& conjugator );
00159   // Expand the subgroup by a conjugator.
00160 
00161   void expressAsConjugateOfOriginalGenerator( const Generator& g, 
00162                                               Generator& og, Word& conjugator)
00163     const;
00164   // It computes an expression of the given generator `g' in an *expanded*
00165   // subgroup in original generator of the subgroup and conjugator of last one.
00166 
00167   ProductOfRelatorConjugates fullDecomposition( const Word& w ) const;
00168 
00169   Trichotomy checkDecomposition( const Word& w ) const;
00170 
00171   bool readPiece( istream& istr, const class Timer& timer );
00172 
00173 private:
00174 
00175   VectorOf<Word> shiftGenerators( const VectorOf<Word>& v, int shift );
00176 
00177 
00178   // Data members:
00179 
00180   SubgroupGraph theConstantGraph;
00181   SubgroupGraph theExpandingGraph;
00182 
00183   VectorOf<Word> theConstantGenerators;
00184   VectorOf<Word> theExpandingGenerators;  
00185 
00186   // Data for expanding subgroup:
00187   int theNumberOfExpandedGenerators;
00188   VectorOf<Generator> theExpandingConjugators;
00189   VectorOf<Word> Nc, NcInOld, Ne0InOld;
00190 
00191 protected:
00192   virtual void write( ostream& ostr ) const;
00193 
00194 
00195 private:
00196   enum ReadingState2 { STOP, BASECLASS, CONSTGRAPH, EXPANDGRAPH, CONSTGENS, 
00197                        EXPANDGENS, READNC,READNCINOLD, READNE0INOLD };
00198 
00199   // Data members:
00200   ReadingState2 readState2;
00201 };
00202 
00203 
00204 class DecomposeInSubgroupOfFPGroup : public DecomposeInExpandingSubgroup
00205 {
00206 public:
00207 
00208   DecomposeInSubgroupOfFPGroup( const FPGroup& G, const VectorOf<Word>& gens );
00209 
00210   DecomposeInSubgroupOfFreeGroup* clone( ) const {
00211     return (DecomposeInSubgroupOfFreeGroup *)
00212               new DecomposeInSubgroupOfFPGroup(*this);
00213   }
00214 
00215   FPGroup group() const { return theGroup; }
00216 
00217   void expandGraph( );
00218 
00219   int numberOfIterations( ) const { return theNumberOfIterations; }
00220 
00221   bool readPiece( istream& istr, const class Timer& timer );
00222 
00223 private:
00224 
00225   FPGroup theGroup;
00226   Generator g;
00227   int theNumberOfIterations;
00228 
00229 protected:
00230   virtual void write( ostream& ostr ) const;
00231 
00232 private:
00233   enum ReadingState3 { STOP, NEWDATA };
00234 
00235   // Data members:
00236   ReadingState3 readState3;
00237 };
00238 
00239 #endif

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