CoxIter  1.2
CoxIter - Computing invariants of hyperbolic Coxeter groups
coxiter.h
Go to the documentation of this file.
1 /*
2 Copyright (C) 2013, 2014, 2015, 2016
3 Rafael Guglielmetti, rafael.guglielmetti@unifr.ch
4 */
5 
6 /*
7 This file is part of CoxIter.
8 
9 CoxIter is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as
11 published by the Free Software Foundation, either version 3 of the
12 License, or (at your option) any later version.
13 
14 CoxIter is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with CoxIter. If not, see <http://www.gnu.org/licenses/>.
21 */
22 
33 #ifndef __COXITER_H__
34 #define __COXITER_H__ 1
35 
36 #include "graphs.list.h"
37 #include "graphs.list.iterator.h"
38 #include "graphs.product.h"
39 #include "graphs.product.set.h"
40 #ifndef _COMPILE_WITHOUT_REGEXP_
41 #include "lib/regexp.h"
42 #endif
43 #include "lib/math_tools.h"
44 #include "lib/polynomials.h"
46 
47 #include <algorithm>
48 #include <iterator>
49 #include <string>
50 #include <fstream>
51 #include <iostream>
52 #include <vector>
53 #include <map>
54 #include <cmath>
55 #include <unordered_set>
56 
57 #ifdef _USE_LOCAL_GMP_
58 #include "gmpxx.h"
59 #else
60 #include <gmpxx.h>
61 #endif
62 
63 #ifdef _OPENMP
64 #include <omp.h>
65 #else
66 inline unsigned int omp_get_thread_num() { return 0; }
67 inline unsigned int omp_get_max_threads() { return 1; }
68 #endif
69 
70 using namespace std;
71 using namespace MathTools;
72 
73 class CoxIter
74 {
75  private:
76  string strError;
77  bool bDebug;
78 
79  bool bUseOpenMP;
80 
81  // -----------------------------------------------------------
82  // I/O
83  bool bWriteInfo;
85 
86  // -----------------------------------------------------------
87  // Redirection cout to a file
88  bool bCoutFile;
89  ofstream *outCout;
90  streambuf *sBufOld;
91 
93 
94  // -----------------------------------------------------------
95  // Graph
96  unsigned int iVerticesCount;
97  unsigned int iDimension;
98  unsigned int iSphericalMaxRankFound;
99  unsigned int iEuclideanMaxRankFound;
101 
105 
114 
115  vector< string > strVerticesRemove;
116  vector< string > strVertices;
117 
118  map< string, unsigned int > map_vertices_labelToIndex;
119  vector< string > map_vertices_indexToLabel;
120 
121  vector< vector <unsigned int > > iCoxeterMatrix;
122  map< unsigned int, string > strWeights;
123  vector< vector<bool> > bEdgesVisited;
124  vector< bool > bVerticesVisited;
125  vector<short unsigned int> iPath;
126 
129 
132 
133  // -----------------------------------------------------------
134  // Graphs products
144  vector< vector< GraphsProductSet > > graphsProducts;
145 
154  vector< vector< GraphsProductSet > > graphsProducts_bCanBeFiniteCovolume;
155 
166  vector< map<vector< vector<short unsigned int> >, unsigned int> > graphsProductsCount_spherical;
167  vector< map<vector< vector<short unsigned int> >, unsigned int> > graphsProductsCount_euclidean;
168 
169  vector< mpz_class > iFactorials, iPowersOf2;
170 
171  // ------------------------------------------------------------
172  // Results
175 
177  vector<unsigned int> iFVector;
179 
181  vector<unsigned int> growthSeries_iCyclotomicNumerator;
183 
185 
186  public:
190  CoxIter( );
191 
199  CoxIter( const vector< vector<unsigned int> >& iMatrix, const unsigned int& iDimension );
200 
201  ~CoxIter( );
202 
216  bool bRunAllComputations( );
217 
221  void printCoxeterMatrix( );
222 
226  void printCoxeterGraph( );
227 
231  void printGramMatrix( );
232 
236  void printGramMatrix_GAP( );
237 
241  void printGramMatrix_Mathematica( );
242 
246  void printGramMatrix_PARI( );
247 
251  void printGramMatrix_LaTeX();
252 
256  void printEdgesVisitedMatrix( );
257 
264  #ifndef _COMPILE_WITHOUT_REGEXP_
265  bool bReadGraphFromFile( const string& strInputFilename );
266  #endif
267 
275  bool bWriteGraphToDraw( const string& strOutFilenameBasis );
276 
283  bool bWriteGraph( const string& strFilename );
284 
291  #ifndef _COMPILE_WITHOUT_REGEXP_
292  bool parseGraph( istream& streamIn );
293  #endif
294 
301  void exploreGraph();
302 
307  bool bEulerCharacteristicFVector();
308 
314  void growthSeries();
315 
321  int iIsGraphCocompact( );
322 
328  int isFiniteCovolume( );
329 
336  bool bCanBeFiniteCovolume( );
337 
342  vector< vector<short unsigned int> > bCanBeFiniteCovolume_complete( );
343 
348  void computeGraphsProducts( );
349 
354  void printGrowthSeries( );
355 
361  void printEuclideanGraphsProducts( vector< map<vector< vector<short unsigned int> >, unsigned int> >* graphsProductsCount );
362 
368  bool bIsVertexValid( const string& strVertexLabel ) const;
369 
375  unsigned int get_iVertexIndex( const string& strVertexLabel ) const;
376 
382  string get_strVertexLabel( const unsigned int& iVertex ) const;
383 
389  string get_strError( ) const;
390 
396  MPZ_rational get_brEulerCaracteristic( ) const;
397 
403  string get_strEulerCaracteristic( ) const;
404 
410  string get_strEulerCharacteristic_computations( ) const;
411 
416  int get_iFVectorAlternateSum( ) const;
417 
422  vector< unsigned int> get_iFVector( ) const;
423 
428  unsigned int get_iVerticesAtInfinityCount( ) const;
429 
434  unsigned int get_iIrreducibleSphericalGraphsCount() const;
435 
441  bool get_bWriteInfo( ) const;
442 
448  bool get_bDebug( ) const;
449 
455  unsigned int get_iDimension( ) const;
456 
462  bool get_bDimensionGuessed( ) const;
463 
469  int get_iIsCocompact( );
470 
476  int get_iIsFiniteCovolume( );
477 
483  int get_iIsArithmetic( ) const;
484 
490  vector< vector<unsigned int> > get_iCoxeterMatrix( ) const;
491 
497  map< unsigned int, string > get_strWeights() const;
498 
504  string get_strCoxeterMatrix( ) const;
505 
511  vector< vector< string > > get_array_str_2_GramMatrix( ) const;
512 
517  string get_strGramMatrix( ) const;
518 
523  string get_strCoxeterGraph( ) const;
524 
529  string get_strGramMatrix_GAP( ) const;
530 
535  string get_strGramMatrix_LaTeX( ) const;
536 
541  string get_strGramMatrix_Mathematica( ) const;
542 
547  string get_strGramMatrix_PARI( ) const;
548 
553  string get_strGramMatrixField( ) const;
554 
559  unsigned int get_iVerticesCount( ) const;
560 
565  bool get_bHasDottedLine( ) const;
566 
571  int get_iHasDottedLineWithoutWeight() const;
572 
577  vector< string > get_str_map_vertices_indexToLabel() const;
578 
585  void set_iIsArithmetic( const unsigned int &iArithmetic );
586 
587  void set_bCheckCocompactness( const bool& bValue );
588  void set_bCheckCofiniteness( const bool& bValue );
589  void set_bDebug( const bool& bValue );
590  void set_bUseOpenMP( const bool& bValue );
591  void set_strOutputFilename( const string& strValue );
592  void set_sdtoutToFile( const string& strFilename );
593  void set_strVerticesToRemove( const vector< string >& strVerticesRemove_ );
594  void set_strVerticesToConsider( const vector< string >& strVerticesToConsider );
595 
602  void set_bWriteInfo( const bool& bNewValue );
603 
608  void set_iDimension( const unsigned int& iDimension_ );
609 
610  GraphsList* get_gl_graphsList_spherical( ) const;
611 
612  GraphsList* get_gl_graphsList_euclidean( ) const;
613 
614  bool get_b_hasSphericalGraphsOfRank( const unsigned int& iRank ) const;
615 
616  bool get_b_hasEuclideanGraphsOfRank( const unsigned int& iRank ) const;
617 
626  void get_iGrowthSeries( vector<unsigned int>& iCyclotomicNumerator, vector< mpz_class >& iPolynomialDenominator, bool& bReduced );
627 
634  bool get_bGrowthSeriesReduced( );
635 
636  vector< mpz_class > get_iGrowthSeries_denominator( );
637 
638  string get_strGrowthSeries();
639  string get_strGrowthSeries_raw();
640 
646  const vector< vector< GraphsProductSet > >* get_ptr_graphsProducts( ) const;
647 
648 
654  void set_iCoxeterMatrix( const vector< vector<unsigned int> >& iMat );
655 
656  void set_strOuputMathematicalFormat( const string& strO );
657 
663  void map_vertices_labels_removeReference( const unsigned int& iIndex );
664 
670  void map_vertices_labels_addReference( const string& strLabel );
671 
676  void map_vertices_labels_create( );
677 
682  void map_vertices_labels_reinitialize();
683 
684  private:
685  CoxIter( const CoxIter& );
686 
690  void initializations( );
691 
700  void DFS( unsigned int iRoot, unsigned int iFrom );
701 
705  void printPath( );
706 
712  void addGraphsFromPath( );
713 
721  void AnToEn_AnToTEn( const vector<short unsigned int>& iPathTemp, const vector< bool >& bVerticesLinkable );
722 
732  void AnToEn_AnToTEn( const vector<short unsigned int>& iPathTemp, const vector< bool >& bVerticesLinkable, const bool& bSpherical, const short unsigned int& iStart );
733 
742  void B3ToF4_B4ToTF4( const vector<bool> &bVerticesBeginLinkable, vector<short unsigned int> iPathTemp, const short unsigned int &iVEnd );
743 
753  void computeGraphsProducts( GraphsListIterator grIt, vector< map<vector< vector<short unsigned int> >, unsigned int> >* graphsProductsCount, const bool& bSpherical, GraphsProduct& gp, vector< bool >& bGPVerticesNonLinkable );
754 
755  void bCanBeFiniteCovolume_computeGraphsProducts( GraphsListIterator grIt, GraphsProduct& gp, vector< bool >& bGPVerticesNonLinkable );
756  void bCanBeFiniteCovolume_complete_computeGraphsProducts( GraphsListIterator grIt, GraphsProduct& gp, vector< bool >& bGPVerticesNonLinkable );
757 
766  mpz_class i_orderFiniteSubgraph( const unsigned int &iType, const unsigned int &iDataSupp );
767 
774  bool b_isGraph_cocompact_finiteVolume_parallel( unsigned int iIndex );
775 
782  bool b_isGraph_cocompact_finiteVolume_sequential( unsigned int iIndex );
783 
791  void growthSeries_symbolExponentFromProduct( const vector< vector<short unsigned int> >& iProduct, vector<unsigned int>& iSymbol, unsigned int& iExponent ) const;
792 
800  void growthSeries_symbolExponentFromProduct( const vector< vector<short unsigned int> >& iProduct, string& strSymbol, unsigned int& iExponent ) const;
801 
805  void growthSeries_parallel();
806 
810  void growthSeries_sequential();
811 
812  void growthSeries_details();
813 
825  void growthSeries_mergeTerms( vector< mpz_class >& iPolynomial, vector<unsigned int>& iSymbol, vector< mpz_class > iTemp_polynomial, const vector<unsigned int>& iTemp_symbol, mpz_class biTemp = 1 );
826 
827  public:
828  friend ostream& operator<<( ostream& , CoxIter const & );
829 };
830 
831 inline unsigned int iLinearizationMatrix_index( const unsigned int& i, const unsigned int& j, const unsigned int& n )
832 {
833  return ( i*(2*n - 1 - i)/2 + j);
834 }
835 
836 inline unsigned int iLinearizationMatrix_row( const unsigned int& k, const unsigned int& n )
837 {
838  return ( ( 2*n+1 - iSQRTsup((2*n+1)*(2*n+1) - 8*k) )/2 );
839 }
840 
841 inline unsigned int iLinearizationMatrix_col( const unsigned int& k, const unsigned int& n )
842 {
843  unsigned int iRow( iLinearizationMatrix_row( k, n ) );
844  return ( k - ( iRow * ( 2*n-1-iRow ))/2 );
845 }
846 
847 #endif
ofstream * outCout
Flow to the file.
Definition: coxiter.h:89
unsigned int iLinearizationMatrix_index(const unsigned int &i, const unsigned int &j, const unsigned int &n)
Definition: coxiter.h:831
int iFVectorAlternateSum
Alternating sum of the components of the f-vector.
Definition: coxiter.h:176
streambuf * sBufOld
To reset the cout, at the end.
Definition: coxiter.h:90
bool bHasBoldLine
True if the graph has a bold line.
Definition: coxiter.h:108
Definition: math_tools.cpp:25
bool bCheckCofiniteness
True if we want to check the finite covolume condition.
Definition: coxiter.h:110
vector< short unsigned int > iPath
chemin en cours (pour le DFS)
Definition: coxiter.h:125
Permet de parcourir une liste de graphes Utilisation (pour un GraphsList *gl ) GraphsListIterator it...
Definition: graphs.list.iterator.h:44
vector< vector< GraphsProductSet > > graphsProducts
Definition: coxiter.h:144
int iIsCocompact
1 If cocompact, 0 if not, -1 if don&#39;t know, -2 if not tested
Definition: coxiter.h:111
int iIsArithmetic
1 If arithmetic, 0 if non-arithmetic, -1 if don&#39;t know
Definition: coxiter.h:112
MPZ_rational brEulerCaracteristic
Euler characteristic.
Definition: coxiter.h:173
vector< string > strVertices
Vertices to be taken.
Definition: coxiter.h:116
Liste des graphes.
Definition: graphs.list.h:40
unsigned int omp_get_max_threads()
Definition: coxiter.h:67
string strEulerCharacteristic_computations
Euler characteristic (without the computations done)
Definition: coxiter.h:174
map< string, unsigned int > map_vertices_labelToIndex
For the correspondance: label <-> indexes of vertices.
Definition: coxiter.h:118
Some mathematical functions.
vector< bool > bVerticesVisited
For the DFS: traversed vertices.
Definition: coxiter.h:124
vector< unsigned int > growthSeries_iCyclotomicNumerator
Contains a list oif cyclotomic polynomials.
Definition: coxiter.h:181
vector< string > map_vertices_indexToLabel
For the correspondance: label <-> indexes of vertices.
Definition: coxiter.h:119
bool growthSeries_bFractionReduced
True if the fraction has been reduced (it is always the case when the cyclotomic terms are <= 60...
Definition: coxiter.h:182
bool bGraphsProductsComputed
True if we computed the graphs products.
Definition: coxiter.h:103
unsigned int iSphericalMaxRankFound
Maximal rank for a spherical graph.
Definition: coxiter.h:98
vector< unsigned int > iFVector
F-vector.
Definition: coxiter.h:177
Rational number.
unsigned int iVerticesAtInfinityCount
Number of vertices at infinity.
Definition: coxiter.h:178
std::enable_if< std::is_unsigned< Type >::value, Type >::type iSQRTsup(Type iN)
Definition: math_tools.h:93
string strGramMatrixField
Field generated by the entries of the Gram matrix.
Definition: coxiter.h:127
map< unsigned int, string > strWeights
Weights of the dotted lines (via linearization)
Definition: coxiter.h:122
vector< mpz_class > iPowersOf2
Some factorials and powers of two.
Definition: coxiter.h:169
Definition: mpz_rational.h:49
vector< string > strVerticesRemove
Vertices to be removed.
Definition: coxiter.h:115
bool bCoutFile
True if we want to redirect cout to a file.
Definition: coxiter.h:88
GraphsList * graphsList_spherical
Pointer to the list of spherical graphs.
Definition: coxiter.h:130
vector< mpz_class > growthSeries_iPolynomialDenominator
(i-1)th term contains the coefficient of x^i
Definition: coxiter.h:180
bool bHasDottedLine
True if the graph has a dotted line.
Definition: coxiter.h:106
int iHasDottedLineWithoutWeight
If the graph dotted lines without weight (-1: maybe, 0: no, 1: yes)
Definition: coxiter.h:107
int iIsFiniteCovolume
1 If finite covolume, 0 if not, -1 if don&#39;t know (or cannot know), -2 if not tested ...
Definition: coxiter.h:113
: Un produit de graphs
Definition: graphs.product.h:45
bool bWriteInfo
If we want to write informations (false if CoxIter is used "as a plugin")
Definition: coxiter.h:83
unsigned int iLinearizationMatrix_row(const unsigned int &k, const unsigned int &n)
Definition: coxiter.h:836
bool bWriteProgress
If we want to display the progress // TODO: option.
Definition: coxiter.h:84
bool bDimension_guessed
If the dimension was not specified but guessed.
Definition: coxiter.h:100
GraphsList * graphsList_euclidean
Pointer to the list of euclidean graphs.
Definition: coxiter.h:131
string strOuputMathematicalFormat
Format for mathematical output (generic, mathematica)
Definition: coxiter.h:92
vector< vector< bool > > bEdgesVisited
For the DFS: traversed edges.
Definition: coxiter.h:123
bool bCheckCocompactness
True if we want to check the cocompacity.
Definition: coxiter.h:109
bool bUseOpenMP
Use OpenMP.
Definition: coxiter.h:79
unsigned int iDimension
Dimension (or 0)
Definition: coxiter.h:97
bool bGraphExplored
True if we looked for connected subgraphs (affine and spherical)
Definition: coxiter.h:102
string growthSeries_raw
Row series, not simplified.
Definition: coxiter.h:184
To simplify the use of regexp.
unsigned int omp_get_thread_num()
Definition: coxiter.h:66
unsigned int iLinearizationMatrix_col(const unsigned int &k, const unsigned int &n)
Definition: coxiter.h:841
vector< vector< GraphsProductSet > > graphsProducts_bCanBeFiniteCovolume
Definition: coxiter.h:154
vector< map< vector< vector< short unsigned int > >, unsigned int > > graphsProductsCount_spherical
Definition: coxiter.h:166
bool bGrowthSeriesComputed
True if we computed the growth series.
Definition: coxiter.h:104
bool bDebug
If true, prints additionnal information.
Definition: coxiter.h:77
string strError
Error code.
Definition: coxiter.h:76
vector< map< vector< vector< short unsigned int > >, unsigned int > > graphsProductsCount_euclidean
Count graphs products (with their multiplicities)
Definition: coxiter.h:167
Main class for the work.
Definition: coxiter.h:73
unsigned int iVerticesCount
Number of vertices.
Definition: coxiter.h:96
ostream & operator<<(ostream &o, const CoxIter &g)
Definition: coxiter.cpp:1313
unsigned int iEuclideanMaxRankFound
Maximal rank for an euclidean graph.
Definition: coxiter.h:99
vector< vector< unsigned int > > iCoxeterMatrix
Coxeter matrix.
Definition: coxiter.h:121
bool bGramMatrixField
True if the field was determined.
Definition: coxiter.h:128
Some mathematical functions regarding polynomials.