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

/magnus/back_end/NilpotentGroup/include/SubgroupBasis.h

Go to the documentation of this file.
00001 // Copyright (C) 1994 The New York Group Theory Cooperative
00002 // See magnus/doc/COPYRIGHT for the full notice.
00003 
00004 // Contents: Definition of SubgroupBasis class.
00005 //
00006 // Principal Author: Eugene Paderin
00007 //
00008 // Status: Draft
00009 //
00010 // Description:
00011 //
00012 // Special Notes:
00013 //
00014 //
00015 // Revision History:
00016 //
00017 
00018 #ifndef _SUBGROUP_BASIS_H_
00019 #define _SUBGROUP_BASIS_H_
00020 
00021 #include "NilpotentGroup.h"
00022 #include "QuickAssociations.h"
00023 #include "AbelianGroup.h"
00024 
00025 //================================================================
00026 //------------------- SubgroupBasis ------------------------------
00027 //================================================================
00028 
00029 // The class is based on QuickAssociations. The key is theWord.leader()
00030 
00031 class SubgroupBasis {
00032 
00033 public:
00034   
00035   //-----------------------------------------------------
00036   //   Constructors / initializers
00037   //-----------------------------------------------------
00038 
00039   SubgroupBasis(const VectorOf<Word>& v, const NilpotentGroup& ng);
00040 
00041   // copy constructor and destructor provided by compiler
00042 
00043   void initialize() const;     //Logical const!
00044   //Initializes theSet and makes it to be full
00045   // Slow, performs full initialization of the parent group
00046 
00047   //-----------------------------------------------------
00048   //   Accessors 
00049   //-----------------------------------------------------
00050 
00051   int cardinality() const { return theSet.cardinality(); }
00052   // returns number of elements currently in the basis
00053 
00054   const NilpotentGroup& parentGroup() const {
00055     return theParent;
00056   }
00057   //returns reference to the parent group
00058 
00059   const VectorOf<Word>& generators() const {
00060     return theGenerators;
00061   }
00062   //returns the generators
00063 
00064   bool isFull() const { return basisIsFull; }
00065   // returns true if the set is full
00066 
00067   bool isNormalClosure() const;
00068   // returns true if the basis is normal closure
00069   // Slow for the first run
00070 
00071   int theHirschNumber() const;
00072   // returns the Hirsch number of the basis
00073   // Fast, the set must be full
00074 
00075   //-----------------------------------------------------
00076   //   Methods to form the set
00077   //-----------------------------------------------------
00078 
00079   // assignment operator provided by compiler
00080 
00081   SubgroupBasis normalClosure() const;
00082   // makes the normal closure of the set
00083   // Slow
00084 
00085 
00086   //-----------------------------------------------------
00087   //   Word containment problem
00088   //-----------------------------------------------------
00089 
00090 
00091   bool contains(const Word& w) const;
00092   // returns true iff the word is a member of the set
00093   // Slow
00094 
00095   bool decomposeWord(const PolyWord& w, PolyWord& decomp) const;
00096   // if w is an element of the subgroup, computes its decomposition;
00097   // if not, decomp is empty word
00098   // returns true iff the word can be decomposed
00099   // Slow
00100 
00101   //-----------------------------------------------------
00102   //   Conversions to other presentations
00103   //-----------------------------------------------------
00104 
00105 
00106   VectorOf<Word> asWords() const;
00107   // returns the basis as a vector of words in terms of
00108   // the group generators
00109   
00110   VectorOf<PolyWord> asGroupWords() const;
00111   // returns the basis as a vector of PolyWords
00112   // in terms of the group basis
00113 
00114 
00115   //-----------------------------------------------------
00116   //   IPC I/O
00117   //-----------------------------------------------------
00118 
00119 
00120   friend ostream& operator < (ostream& s, const SubgroupBasis& b);
00121   // IPC output
00122 
00123   friend istream& operator > (istream& s, const SubgroupBasis& b);
00124   // IPC intput
00125 
00126 
00127   //-----------------------------------------------------
00128   //   Helper methods
00129   //-----------------------------------------------------
00130 
00131 private:
00132 
00133   //---------- operations in parent group ---------------
00134 
00135   //Everywhere it is assumed that arguments and return value
00136   //are expressed in terms of the parent basis
00137 
00138   PolyWord parentMultiply(const PolyWord& pw1, const PolyWord& pw2) const;
00139   // multiplies two words
00140 
00141   PolyWord parentInvert(const PolyWord& pw) const;
00142   // inverts the word
00143 
00144   PolyWord parentRaiseToPower(const PolyWord& pw, int power) const;
00145   // computes pw^power
00146 
00147   PolyWord parentCommute(const PolyWord& pw1, const PolyWord& pw2) const;
00148   // commutes two words
00149 
00150   int leaderOrder(const PolyWord& pw) const;
00151   // returns the order of the leading letter, 0 means infinity
00152 
00153 
00154   PolyWord toParentBasis(const PolyWord& pw) const;
00155   //The argument is expressed in terms of basic commutators.
00156   //Result is in terms of parent basis.
00157 
00158 
00159   PolyWord toBasicCommutators(const PolyWord& pw) const;
00160   //The argument is expressed in terms of parent basis.
00161   //Result is in terms of basic commutators.
00162 
00163 
00164   //---------- properties of the word -------------------
00165 
00166 
00167   static int power(const PolyWord& pw) { 
00168     if( pw.isEmpty() ) return 0;
00169     return pw.firstLetter().power;
00170   }
00171   // power
00172 
00173   static int absPower(const PolyWord& pw) { 
00174     if( pw.isEmpty() ) return 0;
00175     return abs( pw.firstLetter().power );
00176   }
00177   // absolute power :)
00178 
00179   static Generator leader(const PolyWord& pw) {
00180     if( pw.isEmpty() ) return 1;
00181     return pw.firstLetter().gen;
00182   }
00183   //the leading letter of the collected form
00184 
00185   static int sign(const PolyWord& pw) {
00186     if( pw.isEmpty() ) return 0;
00187     return pw.firstLetter().power > 0 ? 1 : 0;
00188   }
00189   // The sign of the leader power
00190 
00191 
00192   //----------- methods to deal with the set -----------------
00193 
00194   bool reduceWords(PolyWord& mw1, PolyWord& mw2) const;
00195   // Reduces two words
00196   // After reduction the leading term of mw1 is in minimal power,
00197   // the leading term of mw2 is greater.
00198   // Returns true iff mw1 was changed
00199   // Slow
00200 
00201   void checkMembership(PolyWord& w) const;
00202   // checks whether w can be presented as an admissible set of exponents.
00203   // returns the "remainder"
00204   // The argument must be collected
00205   // Slow
00206 
00207   bool addWord(const Word& w);
00208   // adds w to the set
00209   // returns true iff the set was changed
00210   // Slow
00211 
00212   bool addWord(const PolyWord& w);
00213   // returns true iff the set was changed
00214   // Slow
00215 
00216   void makeFull();
00217   //forms the basis
00218   // Slow
00219 
00220   void makeNormalClosure();
00221   // makes the set to be normally closed
00222   // Slow
00223 
00224   //-----------------------------------------------------
00225   //   Data
00226   //-----------------------------------------------------
00227 
00228 private:
00229 
00230   NilpotentGroup theParent;
00231   VectorOf<Word> theGenerators;
00232 
00233   QuickAssociationsOf<Generator, PolyWord> theSet;
00234   bool basisIsFull;
00235   Trichotomy isNormal;
00236 
00237   int hirschNumber;
00238 
00239 };
00240 
00241 #endif

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