17#ifndef LATTICE_ALGS_GUARD
18#define LATTICE_ALGS_GUARD
20#include "SatBinomIdeal.h"
26#include "MsmStrategy.h"
27#include "TermTranslator.h"
28#include "TranslatingTermConsumer.h"
29#include "DebugStrategy.h"
31#include "BigTermRecorder.h"
32#include "SliceParams.h"
33#include "SliceFacade.h"
51 cout << "Check condition on line " \
52 << __LINE__ << " of file " << __FILE__ \
53 << " not satisfied:\n "#X << endl; \
65char getPlaceCode(NeighborPlace place);
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;
76 bool operator<(
const SeqPos& pos)
const;
81 size_t comingFromFacet;
90 Neighbor(
const GrobLat& lat,
const size_t row);
91 Neighbor(
const Neighbor&) =
default;
93 Neighbor& operator=(
const Neighbor& neighbor) {
99 bool operator==(
const Neighbor& neighbor)
const {
100 return _lat == neighbor._lat && getRow() == neighbor.getRow();
103 const mpq_class& getH(
size_t i)
const;
104 size_t getHDim()
const;
106 const mpq_class& getY(
size_t i)
const;
107 size_t getYDim()
const;
109 size_t getRow()
const {
return _row;}
112 bool isValid()
const;
113 bool isSpecial()
const;
114 bool isGenerator()
const;
116 string getName()
const;
117 const GrobLat& getGrobLat()
const {
return *_lat;}
129 Neighbor getNeighbor(
size_t row)
const {
130 ASSERT(row < getNeighborCount());
134 size_t getNeighborCount()
const {
135 ASSERT(_h.getRowCount() == _y.getRowCount());
136 return _y.getRowCount();
139 const Matrix& getYMatrix()
const {
return _y;}
140 const Matrix& getHMatrix()
const {
return _h;}
141 const Matrix& getMatrix()
const {
return _mat;}
146 vector<mpq_class> sum(getHDim());
147 for (
size_t i = 0; i < getHDim(); ++i)
148 sum[i] = _h(a.getRow(), i) + _h(b.getRow(), i);
149 for (
size_t row = 0; row < _h.getRowCount(); ++row) {
151 for (
size_t col = 0; col < _h.getColCount(); ++col)
152 if (sum[col] != _h(row, col))
160 Neighbor getSum(
size_t a,
size_t b)
const {
161 vector<mpq_class> sum(getHDim());
162 for (
size_t i = 0; i < getHDim(); ++i)
163 sum[i] = _h(a, i) + _h(b, i);
164 for (
size_t row = 0; row < _h.getRowCount(); ++row) {
166 for (
size_t col = 0; col < _h.getColCount(); ++col)
167 if (sum[col] != _h(row, col))
175 size_t getYDim()
const {
176 ASSERT(_y.getColCount() == _ideal.getVarCount());
177 return _y.getColCount();
180 size_t getHDim()
const {
181 return _h.getColCount();
184 bool hasZeroEntryY()
const {
185 return _ideal.hasZeroEntry();
188 void getInitialIdeal(
BigIdeal& ideal)
const {
189 _ideal.getInitialIdeal(ideal);
194 ASSERT(&n.getGrobLat() ==
this);
195 ASSERT(n.getRow() < _isSumRow.size());
196 return _isSumRow[n.getRow()];
198 const vector<Neighbor>& getNonSums()
const {
return _nonSums;}
199 const mpq_class& getZero()
const {
return _zero;}
204 return _ideal.isPointFreeBody(_ideal.getGenerator(a.getRow()),
205 _ideal.getGenerator(b.getRow()));
211 return _ideal.isPointFreeBody(_ideal.getGenerator(a.getRow()),
212 _ideal.getGenerator(b.getRow()),
213 _ideal.getGenerator(c.getRow()));
219 for (
size_t var = 1; var < a.getYDim(); ++var)
220 if (a.getY(var) <= 0 && b.getY(var) <= 0)
226 vector<bool> _isSumRow;
227 vector<Neighbor> _nonSums;
232 SatBinomIdeal _ideal;
239 const vector<Mlfb>& mlfbs,
const GrobLat& lat);
243 Neighbor getSum()
const {
return _sum;}
244 const vector<const Mlfb*>& getASideMlfbs()
const {
return _aSideMlfbs;}
245 const vector<const Mlfb*>& getBSideMlfbs()
const {
return _bSideMlfbs;}
246 const vector<Neighbor>& getNeighborsOnBoundary()
const {
return _boundary;}
247 const vector<Neighbor>& getNeighborsInInterior()
const {
return _interior;}
253 vector<const Mlfb*> _aSideMlfbs;
254 vector<const Mlfb*> _bSideMlfbs;
255 vector<Neighbor> _interior;
256 vector<Neighbor> _boundary;
262 const vector<Mlfb>& mlfbs,
const GrobLat& lat):
263 tri(a, b, sum, mlfbs, lat) {}
265 size_t getTypeCount(
size_t type)
const;
266 size_t getMaxType()
const;
267 NeighborPlace getPlace(
Neighbor neighbor)
const;
268 bool inPlane(
Neighbor neighbor)
const;
269 bool isPivot(
const Mlfb& mlfb)
const;
270 bool isSidePivot(
const Mlfb& mlfb)
const;
271 bool isFlat(
const Mlfb& mlfb)
const;
272 bool is22(
const Mlfb& mlfb)
const;
273 size_t getType(
const Mlfb& mlfb)
const;
275 bool hasFlat()
const {
276 return getTypeCount(4) > 0;
282 size_t flatIntervalCount;
284 map<size_t, size_t> typeCounts;
285 vector<NeighborPlace> neighborPlace;
286 vector<SeqPos> flatSeq;
287 vector<const Mlfb*> pivots;
292 size_t getMinInitialFacet()
const {
293 return minInitialFacet;
297 for (
size_t i = 0; i < _points.size(); ++i)
303 Neighbor getPoint(
size_t offset)
const {
304 ASSERT(offset < getPointCount());
305 return _points[offset];
308 size_t getPointCount()
const {
309 return _points.size();
312 bool operator==(
const Mlfb& mlfb)
const {
313 return _offset == mlfb._offset;
316 size_t getOffset()
const {
320 const vector<mpz_class>& getRhs()
const {
324 string getName()
const {
326 name <<
'm' << (getOffset() + 1);
330 string getName(
const Plane& plane)
const {
331 if (plane.isPivot(*
this))
332 return getName() +
'P';
333 if (plane.isFlat(*
this))
334 return getName() +
'F';
338 Neighbor getHitsNeighbor(
size_t indexParam)
const {
339 ASSERT(indexParam < edgeHitsFacet.size());
340 return getPoint(getHitsFacet(indexParam));
343 size_t getHitsFacet(
size_t indexParam)
const {
344 ASSERT(indexParam < edgeHitsFacet.size());
345 return edgeHitsFacet[indexParam];
348 const Mlfb* getEdge(
size_t indexParam)
const {
349 ASSERT(indexParam < edges.size());
350 return edges[indexParam];
353 Mlfb* getEdge(
size_t indexParam) {
354 ASSERT(indexParam < edges.size());
355 return edges[indexParam];
358 size_t getFacetOf(
const Mlfb& adjacent)
const {
359 for (
size_t i = 0; i < 4; ++i)
360 if (*getEdge(i) == adjacent)
365 bool isParallelogram()
const {
366 return _isParallelogram;
372 vector<size_t> edgeHitsFacet;
373 size_t minInitialFacet;
375 void reset(
size_t offset,
const vector<Neighbor>& points);
378 vector<mpz_class> _rhs;
379 vector<Neighbor> _points;
381 bool _isParallelogram;
387 _a(a), _b(b), _c(c) {
390 for (
size_t col = 0; col < 3; ++col) {
391 mat(0, col) = a.getH(col) - c.getH(col);
392 mat(1, col) = b.getH(col) - c.getH(col);
395 nullSpace(_normal, mat);
396 transpose(_normal, _normal);
397 _line = (_normal.getRowCount() != 1);
400 bool isLine()
const {
406 mpz_class dn = dotNormal(a);
407 return dn == 0 || dn == 1 || dn == -1;
411 return dotNormal(a) == 0;
414 mpz_class dotNormal(
Neighbor a)
const {
416 for (
size_t i = 0; i < 3; ++i)
417 prod += a.getH(i) * _normal(0, i);
421 bool isParallel(
const TriPlane& plane)
const {
423 ASSERT(!plane.isLine());
424 mpz_class da = plane.dotNormal(_a);
425 return plane.dotNormal(_b) == da && plane.dotNormal(_c) == da;
428 bool isParallel(
const Plane& plane)
const {
430 return plane.nullSpaceBasis ==
getNormal();
444void getThinPlanes(vector<TriPlane>& planes,
const GrobLat& lat);
445void checkPlanes(
const vector<TriPlane>& thinPlanes,
446 const vector<Plane>& dtPlanes);
448size_t pushOutFacetPositive(
size_t facetPushOut,
449 const vector<mpz_class>& rhs,
452size_t pushOutFacetZero(
const vector<mpz_class>& rhs,
const GrobLat& lat);
454void computeMlfbs(vector<Mlfb>& mlfbs,
const GrobLat& lat);
457void computeSeqs(vector<vector<SeqPos> >& left,
458 vector<vector<SeqPos> >& right,
459 const vector<Mlfb>& mlfbs,
464void computePivotSeqs(vector<vector<SeqPos> >& seqs,
const Mlfb& pivot,
467void checkSeqs(
const vector<vector<SeqPos> >& left,
468 const vector<vector<SeqPos> >& right,
470 const vector<Mlfb>& mlfbs);
471void checkMiddle(
const Plane& plane,
472 const vector<Mlfb>& mlfbs);
473void checkDoubleTriangle(
const Plane& plane,
474 const vector<Mlfb>& mlfbs);
475void checkGraph(
const vector<Mlfb>& mlfbs);
476void checkGraphOnPlane(
const Plane& plane,
477 const vector<Mlfb>& mlfbs);
482void checkPivotSeqs(vector<vector<SeqPos> >& pivotSeqs,
484 const vector<Mlfb>& mlfbs,
485 const vector<SeqPos>& flatSeq);
487void checkPlaneTri(
const GrobLat& lat,
488 const vector<Mlfb>& mlfbs,
489 const vector<const Mlfb*>& pivots,
492void computePlanes(vector<Plane>& planes,
494 vector<Mlfb>& mlfbs);
498void setupPlaneCountsAndOrder(vector<Mlfb>& mlfbs,
500 map<size_t, size_t>& typeCounts);
502bool disjointSeqs(
const vector<SeqPos>& a,
const vector<SeqPos>& b);
507void computePivots(vector<const Mlfb*>& pivots,
508 const vector<Mlfb>& mlfbs,
510 const vector<SeqPos>& flatSeq);
512void checkNonSums(
const GrobLat& lat);
514void checkFlatSeq(
const vector<SeqPos>& flatSeq,
518const char* getEdgePos(
size_t index);
519mpq_class getIndexSum(
const vector<Mlfb>& mlfbs);
521void checkMlfbs(
const vector<Mlfb>& mlfbs,
const GrobLat& lat);
522void checkDoubleTrianglePlanes(
const vector<Plane>& planes,
524 const vector<Mlfb>& mlfbs);
525void checkPlane(
const Plane& plane,
const vector<Mlfb>& mlfbs);
Definition LatticeAlgs.h:125
bool isPointFreeBody(Neighbor a, Neighbor b, Neighbor c) const
Definition LatticeAlgs.h:210
bool isPointFreeBody(Neighbor a, Neighbor b) const
Definition LatticeAlgs.h:203
Definition LatticeAlgs.h:290
Definition LatticeAlgs.h:86
Definition LatticeAlgs.h:259
Represents a saturated binomial ideal.
Definition SatBinomIdeal.h:28
const Matrix & getNormal() const
returns the normal of the plane as the row of a matrix.
Definition LatticeAlgs.h:434
Definition LatticeAlgs.h:236