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

/magnus/back_end/Subgroup/include/SubgroupGraphRep.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: SubgroupGraphRep.h,v 1.8 2000/02/10 00:12:31 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 of the SubgroupGraphRep class.
00009 //
00010 // Principal Author: Roger Needham
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 // * 05/97 Dmitry B. implemented IPC tools.
00017 //
00018 // Special Notes:
00019 //
00020 // * The edge table is just a flat array, rather than a vector of
00021 //   vectors, to save memory overhead: since the ambient free group is
00022 //   liable to have small rank, we don't want scads of small vectors on the
00023 //   heap. The tradeoffs are that random-access lookup of target vertices
00024 //   requires an integer multiplication, and expanding the table requires
00025 //   copying the whole thing.
00026 //   At least the multiplication could be optimized away by changing
00027 //   consecutive vertex numbers to row offsets into the edge table.
00028 //   The all-important ordering of vertices would be preserved.
00029 //
00030 // * For the sake of efficiency all functions of SubgroupGraphRep work
00031 //   only with freely reduced words.
00032 //
00033 // Next implementation steps:
00034 //
00035 // * More arg checking on SAFETY?
00036 // * Should generating set be given as a VectorOf?
00037 // * addSubgroupGenerator method.
00038 
00039 
00040 #ifndef _SUBGROUPGRAPHREP_H_
00041 #define _SUBGROUPGRAPHREP_H_
00042 
00043 
00044 #include "Set.h"
00045 #include "Word.h"
00046 #include "Vector.h"
00047 #include "Generator.h"
00048 #include "RefCounter.h"
00049 
00050 // #define DEBUG_SubgroupGraph
00051 // #define DEBUG_IDENTIFY
00052 
00053 //@db: class SubgroupGraphRep : public RefCounter {
00054 // RefCounter does not have clone(), therefore clone() is never
00055 // defined as a virtual method which leads to crash in 
00056 // any deriviation of SubgroupGraph.
00057 
00058 class SubgroupGraphRep : public PureRep {
00059 
00060   friend class SubgroupGraphRepReader;
00061 
00062 public:
00063   
00064   SubgroupGraphRep(int ambientRank, const SetOf<Word>& S);
00065   // Construct a subgroup graph from the rank of the ambient free group,
00066   // and the subgroup generators.
00067 
00068   SubgroupGraphRep(int ambientRank, const VectorOf<Word>& V);
00069   // Construct a subgroup graph from the rank of the ambient free group,
00070   // and the subgroup generators.
00071 
00072   SubgroupGraphRep(const SubgroupGraphRep&);
00073   // Copy constructor does deep copy.
00074   
00075   ~SubgroupGraphRep( );
00076 
00077   SubgroupGraphRep* clone( ) const { return new SubgroupGraphRep( *this ); }
00078   // Standard clone.
00079 
00080   int rank( ) const {
00081          return numberOfEdges() - numberOfVertices + 1;
00082   }
00083   // Returns the rank of this subgroup as a free group.
00084 
00085   VectorOf<Word> normalizer( );
00086   // Returns the normalizer of this subgroup.
00087 
00088   VectorOf<Word> nielsenBasis( );
00089   // Returns a Nielsen basis for this subgroup as a free group.
00090 
00091   Word nielsenWord(int i);
00092   // Returns an i^th element of the Nielsen basis.
00093 
00094   Word inNielsenWords(const Word& w);
00095   // Returns the word `w' written in elements of the Nielsen basis.
00096 
00097   SubgroupGraphRep* join(const SubgroupGraphRep&) const;
00098   // Returns a SubgroupGraphRep* which represents the join of this
00099   // subgroup and the argument.
00100 
00101   SubgroupGraphRep* intersection(const SubgroupGraphRep& SGR) const;
00102   // Returns a SubgroupGraphRep* which represents the intersection
00103   // of this subgroup and the argument.
00104 
00105   Bool contains(const Word& w) const { return loopSearch(w,0); }
00106   // Returns TRUE iff this subgroup contains `w'.
00107 
00108   Bool contains(const SetOf<Word>& S) const;
00109   // Returns TRUE iff this subgroup contains the subgroup generated by `S'.
00110 
00111   Bool contains(const VectorOf<Word>& V) const;
00112   // Returns TRUE iff this subgroup contains the subgroup generated by `V'.
00113 
00114   Bool contains(SubgroupGraphRep& SGR) const;
00115   // Returns TRUE iff this subgroup contains the argument.
00116 
00117   Bool equalTo(const SetOf<Word>& S);
00118   // Returns TRUE iff this subgroup and the subgroup generated by `S' are equal.
00119 
00120   Bool equalTo(SubgroupGraphRep& SGR);
00121   // Returns TRUE iff this subgroup and the argument are equal.
00122 
00123   Bool conjugateInSubgroup(const Word& w, Word& conjugator) const;
00124   // Returns TRUE iff some conjugate of `w' is in the subgroup.
00125   // If TRUE, `conjugator' is set to the conjugator.
00126 
00127   Bool conjugateInSubgroup(const SetOf<Word>& S, Word& conjugator);
00128   // Returns TRUE iff some conjugate of the subgroup generated by `S' is
00129   // in the subgroup. If TRUE, `conjugator' is set to the conjugator.
00130 
00131   bool conjugateTo(const SetOf<Word>& S);
00132   // Returns true iff this subgroup and the argument are conjugate.
00133 
00134   long powerInSubgroup( const Word& aWord ) const;
00135   // returns 'the minimal power' or 0 if there are no powers of the
00136   // element `aWord' in H.
00137 
00138   int findIndex();
00139   // returns the index of the subgroup or 0 if infinite.
00140 
00141   VectorOf<Word> findWhiteheadBasis();
00142   // Finds the subgroup of the free group authomorphic to this with
00143   // smallest sum of lengths of generators.
00144   // Returns a vector of generators.
00145 
00146   Bool isAFreeFactor();
00147   // Returns TRUE iff this subgroup is a free factor.
00148 
00149   Bool generatesTheFreeGroup() const
00150   { 
00151     return (numberOfVertices==1)&&(rank()==valence/2);
00152   }
00153 
00154   Word rightSchreierRepresentative(const Word&);
00155 
00156   void MHallComplete();
00157   // Alters this graph in place so that it becomes a subgroup of
00158   // the ambient free group of finite index, with the original
00159   // subgroup a free factor.
00160 
00161   void joinConjugate(int generator);
00162   // Alters this graph in place so that it also contains the conjugate
00163   // by `generator' of every element it contained before.
00164 
00165   float completeness( ) const {
00166          return ( 2 * numberOfEdges() ) / ( numberOfVertices * valence );
00167   }
00168 
00169   Bool isComplete( ) const {
00170          return ( 2 * numberOfEdges() ) == ( numberOfVertices * valence );
00171   }
00172 
00173   long vertexCount( ) const { return numberOfVertices; }
00174 
00175   #ifdef DEBUG
00176     void debugPrint(ostream&) const;
00177     Bool consistentData( ) const;
00178     //friend int main( );
00179   #endif
00180 
00181   typedef long VertexType;
00182   // A signed integer type big enough to hold the number of vertices in a
00183   // graph. Used for both vertices and indices into vectors of vertices.
00184 
00185   static const VertexType baseVertex = 0;
00186   // The distinguished vertex, i.e. the only start and accept state for
00187   // the graph as a word acceptor.
00188 
00189   static const VertexType emptyTarget = -1;
00190 
00191   typedef int LabelType;
00192   // Any integer type big enough to hold twice the ambient rank.
00193 
00194 
00195   LabelType generatorToLabel(int g) const {
00196          return ( g > 0 ? (g - 1) << 1 : (-g << 1) - 1 );
00197   }
00198   // Performs the mapping of Generator ordinals to labels:
00199   // . . . -3 -2 -1  1  2  3 . . .
00200   // . . .  5  3  1  0  2  4. . .
00201   // This is the inverse function of `labelToGenerator'.
00202 
00203 
00204   int labelToGenerator(LabelType label) const {
00205          return ( label & 1 ? ( -1 - label ) >> 1 : ( label + 2 ) >> 1 );
00206   }
00207   // Performs the mapping of labels to Generator ordinals:
00208   // 0  1  2  3  4  5 . . .
00209   // 1 -1  2 -2  3 -3
00210   // This is the inverse function of `generatorToLabel'.
00211 
00212 
00213   LabelType inverseLabel(LabelType label) const {
00214          return ( label & 1 ? label - 1 : label + 1 );
00215   }
00216   // Returns the label representing the inverse generator to the
00217   // generator represented by `label'.
00218 
00219 
00220   VertexType targetOfGenerator(VertexType source, int generator) const {
00221          return table[ source * valence + generatorToLabel(generator) ];
00222   }
00223   // Returns the vertex gotten to from `source' vertex via `generator'.
00224   // -1 means there is no such edge.
00225 
00226 
00227   VertexType targetOfLabel(VertexType source, LabelType label) const {
00228          return table[ source * valence + label ];
00229   }
00230   // Returns the vertex gotten to from `source' vertex via `label'.
00231   // -1 means there is no such edge.
00232 
00233 
00234   LabelType getValence( ) const {
00235     return valence;
00236   } 
00237 
00238   /////////////////////////////////////////////////////////////////////////
00239   //                                                                     //
00240   // IPC tools:                                                          //
00241   //                                                                     //
00242   /////////////////////////////////////////////////////////////////////////
00243 
00244   virtual void write( ostream& ostr ) const;
00245  
00246   virtual void read( istream& istr );
00247 
00248   virtual bool readPiece( istream& istr, const class Timer& timer );
00249   // To read a big amount of information piece by piece. Returns true
00250   // if the last is read, false otherwise.
00251  
00252 
00253 //@dbprivate:
00254 protected:
00255 
00256   // IPC private data:
00257 
00258   enum { STOP, TABLE, SUBTREE, BASIS_EDGES };
00259   int isReading;
00260   int tableSize, n;
00261 
00262 
00263   /////////////////////////////////////////////////////////////////////////
00264   //                                                                     //
00265   // Private members of the class:                                       //
00266   //                                                                     //
00267   /////////////////////////////////////////////////////////////////////////
00268 
00269   // A graph is comprised of vertices, (edge) labels, and
00270   // a set of ordered triples (source vertex, label, target vertex).
00271   //
00272   // Our labels are integers 0, 1, ..., valence - 1, which represent
00273   // group generators; we map Generator ordinals to labels in the
00274   // sequence 1, -1, 2, -2, ...
00275   //
00276   // Our vertices are integers numbered 0, 1, ..., numberOfVertices - 1.
00277 
00278 
00279   struct Edge {
00280     VertexType v;          // initial vertex
00281     LabelType  l;
00282 
00283     Edge& operator = ( const Edge& anEdge ) { 
00284          v = anEdge.v; l = anEdge.l; 
00285          return *this;
00286     }
00287     Bool operator < ( const Edge& anEdge ) const {
00288          if ( v < anEdge.v ) return TRUE;
00289          if ( v > anEdge.v ) return FALSE;
00290          if ( l < anEdge.l ) return TRUE;
00291          return FALSE;
00292     }
00293     Bool operator > ( const Edge& anEdge ) const {
00294          if ( v > anEdge.v ) return TRUE;
00295          if ( v < anEdge.v ) return FALSE;
00296          if ( l > anEdge.l ) return TRUE;
00297          return FALSE;
00298     }
00299     
00300     friend ostream& operator < ( ostream& ostr, const Edge& e )
00301     {
00302       ostr < e.v < e.l;
00303       return ostr;
00304     }
00305     
00306     friend istream& operator > ( istream& istr, Edge& e )
00307     {
00308       istr > e.v > e.l;
00309       return istr;
00310     }
00311 
00312   };
00313   
00314   // Data members:
00315 
00316   VertexType* table;
00317   // Holds a transition table, represented by a 2D array of
00318   // numberOfVertices rows and valence columns.
00319   // The entry in row i and column j is the target vertex of
00320   // source vertex i via label j.
00321   // This means that finding the target of a label from a source vertex
00322   // requires a multiplication.
00323 
00324   VertexType numberOfVertices;   // Actual number of vertices allocated in table
00325   VertexType spaceForVertices;   // Number of vertices table can hold
00326   LabelType  valence;            // Number of labels
00327 
00328 
00329   LabelType* maximalSubtree;
00330   Edge* basisEdges;
00331   // These are NULL after the constructor exits. They must be explicitly
00332   // initialized by a call to makeMaxlSubtree(). Do NOT forget to
00333   // reinitialize these if table changes.
00334   // 
00335   // maximalSubtree `contains' backpointers which define a maximal subtree
00336   // of the graph: if the maximal subtree contains the edge V1 -- L --> V2,
00337   // then maximalSubtree[V2] == L^-1 (so V1 can be gotten from table).
00338   // This is used to extract a Nielsen basis, and to find a Nielsen-Schreier
00339   // representative of a word in the ambient free group.
00340   // 
00341   // basisEdges `contains' those edges of the graph which are missing from
00342   // the maximal subtree. basisEdges is sorted ( lexicographical order on 
00343   // pairs (iVertex,label).
00344   //
00345   // This is used to extract a Nielsen basis, and to write a word in the
00346   // subgroup as a word in that Nielsen basis.
00347   //
00348   // There is still the problem of indexing basis edges, so that we know
00349   // which element of the Nielsen basis corresponds to which edge.
00350 
00351   
00352   // Private methods:
00353 
00354 
00355   SubgroupGraphRep(int whatValence, long howManyVertices);
00356   // Construct a SubgroupGraphRep with `table' initialized for
00357   //   numberOfVertices == 1,
00358   //   spaceForVertices == howManyVertices,
00359   //   valence == whatValence.
00360 
00361 
00362   void resize(long howManyVertices);
00363   // Data members `table', `valence' and `numberOfVertices' must have
00364   // correct values before calling this.
00365   // Resizes `table' to have exactly enough room for `howManyVertices',
00366   // copying any that are already there, initializes any new vertices
00367   // to have no edges, and sets values of `numberOfVertices' and
00368   // `spaceForVertices' if the size changes.
00369 
00370 
00371   void defineEdges(VertexType source, int generator, VertexType target) {
00372          #if SAFETY > 1
00373          if ( (source < 0) || (source >= numberOfVertices) ||
00374                         (target < -1) || (target >= numberOfVertices) ||
00375                         (generatorToLabel(generator) < 0) ||
00376                         (generatorToLabel(generator) >= valence) )
00377                 error("bad arg(s) to SubgroupGraphRep::defineEdges");
00378          #endif
00379 
00380          table[ source * valence + generatorToLabel(generator) ] = target;
00381          table[ target * valence + generatorToLabel(-generator) ] = source;
00382   }
00383   // Makes `generator' take `source' vertex to `target' vertex, and
00384   // the inverse generator take `target' vertex to `source' vertex.
00385 
00386 
00387   VertexType defineEdges(VertexType source, int generator) {
00388          #if SAFETY > 1
00389          if ( numberOfVertices > spaceForVertices )
00390                 error("table overflow in SubgroupGraphRep::defineEdges");
00391          #endif
00392          if ( numberOfVertices == spaceForVertices )
00393                 resize(numberOfVertices + max(numberOfVertices / 5, 100)); //@rn experiment
00394          ++numberOfVertices;
00395          defineEdges(source, generator, numberOfVertices - 1);
00396          return numberOfVertices - 1;
00397   }
00398   // This version defines a new (target) vertex before doing the work
00399   // of `defineEdges', and returns the new vertex.
00400 
00401 
00402   void defineEdge(VertexType source, LabelType label, VertexType target) {
00403          table[ source * valence + label ] = target;
00404   }
00405   // Makes `label' take `source' vertex to `target' vertex.
00406 
00407 
00408   long numberOfEdges( ) const;
00409   // Returns the number of edge pairs in this graph; an edge labelled by
00410   // a generator and one by the inverse of that generator count as one.
00411 
00412   long valenceAt(VertexType v) const;
00413   // Returns the number of edges outcomming from `v'.
00414                                                 
00415 
00416   void adjoinWord(const Word&, VertexType);
00417   // Adjoins the Word to this graph, which is the same as adding
00418   // the Word to the generating set of this subgroup.
00419   // Calls defineEdges to make new edges, which resizes `table'
00420   // if necessary, and may leave extra space.
00421 
00422 
00423   void addWordArc(const Word&, VertexType, VertexType, int, int);
00424   // Specialized version of adjoinWord.
00425 
00426 
00427   void addWordLoop(const Word&, VertexType, int, int);
00428   // Specialized version of adjoinWord.
00429 
00430 
00431   void identifyVertices(VertexType, VertexType);
00432   // Folds this graph as necessary so that the two vertices are the same,
00433   // then recovers any unneeded space.
00434 
00435 
00436   void reduceGraph(VertexType*);
00437   // See comments in function body. Recovers any unneeded space.
00438 
00439 
00440   SubgroupGraphRep* disjointUnion(const SubgroupGraphRep&) const;
00441   // Returns a SubgroupGraphRep* which is the literal graph-wise
00442   // disjoint union of the argument and this graph.
00443 
00444   Bool loopSearch(const Word& w, VertexType v) const;
00445   // Returns TRUE iff there is a cycle starting at `v' with label `w'.
00446 
00447   Word getLabel(VertexType v) const;
00448   // Returns the label of the path from the base vertex to `v' along the
00449   // maximal subtree.
00450 
00451   Word getInverseLabel(VertexType v) const;
00452   // Returns the label of the path from `v' to the base vertex along the
00453   // maximal subtree.
00454 
00455   int findBasisEdgeIndex(VertexType source,LabelType label);
00456   // Returns index of this edge in BasisEdges if passing it in positive
00457   // direction or -index if passing in negative. 1-based index.
00458 
00459   void makeMaxlSubtree( );
00460   // See the comments above for maximalSubtree and basisEdges.
00461 
00462   int distanceFromOrigin(VertexType) const;
00463 
00464 };
00465 
00466 #endif

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