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

/magnus/back_end/Subgroup/include/DoubleCosetGraph.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: DoubleCosetGraph.h,v 1.4 2000/02/10 00:12:30 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 DoubleCosetGraph class.
00009 //
00010 // Principal Author: Dmitry Bormotov
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 // Special Notes:
00017 //
00018 // Next implementation steps:
00019 //
00020 
00021 
00022 #ifndef _DOUBLE_COSET_GRAPH_H_
00023 #define _DOUBLE_COSET_GRAPH_H_
00024 
00025 #include "SubgroupGraph.h"
00026 
00027 typedef SubgroupGraphRep::LabelType DCGLabelType;
00028 typedef SubgroupGraphRep::VertexType DCGVertexType;
00029 
00030 enum DCGPlace { inH, inU, inK };
00031 
00032 struct DCGState {
00033   
00034   DCGState( DCGPlace place = inH , 
00035         DCGVertexType vertex = SubgroupGraphRep::baseVertex )
00036     : currentPlace( place ), currentVertex( vertex ) { }
00037   
00038   DCGState( DCGPlace place, int uCurrent ) :
00039     currentPlace( place ), UCurrent( uCurrent ) { }
00040 
00041   DCGState& operator = ( const DCGState& state )
00042   {
00043     if( (currentPlace = state.currentPlace) == inU )
00044       UCurrent = state.UCurrent;
00045     else
00046       currentVertex = state.currentVertex;
00047   }
00048 
00049   bool operator == ( const DCGState& state ) const
00050   {
00051     if( currentPlace != state.currentPlace )
00052       return false;
00053     if( currentPlace == inU ) {
00054       if( UCurrent != state.UCurrent )
00055         return false;
00056     }
00057     else
00058       if( currentVertex != state.currentVertex )
00059         return false;
00060     
00061     return true;
00062   }
00063 
00064   bool operator != ( const DCGState& state ) const
00065   {
00066     return !(*this == state);
00067   }
00068 
00069   friend ostream& operator << ( ostream& ostr, const DCGState& state )
00070   {
00071     ostr << "(" << state.currentPlace << ",";
00072     if( state.currentPlace == inU ) 
00073       ostr << state.UCurrent;
00074     else
00075       ostr << state.currentVertex;
00076     ostr << ")";
00077      
00078     return ostr;
00079   }
00080 
00081   void assign( DCGPlace place, DCGVertexType vertex)
00082   {
00083     currentPlace = place;
00084     currentVertex = vertex;
00085   }
00086     
00087   void assign( DCGPlace place, int uCurrent )
00088   {
00089     currentPlace = place;
00090     UCurrent = uCurrent;
00091   }
00092   
00093   
00094   DCGPlace currentPlace;
00095   union {
00096     DCGVertexType currentVertex;
00097     int UCurrent;
00098   };
00099 
00100 };
00101 
00102 
00103 // ------------------------ GraphConjugacyProblem ---------------------------//
00104 
00105 
00106 class DoubleCosetGraph 
00107 {
00108 
00109 public:
00110 
00111 
00112   /////////////////////////////////////////////////////////////////////////
00113   //                                                                     //
00114   // Constructors:                                                       //
00115   //                                                                     //
00116   /////////////////////////////////////////////////////////////////////////
00117 
00118   DoubleCosetGraph( const SubgroupGraph& h, const Word& u, 
00119                     const SubgroupGraph& k, int hWidth, int kWidth);
00120 
00121   ~DoubleCosetGraph();
00122 
00123 
00124   /////////////////////////////////////////////////////////////////////////
00125   //                                                                     //
00126   // Accessors:                                                          //
00127   //                                                                     //
00128   /////////////////////////////////////////////////////////////////////////
00129 
00130   bool contains( const Word& ) const;
00131 
00132   bool canGo( const DCGState& originState, DCGState& newState, 
00133               DCGLabelType label ) const;
00134 
00135   bool canBack( const DCGState& originState, DCGState& newState, 
00136                 DCGLabelType label ) const;
00137 
00138   bool canAdvancedGo( const DCGState& originState,
00139                       DCGState& newState, DCGLabelType label ) const;
00140 
00141   bool canAdvancedBack( const DCGState& originState,
00142                         DCGState& newState, DCGLabelType label ) const;
00143   
00144   bool goThroughWord( const Word& W, const DCGState& originState, 
00145                       DCGState& finishState, int& WCurrent ) const;
00146 
00147   bool findWord( const Word& W, const DCGState& originState, 
00148                  DCGState& finishState ) const;
00149 
00150 
00151   /////////////////////////////////////////////////////////////////////////
00152   //                                                                     //
00153   // Data Members:                                                       //
00154   //                                                                     //
00155   /////////////////////////////////////////////////////////////////////////
00156     
00157   static const DCGVertexType emptyTarget = SubgroupGraphRep::emptyTarget;
00158   static const DCGVertexType baseVertex = SubgroupGraphRep::baseVertex;
00159   
00160   const SubgroupGraph H;
00161   const SubgroupGraph K;
00162   const Word U;
00163 
00164 private:
00165 
00166   DCGVertexType **subgroupArrows;
00167   DCGVertexType *wordArrows;
00168   DCGVertexType **backSubgroupArrows;
00169   DCGVertexType *backWordArrows;
00170  
00171   int HWidth;
00172   int KWidth;
00173 
00174   DCGVertexType enumOriginVertex;
00175   int enumWordLength;
00176 
00177 
00178   //////////////////////////////////////////////////////////////
00179   //                                                          //
00180   // Private functions:                                       //
00181   //                                                          //
00182   //////////////////////////////////////////////////////////////
00183 
00184   DoubleCosetGraph( const DoubleCosetGraph& );
00185 
00186   DoubleCosetGraph& operator = ( const DoubleCosetGraph& );
00187 
00188   void joinPieces( DCGVertexType HVertex, DCGVertexType KVertex );
00189   
00190   
00191   /////////////////////////////////////////////////////////////////////////
00192   //                                                                     //
00193   //  Debugging stuff:                                                   //
00194   //                                                                     //
00195   /////////////////////////////////////////////////////////////////////////
00196 
00197 public:
00198 
00199   void debugPrint( );
00200 
00201 #ifdef DEBUG
00202   
00203   friend int main(...);
00204   
00205 #endif
00206 
00207 };
00208 
00209 
00210 inline bool DoubleCosetGraph::findWord( const Word& W,
00211             const DCGState& originState, DCGState& finishState ) const
00212 {
00213   int WCurrent;
00214   if( goThroughWord(W, originState, finishState, WCurrent) )
00215     return true;
00216   else
00217     return false;
00218 }
00219 
00220 
00221 //--------------------------- DCGVertexIterator -----------------------------//
00222 
00223 
00224 class DCGVertexIterator 
00225 {
00226 
00227 public:
00228 
00229 
00230   /////////////////////////////////////////////////////////////////////////
00231   //                                                                     //
00232   // Constructors:                                                       //
00233   //                                                                     //
00234   /////////////////////////////////////////////////////////////////////////
00235   
00236   DCGVertexIterator( const DoubleCosetGraph& dcg ) : DCG( dcg ) { reset( ); }
00237 
00238   // No default constructor
00239   // Copy constructor provided by compiler (does logical deep copy).
00240 
00241 
00242   /////////////////////////////////////////////////////////////////////////
00243   //                                                                     //
00244   // Status Queries:                                                     //
00245   //                                                                     //
00246   /////////////////////////////////////////////////////////////////////////
00247 
00248   bool done( ) { return bDone; }
00249 
00250 
00251   /////////////////////////////////////////////////////////////////////////
00252   //                                                                     //
00253   // Accessors:                                                          //
00254   //                                                                     //
00255   /////////////////////////////////////////////////////////////////////////
00256 
00257   void reset( );
00258 
00259   DCGState value( ) 
00260   { 
00261   #if SAFETY > 0
00262     if( bDone )
00263       error("DCGState DCGVertexIterator<K>::value( ) : "
00264             "Tried to retrieve value from iterator which is done.");
00265   #endif  
00266     
00267     return state; 
00268   }
00269 
00270   bool next( );
00271 
00272 
00273 private:
00274 
00275 
00276   /////////////////////////////////////////////////////////////////////////
00277   //                                                                     //
00278   // Data Members:                                                       //
00279   //                                                                     //
00280   /////////////////////////////////////////////////////////////////////////
00281 
00282   const DoubleCosetGraph& DCG;
00283   DCGState state;
00284   bool bDone;
00285 
00286 
00287   /////////////////////////////////////////////////////////////////////////
00288   //                                                                     //
00289   // Private functions:                                                  //
00290   //                                                                     //
00291   /////////////////////////////////////////////////////////////////////////
00292   
00293 };
00294 
00295 #endif

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