Frobby  0.9.0
LatticeAlgs.h
Go to the documentation of this file.
1 /* Frobby: Software for monomial ideal computations.
2  Copyright (C) 2011 Bjarke Hammersholt Roune (www.broune.com)
3 
4  This program is free software; you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation; either version 2 of the License, or
7  (at your option) any later version.
8 
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with this program. If not, see http://www.gnu.org/licenses/.
16 */
17 #ifndef LATTICE_ALGS_GUARD
18 #define LATTICE_ALGS_GUARD
19 
20 #include "SatBinomIdeal.h"
21 #include "IOFacade.h"
22 #include "Scanner.h"
23 #include "IOHandler.h"
24 #include "DataType.h"
25 #include "BigIdeal.h"
26 #include "MsmStrategy.h"
27 #include "TermTranslator.h"
29 #include "DebugStrategy.h"
30 #include "Matrix.h"
31 #include "BigTermRecorder.h"
32 #include "SliceParams.h"
33 #include "SliceFacade.h"
34 
35 #include <algorithm>
36 #include <set>
37 #include <sstream>
38 #include <limits>
39 #include <fstream>
40 #include <map>
41 
42 // Computations and data structures on lattices.
43 // Support for LatticeAnalyzeAction.
44 
45 #include <iostream>
46 
47 // wrapped in do .. while(false) to make it act like a single statement.
48 #define CHECK(X) \
49  do { \
50  if (!(X)) { \
51  cout << "Check condition on line " \
52  << __LINE__ << " of file " << __FILE__ \
53  << " not satisfied:\n "#X << endl; \
54  exit(1); \
55  } \
56  } while (false)
57 
63 };
64 
65 char getPlaceCode(NeighborPlace place);
66 
67 class Mlfb;
68 
69 struct SeqPos {
70  SeqPos();
71  SeqPos(const Mlfb* mlfb, size_t nextFacet, size_t previousFacet);
72  size_t getForwardFacet() const;
73  size_t getBackFacet() const;
74  SeqPos getReverse() const;
75  void order();
76  bool operator<(const SeqPos& pos) const;
77 
78  const Mlfb* mlfb;
79  size_t fixFacet1;
80  size_t fixFacet2;
82 };
83 
84 class GrobLat;
85 
86 class Neighbor {
87  public:
88  Neighbor(); // invalid
89  Neighbor(const GrobLat& lat); // zero
90  Neighbor(const GrobLat& lat, const size_t row); // row of lat
91 
92  Neighbor& operator=(const Neighbor& neighbor) {
93  _lat = neighbor._lat;
94  _row = neighbor._row;
95  return *this;
96  }
97 
98  bool operator==(const Neighbor& neighbor) const {
99  return _lat == neighbor._lat && getRow() == neighbor.getRow();
100  }
101 
102  const mpq_class& getH(size_t i) const;
103  size_t getHDim() const;
104 
105  const mpq_class& getY(size_t i) const;
106  size_t getYDim() const;
107 
108  size_t getRow() const {return _row;}
109 
110  bool isZero() const;
111  bool isValid() const;
112  bool isSpecial() const;
113  bool isGenerator() const;
114 
115  string getName() const;
116  const GrobLat& getGrobLat() const {return *_lat;}
117 
118  private:
119  const GrobLat* _lat;
120  size_t _row;
121 };
122 
124 class GrobLat {
125  public:
126  GrobLat(const Matrix& matrix, const SatBinomIdeal& ideal);
127 
128  Neighbor getNeighbor(size_t row) const {
129  ASSERT(row < getNeighborCount());
130  return Neighbor(*this, row);
131  }
132 
133  size_t getNeighborCount() const {
135  return _y.getRowCount();
136  }
137 
138  const Matrix& getYMatrix() const {return _y;}
139  const Matrix& getHMatrix() const {return _h;}
140  const Matrix& getMatrix() const {return _mat;}
141 
142  const SatBinomIdeal& getIdeal() const {return _ideal;}
143 
145  vector<mpq_class> sum(getHDim());
146  for (size_t i = 0; i < getHDim(); ++i)
147  sum[i] = _h(a.getRow(), i) + _h(b.getRow(), i);
148  for (size_t row = 0; row < _h.getRowCount(); ++row) {
149  bool match = true;
150  for (size_t col = 0; col < _h.getColCount(); ++col)
151  if (sum[col] != _h(row, col))
152  match = false;
153  if (match)
154  return Neighbor(*this, row);
155  }
156  return Neighbor();
157  }
158 
159  Neighbor getSum(size_t a, size_t b) const {
160  vector<mpq_class> sum(getHDim());
161  for (size_t i = 0; i < getHDim(); ++i)
162  sum[i] = _h(a, i) + _h(b, i);
163  for (size_t row = 0; row < _h.getRowCount(); ++row) {
164  bool match = true;
165  for (size_t col = 0; col < _h.getColCount(); ++col)
166  if (sum[col] != _h(row, col))
167  match = false;
168  if (match)
169  return Neighbor(*this, row);
170  }
171  return Neighbor();
172  }
173 
174  size_t getYDim() const {
176  return _y.getColCount();
177  }
178 
179  size_t getHDim() const {
180  return _h.getColCount();
181  }
182 
183  bool hasZeroEntryY() const {
184  return _ideal.hasZeroEntry();
185  }
186 
187  void getInitialIdeal(BigIdeal& ideal) const {
188  _ideal.getInitialIdeal(ideal);
189  }
190 
191  bool isSum(Neighbor n) const {
192  ASSERT(n.isValid());
193  ASSERT(&n.getGrobLat() == this);
194  ASSERT(n.getRow() < _isSumRow.size());
195  return _isSumRow[n.getRow()];
196  }
197  const vector<Neighbor>& getNonSums() const {return _nonSums;}
198  const mpq_class& getZero() const {return _zero;} // todo: remove
199 
202  bool isPointFreeBody(Neighbor a, Neighbor b) const {
204  _ideal.getGenerator(b.getRow()));
205  }
206 
212  _ideal.getGenerator(c.getRow()));
213  }
214 
215  bool isInterior(Neighbor a, Neighbor b) const {
216  if (!isPointFreeBody(a, b))
217  return false;
218  for (size_t var = 1; var < a.getYDim(); ++var)
219  if (a.getY(var) <= 0 && b.getY(var) <= 0)
220  return false;
221  return true;
222  }
223 
224  private:
225  vector<bool> _isSumRow;
226  vector<Neighbor> _nonSums;
227 
228  Matrix _y; // rows are neighbors in y-space
229  Matrix _h; // rows are neighbors in h-space
230  Matrix _mat; // matrix that defines lattice
231  SatBinomIdeal _ideal; // other representation of _y, necessary for now
232  mpq_class _zero;
233 };
234 
235 class Tri {
236  public:
237  Tri(Neighbor a, Neighbor b, Neighbor sum,
238  const vector<Mlfb>& mlfbs, const GrobLat& lat);
239 
240  Neighbor getA() const {return _a;}
241  Neighbor getB() const {return _b;}
242  Neighbor getSum() const {return _sum;}
243  const vector<const Mlfb*>& getASideMlfbs() const {return _aSideMlfbs;}
244  const vector<const Mlfb*>& getBSideMlfbs() const {return _bSideMlfbs;}
245  const vector<Neighbor>& getNeighborsOnBoundary() const {return _boundary;}
246  const vector<Neighbor>& getNeighborsInInterior() const {return _interior;}
247 
248  private:
251  Neighbor _sum; // neighbor that is sum of a and b
252  vector<const Mlfb*> _aSideMlfbs; // MLFBs containing {0,a,sum}
253  vector<const Mlfb*> _bSideMlfbs; // MLFBs containing {0,b,sum}
254  vector<Neighbor> _interior; // neighbors on boundary of <0,a,b,sum>
255  vector<Neighbor> _boundary; // neighbors in interior of <0,a,b,sum>
256 };
257 
258 class Plane {
259  public:
261  const vector<Mlfb>& mlfbs, const GrobLat& lat):
262  tri(a, b, sum, mlfbs, lat) {}
263 
264  size_t getTypeCount(size_t type) const;
265  size_t getMaxType() const;
266  NeighborPlace getPlace(Neighbor neighbor) const;
267  bool inPlane(Neighbor neighbor) const;
268  bool isPivot(const Mlfb& mlfb) const;
269  bool isSidePivot(const Mlfb& mlfb) const;
270  bool isFlat(const Mlfb& mlfb) const;
271  bool is22(const Mlfb& mlfb) const;
272  size_t getType(const Mlfb& mlfb) const;
273 
274  bool hasFlat() const {
275  return getTypeCount(4) > 0;
276  }
277 
282 
283  map<size_t, size_t> typeCounts;
284  vector<NeighborPlace> neighborPlace;
285  vector<SeqPos> flatSeq;
286  vector<const Mlfb*> pivots;
287 };
288 
289 class Mlfb {
290  public:
291  size_t getMinInitialFacet() const {
292  return minInitialFacet;
293  }
294 
295  bool hasPoint(Neighbor n) const {
296  for (size_t i = 0; i < _points.size(); ++i)
297  if (_points[i] == n)
298  return true;
299  return false;
300  }
301 
302  Neighbor getPoint(size_t offset) const {
303  ASSERT(offset < getPointCount());
304  return _points[offset];
305  }
306 
307  size_t getPointCount() const {
308  return _points.size();
309  }
310 
311  bool operator==(const Mlfb& mlfb) const {
312  return _offset == mlfb._offset;
313  }
314 
315  size_t getOffset() const {
316  return _offset;
317  }
318 
319  const vector<mpz_class>& getRhs() const {
320  return _rhs;
321  }
322 
323  string getName() const {
324  ostringstream name;
325  name << 'm' << (getOffset() + 1);
326  return name.str();
327  }
328 
329  string getName(const Plane& plane) const {
330  if (plane.isPivot(*this))
331  return getName() + 'P';
332  if (plane.isFlat(*this))
333  return getName() + 'F';
334  return getName();
335  }
336 
337  Neighbor getHitsNeighbor(size_t indexParam) const {
338  ASSERT(indexParam < edgeHitsFacet.size());
339  return getPoint(getHitsFacet(indexParam));
340  }
341 
342  size_t getHitsFacet(size_t indexParam) const {
343  ASSERT(indexParam < edgeHitsFacet.size());
344  return edgeHitsFacet[indexParam];
345  }
346 
347  const Mlfb* getEdge(size_t indexParam) const {
348  ASSERT(indexParam < edges.size());
349  return edges[indexParam];
350  }
351 
352  Mlfb* getEdge(size_t indexParam) {
353  ASSERT(indexParam < edges.size());
354  return edges[indexParam];
355  }
356 
357  size_t getFacetOf(const Mlfb& adjacent) const {
358  for (size_t i = 0; i < 4; ++i)
359  if (*getEdge(i) == adjacent)
360  return i;
361  return 4;
362  }
363 
364  bool isParallelogram() const {
365  return _isParallelogram;
366  }
367 
368  mpq_class index;
369  mpz_class dotDegree;
370  vector<Mlfb*> edges;
371  vector<size_t> edgeHitsFacet;
373 
374  void reset(size_t offset, const vector<Neighbor>& points);
375 
376  private:
377  vector<mpz_class> _rhs;
378  vector<Neighbor> _points;
379  size_t _offset;
381 };
382 
383 class TriPlane {
384 public:
386  _a(a), _b(b), _c(c) {
387 
388  Matrix mat(2, 3);
389  for (size_t col = 0; col < 3; ++col) {
390  mat(0, col) = a.getH(col) - c.getH(col);
391  mat(1, col) = b.getH(col) - c.getH(col);
392  }
393 
394  nullSpace(_normal, mat);
396  _line = (_normal.getRowCount() != 1);
397  }
398 
399  bool isLine() const {
400  return _line;
401  }
402 
404  ASSERT(!isLine());
405  mpz_class dn = dotNormal(a);
406  return dn == 0 || dn == 1 || dn == -1;
407  }
408 
409  bool inPlane(Neighbor a) const {
410  return dotNormal(a) == 0;
411  }
412 
413  mpz_class dotNormal(Neighbor a) const {
414  mpz_class prod = 0;
415  for (size_t i = 0; i < 3; ++i)
416  prod += a.getH(i) * _normal(0, i);
417  return prod;
418  }
419 
420  bool isParallel(const TriPlane& plane) const {
421  ASSERT(!isLine());
422  ASSERT(!plane.isLine());
423  mpz_class da = plane.dotNormal(_a);
424  return plane.dotNormal(_b) == da && plane.dotNormal(_c) == da;
425  }
426 
427  bool isParallel(const Plane& plane) const {
428  ASSERT(!isLine());
429  return plane.nullSpaceBasis == getNormal();
430  }
431 
433  const Matrix& getNormal() const {
434  return _normal;
435  }
436 
437 private:
440  bool _line;
441 };
442 
443 void getThinPlanes(vector<TriPlane>& planes, const GrobLat& lat);
444 void checkPlanes(const vector<TriPlane>& thinPlanes,
445  const vector<Plane>& dtPlanes);
446 
447 size_t pushOutFacetPositive(size_t facetPushOut,
448  const vector<mpz_class>& rhs,
449  const GrobLat& lat);
450 
451 size_t pushOutFacetZero(const vector<mpz_class>& rhs, const GrobLat& lat);
452 
453 void computeMlfbs(vector<Mlfb>& mlfbs, const GrobLat& lat);
454 
455 
456 void computeSeqs(vector<vector<SeqPos> >& left,
457  vector<vector<SeqPos> >& right,
458  const vector<Mlfb>& mlfbs,
459  const Plane& plane);
460 
463 void computePivotSeqs(vector<vector<SeqPos> >& seqs, const Mlfb& pivot,
464  const Plane& plane);
465 
466 void checkSeqs(const vector<vector<SeqPos> >& left,
467  const vector<vector<SeqPos> >& right,
468  const Plane& plane,
469  const vector<Mlfb>& mlfbs);
470 void checkMiddle(const Plane& plane,
471  const vector<Mlfb>& mlfbs);
472 void checkDoubleTriangle(const Plane& plane,
473  const vector<Mlfb>& mlfbs);
474 void checkGraph(const vector<Mlfb>& mlfbs);
475 void checkGraphOnPlane(const Plane& plane,
476  const vector<Mlfb>& mlfbs);
477 
478 
481 void checkPivotSeqs(vector<vector<SeqPos> >& pivotSeqs,
482  const Plane& plane,
483  const vector<Mlfb>& mlfbs,
484  const vector<SeqPos>& flatSeq);
485 
486 void checkPlaneTri(const GrobLat& lat,
487  const vector<Mlfb>& mlfbs,
488  const vector<const Mlfb*>& pivots,
489  const Plane& plane);
490 
491 void computePlanes(vector<Plane>& planes,
492  const GrobLat& lat,
493  vector<Mlfb>& mlfbs);
494 
497 void setupPlaneCountsAndOrder(vector<Mlfb>& mlfbs,
498  const Plane& plane,
499  map<size_t, size_t>& typeCounts);
500 
501 bool disjointSeqs(const vector<SeqPos>& a, const vector<SeqPos>& b);
502 
506 void computePivots(vector<const Mlfb*>& pivots,
507  const vector<Mlfb>& mlfbs,
508  const Plane& plane,
509  const vector<SeqPos>& flatSeq);
510 
511 void checkNonSums(const GrobLat& lat);
512 
513 void checkFlatSeq(const vector<SeqPos>& flatSeq,
514  const GrobLat& lat,
515  const Plane& plane);
516 
517 const char* getEdgePos(size_t index);
518 mpq_class getIndexSum(const vector<Mlfb>& mlfbs);
519 
520 void checkMlfbs(const vector<Mlfb>& mlfbs, const GrobLat& lat);
521 void checkDoubleTrianglePlanes(const vector<Plane>& planes,
522  const GrobLat& lat,
523  const vector<Mlfb>& mlfbs);
524 void checkPlane(const Plane& plane, const vector<Mlfb>& mlfbs);
525 
526 #endif
GrobLat::getMatrix
const Matrix & getMatrix() const
Definition: LatticeAlgs.h:140
Mlfb::dotDegree
mpz_class dotDegree
Definition: LatticeAlgs.h:369
Matrix
Definition: Matrix.h:26
GrobLat::GrobLat
GrobLat(const Matrix &matrix, const SatBinomIdeal &ideal)
Definition: LatticeAlgs.cpp:1533
nullSpace
void nullSpace(Matrix &basis, const Matrix &matParam)
Sets the columns of basis to a basis of the null space of mat.
Definition: Matrix.cpp:296
BigIdeal
Definition: BigIdeal.h:27
computePivots
void computePivots(vector< const Mlfb * > &pivots, const vector< Mlfb > &mlfbs, const Plane &plane, const vector< SeqPos > &flatSeq)
Put all pivots into pivots.
Definition: LatticeAlgs.cpp:746
DataType.h
Mlfb::minInitialFacet
size_t minInitialFacet
Definition: LatticeAlgs.h:372
SeqPos::getReverse
SeqPos getReverse() const
Definition: LatticeAlgs.cpp:1357
GrobLat::_mat
Matrix _mat
Definition: LatticeAlgs.h:230
NeighborPlace
NeighborPlace
Definition: LatticeAlgs.h:58
Plane::isPivot
bool isPivot(const Mlfb &mlfb) const
Definition: LatticeAlgs.cpp:1473
Neighbor::operator=
Neighbor & operator=(const Neighbor &neighbor)
Definition: LatticeAlgs.h:92
SeqPos
Definition: LatticeAlgs.h:69
SeqPos::comingFromFacet
size_t comingFromFacet
Definition: LatticeAlgs.h:81
Plane::getType
size_t getType(const Mlfb &mlfb) const
Definition: LatticeAlgs.cpp:1511
GrobLat::_y
Matrix _y
Definition: LatticeAlgs.h:228
IOHandler.h
computePlanes
void computePlanes(vector< Plane > &planes, const GrobLat &lat, vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:511
Mlfb::edgeHitsFacet
vector< size_t > edgeHitsFacet
Definition: LatticeAlgs.h:371
Mlfb::hasPoint
bool hasPoint(Neighbor n) const
Definition: LatticeAlgs.h:295
Neighbor
Definition: LatticeAlgs.h:86
Tri::getSum
Neighbor getSum() const
Definition: LatticeAlgs.h:242
getPlaceCode
char getPlaceCode(NeighborPlace place)
Definition: LatticeAlgs.cpp:135
Neighbor::getHDim
size_t getHDim() const
Definition: LatticeAlgs.cpp:1419
Tri::_b
Neighbor _b
Definition: LatticeAlgs.h:250
Plane::getPlace
NeighborPlace getPlace(Neighbor neighbor) const
Definition: LatticeAlgs.cpp:1462
SeqPos::order
void order()
Definition: LatticeAlgs.cpp:1369
GrobLat::isInterior
bool isInterior(Neighbor a, Neighbor b) const
Definition: LatticeAlgs.h:215
Neighbor::getName
string getName() const
Definition: LatticeAlgs.cpp:1519
checkPivotSeqs
void checkPivotSeqs(vector< vector< SeqPos > > &pivotSeqs, const Plane &plane, const vector< Mlfb > &mlfbs, const vector< SeqPos > &flatSeq)
Perform checks where pivotSeqs are the 3 non-flat sequences on one side.
Definition: LatticeAlgs.cpp:1092
Neighbor::_lat
const GrobLat * _lat
Definition: LatticeAlgs.h:119
checkPlane
void checkPlane(const Plane &plane, const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:714
checkDoubleTrianglePlanes
void checkDoubleTrianglePlanes(const vector< Plane > &planes, const GrobLat &lat, const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:649
GrobLat::_isSumRow
vector< bool > _isSumRow
Definition: LatticeAlgs.h:225
Tri::getB
Neighbor getB() const
Definition: LatticeAlgs.h:241
Mlfb::index
mpq_class index
Definition: LatticeAlgs.h:368
Mlfb::reset
void reset(size_t offset, const vector< Neighbor > &points)
Definition: LatticeAlgs.cpp:202
Mlfb
Definition: LatticeAlgs.h:289
BigTermRecorder.h
Mlfb::_rhs
vector< mpz_class > _rhs
Definition: LatticeAlgs.h:377
SeqPos::operator<
bool operator<(const SeqPos &pos) const
Definition: LatticeAlgs.cpp:1374
DebugStrategy.h
GrobLat::isPointFreeBody
bool isPointFreeBody(Neighbor a, Neighbor b, Neighbor c) const
Returns true if the smallest body containing zero, a, b and c has no neighbor in its interior.
Definition: LatticeAlgs.h:209
Matrix::getColCount
size_t getColCount() const
Definition: Matrix.h:31
Neighbor::_row
size_t _row
Definition: LatticeAlgs.h:120
Neighbor::Neighbor
Neighbor()
Definition: LatticeAlgs.cpp:1398
Tri::getASideMlfbs
const vector< const Mlfb * > & getASideMlfbs() const
Definition: LatticeAlgs.h:243
Matrix.h
GrobLat::getNeighbor
Neighbor getNeighbor(size_t row) const
Definition: LatticeAlgs.h:128
Mlfb::getOffset
size_t getOffset() const
Definition: LatticeAlgs.h:315
GrobLat::getIdeal
const SatBinomIdeal & getIdeal() const
Definition: LatticeAlgs.h:142
Plane::pivots
vector< const Mlfb * > pivots
Definition: LatticeAlgs.h:286
getIndexSum
mpq_class getIndexSum(const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:1321
checkGraphOnPlane
void checkGraphOnPlane(const Plane &plane, const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:1017
GrobLat::getSum
Neighbor getSum(size_t a, size_t b) const
Definition: LatticeAlgs.h:159
TriPlane::inPlane
bool inPlane(Neighbor a) const
Definition: LatticeAlgs.h:409
GrobLat::getYDim
size_t getYDim() const
Definition: LatticeAlgs.h:174
GrobLat::hasZeroEntryY
bool hasZeroEntryY() const
Definition: LatticeAlgs.h:183
Mlfb::getHitsFacet
size_t getHitsFacet(size_t indexParam) const
Definition: LatticeAlgs.h:342
checkPlaneTri
void checkPlaneTri(const GrobLat &lat, const vector< Mlfb > &mlfbs, const vector< const Mlfb * > &pivots, const Plane &plane)
Definition: LatticeAlgs.cpp:1259
Neighbor::getYDim
size_t getYDim() const
Definition: LatticeAlgs.cpp:1433
Neighbor::getH
const mpq_class & getH(size_t i) const
Definition: LatticeAlgs.cpp:1410
Tri::getNeighborsOnBoundary
const vector< Neighbor > & getNeighborsOnBoundary() const
Definition: LatticeAlgs.h:245
TriPlane::_line
bool _line
Definition: LatticeAlgs.h:440
Plane::isFlat
bool isFlat(const Mlfb &mlfb) const
Definition: LatticeAlgs.cpp:1492
checkSeqs
void checkSeqs(const vector< vector< SeqPos > > &left, const vector< vector< SeqPos > > &right, const Plane &plane, const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:966
setupPlaneCountsAndOrder
void setupPlaneCountsAndOrder(vector< Mlfb > &mlfbs, const Plane &plane, map< size_t, size_t > &typeCounts)
Set the plane vertex count for each mlfb and count how many MLFBs have each possible number of vertic...
Mlfb::getPointCount
size_t getPointCount() const
Definition: LatticeAlgs.h:307
checkNonSums
void checkNonSums(const GrobLat &lat)
Definition: LatticeAlgs.cpp:1157
TriPlane::_c
Neighbor _c
Definition: LatticeAlgs.h:438
GrobLat::getNonSums
const vector< Neighbor > & getNonSums() const
Definition: LatticeAlgs.h:197
checkMiddle
void checkMiddle(const Plane &plane, const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:985
computePivotSeqs
void computePivotSeqs(vector< vector< SeqPos > > &seqs, const Mlfb &pivot, const Plane &plane)
Starting at pivot (which must be a pivot), follow the three non-flat sequences starting at pivot.
Definition: LatticeAlgs.cpp:881
Mlfb::getFacetOf
size_t getFacetOf(const Mlfb &adjacent) const
Definition: LatticeAlgs.h:357
Plane::getTypeCount
size_t getTypeCount(size_t type) const
Definition: LatticeAlgs.cpp:1447
checkDoubleTriangle
void checkDoubleTriangle(const Plane &plane, const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:1043
checkGraph
void checkGraph(const vector< Mlfb > &mlfbs)
Definition: LatticeAlgs.cpp:1060
GrobLat::_zero
mpq_class _zero
Definition: LatticeAlgs.h:232
getEdgePos
const char * getEdgePos(size_t index)
Definition: LatticeAlgs.cpp:1310
SatBinomIdeal::getVarCount
size_t getVarCount() const
Definition: SatBinomIdeal.cpp:72
Scanner.h
Tri::getA
Neighbor getA() const
Definition: LatticeAlgs.h:240
GrobLat::getSum
Neighbor getSum(Neighbor a, Neighbor b) const
Definition: LatticeAlgs.h:144
Mlfb::getRhs
const vector< mpz_class > & getRhs() const
Definition: LatticeAlgs.h:319
SeqPos::getBackFacet
size_t getBackFacet() const
Definition: LatticeAlgs.cpp:1353
Neighbor::isGenerator
bool isGenerator() const
Definition: LatticeAlgs.cpp:1504
GrobLat
A lattice with associated Grobner basis/neighbors.
Definition: LatticeAlgs.h:124
GrobLat::isPointFreeBody
bool isPointFreeBody(Neighbor a, Neighbor b) const
Returns true if the smallest body containing zero, a and b has no neighbor in its interior.
Definition: LatticeAlgs.h:202
Neighbor::isSpecial
bool isSpecial() const
Definition: LatticeAlgs.cpp:1496
SeqPos::fixFacet1
size_t fixFacet1
Definition: LatticeAlgs.h:79
TriPlane::dotNormal
mpz_class dotNormal(Neighbor a) const
Definition: LatticeAlgs.h:413
TriPlane
Definition: LatticeAlgs.h:383
Mlfb::operator==
bool operator==(const Mlfb &mlfb) const
Definition: LatticeAlgs.h:311
Matrix::getRowCount
size_t getRowCount() const
Definition: Matrix.h:30
Neighbor::getRow
size_t getRow() const
Definition: LatticeAlgs.h:108
computeSeqs
void computeSeqs(vector< vector< SeqPos > > &left, vector< vector< SeqPos > > &right, const vector< Mlfb > &mlfbs, const Plane &plane)
Definition: LatticeAlgs.cpp:769
Neighbor::isValid
bool isValid() const
Definition: LatticeAlgs.cpp:1443
checkPlanes
void checkPlanes(const vector< TriPlane > &thinPlanes, const vector< Plane > &dtPlanes)
Definition: LatticeAlgs.cpp:99
Mlfb::getName
string getName() const
Definition: LatticeAlgs.h:323
SeqPos::getForwardFacet
size_t getForwardFacet() const
Definition: LatticeAlgs.cpp:1345
SliceFacade.h
computeMlfbs
void computeMlfbs(vector< Mlfb > &mlfbs, const GrobLat &lat)
Definition: LatticeAlgs.cpp:239
Tri::_sum
Neighbor _sum
Definition: LatticeAlgs.h:251
TriPlane::isLine
bool isLine() const
Definition: LatticeAlgs.h:399
SatBinomIdeal
Represents a saturated binomial ideal.
Definition: SatBinomIdeal.h:28
GrobLat::getHMatrix
const Matrix & getHMatrix() const
Definition: LatticeAlgs.h:139
SeqPos::mlfb
const Mlfb * mlfb
Definition: LatticeAlgs.h:78
Tri::getNeighborsInInterior
const vector< Neighbor > & getNeighborsInInterior() const
Definition: LatticeAlgs.h:246
Mlfb::_points
vector< Neighbor > _points
Definition: LatticeAlgs.h:378
TriPlane::TriPlane
TriPlane(Neighbor a, Neighbor b, Neighbor c)
Definition: LatticeAlgs.h:385
pushOutFacetPositive
size_t pushOutFacetPositive(size_t facetPushOut, const vector< mpz_class > &rhs, const GrobLat &lat)
Definition: LatticeAlgs.cpp:145
InPlane
@ InPlane
Definition: LatticeAlgs.h:59
Tri::_boundary
vector< Neighbor > _boundary
Definition: LatticeAlgs.h:255
MsmStrategy.h
Mlfb::isParallelogram
bool isParallelogram() const
Definition: LatticeAlgs.h:364
Mlfb::_offset
size_t _offset
Definition: LatticeAlgs.h:379
GrobLat::getYMatrix
const Matrix & getYMatrix() const
Definition: LatticeAlgs.h:138
GrobLat::isSum
bool isSum(Neighbor n) const
Definition: LatticeAlgs.h:191
Tri
Definition: LatticeAlgs.h:235
Mlfb::getHitsNeighbor
Neighbor getHitsNeighbor(size_t indexParam) const
Definition: LatticeAlgs.h:337
Neighbor::getGrobLat
const GrobLat & getGrobLat() const
Definition: LatticeAlgs.h:116
SliceParams.h
transpose
void transpose(Matrix &trans, const Matrix &mat)
Sets trans to the transpose of mat.
Definition: Matrix.cpp:129
IOFacade.h
Neighbor::getY
const mpq_class & getY(size_t i) const
Definition: LatticeAlgs.cpp:1424
TriPlane::getNormal
const Matrix & getNormal() const
returns the normal of the plane as the row of a matrix.
Definition: LatticeAlgs.h:433
SeqPos::SeqPos
SeqPos()
Definition: LatticeAlgs.cpp:1328
GrobLat::getHDim
size_t getHDim() const
Definition: LatticeAlgs.h:179
Plane::flatIntervalCount
size_t flatIntervalCount
Definition: LatticeAlgs.h:281
Mlfb::getEdge
Mlfb * getEdge(size_t indexParam)
Definition: LatticeAlgs.h:352
SatBinomIdeal::getInitialIdeal
void getInitialIdeal(BigIdeal &ideal) const
Definition: SatBinomIdeal.cpp:117
Neighbor::isZero
bool isZero() const
Definition: LatticeAlgs.cpp:1438
Plane::inPlane
bool inPlane(Neighbor neighbor) const
Definition: LatticeAlgs.cpp:1469
SeqPos::fixFacet2
size_t fixFacet2
Definition: LatticeAlgs.h:80
getThinPlanes
void getThinPlanes(vector< TriPlane > &planes, const GrobLat &lat)
Definition: LatticeAlgs.cpp:22
TranslatingTermConsumer.h
SatBinomIdeal::isPointFreeBody
bool isPointFreeBody(const vector< mpz_class > &a, const vector< mpz_class > &b) const
Returns true if the smallest body containing zero, a and b has no generator in its interior.
Definition: SatBinomIdeal.cpp:175
TermTranslator.h
GrobLat::getNeighborCount
size_t getNeighborCount() const
Definition: LatticeAlgs.h:133
Plane::tri
Tri tri
Definition: LatticeAlgs.h:279
Tri::Tri
Tri(Neighbor a, Neighbor b, Neighbor sum, const vector< Mlfb > &mlfbs, const GrobLat &lat)
Definition: LatticeAlgs.cpp:567
GrobLat::getInitialIdeal
void getInitialIdeal(BigIdeal &ideal) const
Definition: LatticeAlgs.h:187
TriPlane::_normal
Matrix _normal
Definition: LatticeAlgs.h:439
Plane::getMaxType
size_t getMaxType() const
Definition: LatticeAlgs.cpp:1455
Plane
Definition: LatticeAlgs.h:258
GrobLat::getZero
const mpq_class & getZero() const
Definition: LatticeAlgs.h:198
Tri::_aSideMlfbs
vector< const Mlfb * > _aSideMlfbs
Definition: LatticeAlgs.h:252
TriPlane::isParallel
bool isParallel(const Plane &plane) const
Definition: LatticeAlgs.h:427
Tri::_a
Neighbor _a
Definition: LatticeAlgs.h:249
Plane::isSidePivot
bool isSidePivot(const Mlfb &mlfb) const
Definition: LatticeAlgs.cpp:1478
TriPlane::_b
Neighbor _b
Definition: LatticeAlgs.h:438
Mlfb::edges
vector< Mlfb * > edges
Definition: LatticeAlgs.h:370
checkMlfbs
void checkMlfbs(const vector< Mlfb > &mlfbs, const GrobLat &lat)
Definition: LatticeAlgs.cpp:642
Mlfb::getEdge
const Mlfb * getEdge(size_t indexParam) const
Definition: LatticeAlgs.h:347
Plane::hasFlat
bool hasFlat() const
Definition: LatticeAlgs.h:274
Mlfb::getName
string getName(const Plane &plane) const
Definition: LatticeAlgs.h:329
SatBinomIdeal::getGenerator
const vector< mpz_class > & getGenerator(size_t index) const
Definition: SatBinomIdeal.cpp:39
ASSERT
#define ASSERT(X)
Definition: stdinc.h:85
Plane::Plane
Plane(Neighbor a, Neighbor b, Neighbor sum, const vector< Mlfb > &mlfbs, const GrobLat &lat)
Definition: LatticeAlgs.h:260
Neighbor::operator==
bool operator==(const Neighbor &neighbor) const
Definition: LatticeAlgs.h:98
Plane::is22
bool is22(const Mlfb &mlfb) const
Definition: LatticeAlgs.cpp:1487
Mlfb::_isParallelogram
bool _isParallelogram
Definition: LatticeAlgs.h:380
GrobLat::_ideal
SatBinomIdeal _ideal
Definition: LatticeAlgs.h:231
Tri::_interior
vector< Neighbor > _interior
Definition: LatticeAlgs.h:254
TriPlane::isParallel
bool isParallel(const TriPlane &plane) const
Definition: LatticeAlgs.h:420
Tri::getBSideMlfbs
const vector< const Mlfb * > & getBSideMlfbs() const
Definition: LatticeAlgs.h:244
UnderPlane
@ UnderPlane
Definition: LatticeAlgs.h:60
OverPlane
@ OverPlane
Definition: LatticeAlgs.h:61
TriPlane::closeToPlane
bool closeToPlane(Neighbor a)
Definition: LatticeAlgs.h:403
Plane::nullSpaceBasis
Matrix nullSpaceBasis
Definition: LatticeAlgs.h:278
Plane::typeCounts
map< size_t, size_t > typeCounts
Definition: LatticeAlgs.h:283
BigIdeal.h
Plane::rowAB
Matrix rowAB
Definition: LatticeAlgs.h:280
TriPlane::_a
Neighbor _a
Definition: LatticeAlgs.h:438
SatBinomIdeal::hasZeroEntry
bool hasZeroEntry() const
Returns true if any generator does not involve every variable, i.e.
Definition: SatBinomIdeal.cpp:140
GrobLat::_nonSums
vector< Neighbor > _nonSums
Definition: LatticeAlgs.h:226
disjointSeqs
bool disjointSeqs(const vector< SeqPos > &a, const vector< SeqPos > &b)
Definition: LatticeAlgs.cpp:738
pushOutFacetZero
size_t pushOutFacetZero(const vector< mpz_class > &rhs, const GrobLat &lat)
Definition: LatticeAlgs.cpp:170
checkFlatSeq
void checkFlatSeq(const vector< SeqPos > &flatSeq, const GrobLat &lat, const Plane &plane)
Definition: LatticeAlgs.cpp:1180
NoPlace
@ NoPlace
Definition: LatticeAlgs.h:62
Tri::_bSideMlfbs
vector< const Mlfb * > _bSideMlfbs
Definition: LatticeAlgs.h:253
Plane::neighborPlace
vector< NeighborPlace > neighborPlace
Definition: LatticeAlgs.h:284
SatBinomIdeal.h
Plane::flatSeq
vector< SeqPos > flatSeq
Definition: LatticeAlgs.h:285
GrobLat::_h
Matrix _h
Definition: LatticeAlgs.h:229
Mlfb::getPoint
Neighbor getPoint(size_t offset) const
Definition: LatticeAlgs.h:302
Mlfb::getMinInitialFacet
size_t getMinInitialFacet() const
Definition: LatticeAlgs.h:291