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

/magnus/back_end/AProducts/include/APofFreeGroups.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: APofFreeGroups.h,v 1.6 2000/02/09 22:07:31 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 the AmalgProductOfFreeGroups class.
00009 //
00010 // Principal Authors: Eugene Paderin, Dmitry Pechkin
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 //   02-10-96: the preliminary release.
00017 //
00018 //   03-29-96: bugfix, more comments added.
00019 //
00020 // Special Notes:
00021 //
00022 //  * Local And Global Words
00023 //
00024 //  When dealing with AP words, we use two distinct ways of coding
00025 //  generators. The AP is defined with two groups which of them has
00026 //  its own "local" coding of generators. The result is an FP group
00027 //  generated by the same generators, but coded the different way
00028 //  (generators of the first group have the same numbers while those
00029 //  of the second one have shifted numbers -- we call this coding
00030 //  global). The user gives words in global coding using letters
00031 //  from both groups -- we do not redefine FPGroup::readWord and
00032 //  FPGroup::writeWord (so the FrontEnd developer should take this
00033 //  into account). At the same time, all manipulations with subgroups
00034 //  and their bases are being done in local coding, so we have to
00035 //  convert words from one coding into another, and vice versa.
00036 //
00037 //
00038 
00039 #ifndef _AMALGAMATED_PRODUCT_H_
00040 #define _AMALGAMATED_PRODUCT_H_
00041 
00042 #include "FreeGroup.h"
00043 #include "FPGroup.h"
00044 #include "APofFreeGroupsRep.h"
00045 
00046 
00047 class AmalgProductOfFreeGroups : public DerivedObjectOf<FPGroup,AmalgProductOfFreeGroupsRep> {
00048 
00049 public:
00050 
00051   ///////////////////////////////////////////////////////
00052   //                                                   //
00053   //  Constructors                                     //
00054   //                                                   //
00055   ///////////////////////////////////////////////////////
00056 
00057   // Copy constructor, operator= and destructor provided by compiler.
00058 
00059   // To define the amalgamated product (AP), one should give two
00060   // (free) groups as factors, and two vectors of Words which define
00061   // two subgroups in corresponding groups (so the vectors must be bases).
00062   // Then we claim the subgroups to be amalgamated, i.e. we suppose
00063   // that the ith word of the first vector is mapped to the ith word
00064   // of the second one. This is a standard way to define an AP.
00065 
00066   // At the same time, we define the AP as a FP group, so all the
00067   // methods of FPGroup is fully applicable to the AP class.
00068 
00069   AmalgProductOfFreeGroups() :
00070   DerivedObjectOf<FPGroup, AmalgProductOfFreeGroupsRep>(
00071         new AmalgProductOfFreeGroupsRep(FreeGroup(), FreeGroup(),
00072                                         VectorOf<Word>(), VectorOf<Word>() )
00073     ) {}
00074   // Default constructor is provided solely for constructing an AP group
00075   // from an input stream, e.g. like this:
00076   //
00077   //   AmalgProductOfFreeGroups AP;
00078   //   Chars errMesg = cin >> AP;
00079   //   ...
00080   // Do not use it for purposes other than this.
00081 
00082   AmalgProductOfFreeGroups(const FreeGroup& g1, const FreeGroup& g2,
00083                            const VectorOf<Word>& gen1,
00084                            const VectorOf<Word>& gen2  ) :
00085     DerivedObjectOf<FPGroup, AmalgProductOfFreeGroupsRep>(
00086         new AmalgProductOfFreeGroupsRep(g1, g2, gen1, gen2)
00087     ) {}
00088   // Construct an amalgamated product of given free groups. Given vectors
00089   // of words generate associated subgroups.
00090 
00091   AmalgProductOfFreeGroups(const SGofFreeGroup& sg1, const SGofFreeGroup& sg2)
00092     : DerivedObjectOf<FPGroup, AmalgProductOfFreeGroupsRep>(
00093         new AmalgProductOfFreeGroupsRep(sg1, sg2) 
00094       ) {}
00095   // Construct an amalgamated product with given (associated) subgroups
00096   // which store references to their parent groups.
00097 
00098   AmalgProductOfFreeGroups( const Group& G ) :
00099     DerivedObjectOf<FPGroup,AmalgProductOfFreeGroupsRep>(G) { }
00100   // Cast construtor: to cast an arbitrary group as an AP group.
00101   // NB. This rewraps the unchanged representation, hence is in general
00102   // only useful for casting a group known to be an actual AP group.
00103 
00104   // Destructor provided by compiler.
00105 
00106   ///////////////////////////////////////////////////////
00107   //                                                   //
00108   //  Accessors / Modifiers                            //
00109   //                                                   //
00110   ///////////////////////////////////////////////////////
00111 
00112   static Type type( ) { return AmalgProductOfFreeGroupsRep::type(); }
00113   // Overrides FPGroup::type();
00114   
00115   // Type actualType() const; 
00116   // Overrides pseudo-virtual FPGroup::actualType().
00117 
00118 
00119   FreeGroup factor( const NumberOfFactor& t ) const;
00120   // Returns left or right factor of the amalgamated product.
00121   // LEFT_FACTOR and RIGHT_FACTOR values are valid for number of factor.
00122 
00123   SGofFreeGroup subgroup( const NumberOfFactor& t ) const;
00124   // Returns amalgamated subgroup of left or right factor respectively.
00125   // LEFT_FACTOR and RIGHT_FACTOR values are valid for number of factor.
00126 
00127   ///////////////////////////////////////////////////////
00128   //                                                   //
00129   //  Methods dealing with group structure             //
00130   //                                                   //
00131   ///////////////////////////////////////////////////////
00132 
00133   // int order( ) const;   
00134   // Returns the order of the AP as the FP group.
00135   // Overrides pseudo-virtual FPGroup::order().
00136             
00137   Trichotomy isFree( ) const { return enhance()->isFree(); }
00138   // Returns YES if this group is free on its generators, NO if not,
00139   // and DONTKNOW if this cannot be currently determined.
00140   //@ep  Now gives answer only for some special cases;
00141   //     to be enhanced in the future.
00142   
00143   ///////////////////////////////////////////////////////
00144   //                                                   //
00145   //  Methods which deal with group elements           //
00146   //                                                   //
00147   ///////////////////////////////////////////////////////
00148       
00149   // Elt eval( const Word& w ) const;
00150   // Takes a word and evaluates it as a formal word in the generators
00151   // of the group. Returns a (possibly canonic) representative of the
00152   // element. 
00153   // Overrides pseudo-virtual FPGroup::eval().
00154 
00155   // Trichotomy wordProblem( const Word& w ) const;
00156   // Returns YES if w represents the identity, NO if not, and
00157   // DONTKNOW if no answer can be determined.
00158   // Overrides pseudo-virtual FPGroup::wordProblem().
00159 
00160   VectorOf<Word> decompose(const Word& w) const {
00161     return look()->decompose(w);
00162   }
00163   // Decomposes the given word to the product of words d_1 d_2 ....
00164   // such that every d_i belongs to one of the factors and any
00165   // two successive words belong to distinct factors.
00166   // If w is empty word, returns Vector of size 0.
00167     
00168   VectorOf<Word> reducedDecomposition(const Word& w) const {
00169     return look()->reducedDecomposition(w);
00170   }
00171   // Finds the minimal (in the sense of number of components) decomposition
00172   // of the given word. Each component belongs to one factor and any two 
00173   // successive components belong to different factors.
00174   // If w is identity element in AP, returns Vector of size 0.
00175   
00176   Word reducedFormOf(const Word& w) const {
00177     return compose(reducedDecomposition(w));
00178   }
00179   // As above, but result is presented as a single word.
00180   
00181   VectorOf<Word> normalDecomposition(const Word& w) const {
00182     return look()->normalDecomposition(w);
00183   }
00184   // Finds the normal decomposition of the given word: this is
00185   // the reduced decomposition where all components except the
00186   // first one are some right Schreier representatives.
00187   // Returns vector of components of decomposition.
00188   
00189   Word normalFormOf(const Word& w) const {
00190     return compose(normalDecomposition(w));
00191   }
00192   // Finds the normal decomposition of the given word: this is
00193   // the reduced decomposition where all components except the
00194   // first one are some right Schreier representatives.
00195   // As above, but result is presented as a single word.
00196 
00197   void cyclicDecomposition(const Word& w, VectorOf<Word>& result, 
00198                            Word& conjugator) const 
00199   {
00200     look()->cyclicDecomposition(w,result,conjugator);
00201   }
00202   // Finds cyclic reduced decomposition (named `result') of w such that 
00203   //          w = result^conjugator.
00204   // Cyclic decomposition is normal one satisfied the condition: all cyclic 
00205   // permutations are normal decompositions. Let a normal decomposition 
00206   // be g_1 * g_2 * ... * g_N, then the last one satisfies the condition above 
00207   // iff  N > 1 && factor(g1) != factor(gN)  or N <= 1.
00208   // Each word of `result' represents a component g_i of the decomposition.
00209 
00210   void cyclicReduction(const Word& w, Word& result, Word& conjugator) const {
00211     look()->cyclicReduction(w,result,conjugator);
00212   }
00213   // Finds cyclic reduction (named `result') of w such that 
00214   //          w = result^conjugator.
00215   // Cyclic decomposition is normal one satisfied the condition: all cyclic 
00216   // permutations are normal decompositions. Let a normal decomposition 
00217   // be g1 * g2 * ... * gN, then the last one satisfies the condition above 
00218   // iff  N > 1 && factor(g1) != factor(gN)  or N <= 1.
00219   // As above, but `result' is presented as a single word.
00220 
00221   int numberOfSubstitutions( const Word& w ) const {
00222     return look()->numberOfSubstitutions( w );
00223   }
00224   // If the given word represents 1 in the group
00225   // the function computes the number of uses of a relation
00226   // a = b to deduce that w = 1, i.e. in re-expressing w as 
00227   // a product of conjugates of a * b^-1, computes the number
00228   // of these conjugates.
00229 
00230   
00231   NumberOfFactor factorOfFormalWord(const Word& w) const {
00232     return look()->factorOfFormalWord(w);
00233   }
00234   // Determines the group the given formal word belongs to.
00235   
00236   NumberOfFactor factorOfElement(const Word& w) const {
00237     return look()->factorOfElement(w);
00238   }
00239   // Determines the group the given formal word belongs to
00240   // and also checks whether the given element of the product belongs to 
00241   // the amalgamated subgroup.
00242   
00243   Word localToGlobal(const LocalWord& w) const {
00244     return look()->localToGlobal(w);
00245   }
00246   // Converts local coding word into global one.
00247   
00248   LocalWord globalToLocal(const Word& w) const {
00249     return look()->globalToLocal(w);
00250   }
00251   // Converts global coding word into local one.
00252   
00253   
00254   Trichotomy isHyperbolic() const {
00255     return look()->isHyperbolic();
00256   }
00257   // In general, the problem is undecidable, so this method can
00258   // return dontknow.
00259   //@ep In present, it _always_ returns dontknow -- temporary stub.
00260   
00261   
00262   void maximalRoot(const Word& w, Word& root, int& power) const {
00263     look()->maximalRoot(w,root,power);
00264   }
00265   // Finds maximal root of given word w. The root word is stored in `root',
00266   // and its power in `power'.
00267   //@ep  This is a temporary stub implemented only for one relator case.
00268   // Included here for maintaining inheritance. Invoking this causes
00269   // an error report.
00270   
00271   //@ep  The following two methods need maximalRoot to be implemented, so
00272   // they are now defined only for one relator case.
00273   
00274   bool isProperPower(const Word& w) const {
00275     return look()->isProperPower(w);
00276   }
00277   // Determines whether w is a proper power.
00278   
00279   bool isProperPowerOfSecond(const Word& u, const Word& w, int& power) const {
00280     return look()->isProperPowerOfSecond( u, w, power );
00281   }
00282   // Determines whether u is a proper power of w.
00283   
00284   bool commute(const Word& u, const Word& w) const {
00285     return look()->commute(u,w);
00286   }
00287   // Determines whether [u,w] = 1.
00288   
00289   bool isSubgroupAbelian(const VectorOf<Word>& subgroupWords) const {
00290     return look()->isSubgroupAbelian(subgroupWords);
00291   }
00292   // Determines whether the subgroup generated by the given set of words
00293   // is abelian.
00294 
00295   bool isSubgroupTrivial(const VectorOf<Word>& vec) const {
00296     return look()->isSubgroupTrivial(vec);
00297   }
00298   // Determines whether subgroup generated by vec is trivial.
00299 
00300   bool isSubgroupCyclic(const VectorOf<Word>& vec) const {
00301     return look()->isSubgroupCyclic(vec);
00302   }
00303   // Determines whether subgroup generated by vec is cyclic.
00304   //@ep Invokes maximalRoot, so it is unusable now.
00305 
00306 
00307   ///////////////////////////////////////////////////////
00308   //                                                   //
00309   //  I/O                                              //
00310   //                                                   //
00311   ///////////////////////////////////////////////////////
00312 
00313   // void printRelators(ostream& ostr) const;
00314   // Overrides pseudo-virtual FPGroup::printRelators().
00315 
00316   // void printOn(ostream& o) const;
00317   // Overrides pseudo-virtual FPGroup::printOn().
00318 
00319   // GroupRep* readFrom(istream& istr, Chars& errMesg) const;
00320   // Overrides pseudo-virtual FPGroup::readFrom().
00321 
00322   void printDecomposition(ostream& ostr, const VectorOf<Word> deco) const {
00323     look()->printDecomposition(ostr, deco);
00324   }
00325   // Prints given vector of words which are separated by dot:
00326   //           word1 . word2 .     . wordN
00327 
00328   ///////////////////////////////////////////////////////
00329   //                                                   //
00330   //  Private helper stuff:                            //
00331   //                                                   //
00332   ///////////////////////////////////////////////////////
00333 
00334 protected:
00335 
00336   // Special wrapping constructor to wrap new representations (returned
00337   // by eg. delegated methods) and for base initialisation by derived
00338   // classes:
00339   
00340   AmalgProductOfFreeGroups( AmalgProductOfFreeGroupsRep* newrep ) :
00341   DerivedObjectOf<FPGroup,AmalgProductOfFreeGroupsRep>(newrep) { }
00342   
00343 
00344   ///////////////////////////////////////////////////////
00345   //                                                   //
00346   //  Debugging stuff                                  //
00347   //                                                   //
00348   ///////////////////////////////////////////////////////
00349 
00350 private:
00351 
00352 #ifdef DEBUG
00353   //friend int main( );
00354   friend void debugPrint(ostream&, const AmalgProductOfFreeGroups& g);
00355 #endif
00356 
00357 };
00358 
00359 #endif
00360 
00361 

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