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

/magnus/back_end/Subgroup/include/SubgroupGraph.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: SubgroupGraph.h,v 1.5 1998/08/03 20:30:19 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1994 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Definition and implementation of the SubgroupGraph class.
00009 //           A SubgroupGraph is a user class for representing
00010 //           a finitely generated subgroup of a free group.
00011 //           The representation of the subgroup is as a graph, which
00012 //           can be used as a finite state automaton accepting words
00013 //           in the subgroup.
00014 //           There are methods which transmute the graph into a represen-
00015 //           tation of a different subgroup; see, e.g., MHallComplete().
00016 //
00017 // Principal Author: Roger Needham
00018 //
00019 // Status: in progress
00020 //
00021 // Revision History:
00022 //
00023 // * 9/94 Roger wrote this new class to wrap C. Miller's original graph code.
00024 //
00025 // * 05/97 Dmitry B. implemented IPC tools.
00026 //
00027 // Bugs:
00028 //
00029 // * SubgroupGraph(int ambientRank, const SetOf<Word>& S)
00030 //   can lose if any words in S are not freely reduced.
00031 //
00032 // Special Notes:
00033 //
00034 // * For the sake of efficiency all functions of SubgroupGraphRep work
00035 //   only with freely reduced words.
00036 //
00037 // Next implementation steps:
00038 //
00039 
00040 
00041 #ifndef _SUBGROUPGRAPH_H_
00042 #define _SUBGROUPGRAPH_H_
00043 
00044 
00045 #include "SubgroupGraphRep.h"
00046 
00047 
00048 class SubgroupGraph : public ObjectOf<SubgroupGraphRep> {
00049   
00050 public:
00051 
00052   typedef SubgroupGraphRep::VertexType VertexType;
00053 
00054   typedef SubgroupGraphRep::LabelType LabelType;
00055 
00056   SubgroupGraph(int ambientRank, const SetOf<Word>& S) :
00057     ObjectOf<SubgroupGraphRep>( new SubgroupGraphRep(ambientRank, S) ) { }
00058   // Construct a subgroup graph from the rank of the ambient free group,
00059   // and the subgroup generators.
00060 
00061   SubgroupGraph(int ambientRank, const VectorOf<Word>& V) :
00062     ObjectOf<SubgroupGraphRep>( new SubgroupGraphRep(ambientRank, V) ) { }
00063   // Construct a subgroup graph from the rank of the ambient free group,
00064   // and the subgroup generators.
00065 
00066   // Copy constructor, operator=, and destructor supplied by compiler.
00067 
00068   int rank( ) const { return look()->rank(); }
00069   // Returns the rank of this subgroup as a free group.
00070 
00071   VectorOf<Word> normalizer( ) { return enhance()->normalizer(); }
00072 
00073   VectorOf<Word> nielsenBasis( ) const { return enhance()->nielsenBasis(); }
00074   // Returns a Nielsen basis for this subgroup as a free group.
00075 
00076   Word nielsenWord(int i) const { return enhance()->nielsenWord(i); }
00077   // Returns an  i^th element of the Nielsen basis.
00078 
00079   Word inNielsenWords(const Word& w) const { 
00080     return enhance()->inNielsenWords(w); 
00081   }
00082   // Returns the word `w' written in elements of the Nielsen basis.
00083 
00084   SubgroupGraph join(const SubgroupGraph& SG) const {
00085          return SubgroupGraph( look()->join( *(SG.look()) ) );
00086   }
00087   // Returns a SubgroupGraph which represents the join of this
00088   // subgroup and the argument (i.e. the subgroup generated by the
00089   // union of generating sets for the two subgroups).
00090 
00091   SubgroupGraph intersection(const SubgroupGraph& SG) const {
00092          return SubgroupGraph( look()->intersection( *(SG.look()) ) );
00093   }
00094   // Returns a SubgroupGraph which represents the intersection of
00095   // this subgroup and the argument.
00096 
00097   Bool contains(const Word& w) const { return look()->contains(w); }
00098   // Returns TRUE iff this subgroup contains `w'.
00099 
00100   Bool contains(const SetOf<Word>& S) const { return look()->contains(S); }
00101   // Returns TRUE iff this subgroup contains the subgroup generated by `S'.
00102 
00103   Bool contains(const VectorOf<Word>& V) const { return look()->contains(V); }
00104   // Returns TRUE iff this subgroup contains the subgroup generated by `V'.
00105 
00106   Bool contains(SubgroupGraph& SG) const { 
00107          return look()->contains(*SG.change());
00108   }
00109 
00110   Bool equalTo(const SetOf<Word>& S) { return enhance()->equalTo(S); }
00111   // Returns TRUE iff this subgroup and the subgroup generated by `S' are equal.
00112 
00113   Bool equalTo(SubgroupGraph& SG) { 
00114          return enhance()->equalTo(*SG.enhance());
00115   }
00116   // Returns TRUE iff this subgroup and the argument are equal.
00117 
00118   Bool conjugateInSubgroup(const Word& w, Word& conjugator) const {
00119          return look()->conjugateInSubgroup(w,conjugator);
00120   }
00121   // Returns TRUE iff some conjugate of `w' is in the subgroup.
00122   // If TRUE, `conjugator' is set to the conjugator.
00123 
00124   Bool conjugateInSubgroup(const SetOf<Word>& S, Word& conjugator) {
00125          return enhance()->conjugateInSubgroup(S,conjugator);
00126   }
00127   // Returns TRUE iff some conjugate of the subgroup generated by `S' is
00128   // in the subgroup. If TRUE, `conjugator' is set to the conjugator.
00129 
00130   bool conjugateTo(const SetOf<Word>& S) {
00131     return enhance()->conjugateTo(S);
00132   }
00133   // Returns true iff this subgroup and the argument are conjugate.
00134 
00135   long powerInSubgroup( const Word& w ) const {
00136          return look()->powerInSubgroup(w);
00137   }
00138   // returns `the minimal power' or 0 if there are no powers of the
00139   // element `aWord' in H.
00140 
00141   int findIndex() { return enhance()->findIndex(); }
00142   // Returns the index of the subgroup or 0 if infinite.
00143 
00144   VectorOf<Word> findWhiteheadBasis() { 
00145     return enhance()->findWhiteheadBasis(); 
00146   }
00147   // Finds the subgroup of the free group authomorphic to this with
00148   // smallest sum of lengths of generators.
00149   // Returns a vector of generators.
00150 
00151   Bool isAFreeFactor() { return enhance()->isAFreeFactor(); }
00152   // Returns TRUE iff this subgroup is a free factor.
00153 
00154   Bool generatesTheFreeGroup() const { 
00155          return look()->generatesTheFreeGroup(); 
00156   }
00157 
00158   Word rightSchreierRepresentative(const Word& w) {
00159          return enhance()->rightSchreierRepresentative(w);
00160   }
00161 
00162   SubgroupGraph MHallCompletion( ) const {
00163          SubgroupGraphRep* copy = new SubgroupGraphRep(*(look()));
00164          copy->MHallComplete();
00165          return SubgroupGraph(copy);
00166   }
00167   // Returns a SubgroupGraph which represents a subgroup of the
00168   // ambient free group of finite index, containing this one.
00169   // This one is a free factor of the result.
00170 
00171   void MHallComplete( ) {
00172          change()->MHallComplete();
00173   }
00174   // An `in place' version of above.
00175 
00176   void joinConjugate(Generator g) {
00177          change()->joinConjugate( ord(g) );
00178   }
00179   // Alters this SubgroupGraph in place so that it also contains the
00180   // conjugate by `g' of every element it contained before.
00181 
00182   float completeness( ) const { return look()->completeness(); }
00183   // Returns ratio of existing edges to number of edges in complete graph.
00184 
00185   Bool isComplete( ) const { return look()->isComplete(); }
00186   // Returns TRUE iff this graph is complete (can't trust floats!).
00187 
00188   VertexType vertexCount( ) const { return look()->vertexCount(); }
00189 
00190   #ifdef DEBUG
00191     void debugPrint(ostream& ostr) const {
00192            look()->debugPrint(ostr);
00193     }
00194     Bool consistentData( ) const {
00195            return look()->consistentData();
00196     }
00197   #endif
00198 
00199 
00200   VertexType targetOfGenerator(VertexType source, int generator) const {
00201          return look()->targetOfGenerator(source, generator);
00202   }
00203 
00204 
00205   VertexType targetOfLabel(VertexType source, LabelType label) const {
00206          return look()->targetOfLabel(source, label);
00207   }
00208 
00209 
00210   long getValence( ) const { return look()->getValence(); }
00211 
00212 
00213   LabelType inverseLabel(LabelType label) const {
00214     return look()->inverseLabel(label);
00215   }
00216 
00217   int labelToGenerator(LabelType label) const {
00218     return look()->labelToGenerator(label);
00219   }
00220 
00221   LabelType generatorToLabel(int g) const {
00222     return look()->generatorToLabel(g);
00223   }
00224 
00225   /////////////////////////////////////////////////////////////////////////
00226   //                                                                     //
00227   // IPC tools:                                                          //
00228   //                                                                     //
00229   /////////////////////////////////////////////////////////////////////////
00230 
00231   friend ostream& operator < ( ostream& ostr, const SubgroupGraph& g )
00232   {
00233     g.look()->write(ostr);
00234     return ostr;
00235   }
00236   
00237   friend istream& operator > ( istream& istr, SubgroupGraph& g )
00238   {
00239     g.change()->read(istr);
00240     return istr;
00241   }
00242 
00243   bool readPiece( istream& istr, const class Timer& timer ) {
00244     return change()->readPiece(istr,timer);
00245   }
00246   // To read a big amount of information piece by piece. Returns true
00247   // if the last is read, false otherwise.
00248 
00249 
00250 //@dbprivate:
00251 protected:
00252 
00253   SubgroupGraph(SubgroupGraphRep* SGRp) : ObjectOf<SubgroupGraphRep>(SGRp) { }
00254 
00255 };
00256 
00257 #endif

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