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