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

/magnus/back_end/Equations/include/SolutionsEnum.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 class QEqnSolutionsEnumerator
00005 //
00006 // Principal Author: Dmitry Pechkin, Eugeny Paderin
00007 //
00008 // Status: Under trial
00009 //
00010 // Description:
00011 //
00012 // * A composition of any stabilizing automorphism with any basic
00013 //   solution gives a solution of the quadratic equation. Generally this 
00014 //   solution is "parametrized", i.e. images of variables contain variables.
00015 //   If so, then any specialization of this solution will also be
00016 //   a solution.
00017 //
00018 //   We used algorithm described in:
00019 //
00020 //   L.Comerford, C.Edmunds, Solutions of equations in free groups,
00021 //   in Group Theory: proceedings of the Singapore Group Theory
00022 //   Conference held at the National University of Singapore, June 8-19,
00023 //   1987.   ISBN 3-11-011366-X.
00024 //
00025 // Revision History:
00026 //
00027 // * 10/96 EP: GeneratorOfRandomSolutions added.
00028 //
00029 // Special Notes:
00030 //
00031 // * The greatest problem of the algorithm of enumeration of solutions 
00032 //   is repeating solutions. Unfortunately, the same solution will repeat 
00033 //   too often, but we do not know whether it is possible to avoid repetitions.
00034 //   We took certain measures to reduce them, but there is still
00035 //   a great field for improvements.
00036 //
00037 
00038 #ifndef _QEQN_ENUM_SOLUTIONS_H_
00039 #define _QEQN_ENUM_SOLUTIONS_H_
00040 
00041 #include "QEqnSolutions.h"
00042 #include "TupleEnumerator.h"
00043 #include "RandomNumbers.h"
00044 
00045 
00046 class QEqnSolutionsEnumerator
00047 {
00048 public:
00049 
00050   /////////////////////////////////////////////////////////////////////////
00051   //                                                                     //
00052   // Constructors:                                                       //
00053   //                                                                     //
00054   /////////////////////////////////////////////////////////////////////////
00055 
00056   // no default constructor
00057 
00058   QEqnSolutionsEnumerator(const QEqnSolutionsInFreeGroup& equation);
00059   // Construct enumerator by given (partially) solved equation
00060   // with known basic solutions and generators of stabilizer.
00061 
00062   // Copy constructor, operator=, and destructor supplied by compiler
00063 
00064   /////////////////////////////////////////////////////////////////////////
00065   //                                                                     //
00066   // Activation members and status queries:                              //
00067   //                                                                     //
00068   /////////////////////////////////////////////////////////////////////////
00069 
00070   Endomorphism getSolution() const {
00071     if( done() )
00072       error("EQnSolutionsEnumerator::getSolution(): "
00073             "all known solutions have been enumerated");
00074     return solution;
00075   }
00076   // get a current solution.
00077 
00078   bool nextSolution();
00079   // advances the enumerator. Returns true iff all solutions are enumerated.
00080 
00081   bool done() const { return allSolutionsAreEnumerated; }
00082   // Returns `true' iff all solutions of the equations have been enumerated.
00083 
00084   void reset();
00085   // Back to initial state of enumerator.
00086 
00087 private:
00088 
00089   bool areBasicSolutionsParametrized();
00090   // Returns true iff there is a basic solution mapping theEquation 
00091   // to the word containing variables.
00092 
00093   /////////////////////////////////////////////////////////////////////////
00094   //                                                                     //
00095   // Data Members:                                                       //
00096   //                                                                     //
00097   /////////////////////////////////////////////////////////////////////////
00098 
00099   Word theEquation;     
00100   int theNumberOfGenerators;
00101   int theNumberOfVariables;
00102   FreeGroup theGroup; 
00103 
00104   VectorPtrOf<Automorphism> theRegStabGenerators;
00105   VectorPtrOf<Automorphism> theRegStabInvGenerators;
00106   VectorPtrOf<Endomorphism> theBasicSolutions;
00107   Automorphism prefixAuto; 
00108 
00109   bool allSolutionsAreEnumerated;
00110   Trichotomy numberOfSolutionsIsFinite;
00111   Endomorphism solution;
00112   Automorphism stabAuto;
00113   int currentBasicSolution;
00114   Endomorphism specEndo;
00115   EnumeratorOfWordTuples tuplesEnumerator;
00116   VectorOf<bool> invGensComputed;
00117 
00118 };
00119 
00120 //--------------------------- Random Solution ---------------------------------
00121 
00122 const int randomSolutionsThreshold = 500;
00123 // We cannot make all solutions to be different, there will be repetitions
00124 // always. We can register solutions in the SetOf<Endomorphism> to eliminate
00125 // "too close" repetitions. But we cannot do this endlessly, so sometimes
00126 // we have to clean the set and start to fill it again. The constant
00127 // defines maximal size of the set.
00128 
00129 
00130 class GeneratorOfRandomSolutions 
00131 {
00132 public:
00133 
00134   GeneratorOfRandomSolutions( const FreeGroup& group, const Word& equation, 
00135                               int numberOfVariables );
00136 
00137   // copy constructor, operator= and destructor are generated by compiler
00138 
00139   /////////////////////////////////////////////////////////////////////////
00140   //                                                                     //
00141   //    Modifiers                                                        //
00142   //                                                                     //
00143   /////////////////////////////////////////////////////////////////////////
00144 
00145   void setBasicSolutions( const VectorPtrOf<Endomorphism>& newBasicSolutions )
00146   {
00147     basicSolutions = newBasicSolutions;
00148   }
00149 
00150   void setRegStabGenerators( const VectorPtrOf<Automorphism>& newGenerators )
00151   {
00152     regStabGenerators = newGenerators;
00153     regStabGeneratorsInv = VectorPtrOf<Automorphism>( newGenerators.length() );
00154   }
00155 
00156   void setThreshold( int newThreshold ) { threshold = newThreshold; }
00157 
00158   //////////////////////////////////////////////////////////////////////////
00159   //                                                                      //
00160   //    Accessors:                                                        //
00161   //                                                                      //
00162   //////////////////////////////////////////////////////////////////////////
00163 
00164   bool hasSolutions() const;
00165   // Returns true iff some basic solutions found so far.
00166 
00167   bool generateSolution();
00168   // This function generates a random solution made of the currently found
00169   // basic solutions and RegStab generators.
00170   // You should call hasSolutions before.
00171 
00172   Endomorphism getSolution() const { return solution; }
00173   // Returns the last generated solution.
00174 
00175   int getThreshold( ) const { return threshold; }
00176 
00177   int getCurrentThreshold( ) const { return solutionSet.cardinality(); }
00178 
00179 
00180   const VectorPtrOf<Endomorphism>& getBasicSolutions( ) const 
00181   {
00182     return basicSolutions;
00183   }
00184 
00185   const VectorPtrOf<Automorphism>& getRegStabGenerators(  ) const 
00186   {
00187     return regStabGenerators; 
00188   }
00189 
00190 
00191 protected:
00192 
00193   void generateSomeSolution();
00194   // Generates solution not taking care about uniqueness
00195 
00196   // Data members
00197 
00198 private:
00199 
00200   FreeGroup theGroup;
00201   int numOfVar;    // number of variables
00202   int numOfGen;    // number of generators
00203 
00204 
00205   VectorPtrOf<Endomorphism> basicSolutions;
00206   VectorPtrOf<Automorphism> regStabGenerators;
00207   VectorPtrOf<Automorphism> regStabGeneratorsInv;
00208 
00209   SetOf<Endomorphism> solutionSet;
00210   // The set of solutions
00211 
00212   Endomorphism solution;
00213   // The current solution
00214 
00215   int threshold;
00216   // The maximal number of registered solutions
00217 
00218   UniformRandom rnd;
00219 
00220   Endomorphism variablesEliminator;
00221 };
00222 
00223 #endif
00224 
00225 
00226 
00227 
00228 
00229   

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