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

/magnus/back_end/Subgroup/include/GraphConjugacyProblem.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: GraphConjugacyProblem.h,v 1.5 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 GraphConjugacyProblem 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 _GRAPH_CONJUGACY_PROBLEM_H_
00023 #define _GRAPH_CONJUGACY_PROBLEM_H_
00024 
00025 #include "DoubleCosetGraph.h"
00026 #include "FPGroup.h"
00027 #include "Timer.h"
00028 
00029 
00030 struct DoubleWayElt {
00031   
00032 /*
00033   DoubleWayElt( const DCGState& state1, const DCGState& state2,
00034                 DCGLabelType label = 0 ) 
00035   {
00036     assign(state1, state2, label);
00037   }
00038 */
00039 
00040   void assign( const DCGState& state1, const DCGState& state2,
00041                DCGLabelType label ) 
00042   {
00043     leftState = state1;
00044     rightState = state2;
00045     currentLabel = label;
00046   }
00047 
00048   void take( DCGState& state1, DCGState& state2, DCGLabelType& label) 
00049   {
00050     state1 = leftState;
00051     state2 = rightState;
00052     label = currentLabel;
00053   }
00054   
00055 //private:
00056 
00057   DCGState leftState, rightState;
00058   DCGLabelType currentLabel;
00059 };
00060 
00061 
00062 // ------------------------ GraphConjugacyProblem ---------------------------//
00063 
00064 
00065 class GraphConjugacyProblem 
00066 {
00067 
00068 public:
00069 
00070 
00071   /////////////////////////////////////////////////////////////////////////
00072   //                                                                     //
00073   // Constructors:                                                       //
00074   //                                                                     //
00075   /////////////////////////////////////////////////////////////////////////
00076 
00077   GraphConjugacyProblem( const FPGroup&, const Word& u, const Word& v );
00078 
00079   ~GraphConjugacyProblem( ) 
00080   {
00081     if( !done() )
00082       finishComputation();
00083   }
00084   
00085   /////////////////////////////////////////////////////////////////////////
00086   //                                                                     //
00087   // Activation members:                                                 //
00088   //                                                                     //
00089   /////////////////////////////////////////////////////////////////////////
00090 
00091   void startComputation( )
00092   {
00093   #if SAFETY > 0   
00094     if ( bStart )
00095       error("void GraphConjugacyProblem::startComputation( ) : "
00096             "the computation has been already started.");
00097   #endif
00098 
00099     Word t = U.cyclicallyReduce();
00100     UConjugator = U.terminalSegment( (U.length() - t.length()) / 2 );
00101     U = t;
00102 
00103     t = V.cyclicallyReduce();
00104     VConjugator = V.terminalSegment( (V.length() - t.length()) / 2 );
00105     V = t;
00106 
00107     bStart = true;
00108     bDone = false;
00109     isInterrupted = false;
00110   }  
00111   // Start the problem: are u and v conjugate ?      
00112   // You shouldn't call this more than one time.
00113          
00114   void continueComputation( const SubgroupGraph& theGraph );
00115   // Advance the computation of conjugacy problem.
00116 
00117   void continueComputation( );
00118   // Advance the computation of conjugacy problem.
00119 
00120 
00121   /////////////////////////////////////////////////////////////////////////
00122   //                                                                     //
00123   // Status Queries:                                                     //
00124   //                                                                     //
00125   /////////////////////////////////////////////////////////////////////////
00126 
00127   bool done( ) const { return bDone; }
00128   // Is the conjugacy problem done ?
00129   // If it is done then u and v are conjugate.
00130 
00131   bool theNewGraphIsNeeded( ) const { return I == NULL; }
00132 
00133 
00134   /////////////////////////////////////////////////////////////////////////
00135   //                                                                     //
00136   // Accessors:                                                          //
00137   //                                                                     //
00138   /////////////////////////////////////////////////////////////////////////
00139 
00140   // You can call all these functions iff the computation is finished
00141   // ( when the done() functions returns true ).
00142 
00143 
00144   Word getConjugator( ) 
00145   {
00146   #if SAFETY > 0
00147     if ( !bDone )
00148       error("Word GraphConjugacyProblem::getConjugator( ) : "
00149             "tried to get result before the computation is finished.");
00150   #endif
00151 
00152     return theConjugator;
00153   }
00154 
00155 
00156 private:
00157 
00158 
00159   /////////////////////////////////////////////////////////////////////////
00160   //                                                                     //
00161   // Data Members:                                                       //
00162   //                                                                     //
00163   /////////////////////////////////////////////////////////////////////////
00164     
00165   int numberOfGenerators;
00166   int maxGeneratorLength;
00167   Word theConjugator;
00168   const FPGroup theGroup;
00169   Word UConjugator;
00170   Word VConjugator;
00171 
00172   Word U;                  // fisrt argument for conjugacy problem
00173   Word V;                  // second argument for conjugacy problem
00174   bool bStart;             // TRUE if the computation is started
00175   bool bDone;              // TRUE if the computation is finished
00176 
00177   DoubleCosetGraph *DCG;
00178   DCGVertexIterator *I;
00179   Timer *timer;
00180   static const int timerValue = 1000;
00181 
00182   
00183   // The data which is necessary to divide findConjugator() on arcs.
00184 
00185   bool isInterrupted; 
00186   DoubleWayElt *way;
00187   int saveWayIndex;
00188   int saveLabel;
00189   DCGState saveLeftState;
00190   DCGState saveRightState;
00191   int *leftMarks;
00192   int *rightMarks;
00193 
00194  
00195   //////////////////////////////////////////////////////////////
00196   //                                                          //
00197   // Private functions:                                       //
00198   //                                                          //
00199   //////////////////////////////////////////////////////////////
00200 
00201   GraphConjugacyProblem( const GraphConjugacyProblem& );
00202   // It is hidden, not implemented.
00203 
00204   GraphConjugacyProblem& operator = ( const GraphConjugacyProblem& );
00205   // It is hidden, not implemented.
00206 
00207   void finishComputation( )
00208   {
00209     bDone = true;
00210     // bStart = false;
00211     theConjugator = theGroup.shortenByRelators(theConjugator);
00212     theConjugator = VConjugator.inverse() * theConjugator * UConjugator;
00213     theConjugator = theConjugator.inverse();
00214     if( isInterrupted )
00215       finishInterruption();
00216   }
00217 
00218   bool findConjugator( const DCGState& state1, DCGLabelType label1,
00219                        const DCGState& state2, DCGLabelType label2, 
00220                        int length, Word& conjugator);
00221 
00222   bool theConjugatorIsFound( const DCGState& state1, 
00223                              const DCGState& state2 ) const;
00224 
00225   void mark( int *, const DCGState&, int *, const DCGState&, int );
00226 
00227   void clear( int *, const DCGState&, int *, const DCGState& );
00228 
00229   void getMarks( const int *, const DCGState&, const int *, const DCGState&,
00230                 int&, int& ) const;
00231 
00232   bool weHaveTheSameCycles( int *, const DCGState&, 
00233                             int *, const DCGState& ) const;
00234 
00235   void finishInterruption( );
00236 
00237 
00238   /////////////////////////////////////////////////////////////////////////
00239   //                                                                     //
00240   //  Debugging stuff:                                                   //
00241   //                                                                     //
00242   /////////////////////////////////////////////////////////////////////////
00243 
00244 #ifdef DEBUG
00245 
00246   friend int main(...);
00247 
00248 #endif
00249 
00250 };
00251 
00252 #endif

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