aGrUM  0.13.2
LpInterface_tpl.h
Go to the documentation of this file.
1 
2 /***************************************************************************
3  * Copyright (C) 2017 by Pierre-Henri WUILLEMIN and Christophe GONZALES *
4  * {prenom.nom}_at_lip6.fr *
5  * *
6  * This program is free software; you can redistribute it and/or modify *
7  * it under the terms of the GNU General Public License as published by *
8  * the Free Software Foundation; either version 2 of the License, or *
9  * (at your option) any later version. *
10  * *
11  * This program is distributed in the hope that it will be useful, *
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
14  * GNU General Public License for more details. *
15  * *
16  * You should have received a copy of the GNU General Public License *
17  * along with this program; if not, write to the *
18  * Free Software Foundation, Inc., *
19  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
20  ***************************************************************************/
21 
22 
23 #include "LpInterface.h"
24 
25 namespace gum {
26  namespace credal {
27  namespace lp {
32  LpCol::LpCol(unsigned int id) : __id(id) { GUM_CONSTRUCTOR(LpCol); }
33 
34  LpCol::LpCol(const LpCol& col) : __id(col.__id) { GUM_CONS_CPY(LpCol); }
35 
36  LpCol::~LpCol() { GUM_DESTRUCTOR(LpCol); }
37 
38  unsigned int LpCol::id() const { return __id; }
39 
40  bool LpCol::operator<(const LpCol& col) const { return (__id < col.id()); }
41 
42  bool LpCol::operator==(const LpCol& col) const { return (__id == col.id()); }
43 
44  bool LpCol::operator!=(const LpCol& col) const { return (__id != col.id()); }
45 
46  LpCol& LpCol::operator=(const LpCol& col) {
47  __id = col.__id;
48 
49  return *this;
50  }
51 
52  std::ostream& operator<<(std::ostream& out, const LpCol& col) {
53  out << col.toString();
54  return out;
55  }
56 
57  std::string LpCol::toString() const { return "V" + std::to_string(__id); }
58  } // namespace lp
59 
60  } // namespace credal
61 
63  operator()(const credal::lp::LpCol& key) const {
64  return (((Size)key.id()) * gum::HashFuncConst::gold) & _hash_mask;
65  }
66 
67  namespace credal {
68  namespace lp {
69 
75  __ileft(false), __imiddle(false), __iright(false), __lValue(0.),
76  __mValue(0.), __rValue(0.), __lCoeffs(new HashTable< LpCol, double >()),
77  __mCoeffs(new HashTable< LpCol, double >()),
78  __rCoeffs(new HashTable< LpCol, double >()) {
79  GUM_CONSTRUCTOR(LpExpr);
80  }
81 
82  LpExpr::LpExpr(const LpExpr& expr) :
83  __ileft(expr.__ileft), __imiddle(expr.__imiddle),
84  __iright(expr.__iright), __lValue(expr.__lValue),
85  __mValue(expr.__mValue), __rValue(expr.__rValue),
86  __lCoeffs(new HashTable< LpCol, double >(*expr.__lCoeffs)),
87  __mCoeffs(new HashTable< LpCol, double >(*expr.__mCoeffs)),
88  __rCoeffs(new HashTable< LpCol, double >(*expr.__rCoeffs)) {
89  GUM_CONS_CPY(LpExpr);
90  }
91 
92  LpExpr::LpExpr(const LpExpr& expr,
93  bool copyLeft,
94  bool copyMiddle,
95  bool copyRight) :
96  __ileft(false),
97  __imiddle(false), __iright(false), __lValue(0.), __mValue(0.),
98  __rValue(0.), __lCoeffs(nullptr), __mCoeffs(nullptr),
99  __rCoeffs(nullptr) {
100  if (copyLeft) {
102  __lValue = expr.__lValue;
103  __ileft = true;
104  } else
106 
107  if (copyMiddle) {
109  __mValue = expr.__mValue;
110  __imiddle = true;
111  } else
113 
114  if (copyRight) {
116  __rValue = expr.__rValue;
117  __iright = true;
118  } else
120 
121  GUM_CONS_CPY(LpExpr);
122  }
123 
125  __ileft(expr.__ileft), __imiddle(expr.__imiddle),
126  __iright(expr.__iright), __lValue(expr.__lValue),
127  __mValue(expr.__mValue), __rValue(expr.__rValue),
128  __lCoeffs(expr.__lCoeffs), __mCoeffs(expr.__mCoeffs),
129  __rCoeffs(expr.__rCoeffs) {
130  expr.__lCoeffs = nullptr;
131  expr.__mCoeffs = nullptr;
132  expr.__rCoeffs = nullptr;
133 
134  GUM_CONS_CPY(LpExpr);
135  }
136 
138  bool copyLeft,
139  bool copyMiddle,
140  bool copyRight) :
141  __ileft(false),
142  __imiddle(false), __iright(false), __lValue(0.), __mValue(0.),
143  __rValue(0.), __lCoeffs(nullptr), __mCoeffs(nullptr),
144  __rCoeffs(nullptr) {
145  if (copyLeft) {
146  swap(__lCoeffs, expr.__lCoeffs);
147  __lValue = expr.__lValue;
148  __ileft = true;
149  } else
151 
152  if (copyMiddle) {
153  swap(__mCoeffs, expr.__mCoeffs);
154  __mValue = expr.__mValue;
155  __imiddle = true;
156  } else
158 
159  if (copyRight) {
160  swap(__rCoeffs, expr.__rCoeffs);
161  __rValue = expr.__rValue;
162  __iright = true;
163  } else
165 
166  GUM_CONS_CPY(LpExpr);
167  }
168 
170  delete __lCoeffs;
171  delete __mCoeffs;
172  delete __rCoeffs;
173 
174  GUM_DESTRUCTOR(LpExpr);
175  }
176 
178  clear();
179 
180  __mCoeffs->insert(rhs, 1.);
181  __imiddle = true;
182 
183  return *this;
184  }
185 
188  if (this == &rhs) return *this;
189 
190  *__lCoeffs = *rhs.__lCoeffs;
191  *__mCoeffs = *rhs.__mCoeffs;
192  *__rCoeffs = *rhs.__rCoeffs;
193 
194  __lValue = rhs.__lValue;
195  __mValue = rhs.__mValue;
196  __rValue = rhs.__rValue;
197 
198  __ileft = rhs.__ileft;
199  __imiddle = rhs.__imiddle;
200  __iright = rhs.__iright;
201 
202  return *this;
203  }
204 
207  if (this == &rhs) return *this;
208 
209  swap(__lCoeffs, rhs.__lCoeffs);
210  swap(__mCoeffs, rhs.__mCoeffs);
211  swap(__rCoeffs, rhs.__rCoeffs);
212 
213  __lValue = rhs.__lValue;
214  __mValue = rhs.__mValue;
215  __rValue = rhs.__rValue;
216 
217  __ileft = rhs.__ileft;
218  __imiddle = rhs.__imiddle;
219  __iright = rhs.__iright;
220 
221  return *this;
222  }
223 
224  template < typename SCALAR >
225  LpExpr& LpExpr::operator=(const SCALAR& rhs) {
226  clear();
227 
228  __mValue = rhs;
229  __imiddle = true;
230 
231  return *this;
232  }
233 
235  if (__ileft || __iright)
237  "expr::operator+= (expr) : <= present on one side of expr");
238 
239  if (!__imiddle) __imiddle = true;
240 
241  __mCoeffs->getWithDefault(rhs, 0.) += 1.;
242 
243  return *this;
244  }
245 
247  if (__ileft || __iright || rhs.__ileft || rhs.__iright)
249  "expr::operator+= (rhs) : <= present "
250  "on one side of rhs and/or expr");
251 
252  if (!__imiddle) __imiddle = true;
253 
254  for (const auto& elt : *rhs.__mCoeffs)
255  __mCoeffs->getWithDefault(elt.first, 0.) += elt.second;
256 
257  __mValue += rhs.__mValue;
258 
259  return *this;
260  }
261 
263  if (__ileft || __iright || rhs.__ileft || rhs.__iright)
265  "expr::operator+= (rhs) : <= present "
266  "on one side of rhs and/or expr");
267 
268  if (!__imiddle) {
269  __imiddle = true;
270 
271  __mValue = rhs.__mValue;
272 
273  swap(__mCoeffs, rhs.__mCoeffs);
274 
275  return *this;
276  }
277 
278  for (const auto& elt : *rhs.__mCoeffs)
279  __mCoeffs->getWithDefault(elt.first, 0.) += elt.second;
280 
281  __mValue += rhs.__mValue;
282 
283  return *this;
284  }
285 
286  template < typename T >
287  LpExpr& LpExpr::operator+=(const T& rhs) {
288  if (__ileft || __iright)
290  "expr::operator+= (expr) : <= present on one side of expr");
291 
292  if (!__imiddle) __imiddle = true;
293 
294  __mValue += rhs;
295 
296  return *this;
297  }
298 
300  if (__ileft || __iright)
302  "expr::operator-= (rhs) : <= present in one of expr");
303 
304  if (!__imiddle) __imiddle = true;
305 
306  __mCoeffs->getWithDefault(rhs, 0.) -= 1.;
307 
308  return *this;
309  }
310 
312  if (__ileft || __iright || rhs.__ileft || rhs.__iright)
313  GUM_ERROR(
315  "expr::operator-= (rhs) : <= present in one of rhs and/or expr");
316 
317  if (!__imiddle) __imiddle = true;
318 
319  for (const auto& elt : *rhs.__mCoeffs)
320  __mCoeffs->getWithDefault(elt.first, 0.) -= elt.second;
321 
322  __mValue -= rhs.__mValue;
323 
324  return *this;
325  }
326 
327  template < typename T >
328  LpExpr& LpExpr::operator-=(const T& rhs) {
329  if (__ileft || __iright)
331  "expr::operator-= (rhs) : <= present in one of expr");
332 
333  if (!__imiddle) __imiddle = true;
334 
335  __mValue -= rhs;
336 
337  return *this;
338  }
339 
340  std::ostream& operator<<(std::ostream& out, const LpExpr& expr) {
341  out << expr.toString();
342  return out;
343  }
344 
345  void LpExpr::__addSide(const LpCol& from) {
346  if (!__ileft) {
347  __lCoeffs->insert(from, 1.);
348  __ileft = true;
349  } else if (!__imiddle) {
350  __mCoeffs->insert(from, 1.);
351  __imiddle = true;
352  } else if (!__iright) {
353  __rCoeffs->insert(from, 1.);
354  __iright = true;
355  } else
357  "LpExpr::setSide ( const LpCol & from "
358  ") : too many <= ; no free side");
359  }
360 
361  void LpExpr::__addSide(const LpExpr& from) {
362  if (__ileft && __iright && from.__imiddle)
364  "LpExpr::setSide ( const LpCol & from "
365  ") : too many <= ; no free side");
366 
368  if (!from.__imiddle) return;
369 
373  if (!from.__ileft && !from.__iright) {
374  if (!__ileft) {
375  *__lCoeffs = *from.__mCoeffs;
376  __lValue = from.__mValue;
377  __ileft = true;
378 
379  return;
380  } else if (!__imiddle) {
381  *__mCoeffs = *from.__mCoeffs;
382  __mValue = from.__mValue;
383  __imiddle = true;
384 
385  return;
386  } else if (!__iright) {
387  *__rCoeffs = *from.__mCoeffs;
388  __rValue = from.__mValue;
389  __iright = true;
390 
391  return;
392  } else
394  "LpExpr::setSide ( const LpCol & from ) "
395  ": too many <= ; no free side");
396  }
399  else if (from.__ileft && !from.__iright) {
400  if (!__ileft) {
401  *__lCoeffs = *from.__lCoeffs;
402  __lValue = from.__lValue;
403  __ileft = true;
404 
405  *__mCoeffs = *from.__mCoeffs;
406  __mValue = from.__mValue;
407  __imiddle = true;
408 
409  return;
410  } else if (!__imiddle && !__iright) {
411  *__mCoeffs = *from.__lCoeffs;
412  __mValue = from.__lValue;
413  __imiddle = true;
414 
415  *__rCoeffs = *from.__mCoeffs;
416  __rValue = from.__mValue;
417  __iright = true;
418 
419  return;
420  } else
422  "LpExpr::setSide ( const LpCol & from ) "
423  ": too many <= ; no free side");
424  }
427  else if (from.__ileft && from.__iright) {
428  if (__ileft || __imiddle || __iright)
430  "LpExpr::setSide ( const LpCol & from ) "
431  ": too many <= ; no free side");
432 
433  *this = from;
434 
435  return;
436  } else
438  "LpExpr::setSide ( const LpCol & from "
439  ") : too many <= ; no free side");
440  }
441 
442  void LpExpr::__addSide(LpExpr&& from) {
444  if (__ileft && __iright && from.__imiddle)
446  "LpExpr::setSide ( const LpCol & from "
447  ") : too many <= ; no free side");
448 
450  if (!from.__imiddle) return;
451 
455  if (!from.__ileft && !from.__iright) {
456  if (!__ileft) {
458  swap(__lCoeffs, from.__mCoeffs);
459  __lValue = from.__mValue;
460  __ileft = true;
461 
462  return;
463  } else if (!__imiddle) {
465  swap(__mCoeffs, from.__mCoeffs);
466  __mValue = from.__mValue;
467  __imiddle = true;
468 
469  return;
470  } else if (!__iright) {
472  swap(__rCoeffs, from.__mCoeffs);
473  __rValue = from.__mValue;
474  __iright = true;
475 
476  return;
477  } else
479  "LpExpr::setSide ( const LpCol & from ) "
480  ": too many <= ; no free side");
481  }
484  else if (from.__ileft && !from.__iright) {
485  if (!__ileft) {
487  swap(__lCoeffs, from.__lCoeffs);
488  __lValue = from.__lValue;
489  __ileft = true;
490 
492  swap(__mCoeffs, from.__mCoeffs);
493  __mValue = from.__mValue;
494  __imiddle = true;
495 
496  return;
497  } else if (!__imiddle && !__iright) {
499  swap(__mCoeffs, from.__lCoeffs);
500  __mValue = from.__lValue;
501  __imiddle = true;
502 
504  swap(__rCoeffs, from.__mCoeffs);
505  __rValue = from.__mValue;
506  __iright = true;
507 
508  return;
509  } else
511  "LpExpr::setSide ( const LpCol & from ) "
512  ": too many <= ; no free side");
513  }
516  else if (from.__ileft && from.__iright) {
517  if (__ileft || __imiddle || __iright)
519  "LpExpr::setSide ( const LpCol & from ) "
520  ": too many <= ; no free side");
521 
522  *this = std::move(from);
523 
524  return;
525  } else
527  "LpExpr::setSide ( const LpCol & from "
528  ") : too many <= ; no free side");
529  }
530 
531  template < typename SCALAR >
532  void LpExpr::__addSide(const SCALAR& from) {
533  if (!__ileft) {
534  __lValue = from;
535  __ileft = true;
536  } else if (!__imiddle) {
537  __mValue = from;
538  __imiddle = true;
539  } else if (!__iright) {
540  __rValue = from;
541  __iright = true;
542  } else
544  "LpExpr::setSide ( const LpCol & from "
545  ") : too many <= ; no free side");
546  }
547 
548  void LpExpr::clear() {
549  __lCoeffs->clear();
550  __mCoeffs->clear();
551  __rCoeffs->clear();
552 
553  __lValue = 0.;
554  __mValue = 0.;
555  __rValue = 0.;
556 
557  __ileft = false;
558  __imiddle = false;
559  __iright = false;
560  }
561 
562  std::string LpExpr::toString() const {
563  std::ostringstream s;
564 
565  s << std::endl << "left side : " << std::endl;
566 
567  if (__lCoeffs != nullptr)
568  for (const auto& elt : *__lCoeffs)
569  s << elt.first.toString() << " " << elt.second << " | ";
570 
571  s << std::endl << "middle side : " << std::endl;
572 
573  if (__mCoeffs != nullptr)
574  for (const auto& elt : *__mCoeffs)
575  s << elt.first.toString() << " " << elt.second << " | ";
576 
577  s << std::endl << "right side : " << std::endl;
578 
579  if (__rCoeffs != nullptr)
580  for (const auto& elt : *__rCoeffs)
581  s << elt.first.toString() << " " << elt.second << " | ";
582 
583  s << std::endl
584  << "lvalue : " << __lValue << std::endl
585  << "mvalue : " << __mValue << std::endl
586  << "rvalue : " << __rValue << std::endl;
587 
588  s << std::endl;
589 
590  return s.str();
591  }
592 
597  LpRow::LpRow(const LpExpr& expr, const std::vector< LpCol >& cols) :
598  __coeffs(nullptr) {
599  // we write 0 <= Ax + b from Ex + f <= Cx + d
600  if (expr.__ileft && !expr.__iright) {
602 
603  for (const auto& col : cols) {
604  double col_coeff = 0.;
605 
606  // from left side to middle side : 0 <= middle - left
607  if (expr.__lCoeffs->exists(col))
608  col_coeff = expr.__lCoeffs->operator[](col);
609 
610  __coeffs->getWithDefault(col, 0.) -= col_coeff;
611  }
612 
613  __cste = expr.__mValue - expr.__lValue;
614  } else if (expr.__iright && !expr.__ileft) {
616 
617  for (const auto& col : cols) {
618  double col_coeff = 0;
619 
620  // from middle side to right side : 0 <= right - middle
621  if (expr.__mCoeffs->exists(col))
622  col_coeff = expr.__mCoeffs->operator[](col);
623 
624  __coeffs->getWithDefault(col, 0.) -= col_coeff;
625  }
626 
627  __cste = expr.__rValue - expr.__mValue;
628  } else
630  "expr : " << expr.toString()
631  << "is not a valid inequality; no <= detected");
632 
633  if (__coeffs->size() == 0)
635  "expr : " << expr.toString()
636  << "is not a valid inequality; "
637  "no variable in inequality, "
638  "only constants");
639 
640  GUM_CONSTRUCTOR(LpRow);
641  }
642 
643  LpRow::LpRow(LpExpr&& expr, const std::vector< LpCol >& cols) :
644  __coeffs(nullptr) {
646  if (expr.__ileft && !expr.__iright) {
647  swap(__coeffs, expr.__mCoeffs);
648 
649  for (const auto& col : cols) {
650  double col_coeff = 0;
651 
652  if (expr.__lCoeffs->exists(col))
653  col_coeff = expr.__lCoeffs->operator[](col);
654 
655  __coeffs->getWithDefault(col, 0.) -= col_coeff;
656  }
657 
658  __cste = expr.__mValue - expr.__lValue;
659  } else if (expr.__iright && !expr.__ileft) {
660  swap(__coeffs, expr.__rCoeffs);
661 
662  for (const auto& col : cols) {
663  double col_coeff = 0;
664 
665  if (expr.__mCoeffs->exists(col))
666  col_coeff = expr.__mCoeffs->operator[](col);
667 
668  __coeffs->getWithDefault(col, 0.) -= col_coeff;
669  }
670 
671  __cste = expr.__rValue - expr.__mValue;
672  } else
674  "expr : " << expr.toString()
675  << "is not a valid inequality; no <= detected");
676 
677  if (__coeffs->size() == 0)
679  "expr : " << expr.toString()
680  << "is not a valid inequality; "
681  "no variable in inequality, "
682  "only constants");
683 
684  GUM_CONSTRUCTOR(LpRow);
685  }
686 
687  LpRow::LpRow(const LpRow& row) :
688  __cste(row.__cste),
689  __coeffs(new HashTable< LpCol, double >(*row.__coeffs)) {
690  GUM_CONS_CPY(LpRow);
691  }
692 
694  row.__coeffs = nullptr;
695 
696  GUM_CONS_CPY(LpRow);
697  }
698 
700  delete __coeffs;
701 
702  GUM_DESTRUCTOR(LpRow);
703  }
704 
705  LpRow& LpRow::operator=(const LpRow& row) {
706  __cste = row.__cste;
707  *__coeffs = *row.__coeffs;
708  return *this;
709  }
710 
712  __cste = row.__cste;
713  swap(__coeffs, row.__coeffs);
714  return *this;
715  }
716 
717  std::ostream& operator<<(std::ostream& out, const LpRow& row) {
718  out << row.toString();
719  return out;
720  }
721 
722  std::string LpRow::toString() const {
723  std::ostringstream s;
724 
725  s << "0 <= " << __cste;
726 
727  if (__coeffs != nullptr) {
728  for (const auto& elt : *__coeffs) {
729  if (elt.second > 0) {
730  if (elt.second != 1) {
731  s << " +" << elt.second << "*" << elt.first.toString();
732  } else {
733  s << " +" << elt.first.toString();
734  }
735  } else {
736  if (elt.second < 0) {
737  if (elt.second != -1) {
738  s << " " << elt.second << "*" << elt.first.toString();
739  } else {
740  s << " -" << elt.first.toString();
741  }
742  }
743  }
744  }
745  }
746 
747  return s.str();
748  }
749 
753  template < typename GUM_SCALAR >
755  __positivity = false;
756  __sumIsOne = false;
757  GUM_CONSTRUCTOR(LpInterface);
758  }
759 
760  template < typename GUM_SCALAR >
762  const LpInterface< GUM_SCALAR >& from) :
763  __cols(from.__cols),
764  __positivity(from.__positivity), __sumIsOne(from.__sumIsOne) {
765  __rows.resize(from.__rows.size());
766 
767  for (unsigned int i = 0, end = from.__rows.size(); i < end; i++)
768  __rows[i] = new LpRow(*from.__rows[i]);
769 
770  GUM_CONS_CPY(LpInterface);
771  }
772 
773  template < typename GUM_SCALAR >
776  __rows.swap(from.__rows);
777  __cols.swap(from.__cols);
778  GUM_CONS_CPY(LpInterface);
779  }
780 
781  template < typename GUM_SCALAR >
783  for (const auto row : __rows)
784  delete row;
785 
786  GUM_DESTRUCTOR(LpInterface);
787  }
788 
789  template < typename GUM_SCALAR >
793  for (const auto& row : __rows)
794  delete row;
795 
796  __rows.clear();
797  __rows.shrink_to_fit();
798 
799  __rows.resize(from.__rows.size());
800 
801  for (unsigned int i = 0, end = from.__rows.size(); i < end; i++)
802  __rows[i] = new LpRow(*from.__rows[i]);
803 
804  __cols = from.__cols;
805  __positivity = from.__positivity;
806  __sumIsOne = from.__sumIsOne;
807 
808  return *this;
809  }
810 
811  template < typename GUM_SCALAR >
814  __rows.swap(from.__rows);
815  __cols.swap(from.__cols);
816 
817  __positivity = from.__positivity;
818  __sumIsOne = from.__sumIsOne;
819 
820  return *this;
821  }
822 
823  template < typename T >
824  std::ostream& operator<<(std::ostream& out, const LpInterface< T >& lpi) {
825  out << lpi.toString();
826  return out;
827  }
828 
829  template < typename GUM_SCALAR >
831  LpCol col((unsigned int)__cols.size());
832 
833  __cols.push_back(col);
834 
835  return col;
836  }
837 
838  template < typename GUM_SCALAR >
839  std::vector< LpCol >
840  LpInterface< GUM_SCALAR >::addCols(const unsigned int& cols) {
841  if (cols < 1)
843  "LpInterface::addCols ( cols ) : cols "
844  "needs must be equal or greater than 1 : "
845  << cols << " < 1");
846 
847  for (unsigned int i = 0; i < cols; i++) {
848  __cols.push_back(LpCol((unsigned int)__cols.size()));
849  }
850 
851  return __cols;
852  }
853 
854  template < typename GUM_SCALAR >
856  if (!expr.__ileft && !expr.__iright)
858  "addRow ( const LpExpr & expr ) : expr : "
859  << expr.toString() << "is not an inequality.");
860 
861  if ((expr.__ileft && !expr.__iright) || (!expr.__ileft && expr.__iright)) {
862  __rows.push_back(new LpRow(expr, __cols));
863  } else {
864  LpExpr lexpr(expr, true, true, false);
865  LpExpr rexpr(expr, false, true, true);
866 
867  __rows.push_back(
868  new LpRow(std::move(lexpr),
869  __cols));
870  __rows.push_back(
871  new LpRow(std::move(rexpr),
872  __cols));
873  }
874  }
875 
876  template < typename GUM_SCALAR >
878  if (!expr.__ileft && !expr.__iright)
880  "addRow ( const LpExpr & expr ) : expr : "
881  << expr.toString() << "is not an inequality.");
882 
883  if ((expr.__ileft && !expr.__iright) || (!expr.__ileft && expr.__iright)) {
884  __rows.push_back(new LpRow(std::move(expr), __cols));
885  } else {
886  LpExpr lexpr(std::move(expr), true, true, false);
887 
889  LpExpr rexpr(std::move(expr), false, false, true);
890 
892 
893  *rexpr.__mCoeffs = *lexpr.__mCoeffs;
894  rexpr.__mValue = lexpr.__mValue;
895  rexpr.__imiddle = true;
896 
897  __rows.push_back(
898  new LpRow(std::move(lexpr),
899  __cols));
900  __rows.push_back(
901  new LpRow(std::move(rexpr),
902  __cols));
903  }
904  }
905 
906  template < typename GUM_SCALAR >
908  if (__positivity) return;
909 
910  for (const auto& col : __cols)
911  addRow(0 <= col);
912 
913  __positivity = true;
914  }
915 
916  template < typename GUM_SCALAR >
918  if (__sumIsOne) return;
919 
920  LpExpr expr;
921 
922  for (const auto& col : __cols)
923  expr += col;
924 
925  addRow(1 <= std::move(expr) <= 1);
926 
927  __sumIsOne = true;
928  }
929 
930  template < typename GUM_SCALAR >
932  if (__positivity && __sumIsOne) {
933  return;
934  } else if (__positivity && !__sumIsOne) {
935  addSumIsOne();
936  return;
937  } else if (!__positivity && __sumIsOne) {
938  addPositivity();
939  return;
940  }
941 
942  // we can do both with one loop, don't call the above functions.
943  // addPositivity();
944  // addSumIsOne();
945  LpExpr expr;
946 
947  for (const auto& col : __cols) {
948  addRow(0 <= col);
949  expr += col;
950  }
951 
952  addRow(1 <= std::move(expr) <= 1);
953 
954  __sumIsOne = true;
955  __positivity = true;
956  }
957 
958  template < typename GUM_SCALAR >
959  std::vector< std::vector< GUM_SCALAR > > LpInterface< GUM_SCALAR >::solve() {
961 
962  lrs.setUpH((unsigned int)__cols.size());
963 
964  std::vector< std::vector< GUM_SCALAR > > lrsMatrix;
965 
966  for (const auto& row : __rows) {
967  std::vector< GUM_SCALAR > expandedRow(__cols.size() + 1, 0);
968 
969  expandedRow[0] = row->__cste;
970 
971  for (const auto& elt : *row->__coeffs)
972  expandedRow[elt.first.id() + 1] = elt.second;
973 
974  lrsMatrix.push_back(expandedRow);
975  }
976 
977  lrs.fillMatrix(lrsMatrix);
978 
979  lrs.H2V();
980 
981  return lrs.getOutput();
982  }
983 
984  template < typename GUM_SCALAR >
985  std::vector< LpCol > LpInterface< GUM_SCALAR >::getCols() const {
986  return __cols;
987  }
988 
989  template < typename GUM_SCALAR >
991  std::ostringstream s;
992 
993  s << std::endl << std::endl << "Variables : " << std::endl;
994 
995  for (const auto& col : __cols)
996  s << " " << col.toString();
997 
998  s << std::endl;
999 
1000  for (const auto& row : __rows)
1001  s << std::endl << row->toString();
1002 
1003  s << std::endl << std::endl;
1004 
1005  return s.str();
1006  }
1007 
1008  template < typename GUM_SCALAR >
1010  for (const auto& row : __rows)
1011  delete row;
1012 
1013  __rows.clear();
1014  __rows.shrink_to_fit();
1015 
1019  __cols.clear();
1020  __cols.shrink_to_fit();
1021 
1022  __positivity = false;
1023  __sumIsOne = false;
1024  }
1025 
1026  template < typename GUM_SCALAR >
1028  for (const auto& row : __rows)
1029  delete row;
1030 
1031  __rows.clear();
1032  __rows.shrink_to_fit();
1033 
1034  __positivity = false;
1035  __sumIsOne = false;
1036  }
1037 
1041  a = b;
1042  b = tmp;
1043  }
1044 
1046  template < typename T2 >
1047  LpExpr operator+(LpExpr&& lhs, const T2& rhs) {
1048  LpExpr expr = std::move(lhs);
1049  expr += rhs;
1050 
1051  return expr;
1052  }
1053 
1054  template < typename T2 >
1055  LpExpr operator+(const LpExpr& lhs, const T2& rhs) {
1056  LpExpr expr(lhs);
1057  expr += rhs;
1058 
1059  return expr;
1060  }
1061 
1062  template < typename T1, forbidden_type< T1, LpExpr > >
1063  LpExpr operator+(const T1& lhs, LpExpr&& rhs) {
1064  LpExpr expr = std::move(rhs);
1065  ;
1066  expr += lhs;
1067 
1068  return expr;
1069  }
1070 
1071  template < typename T1, forbidden_type< T1, LpExpr > >
1072  LpExpr operator+(const T1& lhs, LpExpr& rhs) {
1073  LpExpr expr(rhs);
1074  expr += lhs;
1075 
1076  return expr;
1077  }
1078 
1079  template < typename T2, forbidden_type< T2, LpExpr > >
1080  LpExpr operator+(const LpCol& lhs, const T2& rhs) {
1081  LpExpr expr;
1082  expr += lhs;
1083  expr += rhs;
1084 
1085  return expr;
1086  }
1087 
1088  template < typename T1,
1091  LpExpr operator+(const T1& lhs, const LpCol& rhs) {
1092  LpExpr expr;
1093  expr += rhs;
1094  expr += lhs;
1095 
1096  return expr;
1097  }
1098 
1100  template < typename T2 >
1101  LpExpr operator-(LpExpr&& lhs, const T2& rhs) {
1102  LpExpr expr = std::move(lhs);
1103  expr -= rhs;
1104 
1105  return expr;
1106  }
1107 
1108  template < typename T2 >
1109  LpExpr operator-(const LpExpr& lhs, const T2& rhs) {
1110  LpExpr expr(lhs);
1111  expr -= rhs;
1112 
1113  return expr;
1114  }
1115 
1116  template < typename T1, forbidden_type< T1, LpExpr > >
1117  LpExpr operator-(const T1& lhs, LpExpr&& rhs) {
1118  LpExpr expr;
1119  expr += std::move(rhs);
1120  ;
1121  expr -= lhs;
1122 
1123  return expr;
1124  }
1125 
1126  template < typename T1, forbidden_type< T1, LpExpr > >
1127  LpExpr operator-(const T1& lhs, LpExpr& rhs) {
1128  LpExpr expr;
1129  expr += rhs;
1130  expr -= lhs;
1131 
1132  return expr;
1133  }
1134 
1135  template < typename T2, forbidden_type< T2, LpExpr > >
1136  LpExpr operator-(const LpCol& lhs, const T2& rhs) {
1137  LpExpr expr;
1138  expr += lhs;
1139  expr -= rhs;
1140 
1141  return expr;
1142  }
1143 
1144  template < typename T1,
1145  forbidden_type< T1, LpExpr >,
1147  LpExpr operator-(const T1& lhs, const LpCol& rhs) {
1148  LpExpr expr;
1149  expr += rhs;
1150  expr -= lhs;
1151 
1152  return expr;
1153  }
1154 
1156  template < typename SCALAR >
1157  INLINE LpExpr LpExpr::multiply(const SCALAR& lhs, const LpCol& rhs) {
1158  LpExpr expr;
1159  expr.__mCoeffs->insert(rhs, lhs);
1160  expr.__imiddle = true;
1161  return expr;
1162  }
1163 
1164  template < typename SCALAR >
1165  LpExpr operator*(const SCALAR& lhs, const LpCol& rhs) {
1166  return LpExpr::multiply(lhs, rhs);
1167  }
1168 
1169  template < typename SCALAR >
1170  LpExpr operator*(const LpCol& lhs, const SCALAR& rhs) {
1171  return LpExpr::multiply(rhs, lhs);
1172  }
1173 
1175  template < typename T1, typename T2 >
1176  INLINE LpExpr LpExpr::lessThan(T1&& lhs, T2&& rhs) {
1177  LpExpr expr;
1178  expr.__addSide(std::forward< T1 >(lhs));
1179  expr.__addSide(std::forward< T2 >(rhs));
1180  return expr;
1181  }
1182 
1183  // const lvalue
1184  template < typename T2 >
1185  LpExpr operator<=(const LpExpr& lhs, T2&& rhs) {
1186  return LpExpr::lessThan(lhs, std::forward< T2 >(rhs));
1187  }
1188 
1189  template < typename T2 >
1190  LpExpr operator<=(const LpCol& lhs, T2&& rhs) {
1191  return LpExpr::lessThan(lhs, std::forward< T2 >(rhs));
1192  }
1193 
1194  template < typename T1,
1197  LpExpr operator<=(T1&& lhs, const LpExpr& rhs) {
1198  return LpExpr::lessThan(std::forward< T1 >(lhs), rhs);
1199  }
1200 
1201  template < typename T1,
1202  forbidden_type< T1, LpExpr& >,
1204  LpExpr operator<=(T1&& lhs, const LpCol& rhs) {
1205  return LpExpr::lessThan(std::forward< T1 >(lhs), rhs);
1206  }
1207 
1208  // rvaue
1209  template < typename T2 >
1210  LpExpr operator<=(LpExpr&& lhs, T2&& rhs) {
1211  return LpExpr::lessThan(std::move(lhs), std::forward< T2 >(rhs));
1212  }
1213 
1214  template < typename T2 >
1215  LpExpr operator<=(LpCol&& lhs, T2&& rhs) {
1216  return LpExpr::lessThan(std::move(lhs), std::forward< T2 >(rhs));
1217  }
1218 
1219  template < typename T1,
1220  forbidden_type< T1, LpExpr >,
1222  LpExpr operator<=(T1&& lhs, LpExpr&& rhs) {
1223  return LpExpr::lessThan(std::forward< T1 >(lhs), std::move(rhs));
1224  }
1225 
1226  template < typename T1,
1227  forbidden_type< T1, LpExpr >,
1229  LpExpr operator<=(T1&& lhs, LpCol&& rhs) {
1230  return LpExpr::lessThan(std::forward< T1 >(lhs), std::move(rhs));
1231  }
1232  } // namespace lp
1233 
1234  } // namespace credal
1235 
1236 } // namespace gum
~LpRow()
Default destructor.
bool __ileft
True if this expression has a non-empty left side L : L <= M <= R .
Definition: LpInterface.h:406
unsigned int id() const
Variable id accessor.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
std::vector< std::vector< GUM_SCALAR > > solve()
Solve the linear program (H-representation of the polytope) by enumeration (of the polytope vertices)...
HashTable< LpCol, double > * __coeffs
The coefficients of the variables of the linear inequality.
Definition: LpInterface.h:584
void addProba()
Add positivity constraints and sum of variables is 1 ( probability constraints )
static LpExpr lessThan(T1 &&lhs, T2 &&rhs)
void setUpH(const unsigned int &card)
Sets up an H-representation.
bool operator!=(const LpCol &col) const
Opposite of equality != test between two variables.
static constexpr unsigned long gold
Definition: hashFunc.h:80
void fillMatrix(const std::vector< std::vector< GUM_SCALAR > > &matrix)
Fill the H-representation from the matrix given in argument.
std::string toString() const
Get the string representation of a calling linear program.
double __cste
The constant of the linear inequality.
Definition: LpInterface.h:580
bool __iright
True if this expression has a non-empty right side R : L <= M <= R .
Definition: LpInterface.h:414
HashTable< LpCol, double > * __mCoeffs
The coefficients of each variable on the middle side L : L <= M <= R.
Definition: LpInterface.h:430
friend std::ostream & operator<<(std::ostream &out, const LpRow &row)
Overload of << to use with output streams ( such as std::cout << ).
void addRow(const LpExpr &expr)
Add rows to the linear program according to a given expression ( which must be at least an inequality...
std::string toString() const
Get the string representation of a calling variable.
bool operator<(const LpCol &col) const
Test of ordering < between two variables.
void swap(HashTable< LpCol, double > *&a, HashTable< LpCol, double > *&b)
Swap the addresses of two pointers to hashTables.
LpCol(unsigned int id)
Default constructor.
Class representing a polytope ( credal set ) by a set of linear constraints.
LpExpr operator<=(const LpExpr &lhs, T2 &&rhs)
Overload of operator <= between anything and anything.
LpRow & operator=(const LpRow &row)
Class template representing hashing function of LpCol.
Definition: hashFunc.h:612
void __addSide(const LpCol &from)
Set the side of the calling expression, from LEFT TO RIGHT : L <= M <= R.
void addPositivity()
Add positivity constraints for all variables.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
double __mValue
The constant on the middle side L : L <= M <= R.
Definition: LpInterface.h:419
void addSumIsOne()
Add sum of variables is 1 constraints.
The class for generic Hash Tables.
Definition: hashTable.h:676
void clear()
Reset the rows (inequalities) and columns (variables) of the LP as if it was created.
Class representing a variable ( a column ) of a linear program, i.e.
Definition: LpInterface.h:59
const matrix & getOutput() const
Get the output matrix solution of the problem.
LpInterface()
Default constructor, empty problem.
void clear()
Clear all data of the calling expression as if it was constructed.
Class template acting as a wrapper for Lexicographic Reverse Search by David Avis.
Definition: LrsWrapper.h:104
Class representing a linear expression.
Definition: LpInterface.h:201
LpExpr()
Default constructor.
double __rValue
The constant on the right side L : L <= M <= R.
Definition: LpInterface.h:421
Class representing a row of the linear program, i.e.
Definition: LpInterface.h:492
HashTable< LpCol, double > * __rCoeffs
The coefficients of each variable on the right side L : L <= M <= R.
Definition: LpInterface.h:434
LpExpr & operator-=(const LpCol &rhs)
Compound assignment operator -= with a variable.
std::ostream & operator<<(std::ostream &out, const LpCol &col)
std::string to_string(const Formula &f)
Definition: formula_inl.h:479
double __lValue
The constant on the left side L : L <= M <= R.
Definition: LpInterface.h:417
Class representing a linear program.
Definition: LpInterface.h:47
~LpCol()
Default destructor.
LpExpr operator+(LpExpr &&lhs, const T2 &rhs)
Overload of operator + between anything ( a scalar, a variable or an expression ) and anything except...
bool __sumIsOne
true if addSumIsOne() has been called, false otherwise.
Definition: LpInterface.h:752
unsigned int __id
Variable id.
Definition: LpInterface.h:161
bool __positivity
true if addPositivity() has been called, false otherwise.
Definition: LpInterface.h:749
LpExpr & operator=(const LpCol &rhs)
Assignment operator = with a variable.
LpRow(const LpExpr &expr, const std::vector< LpCol > &cols)
Constructor from an expression and the address of the vector of variables of the problem.
friend std::ostream & operator<<(std::ostream &out, const LpCol &col)
Overload of << to use with output streams ( such as std::cout << ).
HashTable< LpCol, double > * __lCoeffs
The coefficients of each variable on the left side L : L <= M <= R.
Definition: LpInterface.h:426
typename std::enable_if< !std::is_same< T1, T2 >::value, int >::type forbidden_type
Forbidden_type<T1,T2> return the "int" type if T1 and T2 are of the same type, else nothing...
Definition: utils_misc.h:112
void clearRows()
Reset the rows (inequalities) of the LP but not the columns (variables are kept). ...
std::string toString() const
Get the string representation of a calling expression.
LpExpr operator*(const SCALAR &lhs, const LpCol &rhs)
Overload of operator * between a scalar and a variable.
std::string toString() const
Get the string representation of a calling row.
std::vector< LpCol > addCols(const unsigned int &cols)
Insert new columns, i.e.
bool operator==(const LpCol &col) const
Test of equality == between two variables.
std::vector< LpRow * > __rows
Rows of the problem.
Definition: LpInterface.h:743
~LpInterface()
Default destructor.
void H2V()
H-representation to V-representation.
std::vector< LpCol > getCols() const
Get the variables of the LP.
static LpExpr multiply(const SCALAR &lhs, const LpCol &rhs)
LpInterface< GUM_SCALAR > & operator=(const LpInterface< GUM_SCALAR > &from)
Copy compound assignment.
~LpExpr()
Default destructor.
LpCol addCol()
Insert a new column, i.e.
LpExpr & operator+=(const LpCol &rhs)
Compound assignment operator += with a variable.
LpCol & operator=(const LpCol &col)
Assignment operator = by copy.
LpExpr operator-(LpExpr &&lhs, const T2 &rhs)
Overload of operator - between anything ( a scalar, a variable or an expression ) and anything except...
std::vector< LpCol > __cols
Variables of the problem.
Definition: LpInterface.h:745
bool __imiddle
True if this expression has a non-empty middle side M ( the default ) : L <= M <= R ...
Definition: LpInterface.h:410
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66