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

/magnus/back_end/Todd-Coxeter/include/CosetRelations.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: 
00003  */
00004 
00005 // Copyright (C) 1997 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 //
00008 // Contents: Definition of class CosetRelation, CosetRelationsSet.
00009 //
00010 // Principal Author: Alexey Myasnikov
00011 //
00012 // Status: Useable
00013 //
00014 // Usage:
00015 //
00016 // Revision History:
00017 //
00018 //
00019 
00020 
00021 #ifndef _COSET_RELATIONS_H_
00022 #define _COSET_RELATIONS_H_
00023 
00024 #include "Word.h"
00025 #include "BTree.h"
00026 #include "Vector.h"
00027 
00028 // ----------------- CosetRelationsSet ----------------------- //
00029 // This is internal class for Todd-Coxeter
00030 
00031 class CosetRelationsSet {
00032 public:
00033   CosetRelationsSet(int num_of_gens):
00034     relations(num_of_gens*2),
00035     numOfCollisions(0),
00036     theCollisions(4){}
00037   
00038   const BTree<int,int>& relationsOf(Generator i)const 
00039     {return relations.constref(indexRelOf(i));}
00040   // Returns relators, corresponding to the given generator
00041   // Relations are pairs in BTree of type <Key><Generator> = <Value>
00042   // Where Key and Value are corresponding Key and Value of a BTree and
00043   // Generator is the given generator.
00044 
00045   bool addRelation(int first,const Generator& g, int second,bool inverse=false);
00046   // Adds relation (relation is first*g = second) to the relations set.
00047   // Looks for collisions and record them if occurs
00048 
00049   int getRelationNumber(int ,const Generator&)const;
00050   // Returns the right part of relation 
00051 
00052   void replaceCosets(int good,int bad);
00053   // Replaces all cosets in relation set equal too 'bad' with 'good' 
00054  
00055   int numberOfCollisions()const;
00056   // Number of collisions, remain in theCollisions
00057 
00058   bool removeCollision(int); 
00059   // Removes i-th collision from theCollisions. 
00060 
00061   bool collision(int& good,int& bad)const;
00062   // True if good theCollisions is not empty.
00063   // Returns good and bad items of current collision
00064 
00065   int indexRelOf(const Generator& g)const;
00066   // Returns index in relations vector, corresponding 
00067   // to the given generator
00068 
00069   Generator genOfRels(int i)const;
00070   // returns Generator, corresponding to given index
00071  
00072   
00073   // I/O
00074   friend ostream& operator << ( ostream& ostr, const CosetRelationsSet& cr )
00075   {
00076     for (int i=0;i<cr.relations.length();i++){
00077       BTreeIterator<int,int> I(cr.relations.constref(i));
00078       for (I.reset();!I.done();I.next()){
00079         ostr << I.getKey() << "g" << i+1 <<"="<<I.getValue() <<", ";
00080       }
00081       ostr << endl;
00082     }
00083     return ostr;
00084   }  
00085 
00086 
00087 private:
00088   CosetRelationsSet(const CosetRelationsSet&);
00089   // Copy constructor prohibited
00090 
00091   void addCollision(int bad,int good);
00092   // add collision to the collision list
00093 
00094   int numOfCollisions;
00095   // Current number of collisions
00096 
00097   VectorOf<BTree<int,int> > relations;
00098   // Set of relations
00099 
00100   BTree< int, int > theCollisions;
00101   // List of collisions
00102 };
00103 
00104 #endif
00105 
00106 
00107 
00108 
00109 
00110 
00111 
00112 
00113 
00114 
00115 
00116 
00117 
00118 
00119 
00120 
00121 
00122 
00123 
00124 
00125 
00126 
00127 
00128 

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