WhiteheadGraph.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexei Miasnikov
00002 // Contents: Definition of classes which implement different versions
00003 //           of Whitehead graphs
00004 //
00005 // Principal Author: Alexei Miasnikov (2005)
00006 //
00007 // Status: Useable.
00008 //
00009 
00010 
00011 
00012 #ifndef _WGRAPH_H_
00013 #define _WGRAPH_H_
00014 
00015 
00016 #include "Word.h"
00017 #include <vector>
00018 #include "errormsgs.h"
00019 
00020 typedef int Generator;
00021 
00023 //
00024 //  Class to compute all cut vertexes of a graph  ( there is an edge (i,j) in the graph iff G[i][j]\f$\neq$\f  0).
00025 //
00027 
00029 class CutVertices
00030 {
00031  public:
00033 
00037   CutVertices( const int** G, int n);
00038   ~CutVertices();
00039 
00041 
00045   void compute();
00046 
00047   
00049 
00053   void computeBruteForce();
00054 
00055   
00056   
00058 
00063   int numberOfComponents( bool ignore_single_vertices = false );
00064 
00065   
00067 
00072   vector<int> getCutVertices()const {return articulation_point;}
00073   
00074  private:
00075   void init();
00076 
00077   
00079   void DepthFirstSearch();
00080 
00082   void RecursiveDepthFirstSearch(int v);
00083 
00085   void RDFS_Compute_Low(int v);
00086 
00088   void ArticulationPoints();
00089 
00091   int** theGraph;
00092 
00094   int N;
00095 
00097   int time;
00099   vector<int> visit;
00101   vector<int> pred;
00103   vector<int>  discover;
00104   vector<int>  Low;
00105 
00106   
00108   vector<int> articulation_point;
00109 
00110 };
00111 
00112 
00114 //
00115 //  Base (interface)  class 
00116 //
00118 
00119 
00121 class WhiteheadGraph 
00122 {
00123  public:
00124 
00126 
00130   WhiteheadGraph( const Word& w, int num_of_gens ): 
00131     theWord( w ), 
00132     nOfGenerators(num_of_gens  ) {}
00133 
00135   /*
00136     \return Reference to the input word. 
00137    */
00138  const Word& getWord()const { return theWord; }
00139  protected:
00141  Word theWord;
00143  int nOfGenerators;
00144 };
00145 
00146 
00148 //
00149 //  Implementation of Whitehead Simple Graph (i.e. no multiple
00150 //                    edges or loops allowed)  
00151 //
00153 
00155 class WhiteheadSimpleGraph : public WhiteheadGraph
00156 {
00157  public:
00158 
00160 
00164   WhiteheadSimpleGraph( const Word& w, int num_of_gens );
00165   
00167   friend ostream& operator << ( ostream& out, const WhiteheadSimpleGraph& g){
00168     g.printOn( out );
00169     return out;
00170   }
00171   
00172   ~WhiteheadSimpleGraph();
00173     
00175 
00180   int getCount(int i, int j)const {
00181     if ( i<0 || j<0 || i>=theSize || j>=theSize )
00182       msgs::error("WhiteheadSimpleGraph::getCount(...): index is out of bounds.");
00183     return theAdjMatrix[i][j];
00184   }
00185   
00187 
00190   int getSize()const { return theSize; }
00192 
00197   vector<double> getWeightVector() const;
00199 
00202   vector<Word> getWeightNames()const;
00203 
00205 
00210   bool isUndirected()const { return undirected; }
00211 
00213 
00220   void makeUndirected();
00221   
00223 
00226   int numberOfComponents() const;
00228 
00231   int numberOfCutVertices()const;
00233 
00236   vector<int> cutVertices()const;  
00237   
00238   int numberOfCutVerticesBruteForce()const;
00239   vector<int> cutVerticesBruteForce()const;
00240 
00241  private:
00243   void printOn( ostream& out ) const;
00244   
00246   int genToIndex( const Generator& g )const{
00247     int ind = g;
00248     if ( ind > 0) 
00249       return ind-1;
00250     else 
00251       return -ind + nOfGenerators - 1;
00252   }
00253   
00255   Generator indToGenerator( int i )const{
00256     if (i < nOfGenerators)
00257       // if positive
00258       return Generator(i+1);
00259     else {
00260       // if negative
00261       return -( Generator(i - nOfGenerators + 1) );
00262     }
00263   }
00264 
00266   int nOfComponents() const;
00267 
00269   int theSize;
00270   
00272   int** theAdjMatrix;
00273 
00275   bool undirected;
00276 };
00277 
00278 
00280 //
00281 //  Implementation of Whitehead Multi-Graph
00282 //
00284 
00286 class WhiteheadMultiGraph : public WhiteheadGraph
00287 {
00288  public:
00289   WhiteheadMultiGraph( const Word& w, int n) : WhiteheadGraph( w,n ) {} 
00290  private:
00291 };
00292 
00293 #endif
 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