aGrUM  0.20.2
a C++ library for (probabilistic) graphical models
LpInterface.cpp
Go to the documentation of this file.
1 /**
2  *
3  * Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
4  * info_at_agrum_dot_org
5  *
6  * This library is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This library 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 Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this library. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief Class to include at least once this header
25  *
26  * @author Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
27  */
28 
29 #include <agrum/CN/polytope/LpInterface.h>
30 
31 #ifdef GUM_NO_INLINE
32 # include <agrum/CN/polytope/LpInterface_inl.h>
33 #endif /* GUM_NO_INLINE */
34 
35 
36 namespace gum {
37  namespace credal {
38  namespace lp {
39 
40  /**
41  * class LpCol
42  */
43 
44  LpCol::LpCol(unsigned int id) : id__(id) { GUM_CONSTRUCTOR(LpCol); }
45 
47 
49 
50  /**
51  * class LpExpr
52  */
53 
55  ileft__(false), imiddle__(false), iright__(false), lValue__(0.),
56  mValue__(0.), rValue__(0.), lCoeffs__(new HashTable< LpCol, double >()),
57  mCoeffs__(new HashTable< LpCol, double >()),
58  rCoeffs__(new HashTable< LpCol, double >()) {
60  }
61 
62  LpExpr::LpExpr(const LpExpr& expr) :
66  lCoeffs__(new HashTable< LpCol, double >(*expr.lCoeffs__)),
67  mCoeffs__(new HashTable< LpCol, double >(*expr.mCoeffs__)),
68  rCoeffs__(new HashTable< LpCol, double >(*expr.rCoeffs__)) {
70  }
71 
73  bool copyLeft,
74  bool copyMiddle,
75  bool copyRight) :
76  ileft__(false),
77  imiddle__(false), iright__(false), lValue__(0.), mValue__(0.),
78  rValue__(0.), lCoeffs__(nullptr), mCoeffs__(nullptr),
79  rCoeffs__(nullptr) {
80  if (copyLeft) {
81  lCoeffs__ = new HashTable< LpCol, double >(*expr.lCoeffs__);
83  ileft__ = true;
84  } else
85  lCoeffs__ = new HashTable< LpCol, double >();
86 
87  if (copyMiddle) {
88  mCoeffs__ = new HashTable< LpCol, double >(*expr.mCoeffs__);
90  imiddle__ = true;
91  } else
92  mCoeffs__ = new HashTable< LpCol, double >();
93 
94  if (copyRight) {
95  rCoeffs__ = new HashTable< LpCol, double >(*expr.rCoeffs__);
97  iright__ = true;
98  } else
99  rCoeffs__ = new HashTable< LpCol, double >();
100 
102  }
103 
110  expr.lCoeffs__ = nullptr;
111  expr.mCoeffs__ = nullptr;
112  expr.rCoeffs__ = nullptr;
113 
115  }
116 
118  bool copyLeft,
119  bool copyMiddle,
120  bool copyRight) :
121  ileft__(false),
122  imiddle__(false), iright__(false), lValue__(0.), mValue__(0.),
123  rValue__(0.), lCoeffs__(nullptr), mCoeffs__(nullptr),
124  rCoeffs__(nullptr) {
125  if (copyLeft) {
128  ileft__ = true;
129  } else
130  lCoeffs__ = new HashTable< LpCol, double >();
131 
132  if (copyMiddle) {
135  imiddle__ = true;
136  } else
137  mCoeffs__ = new HashTable< LpCol, double >();
138 
139  if (copyRight) {
142  iright__ = true;
143  } else
144  rCoeffs__ = new HashTable< LpCol, double >();
145 
147  }
148 
150  delete lCoeffs__;
151  delete mCoeffs__;
152  delete rCoeffs__;
153 
155  }
156 
158  clear();
159 
160  mCoeffs__->insert(rhs, 1.);
161  imiddle__ = true;
162 
163  return *this;
164  }
165 
167  /// self assignment check to avoid hashTable copies
168  if (this == &rhs) return *this;
169 
170  *lCoeffs__ = *rhs.lCoeffs__;
171  *mCoeffs__ = *rhs.mCoeffs__;
172  *rCoeffs__ = *rhs.rCoeffs__;
173 
177 
178  ileft__ = rhs.ileft__;
181 
182  return *this;
183  }
184 
186  /// self assignment check to avoid hashTable copies
187  if (this == &rhs) return *this;
188 
192 
196 
197  ileft__ = rhs.ileft__;
200 
201  return *this;
202  }
203 
204 
206  if (ileft__ || iright__)
208  "expr::operator+= (expr) : <= present on one side of expr");
209 
210  if (!imiddle__) imiddle__ = true;
211 
212  mCoeffs__->getWithDefault(rhs, 0.) += 1.;
213 
214  return *this;
215  }
216 
218  if (ileft__ || iright__ || rhs.ileft__ || rhs.iright__)
220  "expr::operator+= (rhs) : <= present "
221  "on one side of rhs and/or expr");
222 
223  if (!imiddle__) imiddle__ = true;
224 
225  for (const auto& elt: *rhs.mCoeffs__)
227 
228  mValue__ += rhs.mValue__;
229 
230  return *this;
231  }
232 
234  if (ileft__ || iright__ || rhs.ileft__ || rhs.iright__)
236  "expr::operator+= (rhs) : <= present "
237  "on one side of rhs and/or expr");
238 
239  if (!imiddle__) {
240  imiddle__ = true;
243 
244  return *this;
245  }
246 
247  for (const auto& elt: *rhs.mCoeffs__)
249  mValue__ += rhs.mValue__;
250 
251  return *this;
252  }
253 
255  if (ileft__ || iright__)
257  "expr::operator-= (rhs) : <= present in one of expr");
258 
259  if (!imiddle__) imiddle__ = true;
260 
261  mCoeffs__->getWithDefault(rhs, 0.) -= 1.;
262 
263  return *this;
264  }
265 
267  if (ileft__ || iright__ || rhs.ileft__ || rhs.iright__)
268  GUM_ERROR(
270  "expr::operator-= (rhs) : <= present in one of rhs and/or expr");
271 
272  if (!imiddle__) imiddle__ = true;
273 
274  for (const auto& elt: *rhs.mCoeffs__)
276 
277  mValue__ -= rhs.mValue__;
278 
279  return *this;
280  }
281 
282 
283  void LpExpr::addSide__(const LpCol& from) {
284  if (!ileft__) {
285  lCoeffs__->insert(from, 1.);
286  ileft__ = true;
287  } else if (!imiddle__) {
288  mCoeffs__->insert(from, 1.);
289  imiddle__ = true;
290  } else if (!iright__) {
291  rCoeffs__->insert(from, 1.);
292  iright__ = true;
293  } else
295  "LpExpr::setSide ( const LpCol & from "
296  ") : too many <= ; no free side");
297  }
298 
299  void LpExpr::addSide__(const LpExpr& from) {
300  if (ileft__ && iright__ && from.imiddle__)
302  "LpExpr::setSide ( const LpCol & from "
303  ") : too many <= ; no free side");
304 
305  /// nothing to do, from is an empty LpExpr
306  if (!from.imiddle__) return;
307 
308  /// from only has middle side : this should be empty or has left side,
309  /// or has
310  /// left and middle side
311  if (!from.ileft__ && !from.iright__) {
312  if (!ileft__) {
315  ileft__ = true;
316 
317  return;
318  } else if (!imiddle__) {
321  imiddle__ = true;
322 
323  return;
324  } else if (!iright__) {
327  iright__ = true;
328 
329  return;
330  } else
332  "LpExpr::setSide ( const LpCol & from ) "
333  ": too many <= ; no free side");
334  }
335  /// from has left and middle side : this should be empty or has left
336  /// side
337  else if (from.ileft__ && !from.iright__) {
338  if (!ileft__) {
341  ileft__ = true;
342 
345  imiddle__ = true;
346 
347  return;
348  } else if (!imiddle__ && !iright__) {
351  imiddle__ = true;
352 
355  iright__ = true;
356 
357  return;
358  } else
360  "LpExpr::setSide ( const LpCol & from ) "
361  ": too many <= ; no free side");
362  }
363  /// from has left, middle and right side : this should be empty
364  /// to be exhaustive
365  else if (from.ileft__ && from.iright__) {
366  if (ileft__ || imiddle__ || iright__)
368  "LpExpr::setSide ( const LpCol & from ) "
369  ": too many <= ; no free side");
370 
371  *this = from;
372 
373  return;
374  } else
376  "LpExpr::setSide ( const LpCol & from "
377  ") : too many <= ; no free side");
378  }
379 
381  /// std::cout << from;
382  if (ileft__ && iright__ && from.imiddle__)
384  "LpExpr::setSide ( const LpCol & from "
385  ") : too many <= ; no free side");
386 
387  /// nothing to do, from is an empty LpExpr
388  if (!from.imiddle__) return;
389 
390  /// from only has middle side : this should be empty or has left side,
391  /// or has
392  /// left and middle side
393  if (!from.ileft__ && !from.iright__) {
394  if (!ileft__) {
395  ///* lCoeffs__ = * from.mCoeffs__;
398  ileft__ = true;
399 
400  return;
401  } else if (!imiddle__) {
402  ///* mCoeffs__ = * from.mCoeffs__;
405  imiddle__ = true;
406 
407  return;
408  } else if (!iright__) {
409  ///* rCoeffs__ = * from.mCoeffs__;
412  iright__ = true;
413 
414  return;
415  } else
417  "LpExpr::setSide ( const LpCol & from ) "
418  ": too many <= ; no free side");
419  }
420  /// from has left and middle side : this should be empty or has left
421  /// side
422  else if (from.ileft__ && !from.iright__) {
423  if (!ileft__) {
424  ///* lCoeffs__ = * from.lCoeffs__;
427  ileft__ = true;
428 
429  ///* mCoeffs__ = * from.mCoeffs__;
432  imiddle__ = true;
433 
434  return;
435  } else if (!imiddle__ && !iright__) {
436  ///* mCoeffs__ = * from.lCoeffs__;
439  imiddle__ = true;
440 
441  ///* rCoeffs__ = * from.mCoeffs__;
444  iright__ = true;
445 
446  return;
447  } else
449  "LpExpr::setSide ( const LpCol & from ) "
450  ": too many <= ; no free side");
451  }
452  /// from has left, middle and right side : this should be empty
453  /// to be exhaustive
454  else if (from.ileft__ && from.iright__) {
455  if (ileft__ || imiddle__ || iright__)
457  "LpExpr::setSide ( const LpCol & from ) "
458  ": too many <= ; no free side");
459 
460  *this = std::move(from);
461 
462  return;
463  } else
465  "LpExpr::setSide ( const LpCol & from "
466  ") : too many <= ; no free side");
467  }
468 
469 
470  void LpExpr::clear() {
471  lCoeffs__->clear();
472  mCoeffs__->clear();
473  rCoeffs__->clear();
474 
475  lValue__ = 0.;
476  mValue__ = 0.;
477  rValue__ = 0.;
478 
479  ileft__ = false;
480  imiddle__ = false;
481  iright__ = false;
482  }
483 
484  std::string LpExpr::toString() const {
486 
487  s << std::endl << "left side : " << std::endl;
488 
489  if (lCoeffs__ != nullptr)
490  for (const auto& elt: *lCoeffs__)
491  s << elt.first.toString() << " " << elt.second << " | ";
492 
493  s << std::endl << "middle side : " << std::endl;
494 
495  if (mCoeffs__ != nullptr)
496  for (const auto& elt: *mCoeffs__)
497  s << elt.first.toString() << " " << elt.second << " | ";
498 
499  s << std::endl << "right side : " << std::endl;
500 
501  if (rCoeffs__ != nullptr)
502  for (const auto& elt: *rCoeffs__)
503  s << elt.first.toString() << " " << elt.second << " | ";
504 
505  s << std::endl
506  << "lvalue : " << lValue__ << std::endl
507  << "mvalue : " << mValue__ << std::endl
508  << "rvalue : " << rValue__ << std::endl;
509 
510  s << std::endl;
511 
512  return s.str();
513  }
514 
515 
516  /**
517  * class LpRow
518  */
519 
520 
521  LpRow::LpRow(const LpExpr& expr, const std::vector< LpCol >& cols) :
522  coeffs__(nullptr) {
523  // we write 0 <= Ax + b from Ex + f <= Cx + d
524  if (expr.ileft__ && !expr.iright__) {
525  coeffs__ = new HashTable< LpCol, double >(*expr.mCoeffs__);
526 
527  for (const auto& col: cols) {
528  double col_coeff = 0.;
529 
530  // from left side to middle side : 0 <= middle - left
531  if (expr.lCoeffs__->exists(col))
533 
535  }
536 
538  } else if (expr.iright__ && !expr.ileft__) {
539  coeffs__ = new HashTable< LpCol, double >(*expr.rCoeffs__);
540 
541  for (const auto& col: cols) {
542  double col_coeff = 0;
543 
544  // from middle side to right side : 0 <= right - middle
545  if (expr.mCoeffs__->exists(col))
547 
549  }
550 
552  } else
554  "expr : " << expr.toString()
555  << "is not a valid inequality; no <= detected");
556 
557  if (coeffs__->size() == 0)
559  "expr : " << expr.toString()
560  << "is not a valid inequality; "
561  "no variable in inequality, "
562  "only constants");
563 
565  }
566 
567  LpRow::LpRow(LpExpr&& expr, const std::vector< LpCol >& cols) :
568  coeffs__(nullptr) {
569  /// we write 0 <= Ax + b from Ex + f <= Cx + d
570  if (expr.ileft__ && !expr.iright__) {
572 
573  for (const auto& col: cols) {
574  double col_coeff = 0;
575 
576  if (expr.lCoeffs__->exists(col))
578 
580  }
581 
583  } else if (expr.iright__ && !expr.ileft__) {
585 
586  for (const auto& col: cols) {
587  double col_coeff = 0;
588 
589  if (expr.mCoeffs__->exists(col))
591 
593  }
594 
596  } else
598  "expr : " << expr.toString()
599  << "is not a valid inequality; no <= detected");
600 
601  if (coeffs__->size() == 0)
603  "expr : " << expr.toString()
604  << "is not a valid inequality; "
605  "no variable in inequality, "
606  "only constants");
607 
609  }
610 
611  LpRow::LpRow(const LpRow& row) :
612  cste__(row.cste__),
613  coeffs__(new HashTable< LpCol, double >(*row.coeffs__)) {
615  }
616 
618  row.coeffs__ = nullptr;
619 
621  }
622 
623  LpRow::~LpRow() {
624  delete coeffs__;
625 
627  }
628 
629  LpRow& LpRow::operator=(const LpRow& row) {
630  cste__ = row.cste__;
631  *coeffs__ = *row.coeffs__;
632  return *this;
633  }
634 
636  cste__ = row.cste__;
638  return *this;
639  }
640 
642  out << row.toString();
643  return out;
644  }
645 
646  std::string LpRow::toString() const {
648 
649  s << "0 <= " << cste__;
650 
651  if (coeffs__ != nullptr) {
652  for (const auto& elt: *coeffs__) {
653  if (elt.second > 0) {
654  if (elt.second != 1) {
655  s << " +" << elt.second << "*" << elt.first.toString();
656  } else {
657  s << " +" << elt.first.toString();
658  }
659  } else {
660  if (elt.second < 0) {
661  if (elt.second != -1) {
662  s << " " << elt.second << "*" << elt.first.toString();
663  } else {
664  s << " -" << elt.first.toString();
665  }
666  }
667  }
668  }
669  }
670 
671  return s.str();
672  }
673 
674  } // namespace lp
675  } // namespace credal
676 } // namespace gum
INLINE void emplace(Args &&... args)
Definition: set_tpl.h:669
std::ostream & operator<<(std::ostream &out, const LpRow &row)
namespace for constraint-based description of credal sets
Definition: LpInterface.cpp:38
namespace for all credal networks entities
Definition: LpInterface.cpp:37