WhiteheadGraph.h

Go to the documentation of this file.

// Copyright (C) 2005 Alexei Miasnikov
// Contents: Definition of classes which implement different versions
//           of Whitehead graphs
//
// Principal Author: Alexei Miasnikov (2005)
//
// Status: Useable.
//



#ifndef _WGRAPH_H_
#define _WGRAPH_H_


#include "Word.h"
#include <vector>
#include "errormsgs.h"

typedef int Generator;

//
//  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).
//

class CutVertices
{
 public:

  CutVertices( const int** G, int n);
  ~CutVertices();


  void compute();

  

  void computeBruteForce();

  
  

  int numberOfComponents( bool ignore_single_vertices = false );

  

  vector<int> getCutVertices()const {return articulation_point;}
  
 private:
  void init();

  
  void DepthFirstSearch();

  void RecursiveDepthFirstSearch(int v);

  void RDFS_Compute_Low(int v);

  void ArticulationPoints();

  int** theGraph;

  int N;

  int time;
  vector<int> visit;
  vector<int> pred;
  vector<int>  discover;
  vector<int>  Low;

  
  vector<int> articulation_point;

};


//
//  Base (interface)  class 
//


class WhiteheadGraph 
{
 public:


  WhiteheadGraph( const Word& w, int num_of_gens ): 
    theWord( w ), 
    nOfGenerators(num_of_gens  ) {}

  /*
    \return Reference to the input word. 
   */
 const Word& getWord()const { return theWord; }
 protected:
 Word theWord;
 int nOfGenerators;
};


//
//  Implementation of Whitehead Simple Graph (i.e. no multiple
//                    edges or loops allowed)  
//

class WhiteheadSimpleGraph : public WhiteheadGraph
{
 public:


  WhiteheadSimpleGraph( const Word& w, int num_of_gens );
  
  friend ostream& operator << ( ostream& out, const WhiteheadSimpleGraph& g){
    g.printOn( out );
    return out;
  }
  
  ~WhiteheadSimpleGraph();
    

  int getCount(int i, int j)const {
    if ( i<0 || j<0 || i>=theSize || j>=theSize )
      msgs::error("WhiteheadSimpleGraph::getCount(...): index is out of bounds.");
    return theAdjMatrix[i][j];
  }
  

  int getSize()const { return theSize; }

  vector<double> getWeightVector() const;

  vector<Word> getWeightNames()const;


  bool isUndirected()const { return undirected; }


  void makeUndirected();
  

  int numberOfComponents() const;

  int numberOfCutVertices()const;

  vector<int> cutVertices()const;  
  
  int numberOfCutVerticesBruteForce()const;
  vector<int> cutVerticesBruteForce()const;

 private:
  void printOn( ostream& out ) const;
  
  int genToIndex( const Generator& g )const{
    int ind = g;
    if ( ind > 0) 
      return ind-1;
    else 
      return -ind + nOfGenerators - 1;
  }
  
  Generator indToGenerator( int i )const{
    if (i < nOfGenerators)
      // if positive
      return Generator(i+1);
    else {
      // if negative
      return -( Generator(i - nOfGenerators + 1) );
    }
  }

  int nOfComponents() const;

  int theSize;
  
  int** theAdjMatrix;

  bool undirected;
};


//
//  Implementation of Whitehead Multi-Graph
//

class WhiteheadMultiGraph : public WhiteheadGraph
{
 public:
  WhiteheadMultiGraph( const Word& w, int n) : WhiteheadGraph( w,n ) {} 
 private:
};

#endif