coxiter.h

Go to the documentation of this file.

/*
Copyright (C) 2013-2017
Rafael Guglielmetti, rafael.guglielmetti@unifr.ch
*/
 
/*
This file is part of CoxIter.
 
CoxIter is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as
published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.
 
CoxIter is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
 
You should have received a copy of the GNU General Public License
along with CoxIter. If not, see <http://www.gnu.org/licenses/>.
*/
 
#ifndef __COXITER_H__
#define __COXITER_H__ 1
 
#include "graphs.list.h"
#include "graphs.list.iterator.h"
#include "graphs.product.h"
#include "graphs.product.set.h"
#ifndef _COMPILE_WITHOUT_REGEXP_
#include "lib/regexp.h"
#endif
#include "lib/math_tools.h"
#include "lib/numbers/mpz_rational.h"
#include "lib/polynomials.h"
 
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <string>
#include <unordered_set>
#include <vector>
 
#ifdef _USE_LOCAL_GMP_
#include "gmpxx.h"
#else
#include <gmpxx.h>
#endif
 
#ifdef _OPENMP
#include <omp.h>
#else
inline unsigned int omp_get_thread_num() { return 0; }
inline unsigned int omp_get_max_threads() { return 1; }
#endif
 
using namespace std;
using namespace MathTools;
 
class CoxIter {
private:
  string error; 
  bool debug;   
 
  bool useOpenMP; 
 
  // -----------------------------------------------------------
  // I/O
  bool bWriteInfo; 
 
  // -----------------------------------------------------------
  // Redirection cout to a file
  bool bCoutFile;     
  ofstream *outCout;  
  streambuf *sBufOld; 
 
  string ouputMathematicalFormat; 
 
  // -----------------------------------------------------------
  // Graph
  unsigned int verticesCount;       
  unsigned int maximalSubgraphRank; 
 
  unsigned int dimension;             
  unsigned int sphericalMaxRankFound; 
  unsigned int euclideanMaxRankFound; 
  bool isDimensionGuessed; 
 
  bool isGraphExplored; 
  bool isGraphsProductsComputed; 
  bool isGrowthSeriesComputed;   
 
  bool hasDottedLine;             
  int hasDottedLineWithoutWeight; 
  bool hasBoldLine;               
  bool checkCocompactness;        
  bool checkCofiniteness; 
  int isCocompact;  
  int isArithmetic; 
  int isFiniteCovolume; 
 
  vector<string> verticesToRemove; 
  vector<string> vertices;         
 
  map<string, unsigned int>
      map_vertices_labelToIndex; 
  vector<string> map_vertices_indexToLabel; 
 
  vector<vector<unsigned int>> coxeterMatrix; 
  map<unsigned int, string>
      weightsDotted; 
  vector<vector<bool>> visitedEdges; 
  vector<bool> visitedVertices;      
  vector<short unsigned int> path;   
 
  string gramMatrixField; 
  bool isGramMatrixFieldKnown; 
 
  GraphsList *graphsList_spherical; 
  GraphsList *graphsList_euclidean; 
 
  // Computations relative to the infinite sequence
  unsigned int infSeq_t0; 
  unsigned int infSeq_s0; 
  vector<unsigned int> infSeqFVectorsUnits;  
  vector<unsigned int> infSeqFVectorsPowers; 
 
  // -----------------------------------------------------------
  // Graphs products
  vector<vector<GraphsProductSet>> graphsProducts;
 
  vector<vector<GraphsProductSet>> graphsProducts_canBeFiniteCovolume;
 
  vector<map<vector<vector<short unsigned int>>, unsigned int>>
      graphsProductsCount_spherical;
  vector<map<vector<vector<short unsigned int>>, unsigned int>>
      graphsProductsCount_euclidean;
 
  vector<mpz_class> factorials;
  vector<mpz_class> powersOf2;
 
  // ------------------------------------------------------------
  // Results
  MPZ_rational brEulerCaracteristic;       
  string eulerCharacteristic_computations; 
 
  int fVectorAlternateSum; 
  vector<unsigned int> fVector;         
  unsigned int verticesAtInfinityCount; 
 
  vector<mpz_class>
      growthSeries_polynomialDenominator; 
 
  vector<unsigned int>
      growthSeries_cyclotomicNumerator; 
  bool growthSeries_isFractionReduced;  
 
  string growthSeries_raw; 
 
public:
  CoxIter();
 
  CoxIter(const vector<vector<unsigned int>> &iMatrix,
          const unsigned int &dimension);
 
  ~CoxIter();
 
  bool bRunAllComputations();
 
  void printCoxeterMatrix();
 
  void printCoxeterGraph();
 
  void printGramMatrix();
 
  void printGramMatrix_GAP();
 
  void printGramMatrix_Mathematica();
 
  void printGramMatrix_PARI();
 
  void printGramMatrix_LaTeX();
 
  void printEdgesVisitedMatrix();
 
#ifndef _COMPILE_WITHOUT_REGEXP_
  bool readGraphFromFile(const string &inputFilename);
#endif
 
  bool writeGraphToDraw(const string &outFilenameBasis);
 
  bool writeGraph(const string &filename);
 
#ifndef _COMPILE_WITHOUT_REGEXP_
  bool parseGraph(istream &streamIn);
#endif
 
  void exploreGraph();
 
  void IS_computations(const string &t0, const string &s0);
 
  bool computeEulerCharacteristicFVector();
 
  void growthSeries();
 
  int isGraphCocompact();
 
  int checkCovolumeFiniteness();
 
  bool canBeFiniteCovolume();
 
  vector<vector<short unsigned int>> canBeFiniteCovolume_complete();
 
  void computeGraphsProducts();
 
  void printGrowthSeries();
 
  void printEuclideanGraphsProducts(
      vector<map<vector<vector<short unsigned int>>, unsigned int>>
          *graphsProductsCount);
 
  bool isVertexValid(const string &vertexLabel) const;
 
  unsigned int get_vertexIndex(const string &vertexLabel) const;
 
  string get_vertexLabel(const unsigned int &vertex) const;
 
  string get_error() const;
 
  MPZ_rational get_brEulerCaracteristic() const;
 
  string get_eulerCaracteristicString() const;
 
  string get_eulerCharacteristic_computations() const;
 
  int get_fVectorAlternateSum() const;
 
  vector<unsigned int> get_fVector() const;
 
  vector<unsigned int> get_infSeqFVectorsUnits() const;
 
  vector<unsigned int> get_infSeqFVectorsPowers() const;
 
  unsigned int get_verticesAtInfinityCount() const;
 
  unsigned int get_irreducibleSphericalGraphsCount() const;
 
  bool get_bWriteInfo() const;
 
  bool get_debug() const;
 
  unsigned int get_dimension() const;
 
  bool get_dimensionGuessed() const;
 
  int get_isCocompact();
 
  int get_isFiniteCovolume();
 
  int get_isArithmetic() const;
 
  vector<vector<unsigned int>> get_coxeterMatrix() const;
 
  unsigned int get_coxeterMatrixEntry(const unsigned int &i,
                                      const unsigned int &j) const;
 
  map<unsigned int, string> get_weights() const;
 
  string get_CoxeterMatrixString() const;
 
  vector<vector<string>> get_array_str_2_GramMatrix() const;
 
  string get_gramMatrix() const;
 
  string get_coxeterGraph() const;
 
  string get_gramMatrix_GAP() const;
 
  string get_gramMatrix_LaTeX() const;
 
  string get_gramMatrix_Mathematica() const;
 
  string get_gramMatrix_PARI() const;
 
  string get_gramMatrixField() const;
 
  unsigned int get_verticesCount() const;
 
  bool get_hasDottedLine() const;
 
  int get_hasDottedLineWithoutWeight() const;
 
  vector<string> get_str_map_vertices_indexToLabel() const;
 
  void set_isArithmetic(const unsigned int &arithmetic);
 
  void set_checkCocompactness(const bool &value);
  void set_checkCofiniteness(const bool &value);
  void set_debug(const bool &value);
  void set_useOpenMP(const bool &value);
  void set_outputFilename(const string &filename);
  void set_sdtOutToFile(const string &filename);
  void set_verticesToRemove(const vector<string> &verticesRemove_);
  void set_verticesToConsider(const vector<string> &verticesToConsider);
 
  void set_bWriteInfo(const bool &newValue);
 
  void set_dimension(const unsigned int &dimension_);
 
  GraphsList *get_gl_graphsList_spherical() const;
 
  GraphsList *get_gl_graphsList_euclidean() const;
 
  bool get_hasSphericalGraphsOfRank(const unsigned int &rank) const;
 
  bool get_hasEuclideanGraphsOfRank(const unsigned int &rank) const;
 
  void get_growthSeries(vector<unsigned int> &cyclotomicNumerator,
                        vector<mpz_class> &polynomialDenominator,
                        bool &isReduced);
 
  bool get_isGrowthSeriesReduced();
 
  vector<mpz_class> get_growthSeries_denominator();
 
  string get_growthSeries();
  string get_growthSeries_raw();
 
  const vector<vector<GraphsProductSet>> *get_ptr_graphsProducts() const;
 
  void set_coxeterMatrix(const vector<vector<unsigned int>> &matrix);
 
  void set_ouputMathematicalFormat(const string &format);
 
  void map_vertices_labels_removeReference(const unsigned int &index);
 
  void map_vertices_labels_addReference(const string &label);
 
  void map_vertices_labels_create();
 
  void map_vertices_labels_reinitialize();
 
private:
  CoxIter(const CoxIter &); 
 
  void initializations();
 
  void DFS(unsigned int root, unsigned int from);
 
  void printPath();
 
  void addGraphsFromPath();
 
  void AnToEn_AnToTEn(const vector<short unsigned int> &pathTemp,
                      const vector<bool> &verticesLinkable);
 
  void AnToEn_AnToTEn(const vector<short unsigned int> &pathTemp,
                      const vector<bool> &linkableVertices,
                      const bool &isSpherical,
                      const short unsigned int &iStart);
 
  void B3ToF4_B4ToTF4(const vector<bool> &linkableVerticesStart,
                      vector<short unsigned int> pathTemp,
                      const short unsigned int &endVertex);
 
  void computeGraphsProducts(
      GraphsListIterator grIt,
      vector<map<vector<vector<short unsigned int>>, unsigned int>>
          *graphsProductsCount,
      const bool &isSpherical, GraphsProduct &gp,
      vector<bool> &gpNonLinkableVertices);
 
  void computeGraphsProducts_IS(GraphsListIterator grIt,
                                const bool &isSpherical, GraphsProduct &gp,
                                vector<bool> &gpNonLinkableVertices);
 
  void canBeFiniteCovolume_computeGraphsProducts(
      GraphsListIterator grIt, GraphsProduct &gp,
      vector<bool> &gpNonLinkableVertices);
  void canBeFiniteCovolume_complete_computeGraphsProducts(
      GraphsListIterator grIt, GraphsProduct &gp,
      vector<bool> &gpNonLinkableVertices);
 
  mpz_class i_orderFiniteSubgraph(const unsigned int &type,
                                  const unsigned int &dataSupp);
 
  bool isGraph_cocompact_finiteVolume_parallel(unsigned int index);
 
  bool isGraph_cocompact_finiteVolume_sequential(unsigned int index);
 
  void growthSeries_symbolExponentFromProduct(
      const vector<vector<short unsigned int>> &product,
      vector<unsigned int> &symbol, unsigned int &exponent) const;
 
  void growthSeries_symbolExponentFromProduct(
      const vector<vector<short unsigned int>> &product, string &symbol,
      unsigned int &exponent) const;
 
  void growthSeries_parallel();
 
  void growthSeries_sequential();
 
  void growthSeries_details();
 
  void growthSeries_mergeTerms(vector<mpz_class> &polynomial,
                               vector<unsigned int> &symbol,
                               vector<mpz_class> tempPolynomial,
                               const vector<unsigned int> &tempSymbol,
                               mpz_class biTemp = 1);
 
public:
  friend ostream &operator<<(ostream &, CoxIter const &);
};
 
inline unsigned int linearizationMatrix_index(const unsigned int &i,
                                              const unsigned int &j,
                                              const unsigned int &n) {
  return (i * (2 * n - 1 - i) / 2 + j);
}
 
inline unsigned int linearizationMatrix_row(const unsigned int &k,
                                            const unsigned int &n) {
  return ((2 * n + 1 - sqrtSup((2 * n + 1) * (2 * n + 1) - 8 * k)) / 2);
}
 
inline unsigned int linearizationMatrix_col(const unsigned int &k,
                                            const unsigned int &n) {
  unsigned int row(linearizationMatrix_row(k, n));
  return (k - (row * (2 * n - 1 - row)) / 2);
}
 
#endif