aGrUM  0.14.1
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 
62 
63  namespace credal {
64  namespace lp {
65 
71  __ileft(false), __imiddle(false), __iright(false), __lValue(0.),
72  __mValue(0.), __rValue(0.), __lCoeffs(new HashTable< LpCol, double >()),
73  __mCoeffs(new HashTable< LpCol, double >()),
74  __rCoeffs(new HashTable< LpCol, double >()) {
75  GUM_CONSTRUCTOR(LpExpr);
76  }
77 
78  LpExpr::LpExpr(const LpExpr& expr) :
79  __ileft(expr.__ileft), __imiddle(expr.__imiddle),
80  __iright(expr.__iright), __lValue(expr.__lValue),
81  __mValue(expr.__mValue), __rValue(expr.__rValue),
82  __lCoeffs(new HashTable< LpCol, double >(*expr.__lCoeffs)),
83  __mCoeffs(new HashTable< LpCol, double >(*expr.__mCoeffs)),
84  __rCoeffs(new HashTable< LpCol, double >(*expr.__rCoeffs)) {
85  GUM_CONS_CPY(LpExpr);
86  }
87 
88  LpExpr::LpExpr(const LpExpr& expr,
89  bool copyLeft,
90  bool copyMiddle,
91  bool copyRight) :
92  __ileft(false),
93  __imiddle(false), __iright(false), __lValue(0.), __mValue(0.),
94  __rValue(0.), __lCoeffs(nullptr), __mCoeffs(nullptr),
95  __rCoeffs(nullptr) {
96  if (copyLeft) {
98  __lValue = expr.__lValue;
99  __ileft = true;
100  } else
102 
103  if (copyMiddle) {
105  __mValue = expr.__mValue;
106  __imiddle = true;
107  } else
109 
110  if (copyRight) {
112  __rValue = expr.__rValue;
113  __iright = true;
114  } else
116 
117  GUM_CONS_CPY(LpExpr);
118  }
119 
121  __ileft(expr.__ileft), __imiddle(expr.__imiddle),
122  __iright(expr.__iright), __lValue(expr.__lValue),
123  __mValue(expr.__mValue), __rValue(expr.__rValue),
124  __lCoeffs(expr.__lCoeffs), __mCoeffs(expr.__mCoeffs),
125  __rCoeffs(expr.__rCoeffs) {
126  expr.__lCoeffs = nullptr;
127  expr.__mCoeffs = nullptr;
128  expr.__rCoeffs = nullptr;
129 
130  GUM_CONS_CPY(LpExpr);
131  }
132 
134  bool copyLeft,
135  bool copyMiddle,
136  bool copyRight) :
137  __ileft(false),
138  __imiddle(false), __iright(false), __lValue(0.), __mValue(0.),
139  __rValue(0.), __lCoeffs(nullptr), __mCoeffs(nullptr),
140  __rCoeffs(nullptr) {
141  if (copyLeft) {
142  swap(__lCoeffs, expr.__lCoeffs);
143  __lValue = expr.__lValue;
144  __ileft = true;
145  } else
147 
148  if (copyMiddle) {
149  swap(__mCoeffs, expr.__mCoeffs);
150  __mValue = expr.__mValue;
151  __imiddle = true;
152  } else
154 
155  if (copyRight) {
156  swap(__rCoeffs, expr.__rCoeffs);
157  __rValue = expr.__rValue;
158  __iright = true;
159  } else
161 
162  GUM_CONS_CPY(LpExpr);
163  }
164 
166  delete __lCoeffs;
167  delete __mCoeffs;
168  delete __rCoeffs;
169 
170  GUM_DESTRUCTOR(LpExpr);
171  }
172 
174  clear();
175 
176  __mCoeffs->insert(rhs, 1.);
177  __imiddle = true;
178 
179  return *this;
180  }
181 
184  if (this == &rhs) return *this;
185 
186  *__lCoeffs = *rhs.__lCoeffs;
187  *__mCoeffs = *rhs.__mCoeffs;
188  *__rCoeffs = *rhs.__rCoeffs;
189 
190  __lValue = rhs.__lValue;
191  __mValue = rhs.__mValue;
192  __rValue = rhs.__rValue;
193 
194  __ileft = rhs.__ileft;
195  __imiddle = rhs.__imiddle;
196  __iright = rhs.__iright;
197 
198  return *this;
199  }
200 
203  if (this == &rhs) return *this;
204 
205  swap(__lCoeffs, rhs.__lCoeffs);
206  swap(__mCoeffs, rhs.__mCoeffs);
207  swap(__rCoeffs, rhs.__rCoeffs);
208 
209  __lValue = rhs.__lValue;
210  __mValue = rhs.__mValue;
211  __rValue = rhs.__rValue;
212 
213  __ileft = rhs.__ileft;
214  __imiddle = rhs.__imiddle;
215  __iright = rhs.__iright;
216 
217  return *this;
218  }
219 
220  template < typename SCALAR >
221  LpExpr& LpExpr::operator=(const SCALAR& rhs) {
222  clear();
223 
224  __mValue = rhs;
225  __imiddle = true;
226 
227  return *this;
228  }
229 
231  if (__ileft || __iright)
233  "expr::operator+= (expr) : <= present on one side of expr");
234 
235  if (!__imiddle) __imiddle = true;
236 
237  __mCoeffs->getWithDefault(rhs, 0.) += 1.;
238 
239  return *this;
240  }
241 
243  if (__ileft || __iright || rhs.__ileft || rhs.__iright)
245  "expr::operator+= (rhs) : <= present "
246  "on one side of rhs and/or expr");
247 
248  if (!__imiddle) __imiddle = true;
249 
250  for (const auto& elt : *rhs.__mCoeffs)
251  __mCoeffs->getWithDefault(elt.first, 0.) += elt.second;
252 
253  __mValue += rhs.__mValue;
254 
255  return *this;
256  }
257 
259  if (__ileft || __iright || rhs.__ileft || rhs.__iright)
261  "expr::operator+= (rhs) : <= present "
262  "on one side of rhs and/or expr");
263 
264  if (!__imiddle) {
265  __imiddle = true;
266 
267  __mValue = rhs.__mValue;
268 
269  swap(__mCoeffs, rhs.__mCoeffs);
270 
271  return *this;
272  }
273 
274  for (const auto& elt : *rhs.__mCoeffs)
275  __mCoeffs->getWithDefault(elt.first, 0.) += elt.second;
276 
277  __mValue += rhs.__mValue;
278 
279  return *this;
280  }
281 
282  template < typename T >
283  LpExpr& LpExpr::operator+=(const T& rhs) {
284  if (__ileft || __iright)
286  "expr::operator+= (expr) : <= present on one side of expr");
287 
288  if (!__imiddle) __imiddle = true;
289 
290  __mValue += rhs;
291 
292  return *this;
293  }
294 
296  if (__ileft || __iright)
298  "expr::operator-= (rhs) : <= present in one of expr");
299 
300  if (!__imiddle) __imiddle = true;
301 
302  __mCoeffs->getWithDefault(rhs, 0.) -= 1.;
303 
304  return *this;
305  }
306 
308  if (__ileft || __iright || rhs.__ileft || rhs.__iright)
309  GUM_ERROR(
311  "expr::operator-= (rhs) : <= present in one of rhs and/or expr");
312 
313  if (!__imiddle) __imiddle = true;
314 
315  for (const auto& elt : *rhs.__mCoeffs)
316  __mCoeffs->getWithDefault(elt.first, 0.) -= elt.second;
317 
318  __mValue -= rhs.__mValue;
319 
320  return *this;
321  }
322 
323  template < typename T >
324  LpExpr& LpExpr::operator-=(const T& rhs) {
325  if (__ileft || __iright)
327  "expr::operator-= (rhs) : <= present in one of expr");
328 
329  if (!__imiddle) __imiddle = true;
330 
331  __mValue -= rhs;
332 
333  return *this;
334  }
335 
336  std::ostream& operator<<(std::ostream& out, const LpExpr& expr) {
337  out << expr.toString();
338  return out;
339  }
340 
341  void LpExpr::__addSide(const LpCol& from) {
342  if (!__ileft) {
343  __lCoeffs->insert(from, 1.);
344  __ileft = true;
345  } else if (!__imiddle) {
346  __mCoeffs->insert(from, 1.);
347  __imiddle = true;
348  } else if (!__iright) {
349  __rCoeffs->insert(from, 1.);
350  __iright = true;
351  } else
353  "LpExpr::setSide ( const LpCol & from "
354  ") : too many <= ; no free side");
355  }
356 
357  void LpExpr::__addSide(const LpExpr& from) {
358  if (__ileft && __iright && from.__imiddle)
360  "LpExpr::setSide ( const LpCol & from "
361  ") : too many <= ; no free side");
362 
364  if (!from.__imiddle) return;
365 
369  if (!from.__ileft && !from.__iright) {
370  if (!__ileft) {
371  *__lCoeffs = *from.__mCoeffs;
372  __lValue = from.__mValue;
373  __ileft = true;
374 
375  return;
376  } else if (!__imiddle) {
377  *__mCoeffs = *from.__mCoeffs;
378  __mValue = from.__mValue;
379  __imiddle = true;
380 
381  return;
382  } else if (!__iright) {
383  *__rCoeffs = *from.__mCoeffs;
384  __rValue = from.__mValue;
385  __iright = true;
386 
387  return;
388  } else
390  "LpExpr::setSide ( const LpCol & from ) "
391  ": too many <= ; no free side");
392  }
395  else if (from.__ileft && !from.__iright) {
396  if (!__ileft) {
397  *__lCoeffs = *from.__lCoeffs;
398  __lValue = from.__lValue;
399  __ileft = true;
400 
401  *__mCoeffs = *from.__mCoeffs;
402  __mValue = from.__mValue;
403  __imiddle = true;
404 
405  return;
406  } else if (!__imiddle && !__iright) {
407  *__mCoeffs = *from.__lCoeffs;
408  __mValue = from.__lValue;
409  __imiddle = true;
410 
411  *__rCoeffs = *from.__mCoeffs;
412  __rValue = from.__mValue;
413  __iright = true;
414 
415  return;
416  } else
418  "LpExpr::setSide ( const LpCol & from ) "
419  ": too many <= ; no free side");
420  }
423  else if (from.__ileft && from.__iright) {
424  if (__ileft || __imiddle || __iright)
426  "LpExpr::setSide ( const LpCol & from ) "
427  ": too many <= ; no free side");
428 
429  *this = from;
430 
431  return;
432  } else
434  "LpExpr::setSide ( const LpCol & from "
435  ") : too many <= ; no free side");
436  }
437 
438  void LpExpr::__addSide(LpExpr&& from) {
440  if (__ileft && __iright && from.__imiddle)
442  "LpExpr::setSide ( const LpCol & from "
443  ") : too many <= ; no free side");
444 
446  if (!from.__imiddle) return;
447 
451  if (!from.__ileft && !from.__iright) {
452  if (!__ileft) {
454  swap(__lCoeffs, from.__mCoeffs);
455  __lValue = from.__mValue;
456  __ileft = true;
457 
458  return;
459  } else if (!__imiddle) {
461  swap(__mCoeffs, from.__mCoeffs);
462  __mValue = from.__mValue;
463  __imiddle = true;
464 
465  return;
466  } else if (!__iright) {
468  swap(__rCoeffs, from.__mCoeffs);
469  __rValue = from.__mValue;
470  __iright = true;
471 
472  return;
473  } else
475  "LpExpr::setSide ( const LpCol & from ) "
476  ": too many <= ; no free side");
477  }
480  else if (from.__ileft && !from.__iright) {
481  if (!__ileft) {
483  swap(__lCoeffs, from.__lCoeffs);
484  __lValue = from.__lValue;
485  __ileft = true;
486 
488  swap(__mCoeffs, from.__mCoeffs);
489  __mValue = from.__mValue;
490  __imiddle = true;
491 
492  return;
493  } else if (!__imiddle && !__iright) {
495  swap(__mCoeffs, from.__lCoeffs);
496  __mValue = from.__lValue;
497  __imiddle = true;
498 
500  swap(__rCoeffs, from.__mCoeffs);
501  __rValue = from.__mValue;
502  __iright = true;
503 
504  return;
505  } else
507  "LpExpr::setSide ( const LpCol & from ) "
508  ": too many <= ; no free side");
509  }
512  else if (from.__ileft && from.__iright) {
513  if (__ileft || __imiddle || __iright)
515  "LpExpr::setSide ( const LpCol & from ) "
516  ": too many <= ; no free side");
517 
518  *this = std::move(from);
519 
520  return;
521  } else
523  "LpExpr::setSide ( const LpCol & from "
524  ") : too many <= ; no free side");
525  }
526 
527  template < typename SCALAR >
528  void LpExpr::__addSide(const SCALAR& from) {
529  if (!__ileft) {
530  __lValue = from;
531  __ileft = true;
532  } else if (!__imiddle) {
533  __mValue = from;
534  __imiddle = true;
535  } else if (!__iright) {
536  __rValue = from;
537  __iright = true;
538  } else
540  "LpExpr::setSide ( const LpCol & from "
541  ") : too many <= ; no free side");
542  }
543 
544  void LpExpr::clear() {
545  __lCoeffs->clear();
546  __mCoeffs->clear();
547  __rCoeffs->clear();
548 
549  __lValue = 0.;
550  __mValue = 0.;
551  __rValue = 0.;
552 
553  __ileft = false;
554  __imiddle = false;
555  __iright = false;
556  }
557 
558  std::string LpExpr::toString() const {
559  std::ostringstream s;
560 
561  s << std::endl << "left side : " << std::endl;
562 
563  if (__lCoeffs != nullptr)
564  for (const auto& elt : *__lCoeffs)
565  s << elt.first.toString() << " " << elt.second << " | ";
566 
567  s << std::endl << "middle side : " << std::endl;
568 
569  if (__mCoeffs != nullptr)
570  for (const auto& elt : *__mCoeffs)
571  s << elt.first.toString() << " " << elt.second << " | ";
572 
573  s << std::endl << "right side : " << std::endl;
574 
575  if (__rCoeffs != nullptr)
576  for (const auto& elt : *__rCoeffs)
577  s << elt.first.toString() << " " << elt.second << " | ";
578 
579  s << std::endl
580  << "lvalue : " << __lValue << std::endl
581  << "mvalue : " << __mValue << std::endl
582  << "rvalue : " << __rValue << std::endl;
583 
584  s << std::endl;
585 
586  return s.str();
587  }
588 
593  LpRow::LpRow(const LpExpr& expr, const std::vector< LpCol >& cols) :
594  __coeffs(nullptr) {
595  // we write 0 <= Ax + b from Ex + f <= Cx + d
596  if (expr.__ileft && !expr.__iright) {
598 
599  for (const auto& col : cols) {
600  double col_coeff = 0.;
601 
602  // from left side to middle side : 0 <= middle - left
603  if (expr.__lCoeffs->exists(col))
604  col_coeff = expr.__lCoeffs->operator[](col);
605 
606  __coeffs->getWithDefault(col, 0.) -= col_coeff;
607  }
608 
609  __cste = expr.__mValue - expr.__lValue;
610  } else if (expr.__iright && !expr.__ileft) {
612 
613  for (const auto& col : cols) {
614  double col_coeff = 0;
615 
616  // from middle side to right side : 0 <= right - middle
617  if (expr.__mCoeffs->exists(col))
618  col_coeff = expr.__mCoeffs->operator[](col);
619 
620  __coeffs->getWithDefault(col, 0.) -= col_coeff;
621  }
622 
623  __cste = expr.__rValue - expr.__mValue;
624  } else
626  "expr : " << expr.toString()
627  << "is not a valid inequality; no <= detected");
628 
629  if (__coeffs->size() == 0)
631  "expr : " << expr.toString()
632  << "is not a valid inequality; "
633  "no variable in inequality, "
634  "only constants");
635 
636  GUM_CONSTRUCTOR(LpRow);
637  }
638 
639  LpRow::LpRow(LpExpr&& expr, const std::vector< LpCol >& cols) :
640  __coeffs(nullptr) {
642  if (expr.__ileft && !expr.__iright) {
643  swap(__coeffs, expr.__mCoeffs);
644 
645  for (const auto& col : cols) {
646  double col_coeff = 0;
647 
648  if (expr.__lCoeffs->exists(col))
649  col_coeff = expr.__lCoeffs->operator[](col);
650 
651  __coeffs->getWithDefault(col, 0.) -= col_coeff;
652  }
653 
654  __cste = expr.__mValue - expr.__lValue;
655  } else if (expr.__iright && !expr.__ileft) {
656  swap(__coeffs, expr.__rCoeffs);
657 
658  for (const auto& col : cols) {
659  double col_coeff = 0;
660 
661  if (expr.__mCoeffs->exists(col))
662  col_coeff = expr.__mCoeffs->operator[](col);
663 
664  __coeffs->getWithDefault(col, 0.) -= col_coeff;
665  }
666 
667  __cste = expr.__rValue - expr.__mValue;
668  } else
670  "expr : " << expr.toString()
671  << "is not a valid inequality; no <= detected");
672 
673  if (__coeffs->size() == 0)
675  "expr : " << expr.toString()
676  << "is not a valid inequality; "
677  "no variable in inequality, "
678  "only constants");
679 
680  GUM_CONSTRUCTOR(LpRow);
681  }
682 
683  LpRow::LpRow(const LpRow& row) :
684  __cste(row.__cste),
685  __coeffs(new HashTable< LpCol, double >(*row.__coeffs)) {
686  GUM_CONS_CPY(LpRow);
687  }
688 
690  row.__coeffs = nullptr;
691 
692  GUM_CONS_CPY(LpRow);
693  }
694 
696  delete __coeffs;
697 
698  GUM_DESTRUCTOR(LpRow);
699  }
700 
701  LpRow& LpRow::operator=(const LpRow& row) {
702  __cste = row.__cste;
703  *__coeffs = *row.__coeffs;
704  return *this;
705  }
706 
708  __cste = row.__cste;
709  swap(__coeffs, row.__coeffs);
710  return *this;
711  }
712 
713  std::ostream& operator<<(std::ostream& out, const LpRow& row) {
714  out << row.toString();
715  return out;
716  }
717 
718  std::string LpRow::toString() const {
719  std::ostringstream s;
720 
721  s << "0 <= " << __cste;
722 
723  if (__coeffs != nullptr) {
724  for (const auto& elt : *__coeffs) {
725  if (elt.second > 0) {
726  if (elt.second != 1) {
727  s << " +" << elt.second << "*" << elt.first.toString();
728  } else {
729  s << " +" << elt.first.toString();
730  }
731  } else {
732  if (elt.second < 0) {
733  if (elt.second != -1) {
734  s << " " << elt.second << "*" << elt.first.toString();
735  } else {
736  s << " -" << elt.first.toString();
737  }
738  }
739  }
740  }
741  }
742 
743  return s.str();
744  }
745 
749  template < typename GUM_SCALAR >
751  __positivity = false;
752  __sumIsOne = false;
753  GUM_CONSTRUCTOR(LpInterface);
754  }
755 
756  template < typename GUM_SCALAR >
758  const LpInterface< GUM_SCALAR >& from) :
759  __cols(from.__cols),
760  __positivity(from.__positivity), __sumIsOne(from.__sumIsOne) {
761  __rows.resize(from.__rows.size());
762 
763  for (unsigned int i = 0, end = from.__rows.size(); i < end; i++)
764  __rows[i] = new LpRow(*from.__rows[i]);
765 
766  GUM_CONS_CPY(LpInterface);
767  }
768 
769  template < typename GUM_SCALAR >
772  __rows.swap(from.__rows);
773  __cols.swap(from.__cols);
774  GUM_CONS_CPY(LpInterface);
775  }
776 
777  template < typename GUM_SCALAR >
779  for (const auto row : __rows)
780  delete row;
781 
782  GUM_DESTRUCTOR(LpInterface);
783  }
784 
785  template < typename GUM_SCALAR >
789  for (const auto& row : __rows)
790  delete row;
791 
792  __rows.clear();
793  __rows.shrink_to_fit();
794 
795  __rows.resize(from.__rows.size());
796 
797  for (unsigned int i = 0, end = from.__rows.size(); i < end; i++)
798  __rows[i] = new LpRow(*from.__rows[i]);
799 
800  __cols = from.__cols;
801  __positivity = from.__positivity;
802  __sumIsOne = from.__sumIsOne;
803 
804  return *this;
805  }
806 
807  template < typename GUM_SCALAR >
810  __rows.swap(from.__rows);
811  __cols.swap(from.__cols);
812 
813  __positivity = from.__positivity;
814  __sumIsOne = from.__sumIsOne;
815 
816  return *this;
817  }
818 
819  template < typename T >
820  std::ostream& operator<<(std::ostream& out, const LpInterface< T >& lpi) {
821  out << lpi.toString();
822  return out;
823  }
824 
825  template < typename GUM_SCALAR >
827  LpCol col((unsigned int)__cols.size());
828 
829  __cols.push_back(col);
830 
831  return col;
832  }
833 
834  template < typename GUM_SCALAR >
835  std::vector< LpCol >
836  LpInterface< GUM_SCALAR >::addCols(const unsigned int& cols) {
837  if (cols < 1)
839  "LpInterface::addCols ( cols ) : cols "
840  "needs must be equal or greater than 1 : "
841  << cols << " < 1");
842 
843  for (unsigned int i = 0; i < cols; i++) {
844  __cols.push_back(LpCol((unsigned int)__cols.size()));
845  }
846 
847  return __cols;
848  }
849 
850  template < typename GUM_SCALAR >
852  if (!expr.__ileft && !expr.__iright)
854  "addRow ( const LpExpr & expr ) : expr : "
855  << expr.toString() << "is not an inequality.");
856 
857  if ((expr.__ileft && !expr.__iright) || (!expr.__ileft && expr.__iright)) {
858  __rows.push_back(new LpRow(expr, __cols));
859  } else {
860  LpExpr lexpr(expr, true, true, false);
861  LpExpr rexpr(expr, false, true, true);
862 
863  __rows.push_back(
864  new LpRow(std::move(lexpr),
865  __cols));
866  __rows.push_back(
867  new LpRow(std::move(rexpr),
868  __cols));
869  }
870  }
871 
872  template < typename GUM_SCALAR >
874  if (!expr.__ileft && !expr.__iright)
876  "addRow ( const LpExpr & expr ) : expr : "
877  << expr.toString() << "is not an inequality.");
878 
879  if ((expr.__ileft && !expr.__iright) || (!expr.__ileft && expr.__iright)) {
880  __rows.push_back(new LpRow(std::move(expr), __cols));
881  } else {
882  LpExpr lexpr(std::move(expr), true, true, false);
883 
885  LpExpr rexpr(std::move(expr), false, false, true);
886 
888 
889  *rexpr.__mCoeffs = *lexpr.__mCoeffs;
890  rexpr.__mValue = lexpr.__mValue;
891  rexpr.__imiddle = true;
892 
893  __rows.push_back(
894  new LpRow(std::move(lexpr),
895  __cols));
896  __rows.push_back(
897  new LpRow(std::move(rexpr),
898  __cols));
899  }
900  }
901 
902  template < typename GUM_SCALAR >
904  if (__positivity) return;
905 
906  for (const auto& col : __cols)
907  addRow(0 <= col);
908 
909  __positivity = true;
910  }
911 
912  template < typename GUM_SCALAR >
914  if (__sumIsOne) return;
915 
916  LpExpr expr;
917 
918  for (const auto& col : __cols)
919  expr += col;
920 
921  addRow(1 <= std::move(expr) <= 1);
922 
923  __sumIsOne = true;
924  }
925 
926  template < typename GUM_SCALAR >
928  if (__positivity && __sumIsOne) {
929  return;
930  } else if (__positivity && !__sumIsOne) {
931  addSumIsOne();
932  return;
933  } else if (!__positivity && __sumIsOne) {
934  addPositivity();
935  return;
936  }
937 
938  // we can do both with one loop, don't call the above functions.
939  // addPositivity();
940  // addSumIsOne();
941  LpExpr expr;
942 
943  for (const auto& col : __cols) {
944  addRow(0 <= col);
945  expr += col;
946  }
947 
948  addRow(1 <= std::move(expr) <= 1);
949 
950  __sumIsOne = true;
951  __positivity = true;
952  }
953 
954  template < typename GUM_SCALAR >
955  std::vector< std::vector< GUM_SCALAR > > LpInterface< GUM_SCALAR >::solve() {
957 
958  lrs.setUpH((unsigned int)__cols.size());
959 
960  std::vector< std::vector< GUM_SCALAR > > lrsMatrix;
961 
962  for (const auto& row : __rows) {
963  std::vector< GUM_SCALAR > expandedRow(__cols.size() + 1, 0);
964 
965  expandedRow[0] = row->__cste;
966 
967  for (const auto& elt : *row->__coeffs)
968  expandedRow[elt.first.id() + 1] = elt.second;
969 
970  lrsMatrix.push_back(expandedRow);
971  }
972 
973  lrs.fillMatrix(lrsMatrix);
974 
975  lrs.H2V();
976 
977  return lrs.getOutput();
978  }
979 
980  template < typename GUM_SCALAR >
981  std::vector< LpCol > LpInterface< GUM_SCALAR >::getCols() const {
982  return __cols;
983  }
984 
985  template < typename GUM_SCALAR >
987  std::ostringstream s;
988 
989  s << std::endl << std::endl << "Variables : " << std::endl;
990 
991  for (const auto& col : __cols)
992  s << " " << col.toString();
993 
994  s << std::endl;
995 
996  for (const auto& row : __rows)
997  s << std::endl << row->toString();
998 
999  s << std::endl << std::endl;
1000 
1001  return s.str();
1002  }
1003 
1004  template < typename GUM_SCALAR >
1006  for (const auto& row : __rows)
1007  delete row;
1008 
1009  __rows.clear();
1010  __rows.shrink_to_fit();
1011 
1015  __cols.clear();
1016  __cols.shrink_to_fit();
1017 
1018  __positivity = false;
1019  __sumIsOne = false;
1020  }
1021 
1022  template < typename GUM_SCALAR >
1024  for (const auto& row : __rows)
1025  delete row;
1026 
1027  __rows.clear();
1028  __rows.shrink_to_fit();
1029 
1030  __positivity = false;
1031  __sumIsOne = false;
1032  }
1033 
1037  a = b;
1038  b = tmp;
1039  }
1040 
1042  template < typename T2 >
1043  LpExpr operator+(LpExpr&& lhs, const T2& rhs) {
1044  LpExpr expr = std::move(lhs);
1045  expr += rhs;
1046 
1047  return expr;
1048  }
1049 
1050  template < typename T2 >
1051  LpExpr operator+(const LpExpr& lhs, const T2& rhs) {
1052  LpExpr expr(lhs);
1053  expr += rhs;
1054 
1055  return expr;
1056  }
1057 
1058  template < typename T1, forbidden_type< T1, LpExpr > >
1059  LpExpr operator+(const T1& lhs, LpExpr&& rhs) {
1060  LpExpr expr = std::move(rhs);
1061  ;
1062  expr += lhs;
1063 
1064  return expr;
1065  }
1066 
1067  template < typename T1, forbidden_type< T1, LpExpr > >
1068  LpExpr operator+(const T1& lhs, LpExpr& rhs) {
1069  LpExpr expr(rhs);
1070  expr += lhs;
1071 
1072  return expr;
1073  }
1074 
1075  template < typename T2, forbidden_type< T2, LpExpr > >
1076  LpExpr operator+(const LpCol& lhs, const T2& rhs) {
1077  LpExpr expr;
1078  expr += lhs;
1079  expr += rhs;
1080 
1081  return expr;
1082  }
1083 
1084  template < typename T1,
1087  LpExpr operator+(const T1& lhs, const LpCol& rhs) {
1088  LpExpr expr;
1089  expr += rhs;
1090  expr += lhs;
1091 
1092  return expr;
1093  }
1094 
1096  template < typename T2 >
1097  LpExpr operator-(LpExpr&& lhs, const T2& rhs) {
1098  LpExpr expr = std::move(lhs);
1099  expr -= rhs;
1100 
1101  return expr;
1102  }
1103 
1104  template < typename T2 >
1105  LpExpr operator-(const LpExpr& lhs, const T2& rhs) {
1106  LpExpr expr(lhs);
1107  expr -= rhs;
1108 
1109  return expr;
1110  }
1111 
1112  template < typename T1, forbidden_type< T1, LpExpr > >
1113  LpExpr operator-(const T1& lhs, LpExpr&& rhs) {
1114  LpExpr expr;
1115  expr += std::move(rhs);
1116  ;
1117  expr -= lhs;
1118 
1119  return expr;
1120  }
1121 
1122  template < typename T1, forbidden_type< T1, LpExpr > >
1123  LpExpr operator-(const T1& lhs, LpExpr& rhs) {
1124  LpExpr expr;
1125  expr += rhs;
1126  expr -= lhs;
1127 
1128  return expr;
1129  }
1130 
1131  template < typename T2, forbidden_type< T2, LpExpr > >
1132  LpExpr operator-(const LpCol& lhs, const T2& rhs) {
1133  LpExpr expr;
1134  expr += lhs;
1135  expr -= rhs;
1136 
1137  return expr;
1138  }
1139 
1140  template < typename T1,
1141  forbidden_type< T1, LpExpr >,
1143  LpExpr operator-(const T1& lhs, const LpCol& rhs) {
1144  LpExpr expr;
1145  expr += rhs;
1146  expr -= lhs;
1147 
1148  return expr;
1149  }
1150 
1152  template < typename SCALAR >
1153  INLINE LpExpr LpExpr::multiply(const SCALAR& lhs, const LpCol& rhs) {
1154  LpExpr expr;
1155  expr.__mCoeffs->insert(rhs, lhs);
1156  expr.__imiddle = true;
1157  return expr;
1158  }
1159 
1160  template < typename SCALAR >
1161  LpExpr operator*(const SCALAR& lhs, const LpCol& rhs) {
1162  return LpExpr::multiply(lhs, rhs);
1163  }
1164 
1165  template < typename SCALAR >
1166  LpExpr operator*(const LpCol& lhs, const SCALAR& rhs) {
1167  return LpExpr::multiply(rhs, lhs);
1168  }
1169 
1171  template < typename T1, typename T2 >
1172  INLINE LpExpr LpExpr::lessThan(T1&& lhs, T2&& rhs) {
1173  LpExpr expr;
1174  expr.__addSide(std::forward< T1 >(lhs));
1175  expr.__addSide(std::forward< T2 >(rhs));
1176  return expr;
1177  }
1178 
1179  // const lvalue
1180  template < typename T2 >
1181  LpExpr operator<=(const LpExpr& lhs, T2&& rhs) {
1182  return LpExpr::lessThan(lhs, std::forward< T2 >(rhs));
1183  }
1184 
1185  template < typename T2 >
1186  LpExpr operator<=(const LpCol& lhs, T2&& rhs) {
1187  return LpExpr::lessThan(lhs, std::forward< T2 >(rhs));
1188  }
1189 
1190  template < typename T1,
1193  LpExpr operator<=(T1&& lhs, const LpExpr& rhs) {
1194  return LpExpr::lessThan(std::forward< T1 >(lhs), rhs);
1195  }
1196 
1197  template < typename T1,
1198  forbidden_type< T1, LpExpr& >,
1200  LpExpr operator<=(T1&& lhs, const LpCol& rhs) {
1201  return LpExpr::lessThan(std::forward< T1 >(lhs), rhs);
1202  }
1203 
1204  // rvaue
1205  template < typename T2 >
1206  LpExpr operator<=(LpExpr&& lhs, T2&& rhs) {
1207  return LpExpr::lessThan(std::move(lhs), std::forward< T2 >(rhs));
1208  }
1209 
1210  template < typename T2 >
1211  LpExpr operator<=(LpCol&& lhs, T2&& rhs) {
1212  return LpExpr::lessThan(std::move(lhs), std::forward< T2 >(rhs));
1213  }
1214 
1215  template < typename T1,
1216  forbidden_type< T1, LpExpr >,
1218  LpExpr operator<=(T1&& lhs, LpExpr&& rhs) {
1219  return LpExpr::lessThan(std::forward< T1 >(lhs), std::move(rhs));
1220  }
1221 
1222  template < typename T1,
1223  forbidden_type< T1, LpExpr >,
1225  LpExpr operator<=(T1&& lhs, LpCol&& rhs) {
1226  return LpExpr::lessThan(std::forward< T1 >(lhs), std::move(rhs));
1227  }
1228  } // namespace lp
1229 
1230  } // namespace credal
1231 
1232 } // namespace gum
~LpRow()
Default destructor.
bool __ileft
True if this expression has a non-empty left side L : L <= M <= R .
Definition: LpInterface.h:413
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:591
void addProba()
Add positivity constraints and sum of variables is 1 ( probability constraints )
static LpExpr lessThan(T1 &&lhs, T2 &&rhs)
std::string toString() const
Get the string representation of a calling variable.
bool operator==(const LpCol &col) const
Test of equality == between two variables.
void fillMatrix(const std::vector< std::vector< GUM_SCALAR > > &matrix)
Fill the H-representation from the matrix given in argument.
double __cste
The constant of the linear inequality.
Definition: LpInterface.h:587
bool __iright
True if this expression has a non-empty right side R : L <= M <= R .
Definition: LpInterface.h:421
HashTable< LpCol, double > * __mCoeffs
The coefficients of each variable on the middle side L : L <= M <= R.
Definition: LpInterface.h:437
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...
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)
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:426
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
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:105
void setUpH(const Size &card)
Sets up an H-representation.
Class representing a linear expression.
Definition: LpInterface.h:208
LpExpr()
Default constructor.
double __rValue
The constant on the right side L : L <= M <= R.
Definition: LpInterface.h:428
Class representing a row of the linear program, i.e.
Definition: LpInterface.h:499
HashTable< LpCol, double > * __rCoeffs
The coefficients of each variable on the right side L : L <= M <= R.
Definition: LpInterface.h:441
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:424
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:759
unsigned int __id
Variable id.
Definition: LpInterface.h:161
bool __positivity
true if addPositivity() has been called, false otherwise.
Definition: LpInterface.h:756
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:433
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:124
void clearRows()
Reset the rows (inequalities) of the LP but not the columns (variables are kept). ...
std::vector< LpCol > getCols() const
Get the variables of the LP.
LpExpr operator*(const SCALAR &lhs, const LpCol &rhs)
Overload of operator * between a scalar and a variable.
std::vector< LpCol > addCols(const unsigned int &cols)
Insert new columns, i.e.
std::vector< LpRow *> __rows
Rows of the problem.
Definition: LpInterface.h:750
~LpInterface()
Default destructor.
void H2V()
H-representation to V-representation.
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.
const matrix & getOutput() const
Get the output matrix solution of the problem.
std::string toString() const
Get the string representation of a calling expression.
std::string toString() const
Get the string representation of a calling linear program.
bool operator!=(const LpCol &col) const
Opposite of equality != test between two variables.
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:752
bool __imiddle
True if this expression has a non-empty middle side M ( the default ) : L <= M <= R ...
Definition: LpInterface.h:417
unsigned int id() const
Variable id accessor.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52
bool operator<(const LpCol &col) const
Test of ordering < between two variables.
std::string toString() const
Get the string representation of a calling row.