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( int n_gens = 0 );
00038   SubgroupFG( int n_gens , const vector< Word >& gens );
00039   
00040   template< class ConstWordIterator > SubgroupFG( int n_gens , ConstWordIterator B , ConstWordIterator E ) : 
00041     theNumberOfGenerators( n_gens ),
00042     fsaDone( false ),
00043     nielsDone( false )
00044       {
00045         int sz = 0;
00046         ConstWordIterator C = B;
00047         for( ; C!=E ; ++C, ++sz );
00048         theGenerators = vector< Word >( sz );
00049         for( int i=0 ; B!=E ; ++B, ++i )
00050           theGenerators[i] = *B;
00051       }
00052 
00053  protected:
00054   SubgroupFG( int n_gens , const IntLabeledGraph& fsa );
00055 
00056 
00058   //                                                     //
00059   //  Operators:                                         //
00060   //                                                     //
00062 public:
00063 
00065   bool operator== ( const SubgroupFG& S ) const;
00066 
00067 
00069   SubgroupFG operator* ( const SubgroupFG& S ) const;
00070   
00071   
00073   SubgroupFG& operator^= ( const Word& conjugator );
00074   
00075   
00077   SubgroupFG  operator^  ( const Word& conjugator ) const {
00078     SubgroupFG result = *this;
00079     result ^= conjugator;
00080     return result;
00081   }
00082   
00083 
00085   SubgroupFG& operator+= ( const SubgroupFG& sbgp );
00086 
00087 
00089   SubgroupFG  operator+  ( const SubgroupFG& sbgp ) const {
00090     SubgroupFG result = *this;
00091     result += sbgp;
00092     return result;
00093   }
00094 
00095 
00097   SubgroupFG& operator+= ( const Word& w );
00098 
00099 
00101   SubgroupFG  operator+  ( const Word& w ) const {
00102     SubgroupFG result = *this;
00103     result += w;
00104     return result;
00105   }
00106 
00107   
00109   //                                                     //
00110   //  Accessors:                                         //
00111   //                                                     //
00113 public:
00114   
00116   bool checkIsomorphism( const SubgroupFG& S , int vert1 , int vert2 ) const;
00117   
00118   
00120   const vector< Word >& getGenerators( ) const { return theGenerators; }
00121 
00122 
00124   const vector< Word >& getNielsenGenerators( ) const;
00125   
00126   
00128   const IntLabeledGraph& getFSA( ) const;
00129   
00130   
00132   int getIndex( ) const;
00133 
00134 
00136   int getRank( ) const;
00137   
00138   
00140   bool doesBelong( const Word& w ) const;
00141 
00142 
00144   Word express( const Word& w ) const;
00145   
00146 
00148   SubgroupFG centralizer( ) const;
00149   
00150   
00152   SubgroupFG normalizer( ) const;
00153   
00154 
00156   pair< SubgroupFG , Word > trim( ) const;
00157   
00158   
00160   pair< bool , Word > areConjugate( const SubgroupFG& sbgp ) const;
00161   
00162   
00164   string graphviz_format( ) const;
00165 
00166 
00167 
00169   //                                                     //
00170   //  Internal functions:                                //
00171   //                                                     //
00173   
00174 private:
00175 
00176 
00177   void computeFSA( ) const;
00178   void computeNielsenGenerators( ) const;
00179   
00181   //                                                     //
00182   //  Data members                                       //
00183   //                                                     //
00185   
00186 private:
00187 
00188   vector< Word > theGenerators;
00189   int theNumberOfGenerators;
00190   
00191   mutable bool fsaDone;
00192   mutable IntLabeledGraph theFSA;
00193   mutable list< FoldDetails< IntLabeledGraph::vertex_type , IntLabeledGraph::edge_type > > foldDetails;
00194   
00195   mutable bool nielsDone;
00196   mutable vector< Word > theNielsenGenerators;
00197 };
00198 
00199 
00200 //---------------------------------------------------------------------------//
00201 //------------------------------ Substitute ---------------------------------//
00202 //---------------------------------------------------------------------------//
00203 
00204 
00205 template < class ConstIterator >
00206 Word substitute( ConstIterator B , ConstIterator E , const vector< Word >& wrds ) 
00207 {
00208   Word result;
00209   for( ; B!=E ; ++B ) {
00210     int letter = *B;
00211     if( letter>0 )
00212       result *=  wrds[ letter-1];
00213     else
00214       result *= -wrds[-letter-1];
00215   }
00216   
00217   return result;
00218 }
00219 
00220 
00221 Word substitute( const Word& w , const vector< Word >& wrds );
00222 
00223 
00224 //---------------------------------------------------------------------------//
00225 //------------------------------ operator << --------------------------------//
00226 //---------------------------------------------------------------------------//
00227 
00228 ostream& operator << ( ostream& os , const SubgroupFG& sbgp );
00229 
00230 
00231 
00232 #endif
00233 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on Mon Sep 26 18:43:45 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1