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

/magnus/back_end/Genetic/include/GeneticGraphWP.h

Go to the documentation of this file.
00001 /*
00002  *   $Id$
00003  */
00004  
00005 // Copyright (C) 1997-1998 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 //
00008 // Contents: Definition of GeneticGraphWP class
00009 //
00010 // Principal Author: Dmitry Bormotov
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 
00017 
00018 #ifndef _GeneticGraphWP_H_
00019 #define _GeneticGraphWP_H_
00020 
00021 #include "RandomNumbers.h"
00022 #include "FPGroup.h"
00023 #include "FreeGroup.h"
00024 #include "Config.h"
00025 #include "SubgroupGraph.h"
00026 
00027 
00028 // ------------------------------- NCChunk --------------------------------- //
00029 
00030 
00031 class NCChunkRep : public SubgroupGraphRep
00032 {
00033 public:
00034 
00035   NCChunkRep( int rank, SetOf<Word> S ) 
00036     : SubgroupGraphRep( rank,S ), distance(0) { }
00037 
00038   NCChunkRep( const NCChunkRep& G ) 
00039     : SubgroupGraphRep( G ), distance(0) { }
00040 
00041   NCChunkRep( const SubgroupGraphRep& G ) 
00042     : SubgroupGraphRep( G ), distance(0) { }
00043 
00044   ~NCChunkRep( ) { delete [] distance; }
00045 
00046   void deleteVertex( VertexType v);  
00047 
00048   void collectGarbage( );
00049 
00050   void updateDistanceTable( );
00051 
00052   void reduce( const Word& );
00053 
00054   long getDistance( VertexType v ) const;
00055 
00056   NCChunkRep* join(const NCChunkRep& C) const;
00057 
00058   NCChunkRep* clone( ) const { return new NCChunkRep( *this ); }
00059   // Standard clone.
00060 
00061 private:
00062 
00063   bool isGarbage( VertexType v);
00064   void moveVertex( VertexType source, VertexType target);
00065   int power( VertexType v);
00066   SetOf<Integer> getWordVertices( const Word& ) const;
00067 
00068   // Data members:
00069   
00070   long* distance;
00071 };
00072 
00073 
00074 class NCChunk : public DerivedObjectOf<SubgroupGraph,NCChunkRep> 
00075 {
00076 public:
00077   
00078   NCChunk( int rank = 0, SetOf<Word> S = SetOf<Word>() ) : 
00079     DerivedObjectOf<SubgroupGraph,NCChunkRep>( new NCChunkRep(rank,S) ) { }
00080   /*
00081   NCChunk( const SubgroupGraph& G ) : 
00082     DerivedObjectOf<SubgroupGraph,NCChunkRep>( new NCChunkRep(G.enhance()) ) 
00083   { }
00084   */
00085   void deleteVertex( VertexType v )  
00086   {
00087     change()->deleteVertex(v);
00088   }
00089 
00090   void collectGarbage( )  
00091   {
00092     change()->collectGarbage();
00093   }
00094 
00095   void updateDistanceTable( )  
00096   {
00097     change()->updateDistanceTable();
00098   }
00099 
00100   void reduce( const Word& w )  
00101   {
00102     change()->reduce(w);
00103   }
00104 
00105   long getDistance( VertexType v ) const
00106   {
00107     return look()->getDistance(v);
00108   }
00109 
00110   NCChunk join(const NCChunk& C) const {
00111     return NCChunk( look()->join( *(C.look()) ) );
00112   }
00113     
00114 private:
00115 
00116   NCChunk(NCChunkRep* rep) : DerivedObjectOf<SubgroupGraph,NCChunkRep>(rep) { }
00117 
00118 };
00119 
00120 
00121 // --------------------------- GeneticGraphWP ------------------------------ //
00122 
00123 
00124 class GeneticGraphWP
00125 {
00126 
00127 public:
00128   
00129   /////////////////////////////////////////////////////////////////////////
00130   //                                                                     //
00131   // Constructors:                                                       //
00132   //                                                                     //
00133   /////////////////////////////////////////////////////////////////////////
00134   
00135   GeneticGraphWP( const FPGroup& G, const GHNConfig& config );
00136   
00137   // copy constructor supplied by compiler.
00138   
00139   // destructor supplied by compiler.
00140 
00141 
00142   /////////////////////////////////////////////////////////////////////////
00143   //                                                                     //
00144   // Accessors:                                                          //
00145   //                                                                     //
00146   /////////////////////////////////////////////////////////////////////////
00147 
00148   Trichotomy isTrivial( const Word& u, ostream* out = NULL );
00149   // returns yes if the genetic algorithm could prove that u
00150   // is trivial; returns dontknow after computing all generations;
00151   // if out is not NULL it keeps details of the computation
00152 
00153 
00154   /////////////////////////////////////////////////////////////////////////
00155   //                                                                     //
00156   // OI:                                                                 //
00157   //                                                                     //
00158   /////////////////////////////////////////////////////////////////////////
00159 
00160 
00161 private:
00162 
00163   /////////////////////////////////////////////////////////////////////////
00164   //                                                                     //
00165   // Private functions:                                                  //
00166   //                                                                     //
00167   /////////////////////////////////////////////////////////////////////////
00168 
00169   int fitness( NCChunk& ) const;
00170   
00171   NCChunk mutate( const NCChunk& );
00172 
00173   NCChunk crossover( const NCChunk&, const NCChunk& ) const;
00174 
00175   int randomGen( );
00176   
00177   Word randomWord( int ); 
00178   
00179   
00180   /////////////////////////////////////////////////////////////////////////
00181   //                                                                     //
00182   // Data members:                                                       //
00183   //                                                                     //
00184   /////////////////////////////////////////////////////////////////////////
00185   
00186   FreeGroup theGroup;
00187   GHNConfig cfg;
00188   SetOf<Word> relators;
00189   Word w;
00190   int wLen;
00191   int automataSize;
00192   UniformRandom r;
00193 };
00194 
00195 #endif

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