SubgroupFG.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class SubgroupFG
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _SubgroupFG_h_
00010 #define _SubgroupFG_h_
00011 
00012 
00013 #include "Word.h"
00014 #include "GraphType.h"
00015 #include "GraphConcept.h"
00016 #include "GraphConceptAlgorithms.h"
00017 using namespace Graphs;
00018 
00019 
00020 #include "vector"
00021 using namespace std;
00022 
00023 
00024 //---------------------------------------------------------------------------//
00025 //------------------------------ SubgroupFG ---------------------------------//
00026 //---------------------------------------------------------------------------//
00027 
00028 
00029 class SubgroupFG
00030 {
00032   //                                                     //
00033   //  Constructors                                       //
00034   //                                                     //
00036 public:
00037   SubgroupFG( );
00038   SubgroupFG( int n_gens , const vector< Word >& gens );
00039   
00040 protected:
00041   SubgroupFG( int n_gens , const IntLabeledGraph& fsa );
00042 
00043 
00045   //                                                     //
00046   //  Operators:                                         //
00047   //                                                     //
00049 public:
00050   bool operator== ( const SubgroupFG& S ) const;
00051   SubgroupFG operator* ( const SubgroupFG& S ) const;
00052   
00054   //                                                     //
00055   //  Accessors:                                         //
00056   //                                                     //
00058 public:
00059 
00060   const vector< Word >& getGenerators( ) const { return theGenerators; }
00061   const vector< Word >& getNielsenGenerators( ) const;
00062   
00063   const IntLabeledGraph& getFSA( ) const;
00064   bool doesBelong( const Word& w ) const;
00065   
00066   int getIndex( ) const;
00067   int getRank( ) const;
00068   
00069   Word express( const Word& w ) const;
00070   
00072   //                                                     //
00073   //  Internal functions:                                //
00074   //                                                     //
00076   
00077 private:
00078 
00079 
00080   void computeFSA( ) const;
00081   void computeNielsenGenerators( ) const;
00082   
00084   //                                                     //
00085   //  Data members                                       //
00086   //                                                     //
00088   
00089 private:
00090 
00091   vector< Word > theGenerators;
00092   int theNumberOfGenerators;
00093   
00094   mutable bool fsaDone;
00095   mutable IntLabeledGraph theFSA;
00096   mutable list< FoldDetails< IntLabeledGraph::vertex_type , IntLabeledGraph::edge_type > > foldDetails;
00097   
00098   mutable bool nielsDone;
00099   mutable vector< Word > theNielsenGenerators;
00100 };
00101 
00102 
00103 //---------------------------------------------------------------------------//
00104 //------------------------------ Substitute ---------------------------------//
00105 //---------------------------------------------------------------------------//
00106 
00107 
00108 template < class ConstIterator >
00109 Word substitute( ConstIterator B , ConstIterator E , const vector< Word >& wrds ) 
00110 {
00111   Word result;
00112   for( ; B!=E ; ++B ) {
00113     int letter = *B;
00114     if( letter>0 )
00115       result *=  wrds[ letter-1];
00116     else
00117       result *= -wrds[-letter-1];
00118   }
00119   
00120   return result;
00121 }
00122 
00123 
00124 Word substitute( const Word& w , const vector< Word >& wrds );
00125 
00126 
00127 //---------------------------------------------------------------------------//
00128 //------------------------------ operator << --------------------------------//
00129 //---------------------------------------------------------------------------//
00130 
00131 ostream& operator << ( ostream& os , const SubgroupFG& sbgp );
00132 
00133 
00134 
00135 #endif
00136 

Generated on Mon Feb 27 22:47:05 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.4