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

/magnus/back_end/NilpotentGroup/include/Presentation.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 classes NilpotentRelator, NilpotentPresentation,
00005 //           PresentationForFNG
00006 //
00007 // Principal Author: Eugene Paderin
00008 //
00009 // Status: Draft
00010 //
00011 // Description:
00012 //
00013 //  1. The abstract class NilpotentPresentation presents certain nilpotent group
00014 //  or a subgroup of a nilpotent group. There are two main components of the 
00015 //  structure: theGenerators and theRelators. The former can be just one-letter
00016 //  words or words in terms of the group's initial basis. The latter are words
00017 //  int terms of presentation generators.
00018 //
00019 //  The relator looks like
00020 //     [hi, hj] = h1^p1 h2^p2 ...., 
00021 //  or:  
00022 //     h1^p1 h2^p2 ... = 1.
00023 //
00024 //
00025 // Special Notes:
00026 //
00027 //
00028 // Revision History:
00029 //
00030 
00031 #ifndef _PRESENTATION_H_
00032 #define _PRESENTATION_H_
00033 
00034 #include "MalcevSet.h"
00035 #include <iostream.h>
00036 
00037 //=======================================================================
00038 //====================== NilpotentRelator ===============================
00039 //=======================================================================
00040 
00041 // This is a structure to store relators.
00042 //
00043 // The relator looks like   [left1, left2] = right.
00044 //
00045 // If left1 == left2 == 0 then the relator is:   right = 1.
00046 
00047 struct NilpotentRelator {
00048 
00049   void setLeft( int s1, int s2 ) {
00050     left1 = s1;
00051     left2 = s2;
00052   }
00053   // sets the left side of relator
00054 
00055   bool isCommutation() const {
00056     return left1 != 0 && left2 != 0;
00057   }
00058   // returns true iff this is a commutation relator
00059 
00060 
00061   // Data
00062 
00063   int left1, left2;
00064   PolyWord right;
00065 };
00066 
00067 inline ostream& operator < ( ostream& s, const NilpotentRelator& rel ) {
00068   return s < rel.left1 < rel.left2 < rel.right;
00069 }
00070 // IPC output
00071 
00072 inline istream& operator > ( istream& s, NilpotentRelator& rel ) {
00073   return s > rel.left1 > rel.left2 > rel.right;
00074 }
00075 // IPC input
00076 
00077 ostream& operator << ( ostream& s, const NilpotentRelator& rel );
00078 
00079 inline bool operator == (const NilpotentRelator& r1, const NilpotentRelator& r2) {
00080   return r1.left1 == r2.left1 && r1.left2 == r2.left2 
00081   && (Word)r1.right == (Word)r2.right;
00082 }
00083 
00084 
00085 
00086 //=======================================================================
00087 //====================== NilpotentPresentation ==========================
00088 //=======================================================================
00089 
00090 class NilpotentPresentation {
00091 
00092 public:
00093 
00094   //---------------------------------------------------------------------
00095   //  Constructors
00096   //---------------------------------------------------------------------
00097 
00098   NilpotentPresentation() : built( false ), theCollector(1,1) { }
00099   // default constructor creates empty presentation.
00100   // The only purpose of this constructor is to allocate space for the
00101   // object. The object must be initialized by assignment.
00102 
00103   NilpotentPresentation(const NGCollector& coll,
00104                         const VectorOf<Word>& rels)
00105     : built(false), theGroupRelators(rels), theCollector(coll)
00106   { }
00107  
00108 
00109   // copy constructor, destructor and assignment operator provided by compiler
00110 
00111 
00112   //---------------------------------------------------------------------
00113   //  User interface
00114   //---------------------------------------------------------------------
00115 
00116   bool isBuilt() const { return built; }
00117   // returns true iff the presentation is built
00118 
00119   void build();
00120   // to build the presentation completely
00121 
00122   void print( ostream& s ) const;
00123   // output presentation to the stream s
00124 
00125   class FPGroup makeGroup() const;
00126   // produces a group using the presentation
00127 
00128 
00129   //---------------------------------------------------------------------
00130   //   IPC tools
00131   //---------------------------------------------------------------------
00132 
00133   virtual ostream& write(ostream& s) const;
00134 
00135   virtual istream& read(istream& s);
00136  
00137 
00138   //---------------------------------------------------------------------
00139   //  Helper methods to form and use the presentation
00140   //---------------------------------------------------------------------
00141 
00142 protected:
00143 
00144   SetOf<Word> convertRelators() const;
00145   // converts the presentation relators to Words
00146 
00147   Chars printRelator(int i) const;
00148   // outputs the ith relator in terms of theGenerators
00149 
00150   void buildKernelRelators();
00151   // builds relators di = 1.
00152 
00153   void improvePresentation();
00154   // extract identity generators from presentation
00155 
00156   //---------------------------------------------------------------------
00157   //  Virtual helper methods specific for each kind of presentation
00158   //---------------------------------------------------------------------
00159 
00160   virtual PolyWord decompose( const PolyWord& pw ) const = 0;
00161   // decomposes the word given in terms of the group generators
00162   // the result is the word in terms of theGenerators.
00163 
00164   virtual void printGenerators( ostream& s ) const = 0;
00165   // outputs the generators as a word s in terms of the group's generators
00166 
00167   //---------------------------------------------------------------------
00168   //  Data
00169   //---------------------------------------------------------------------
00170 
00171 protected:
00172 
00173   VectorOf<PolyWord> theGenerators;
00174   //theGenerators are words in terms of the group generators
00175   //They are set within constructor
00176 
00177   VectorOf<Chars> theNames;
00178   // the names for the words from theGenerators
00179   //They are set within constructor
00180 
00181   VectorOf<NilpotentRelator> theRelators;
00182   // The nilpotent relators form presentation.
00183   //They are set within build() method.
00184 
00185   bool built;
00186   // Indicates whether the presentation is built.
00187 
00188   VectorOf<Word> theGroupRelators;
00189   // The relators of the nilpotent group
00190   
00191   NGCollector theCollector;
00192   //the group collector
00193 };
00194 
00195 
00196 //=======================================================================
00197 //====================== PresentationForNG ==============================
00198 //=======================================================================
00199 
00200 // The presentation for nilpotent group
00201 // theGenerators are just 1,2, ....
00202 // theNames are c1,c2, ....
00203 // theRelators are all commutation relators plus
00204 //     di = 1 where di are words of Malcev basis for the relation subgroup
00205 //     (in FPNilpotentGroup case)
00206 
00207 
00208 
00209 
00210 class PresentationForNG : public NilpotentPresentation {
00211 
00212 public:
00213 
00214   //---------------------------------------------------------------------
00215   //  Constructors
00216   //---------------------------------------------------------------------
00217 
00218   PresentationForNG(const NGCollector& coll, const VectorOf<Word>& rels);
00219 
00220 protected:
00221 
00222   virtual PolyWord decompose( const PolyWord& pw ) const;
00223   // decomposes the word given in terms of the group generators
00224   // the result is the word in terms of theGenerators.
00225 
00226   void printGenerators( ostream& s ) const { }
00227   // nothing to print (now)
00228 
00229 };
00230 
00231 
00232 
00233 //=======================================================================
00234 //====================== PresentationForSNG =============================
00235 //=======================================================================
00236 
00237 // The presentation for subgroup of nilpotent group
00238 // theGenerators are the words of Malcev basis for the full preimage
00239 // theRelators are all commutation relators plus
00240 //     di = 1 where di are words of Malcev basis for the relation subgroup
00241 //     (in SGOfFPNilpotentGroup case)
00242 
00243 
00244 class PresentationForSNG : public NilpotentPresentation {
00245 
00246 public:
00247 
00248   //---------------------------------------------------------------------
00249   //  Constructors
00250   //---------------------------------------------------------------------
00251 
00252   PresentationForSNG(const MalcevSet& preimage, const VectorOf<Word>& rels,
00253                      const NGCollector& coll);
00254   
00255 protected:
00256 
00257   virtual PolyWord decompose( const PolyWord& pw ) const;
00258   // decomposes the word given in terms of the group generators
00259   // the result is the word in terms of theGenerators.
00260 
00261   virtual void printGenerators( ostream& s ) const;
00262 
00263 private:
00264 
00265   MalcevSet thePreimageBasis;
00266 };
00267 
00268 
00269 //=======================================================================
00270 //====================== global functions ===============================
00271 //=======================================================================
00272 
00273 
00274 inline ostream& operator < ( ostream& s, const NilpotentPresentation& pres ) {
00275   return pres.write(s);
00276 }
00277 // IPC output
00278 
00279 inline istream& operator > ( istream& s, NilpotentPresentation& pres ) {
00280   return pres.read(s);
00281 }
00282 // IPC input
00283 
00284 
00285 #endif

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