SubgroupFG.h

Go to the documentation of this file.

// Copyright (C) 2005 Alexander Ushakov
// Contents: Definition of class SubgroupFG
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//

#ifndef _SubgroupFG_h_
#define _SubgroupFG_h_


#include "Word.h"
#include "GraphType.h"
#include "GraphConcept.h"
#include "GraphConceptAlgorithms.h"
using namespace Graphs;


#include "vector"
using namespace std;


//---------------------------------------------------------------------------//
//------------------------------ SubgroupFG ---------------------------------//
//---------------------------------------------------------------------------//


class SubgroupFG
{
  //                                                     //
  //  Constructors                                       //
  //                                                     //
public:
  SubgroupFG( int n_gens = 0 );
  SubgroupFG( int n_gens , const vector< Word >& gens );
  
  template< class ConstWordIterator > SubgroupFG( int n_gens , ConstWordIterator B , ConstWordIterator E ) : 
    theNumberOfGenerators( n_gens ),
    fsaDone( false ),
    nielsDone( false )
      {
        int sz = 0;
        ConstWordIterator C = B;
        for( ; C!=E ; ++C, ++sz );
        theGenerators = vector< Word >( sz );
        for( int i=0 ; B!=E ; ++B, ++i )
          theGenerators[i] = *B;
      }

 protected:
  SubgroupFG( int n_gens , const IntLabeledGraph& fsa );


  //                                                     //
  //  Operators:                                         //
  //                                                     //
public:

  bool operator== ( const SubgroupFG& S ) const;


  SubgroupFG operator* ( const SubgroupFG& S ) const;
  
  
  SubgroupFG& operator^= ( const Word& conjugator );
  
  
  SubgroupFG  operator^  ( const Word& conjugator ) const {
    SubgroupFG result = *this;
    result ^= conjugator;
    return result;
  }
  

  SubgroupFG& operator+= ( const SubgroupFG& sbgp );


  SubgroupFG  operator+  ( const SubgroupFG& sbgp ) const {
    SubgroupFG result = *this;
    result += sbgp;
    return result;
  }


  SubgroupFG& operator+= ( const Word& w );


  SubgroupFG  operator+  ( const Word& w ) const {
    SubgroupFG result = *this;
    result += w;
    return result;
  }

  
  //                                                     //
  //  Accessors:                                         //
  //                                                     //
public:
  
  bool checkIsomorphism( const SubgroupFG& S , int vert1 , int vert2 ) const;
  
  
  const vector< Word >& getGenerators( ) const { return theGenerators; }


  const vector< Word >& getNielsenGenerators( ) const;
  
  
  const IntLabeledGraph& getFSA( ) const;
  
  
  int getIndex( ) const;


  int getRank( ) const;
  
  
  bool doesBelong( const Word& w ) const;


  Word express( const Word& w ) const;
  

  SubgroupFG centralizer( ) const;
  
  
  SubgroupFG normalizer( ) const;
  

  pair< SubgroupFG , Word > trim( ) const;
  
  
  pair< bool , Word > areConjugate( const SubgroupFG& sbgp ) const;
  
  
  string graphviz_format( ) const;



  //                                                     //
  //  Internal functions:                                //
  //                                                     //
  
private:


  void computeFSA( ) const;
  void computeNielsenGenerators( ) const;
  
  //                                                     //
  //  Data members                                       //
  //                                                     //
  
private:

  vector< Word > theGenerators;
  int theNumberOfGenerators;
  
  mutable bool fsaDone;
  mutable IntLabeledGraph theFSA;
  mutable list< FoldDetails< IntLabeledGraph::vertex_type , IntLabeledGraph::edge_type > > foldDetails;
  
  mutable bool nielsDone;
  mutable vector< Word > theNielsenGenerators;
};


//---------------------------------------------------------------------------//
//------------------------------ Substitute ---------------------------------//
//---------------------------------------------------------------------------//


template < class ConstIterator >
Word substitute( ConstIterator B , ConstIterator E , const vector< Word >& wrds ) 
{
  Word result;
  for( ; B!=E ; ++B ) {
    int letter = *B;
    if( letter>0 )
      result *=  wrds[ letter-1];
    else
      result *= -wrds[-letter-1];
  }
  
  return result;
}


Word substitute( const Word& w , const vector< Word >& wrds );


//---------------------------------------------------------------------------//
//------------------------------ operator << --------------------------------//
//---------------------------------------------------------------------------//

ostream& operator << ( ostream& os , const SubgroupFG& sbgp );



#endif