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

/magnus/back_end/Subgroup/include/Subgroup.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 SubgroupRep and Subgroup classes.
00005 //
00006 // * provisional one-class implementation of the notion of subgroup
00007 //
00008 // Principal Authors: Stephane Collart, Roger Needham
00009 //
00010 // Status: Draft
00011 //
00012 // Description:
00013 //
00014 //   A subgroup stores a shared-reference `copy' of its parent group.
00015 //   Enhancements to the parent group are thus available to its
00016 //   subgroups. The subgroup is generated by (formal) words interpretable
00017 //   in the generators of the parent group.
00018 //
00019 // Caveats:
00020 //
00021 // * If adding data members which store information computed about the
00022 //   the subgroup, make sure that subgroup manipulators which modify the
00023 //   semantics of the subgroup (for instance addGenerator()) either
00024 //   recompute or erase any data which might become invalid.
00025 //
00026 // Restrictions:
00027 //
00028 // * The subgroup does not store names for its generators (generating
00029 //   words): as the subgroup is mutable, this would involve finicky work.
00030 //
00031 // Bugs:
00032 //
00033 // * Being stored as a set, the generators do not have a fixed controllable
00034 //   order when generators are added or deleted, making the meaning of
00035 //   of formal words in the subgroup generators vary unpredictably.
00036 //
00037 // Revision History:
00038 //
00039 // * First implemented: oct 94.
00040 //
00041 // Notes:
00042 //
00043 // * If it becomes necessary to initialise subgroups with unspecified parent
00044 //   groups, several alternatives are possible
00045 //   - Group can be given a default constructor
00046 //   - SubgroupRep can be made to derive from a representation
00047 //     `UnspecifiedSubgroupRep' not requiring a parent group
00048 //
00049 // Questions:
00050 //
00051 // * It might be better to store the subgroup generators as a vector, in
00052 //   order to have faster permanent direct access, for instance for
00053 //   interpreting subgroup elements in the parent group. This would
00054 //   make adjoining and removing generators less efficient. Another
00055 //   possibility is taking seperate representations.
00056 //
00057 
00058 #ifndef _SUBGROUP_H_
00059 #define _SUBGROUP_H_
00060 
00061 #include "FGGroupRep.h"
00062 #include "FGGroup.h"
00063 #include "FPGroup.h"
00064 #include "File.h"
00065 #include "CosetEnumerator.h"
00066 
00067 struct SubgroupRep : FGGroupRep {
00068 
00069   // Constructors:
00070 
00071   SubgroupRep( const FGGroup& parent )
00072   : FGGroupRep(0),
00073          theParentGroup(parent)
00074   { }
00075 
00076   SubgroupRep( const FGGroup& parent, const VectorOf<Word>& gens )
00077   : FGGroupRep( gens.length() ),
00078          theParentGroup( parent ),
00079          theGenerators( gens )
00080   { }
00081 
00082   SubgroupRep( const FGGroup& parent, const SetOf<Word>& gens );
00083   // @rn Can do without this when we have container class conversions.
00084 
00085 
00086   // Representation methods:
00087 
00088   PureRep* clone( ) const { return new SubgroupRep(*this); }
00089   // overrides PureRep* FGGroupRep::clone();
00090 
00091   static const Type theSubgroupType;
00092 
00093   static Type type( ) { return theSubgroupType; }
00094 
00095   Type actualType( ) const { return type(); }
00096   // Overrides FGGroupRep::actualType( )
00097 
00098 
00099   // Operators:
00100 
00101 private:
00102 
00103   SubgroupRep& operator = ( const SubgroupRep& );
00104   // disable assignment
00105 
00106 public:
00107 
00108   // Methods dealing with group structure:
00109   // @stc these are implemented provisionally in a trivial way
00110  
00111   int order( ) const { return -1; }
00112   // overrides FGGroupRep::...
00113 
00114   Trichotomy isTrivial( ) const { return DONTKNOW; }
00115   // overrides FGGroupRep::...
00116 
00117   Trichotomy isFinite( ) const { return DONTKNOW; }
00118   // overrides FGGroupRep::...
00119 
00120   Trichotomy isInfinite( ) const { return DONTKNOW; }
00121   // overrides FGGroupRep::...
00122 
00123   Trichotomy isAbelian( ) const { return DONTKNOW; } //@rn can do
00124   // overrides FGGroupRep::...
00125 
00126   // Methods dealing with group elements:
00127 
00128   // Inherited from FGGroupRep:
00129   // Elt makeIdentity( ) const;
00130 
00131   // Inherited from FGGroupRep:
00132   // Bool isSyntacticIdentity(const Elt&) const
00133 
00134   Trichotomy areEqual(const Elt&, const Elt&) const { return DONTKNOW; } //@rn can do
00135   // overrides FGGroupRep::...
00136   // @stc provisional trivial implementation
00137 
00138   // Inherited from FGGroupRep:
00139   // Elt firstElt( ) const
00140 
00141   // Inherited from FGGroupRep:
00142   // Elt nextElt(const Elt&) const
00143   // beware: this deals with formal words in the subgroup generators:
00144   // to get an element in the parent group, apply eval
00145          
00146   // Inherited from FGGroupRep:
00147   // Elt multiply(const Elt&, const Elt&) const
00148   // result is as actual type of args: if formal words in subgroup
00149   // generators, then such; if elt in parent group, then such
00150   // if mixed, then nonsense
00151 
00152   // Inherited from FGGroupRep:
00153   // Elt inverseOf(const Elt&) const
00154   // @stc this should really override with appropriate algorithm
00155          
00156   // Inherited from FGGroupRep:
00157   // Elt raiseToPower(const Elt&, int) const
00158   // @stc this should really override with appropriate algorithm
00159 
00160   // Inherited from FGGroupRep:
00161   // Elt conjugateBy(const Elt&, const Elt&) const
00162   // @stc this should really override with appropriate algorithm
00163 
00164   // Inherited from FGGroupRep:
00165   // Elt commutator(const Elt&, const Elt&) const
00166   // @stc this should really override with appropriate algorithm
00167 
00168   Elt eval( const Word& w ) const;
00169   // overrides FGGroupRep::...
00170  
00171   Trichotomy wordProblem( const Word& w ) const;
00172   // overrides FGGroupRep::...
00173  
00174   Trichotomy conjugacyProblem( const Word& u, const Word& v ) const;
00175   // overrides FGGroupRep::...
00176 
00177   Word findRelator( );
00178 
00179   Bool redundantRelator(const Word& u);
00180   // This tries as best it can to decide whether the given word is a
00181   // product of conjugates of words from relators.
00182 
00183   // I/O:
00184  
00185   void printOn(ostream&) const { }
00186   // overrides FGGroupRep::...
00187   // @stc provisional
00188 
00189   virtual GroupRep* readFrom(istream&, Chars&) const { return 0; }
00190   // overrides FGGroupRep::...
00191   // @stc provisional: do not call...
00192 
00193   // Inherited from FGGroupRep:
00194   // virtual void printGenerator( ostream& ostr, int n ) const;
00195   // virtual void printGenerators( ostream& ostr ) const;
00196   // virtual void printWord( ostream& ostr, const Word& w ) const;
00197 
00198 
00199   // Data members:
00200 
00201   // Inherited from FGGroupRep:
00202   // int theOrder;
00203   // int theNumberOfGenerators;
00204   // VectorOf<Chars> theNamesOfGenerators;
00205 
00206   FGGroup theParentGroup;
00207 
00208   VectorOf<Word> theGenerators;
00209 
00210   // @rn Provisional members which support finding relators:
00211 
00212   Word lastWordTried;
00213   // The last cyclically reduced word we checked for relatorness.
00214   // Start with the empty word.
00215 
00216   SetOf<Word> relators;  // The relators we've found so far.
00217 
00218 };
00219 
00220 
00221 //------------------------- Subgroup ---------------------------//
00222 
00223 
00224 class Subgroup : public FGGroup {
00225 
00226 public:
00227 
00228   ///////////////////////////////////////////////////////
00229   //                                                   //
00230   //  Constructors                                     //
00231   //                                                   //
00232   ///////////////////////////////////////////////////////
00233 
00234   // @stc at some point, this default construtor may be wanted (see notes)
00235   // Subgroup( ) : FGGroup( new SubgroupRep() ) { }
00236   // to initialise an unspecified subgroup
00237 
00238   Subgroup( const FGGroup& parent )
00239   : FGGroup( new SubgroupRep( parent ) )
00240   { }
00241   // to make the trivial subgroup
00242 
00243   Subgroup( const FGGroup& parent, const VectorOf<Word>& gens )
00244   : FGGroup( new SubgroupRep(parent,gens) )
00245   { }
00246   // to make a finitely generated subgroup with a vector of unnamed
00247   // generators
00248 
00249   Subgroup( const FGGroup& parent, const SetOf<Word>& gens )
00250   : FGGroup( new SubgroupRep(parent,gens) )
00251   { }
00252   // to make a finitely generated subgroup with a set of unnamed
00253   // generators
00254 
00255 
00256   ///////////////////////////////////////////////////////
00257   //                                                   //
00258   //  Accessors                                        //
00259   //                                                   //
00260   ///////////////////////////////////////////////////////
00261 
00262   static Type type( ) { return SubgroupRep::type(); }
00263 
00264   // Inherited from FGGroup:
00265   // Chars FGGroup::nameOfGenerator( int i ) const;
00266   // VectorOf<Chars> FGGroup::namesOfGenerators( ) const;
00267 
00268   const FGGroup& parentGroup( ) const { return look()->theParentGroup; }
00269 
00270   const VectorOf<Word>& generators( ) const { return look()->theGenerators; }
00271 
00272   void setParentGroup( const Group& g ) { change()->theParentGroup = g; }
00273 
00274   void setGenerators( const VectorOf<Word>& s ) { change()->theGenerators = s; }
00275 
00276 public:
00277 
00278   ///////////////////////////////////////////////////////
00279   //                                                   //
00280   //  Subgroup manipulators                            //
00281   //                                                   //
00282   ///////////////////////////////////////////////////////
00283 
00284   // NB manipulators which modify the semantics of the subgroup must
00285   // modify all necessary stored data to maintain consistency
00286 
00287   Subgroup& addGenerator( const Word& w );
00288 
00289   Subgroup& deleteGenerator( const Word& w );
00290 
00291   ///////////////////////////////////////////////////////
00292   //                                                   //
00293   //  Group structure methods                          //
00294   //                                                   //
00295   ///////////////////////////////////////////////////////
00296  
00297   // Inherited from FGGroup:
00298   // int order( ) const;             // pseudo-virtual
00299   // Trichotomy isTrivial( ) const;  // pseudo-virtual
00300   // Trichotomy isFinite( ) const;   // pseudo-virtual
00301   // Trichotomy isInfinite( ) const; // pseudo-virtual
00302   // Trichotomy isAbelian( ) const;  // pseudo-virtual
00303  
00304   ///////////////////////////////////////////////////////
00305   //                                                   //
00306   //  Methods which deal with group elements           //
00307   //                                                   //
00308   ///////////////////////////////////////////////////////
00309 
00310   // Inherited from FGGroup:
00311   // Elt makeIdentity( ) const;                               // pseudo-virtual
00312   // Bool isSyntacticIdentity(const Elt& e) const;            // pseudo-virtual
00313   // Trichotomy areEqual(const Elt& e1, const Elt& e2) const; // pseudo-virtual
00314   // Elt firstElt( ) const;                                   // pseudo-virtual
00315   // Elt nextElt(const Elt& e) const;                         // pseudo-virtual
00316   // Elt multiply(const Elt& e1, const Elt& e2) const;        // pseudo-virtual
00317   // Elt inverseOf(const Elt& e) const;                       // pseudo-virtual
00318   // Elt raiseToPower(const Elt& e, int n) const;             // pseudo-virtual
00319   // Elt conjugateBy(const Elt& e1, const Elt& e2) const;     // pseudo-virtual
00320   // Elt commutator(const Elt& e1, const Elt& e2) const;      // pseudo-virtual
00321   // Elt eval( const Word& w ) const;                         // pseudo-virtual
00322   // Trichotomy wordProblem( const Word& w ) const;           // pseudo-virtual
00323   // Trichotomy conjugacyProblem( const Word& u, const Word& v ) const;
00324                                                               // pseudo-virtual
00325 
00326   Word findRelator( ) { return enhance()->findRelator(); }
00327   // Attempts to find and return a relator for this group.
00328   // The words returned by successive calls will be distinct, but
00329   // they may be redundant as relators.
00330   // @rn We could use some means of querying whether this has any
00331   //     chance at all, e.g., is there at least a partial soln of the
00332   //     word problem for the parent group?
00333 
00334   Bool redundantRelator(const Word& u) {
00335          return enhance()->redundantRelator(u);
00336   }
00337   
00338   ///////////////////////////////////////////////////////
00339   //                                                   //
00340   //  Methods which deal with sets of group elements   //
00341   //                                                   //
00342   ///////////////////////////////////////////////////////
00343  
00344   // Inherited from FGGroup:
00345   // SetOf<Elt> setMultiply(const SetOf<Elt>& S1, const SetOf<Elt>& S2) const;
00346   // SetOf<Elt> setMultiply(const Elt& e, const SetOf<Elt>& S) const;
00347   // SetOf<Elt> setMultiply(const SetOf<Elt>& S, const Elt& e) const;
00348   // SetOf<Elt> conjugateBy(const SetOf<Elt>& S1, const SetOf<Elt>& S2) const;
00349   // SetOf<Elt> conjugateBy(const Elt& e, const SetOf<Elt>& S) const;
00350   // SetOf<Elt> conjugateBy(const SetOf<Elt>& S, const Elt& e) const;
00351   // void closeUnderInverses(SetOf<Elt>& S) const;
00352   // void closeUnderCyclicPermutations(SetOf<Word>& S) const;
00353  
00354   ///////////////////////////////////////////////////////
00355   //                                                   //
00356   //  Representation access methods                    //
00357   //                                                   //
00358   ///////////////////////////////////////////////////////
00359  
00360 private:
00361 
00362   // Shadow representation accessors to get representations of the
00363   // right type in the members of this class:
00364 
00365   const SubgroupRep* look( ) const {
00366          return (const SubgroupRep*)GenericObject::look();
00367   }
00368   SubgroupRep* enhance( ) const {
00369          return (SubgroupRep*)GenericObject::enhance();
00370   }
00371   SubgroupRep* change( ) {
00372          return (SubgroupRep*)GenericObject::change();
00373   }
00374 
00375   // Special wrapping constructor to wrap new representations (returned
00376   // by eg. delegated methods) and for GenericObject initialisation by derived
00377   // classes:
00378 
00379   Subgroup( SubgroupRep* newrep ) : FGGroup(newrep) { }
00380 
00381 };
00382 
00383 #endif
00384 
00385 
00386 
00387 
00388 
00389 
00390 

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