aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
gum::credal::LRSWrapper< GUM_SCALAR > Class Template Reference

Class template acting as a wrapper for Lexicographic Reverse Search by David Avis. More...

#include <agrum/CN/LrsWrapper.h>

Collaboration diagram for gum::credal::LRSWrapper< GUM_SCALAR >:
[legend]

Public Member Functions

Constructors / Destructors
 LRSWrapper ()
 Default Constructor.
 ~LRSWrapper ()
 Default Destructor.
Getters and setters
const matrix & getInput () const
 Get the intput matrix of the problem.
const matrix & getOutput () const
 Get the output matrix solution of the problem.
const unsigned int & getVerticesNumber () const
 Get the number of vertices of this polytope.
const GUM_SCALAR & getVolume () const
 Get the volume of the polytope that has been computed.
setUp / tearDown
void setUpH (const Size &card)
 Sets up an H-representation.
void setUpV (const Size &card, const Size &vertices)
 Sets up a V-representation.
void tearDown ()
 Reset the wrapper as if it was built.
void nextHInput ()
 Reset the wrapper for next computation for a H-representation with the same variable cardinality and number of inequalities.
Input filling methods
void fillH (const GUM_SCALAR &min, const GUM_SCALAR &max, const Size &modal)
 Creates the H-representation of min <= p(X=modal | .) <= max and add it to the problem input _input_.
void fillMatrix (const std::vector< std::vector< GUM_SCALAR > > &matrixmatrix)
 Fill the H-representation from the matrix given in argument.
void fillV (const std::vector< GUM_SCALAR > &vertex)
 Creates the V-representation of a polytope by adding a vertex to the problem input _input_.
lrs algorithms
void H2V ()
 H-representation to V-representation.
void V2H ()
 V-representation to H-representation.
void computeVolume ()
 Computes a polytope ( pseudo ) volume from it's V-representation.
void elimRedundVrep ()
 V-Redundancy elimination.

Private Types

enum class  _states_ : char {
  none = char(0) , Hup = char(1) , Vup = char(2) , H2Vready = char(3) ,
  V2Hready = char(4)
}
 The possible states of the LrsWrapper. More...
using matrix = typename std::vector< std::vector< GUM_SCALAR > >
 Shortcut for dynamic matrix using vectors.

Private Member Functions

lrs datas <-> wrapper datas
void _freeLrs_ ()
 Free lrs space.
void _initLrs_ ()
 Initialize lrs structs and first basis according to flags.
void _fill_ () const
 Fill lrs_dictionnary and datas from _input_ using integer rationals.
void _getLRSWrapperOutput_ (lrs_mp Nin, lrs_mp Din, std::vector< int64_t > &Num, std::vector< int64_t > &Den) const
 Translate a single output from lrs.

Private Attributes

matrix _input_
 Input matrix - either a V-representation or an H-representation.
matrix _output_
 Output matrix - either a V-representation or an H-representation.
unsigned int _card_
 Cardinality of the variable.
std::unordered_set< int > _insertedModals_
 To keep track of which constraints over modalities have been inserted.
unsigned int _vertices_
 The number of vertices of the polytope.
std::vector< std::vector< GUM_SCALAR > > _insertedVertices_
 To keep track of inserted vertices and total.
std::vector< GUM_SCALAR > _vertex_
 In case we have lower = upper for all modalities, a point probability, there is no need to use lrs.
_states_ _state_
 The current state of the LrsWrapper.
GUM_SCALAR _volume_
 The volume of the polytope, if computed, 0 otherwise.
const char * _setUpStateNames_ [5]
 To print an enum field name instead of it's value.
int _oldCout_
 File descriptor of standard cout.
lrs structs
lrs_dic * _dic_
 Structure for holding current dictionary and indices of lrs.
lrs_dat * _dat_
 Structure for holding static problem data of lrs.
lrs_mp_vector _lrsOutput_
 One line of output of lrs : aither a ray, a vertex, a facet or a linearity.
lrs_mp_matrix _Lin_
 Holds lrs input linearities if any are found.
flags
bool _getVolume_
bool _hull_
bool _polytope_

Detailed Description

template<GUM_Numeric GUM_SCALAR>
class gum::credal::LRSWrapper< GUM_SCALAR >

Class template acting as a wrapper for Lexicographic Reverse Search by David Avis.

Template Parameters
GUM_SCALARA floating type ( float, double, long double ... ).
Author
Matthieu HOURBRACQ and Pierre-Henri WUILLEMIN(_at_LIP6)

Definition at line 121 of file LrsWrapper.h.

Member Typedef Documentation

◆ matrix

template<GUM_Numeric GUM_SCALAR>
using gum::credal::LRSWrapper< GUM_SCALAR >::matrix = typename std::vector< std::vector< GUM_SCALAR > >
private

Shortcut for dynamic matrix using vectors.

Definition at line 123 of file LrsWrapper.h.

Member Enumeration Documentation

◆ _states_

template<GUM_Numeric GUM_SCALAR>
enum class gum::credal::LRSWrapper::_states_ : char
strongprivate

The possible states of the LrsWrapper.

Some functions will throw an exception if the state is not correct. It allows the user to avoid making - invisible - mistakes.

Enumerator
none 
Hup 
Vup 
H2Vready 
V2Hready 

Definition at line 157 of file LrsWrapper.h.

157 : char {
158 none = char(0),
159 Hup = char(1),
160 Vup = char(2),
161 H2Vready = char(3),
162 V2Hready = char(4),
163 };

Constructor & Destructor Documentation

◆ LRSWrapper()

template<GUM_Numeric GUM_SCALAR>
gum::credal::LRSWrapper< GUM_SCALAR >::LRSWrapper ( )

Default Constructor.

Definition at line 57 of file LrsWrapper_tpl.h.

57 {
59
60 _vertices_ = 0;
61 _card_ = 0;
62
63 _volume_ = 0;
64
65 _getVolume_ = false;
66 _hull_ = false;
67 _polytope_ = false;
68
70 }
Class template acting as a wrapper for Lexicographic Reverse Search by David Avis.
Definition LrsWrapper.h:121
_states_ _state_
The current state of the LrsWrapper.
Definition LrsWrapper.h:166
unsigned int _vertices_
The number of vertices of the polytope.
Definition LrsWrapper.h:141
LRSWrapper()
Default Constructor.
unsigned int _card_
Cardinality of the variable.
Definition LrsWrapper.h:134
GUM_SCALAR _volume_
The volume of the polytope, if computed, 0 otherwise.
Definition LrsWrapper.h:169

References LRSWrapper(), _card_, _getVolume_, _hull_, _polytope_, _state_, _vertices_, _volume_, and none.

Referenced by LRSWrapper(), and ~LRSWrapper().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ~LRSWrapper()

template<GUM_Numeric GUM_SCALAR>
gum::credal::LRSWrapper< GUM_SCALAR >::~LRSWrapper ( )

Default Destructor.

Definition at line 73 of file LrsWrapper_tpl.h.

73 {
75 }

References LRSWrapper().

Here is the call graph for this function:

Member Function Documentation

◆ _fill_()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::_fill_ ( ) const
private

Fill lrs_dictionnary and datas from _input_ using integer rationals.

Build polyhedron constraints and objective. Rational< GUM_SCALAR >::continuedFrac is the default algorithm used to approximate reals by integer rationals.

Definition at line 559 of file LrsWrapper_tpl.h.

559 {
560 std::size_t cols = _input_[0].size();
561
562 int64_t* num = new int64_t[cols]; // ISO C++ forbids variable length array,
563 // we need to do this instead
564 int64_t* den = new int64_t[cols];
565
566 int64_t rows = int64_t(_input_.size());
567
569
570 for (int64_t row = 0; row < rows; row++) {
571 for (std::size_t col = 0; col < cols; col++) {
575
576 num[col] = numerator;
578 }
579
580 /* GE is inequality, EQ is equation */
581 /* 1L, 0L respectively */
583 _dat_,
584 int64_t(row + 1),
585 num,
586 den,
587 1L); // do NOT forget this + 1 on row
588 }
589
590 delete[] num;
591 delete[] den;
592 }
static void continuedFracFirst(int64_t &numerator, int64_t &denominator, const GUM_SCALAR &number, const double &zero=config().epsilonStandard())
Find the first best rational approximation.
lrs_dat * _dat_
Structure for holding static problem data of lrs.
Definition LrsWrapper.h:198
matrix _input_
Input matrix - either a V-representation or an H-representation.
Definition LrsWrapper.h:127
lrs_dic * _dic_
Structure for holding current dictionary and indices of lrs.
Definition LrsWrapper.h:195

References _dat_, _dic_, _input_, and gum::Rational< GUM_SCALAR >::continuedFracFirst().

Referenced by _initLrs_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _freeLrs_()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::_freeLrs_ ( )
private

Free lrs space.

Definition at line 661 of file LrsWrapper_tpl.h.

661 {
662 /* free space : do not change order of next lines! */
663
665
666 if (_dat_->nredundcol > 0) lrs_clear_mp_matrix(_Lin_, _dat_->nredundcol, _dat_->n);
667
668 if (_dat_->runs > 0) {
669 free(_dat_->isave);
670 free(_dat_->jsave);
671 }
672
673 auto savem = _dic_->m; /* need this to clear _dat_*/
674
675 lrs_free_dic(_dic_, _dat_); /* deallocate lrs_dic */
676
677 _dat_->m = savem;
679
680 std::string name = "LrsWrapper:";
681 std::vector< char > chars(name.c_str(), name.c_str() + name.size() + 1u);
682
683 lrs_close(&chars[0]);
684 }
lrs_mp_vector _lrsOutput_
One line of output of lrs : aither a ray, a vertex, a facet or a linearity.
Definition LrsWrapper.h:203
lrs_mp_matrix _Lin_
Holds lrs input linearities if any are found.
Definition LrsWrapper.h:206

References _dat_, _dic_, _Lin_, and _lrsOutput_.

Referenced by computeVolume(), elimRedundVrep(), and H2V().

Here is the caller graph for this function:

◆ _getLRSWrapperOutput_()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::_getLRSWrapperOutput_ ( lrs_mp Nin,
lrs_mp Din,
std::vector< int64_t > & Num,
std::vector< int64_t > & Den ) const
private

Translate a single output from lrs.

Only vertices are supposed to be read at this step.

Parameters
NinInput numerators in mp format (returned by lrs).
DinInput denominators in mp format (returned by lrs).
NumOutput integer numerators.
DenOutput integer denominators.

Definition at line 501 of file LrsWrapper_tpl.h.

504 {
505 int64_t Nsize = (Nin[0] > 0) ? Nin[0] : -Nin[0];
506 int64_t Dsize = (Din[0] > 0) ? Din[0] : -Din[0];
507
508 int64_t num = 0L;
509 int64_t den = 0L;
510
511 int64_t tmp;
512
513 for (decltype(Nsize) i = Nsize - 1; i > 0; i--) {
514 tmp = Nin[i];
515
516 for (decltype(i) j = 1; j < i; j++)
517 tmp *= BASE;
518
519 num += tmp;
520 }
521
522 if (!(Din[0] == 2L && Din[1] == 1L)) { /* rational */
523 for (decltype(Dsize) i = Dsize - 1; i > 0; i--) {
524 tmp = Din[i];
525
526 for (decltype(i) j = 1; j < i; j++)
527 tmp *= BASE;
528
529 den += tmp;
530 }
531 } else {
532 den = 1L;
533 }
534
535 int64_t Nsign = ((Nin[0] < 0) ? -1L : 1L);
536 int64_t Dsign = ((Din[0] < 0) ? -1L : 1L);
537
538 if ((Nsign * Dsign) == -1L) num = -num;
539
540 Num.push_back(num);
541 Den.push_back(den);
542 }

References BASE.

Referenced by H2V().

Here is the caller graph for this function:

◆ _initLrs_()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::_initLrs_ ( )
private

Initialize lrs structs and first basis according to flags.

Definition at line 595 of file LrsWrapper_tpl.h.

595 {
598 "LRSWrapper< GUM_SCALAR >:: _initLrs_ : not ready, current state "
599 "is still : "
600 << _setUpStateNames_[static_cast< int >(_state_)]);
601
602 std::string name = "\n*LrsWrapper:";
603 std::vector< char > chars(name.c_str(), name.c_str() + name.size() + 1u);
604 // use &chars[0] as a char*
605
606 if (!lrs_init(&chars[0])) {
607 GUM_ERROR(FatalError, "LRSWrapper< GUM_SCALAR >:: _initLrs_ : failed lrs_init")
608 }
609
610 name = "LRSWrapper globals";
611 chars = std::vector< char >(name.c_str(), name.c_str() + name.size() + 1u);
612
614
615 if (_dat_ == nullptr) {
616 GUM_ERROR(FatalError, "LRSWrapper< GUM_SCALAR >:: _initLrs_ : failed lrs_alloc_dat")
617 }
618
619 _dat_->n = Size(_input_[0].size());
620 _dat_->m = Size(_input_.size());
621
622 _dat_->getvolume = (_getVolume_) ? 1L : 0L;
623 _dat_->hull = (_hull_) ? 1L : 0L;
624 _dat_->polytope = (_polytope_) ? 1L : 0L;
625
627
629
630 if (_dic_ == nullptr) {
631 GUM_ERROR(FatalError, "LRSWrapper< GUM_SCALAR >:: _initLrs_ : failed lrs_alloc_dic")
632 }
633
634 _fill_();
635
636 /* Pivot to a starting dictionary */
637 if (!lrs_getfirstbasis(&_dic_, _dat_, &_Lin_, 0L)) {
638 GUM_ERROR(FatalError, "LRSWrapper< GUM_SCALAR >:: _initLrs_ : failed lrs_getfirstbasis");
639 }
640
641 /* There may have been column redundancy */
642 /* If so the linearity space is obtained and redundant */
643 /* columns are removed. User can access linearity space */
644 /* from lrs_mp_matrix Lin dimensions nredundcol x d+1 */
645
646 decltype(_dat_->nredundcol) startcol = 0;
647
648 if (_dat_->homogeneous && _dat_->hull) {
649 startcol++; /* col zero not treated as redundant */
650
651 if (!_dat_->restart) {
652 for (decltype(_dat_->nredundcol) col = startcol; col < _dat_->nredundcol; col++)
654
655 GUM_ERROR(FatalError, "LRSWrapper< GUM_SCALAR >:: _initLrs_ : redundant columns !")
656 }
657 }
658 }
const char * _setUpStateNames_[5]
To print an enum field name instead of it's value.
Definition LrsWrapper.h:173
void _fill_() const
Fill lrs_dictionnary and datas from _input_ using integer rationals.

References _dat_, _dic_, _fill_(), _getVolume_, _hull_, _input_, _Lin_, _lrsOutput_, _polytope_, _setUpStateNames_, _state_, GUM_ERROR, H2Vready, and V2Hready.

Referenced by computeVolume(), elimRedundVrep(), and H2V().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ computeVolume()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::computeVolume ( )

Computes a polytope ( pseudo ) volume from it's V-representation.

Warning
Volume can only be computed using V-representation. H-representation volume computation is not predictable.
Probabilistic polytopes are not full dimensional : they lie in the simplex' hyper plane, therefore a pseudo-volume will be computed by projecting the polytope. The projection used is the lexicographically smallest coordinate subspace.

Definition at line 382 of file LrsWrapper_tpl.h.

382 {
385 "LRSWrapper< GUM_SCALAR >::computeVolume : "
386 "volume is only for V-representation or "
387 "fillV has not been called with all "
388 "vertices, current state is still : "
390
391 _getVolume_ = true;
392
393 _initLrs_();
394
395 do {
396 for (decltype(_dic_->d) col = 0, end = _dic_->d; col <= end; col++)
398 } while (lrs_getnextbasis(&_dic_, _dat_, 0L));
399
400 int64_t Nsize = (_dat_->Nvolume[0] > 0) ? _dat_->Nvolume[0] : -_dat_->Nvolume[0];
401 int64_t Dsize = (_dat_->Dvolume[0] > 0) ? _dat_->Dvolume[0] : -_dat_->Dvolume[0];
402
403 int64_t num = 0L, den = 0L;
404 int64_t tmp;
405
406 for (decltype(Nsize) i = Nsize - 1; i > 0; i--) {
407 tmp = _dat_->Nvolume[i];
408
409 for (decltype(i) j = 1; j < i; j++)
410 tmp *= BASE;
411
412 num += tmp;
413 }
414
415 for (decltype(Dsize) i = Dsize - 1; i > 0; i--) {
416 tmp = _dat_->Dvolume[i];
417
418 for (decltype(i) j = 1; j < i; j++)
419 tmp *= BASE;
420
421 den += tmp;
422 }
423
424 _volume_ = num * 1.0 / den;
425
426 _freeLrs_();
427 }
void _initLrs_()
Initialize lrs structs and first basis according to flags.
void _freeLrs_()
Free lrs space.

References _dat_, _dic_, _freeLrs_(), _getVolume_, _initLrs_(), _lrsOutput_, _setUpStateNames_, _state_, _volume_, BASE, GUM_ERROR, and V2Hready.

Here is the call graph for this function:

◆ elimRedundVrep()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::elimRedundVrep ( )

V-Redundancy elimination.

Eliminates redundant vertices from a polytope V-representation input input.

Definition at line 430 of file LrsWrapper_tpl.h.

430 {
433 "LRSWrapper< GUM_SCALAR >::elimRedundVrep : only for "
434 "V-representation or fillV has not been called with all vertices, "
435 "current state is still : "
436 << _setUpStateNames_[static_cast< int >(_state_)]);
437
438 _initLrs_();
439
440 int64_t* redineq; /* redineq[i]=0 if ineq i non-red,1 if red,2 linearity */
441
442 /*********************************************************************************/
443 /* Test each row of the dictionary to see if it is redundant */
444 /*********************************************************************************/
445
446 /* note some of these may have been changed in getting initial dictionary
447 */
448 auto m = _dic_->m_A;
449 auto d = _dic_->d;
450 /* number of linearities in input */ /* should be 0 ! */
451 auto nlinearity = _dat_->nlinearity;
452 auto lastdv = _dat_->lastdv;
453
454 /* linearities are not considered for redundancy */
455 redineq = (int64_t*)calloc(std::size_t(m + 1), sizeof(int64_t));
456
457 for (decltype(nlinearity) i = 0; i < nlinearity; i++)
458 redineq[_dat_->linearity[i]] = 2L;
459
460 /* rows 0..lastdv are cost, decision variables, or linearities */
461 /* other rows need to be tested */
462
463 for (decltype(m + d) index = lastdv + 1, end = m + d; index <= end; index++) {
464 /* input inequality number of current index */
465 auto ineq = _dat_->inequality[index - lastdv]; /* the input inequality number
466 corr. to this index */
467
469 }
470
471 /* linearities */
472 if (nlinearity > 0)
474 "LRSWrapper< GUM_SCALAR >::elimRedundVrep : not "
475 "reading a vertex but a linearity !");
476
477 /* count number of non-redundant inequalities */
478 /*
479 auto nredund = nlinearity;
480 for ( decltype ( m ) i = 1; i <= m; i++ )
481 if ( redineq[ i ] == 0 )
482 nredund++;
483 */
484
485 // __vertices = nredund;
486 // __output = std::vector< std::vector< GUM_SCALAR > > ( nredund,
487 // std::vector<
488 // GUM_SCALAR > ( _dat_->n - 1 ) );
489
490 for (decltype(m) i = 1; i <= m; i++)
491 if (redineq[i] == 0)
493 _input_[std::size_t(i - 1)].end()));
494
495 _vertices_ = (unsigned int)_output_.size();
496
497 _freeLrs_();
498 }
matrix _output_
Output matrix - either a V-representation or an H-representation.
Definition LrsWrapper.h:131

References _dat_, _dic_, _freeLrs_(), _initLrs_(), _input_, _output_, _setUpStateNames_, _state_, _vertices_, GUM_ERROR, and V2Hready.

Here is the call graph for this function:

◆ fillH()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::fillH ( const GUM_SCALAR & min,
const GUM_SCALAR & max,
const Size & modal )

Creates the H-representation of min <= p(X=modal | .) <= max and add it to the problem input _input_.

Parameters
minThe lower value of p(X=modal | .).
maxThe upper value of p(X=modal | .).
modalThe modality on which we put constraints.

Definition at line 206 of file LrsWrapper_tpl.h.

208 {
209 if (_state_ != _states_::Hup)
211 "LRSWrapper< GUM_SCALAR >::fillH : setUpH or nextInput has not "
212 "been called or H-representation is complete, current state is : "
213 << _setUpStateNames_[static_cast< int >(_state_)]);
214
215 if (modal >= _card_)
217 "LRSWrapper< GUM_SCALAR >::fillH : modality is "
218 "greater or equal than cardinality : "
219 << modal << " >= " << _card_);
220
221 _input_[modal * 2][0] = -min;
222 _input_[modal * 2][modal + 1] = 1;
223
224 _input_[modal * 2 + 1][0] = max;
225 _input_[modal * 2 + 1][modal + 1] = -1;
226
227 _vertex_[modal] = max;
228
229 _insertedModals_.insert(int(modal));
230
232 }
std::unordered_set< int > _insertedModals_
To keep track of which constraints over modalities have been inserted.
Definition LrsWrapper.h:138
std::vector< GUM_SCALAR > _vertex_
In case we have lower = upper for all modalities, a point probability, there is no need to use lrs.
Definition LrsWrapper.h:150

References _card_, _input_, _insertedModals_, _setUpStateNames_, _state_, _vertex_, GUM_ERROR, H2Vready, and Hup.

Referenced by gum::credal::CredalNet< GUM_SCALAR >::intervalToCredal().

Here is the caller graph for this function:

◆ fillMatrix()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::fillMatrix ( const std::vector< std::vector< GUM_SCALAR > > & matrix)

Fill the H-representation from the matrix given in argument.

Parameters
matrixThe H-representation of the polytope of the form 0 <= -b
  • Ax, A is the matrix, each column the coefficient of the variable in x.

Definition at line 235 of file LrsWrapper_tpl.h.

236 {
237 if (_state_ != _states_::Hup)
239 "LRSWrapper< GUM_SCALAR >::fillH : setUpH or nextInput has not "
240 "been called or H-representation is complete, current state is : "
241 << _setUpStateNames_[static_cast< int >(_state_)]);
242
243 if (matrix[0].size() - 1 != _card_)
245 "LRSWrapper< GUM_SCALAR >::fillMatrix : size is "
246 "different than cardinality : "
247 << (matrix[0].size() - 1) << " != " << _card_);
248
249 _input_ = matrix;
250
251 for (unsigned int modal = 0; modal < _card_; modal++) {
252 _insertedModals_.insert(modal);
253 }
254
256 }
typename std::vector< std::vector< GUM_SCALAR > > matrix
Shortcut for dynamic matrix using vectors.
Definition LrsWrapper.h:123

References _card_, _input_, _insertedModals_, _setUpStateNames_, _state_, GUM_ERROR, H2Vready, and Hup.

Referenced by gum::credal::lp::LpInterface< GUM_SCALAR >::solve().

Here is the caller graph for this function:

◆ fillV()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::fillV ( const std::vector< GUM_SCALAR > & vertex)

Creates the V-representation of a polytope by adding a vertex to the problem input _input_.

Parameters
vertexThe vertex we wish to add to the V-representation of the polytope.

Definition at line 259 of file LrsWrapper_tpl.h.

259 {
260 if (_state_ != _states_::Vup)
262 "LRSWrapper< GUM_SCALAR >::fillV : setUpV or nextInput has not "
263 "been called or V-representation is complete, current state is : "
264 << _setUpStateNames_[static_cast< int >(_state_)]);
265
266 if (_insertedVertices_.size() == _vertices_)
268 "LRSWrapper< GUM_SCALAR >::fillV : input is already full with " << _vertices_
269 << " vertices.");
270
271 bool eq = true;
272 const double epsilon = config().epsilonStandard();
273
274 for (const auto& v: _insertedVertices_) {
275 eq = true;
276
277 for (decltype(_card_) mod = 0; mod < _card_; mod++)
278 if (std::fabs(v[mod] - vertex[mod]) > epsilon) {
279 eq = false;
280 break;
281 }
282
283 if (eq) {
284 _vertices_--;
285 return;
286 // GUM_ERROR ( DuplicateElement, "LRSWrapper< GUM_SCALAR >::fillV :
287 // vertex
288 // already present : " << vertex );
289 }
290 }
291
292 auto row = _insertedVertices_.size();
293
294 for (decltype(_card_) mod = 0; mod < _card_; mod++)
295 _input_[row][mod + 1] = vertex[mod];
296
297 _insertedVertices_.push_back(vertex);
298
300 }
std::vector< std::vector< GUM_SCALAR > > _insertedVertices_
To keep track of inserted vertices and total.
Definition LrsWrapper.h:146

References _card_, _input_, _insertedVertices_, _setUpStateNames_, _state_, _vertices_, gum::config(), gum::Configuration::epsilonStandard(), GUM_ERROR, V2Hready, and Vup.

Here is the call graph for this function:

◆ getInput()

template<GUM_Numeric GUM_SCALAR>
auto gum::credal::LRSWrapper< GUM_SCALAR >::getInput ( ) const

Get the intput matrix of the problem.

Returns
A constant reference to the _intput_ matrix.

Definition at line 78 of file LrsWrapper_tpl.h.

78 {
79 return _input_;
80 }

References _input_.

◆ getOutput()

template<GUM_Numeric GUM_SCALAR>
auto gum::credal::LRSWrapper< GUM_SCALAR >::getOutput ( ) const

Get the output matrix solution of the problem.

Returns
A constant reference to the _output_ matrix.

Definition at line 83 of file LrsWrapper_tpl.h.

83 {
84 return _output_;
85 }

References _output_.

Referenced by gum::credal::CredalNet< GUM_SCALAR >::intervalToCredal(), and gum::credal::lp::LpInterface< GUM_SCALAR >::solve().

Here is the caller graph for this function:

◆ getVerticesNumber()

template<GUM_Numeric GUM_SCALAR>
const unsigned int & gum::credal::LRSWrapper< GUM_SCALAR >::getVerticesNumber ( ) const

Get the number of vertices of this polytope.

Returns
A constant reference to the number of vertices _vertices_.

Definition at line 88 of file LrsWrapper_tpl.h.

88 {
89 return _vertices_;
90 }

References _vertices_.

◆ getVolume()

template<GUM_Numeric GUM_SCALAR>
const GUM_SCALAR & gum::credal::LRSWrapper< GUM_SCALAR >::getVolume ( ) const

Get the volume of the polytope that has been computed.

Warning
Volume can only be computed using V-representation. H-representation volume computation is not predictable.
Probabilistic polytopes are not full dimensional : they lie in the simplex' hyper plane, therefore a pseudo-volume will be computed by projecting the polytope. The projection used is the lexicographically smallest coordinate subspace.
Returns
A constant reference to the polytope volume.

Definition at line 93 of file LrsWrapper_tpl.h.

93 {
94 if (_volume_ != 0) return _volume_;
95 else
97 "LRSWrapper< GUM_SCALAR >::getVolume () : "
98 "volume computation was not asked for this "
99 "credal set, call computeVolume() from a "
100 "V-representation.");
101 }

References _volume_, and GUM_ERROR.

◆ H2V()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::H2V ( )

H-representation to V-representation.

Computes the V-representation of a polytope, i.e. it's vertices, from it's H-representation, i.e. the hyper-plan inequalities.

Definition at line 303 of file LrsWrapper_tpl.h.

303 {
306 "LRSWrapper< GUM_SCALAR >::H2V : fillH has not been called with "
307 "all modalities, current state is still : "
308 << _setUpStateNames_[static_cast< int >(_state_)]);
309
310 // check that we have a credal set and not a precise point probability,
311 // i.e.
312 // sum of vertex elements is close to one ( floating type precision )
313 GUM_SCALAR sum = 0;
314
315 for (const auto elem: _vertex_)
316 sum += elem;
317
320 return;
321 }
322
323 // not precise point probability, initialize lrs
324
325 _initLrs_();
326
327 /* We initiate reverse search from this dictionary */
328 /* getting new dictionaries until the search is complete */
329 /* User can access each output line from output which is */
330 /* vertex/ray/facet from the lrs_mp_vector output */
331 /* prune is TRUE if tree should be pruned at current node */
332
333 // pruning is not used
334
335 std::vector< int64_t > Num; /* numerators of all vertices */
336 std::vector< int64_t > Den; /* denominators of all vertices */
337
338 do {
339 for (decltype(_dic_->d) col = 0, end = _dic_->d; col <= end; col++)
341 // iszero macro could be used here for the test on right
342 if (_dat_->hull
343 || ((((_lrsOutput_[0])[0] == 2 || (_lrsOutput_[0])[0] == -2)
344 && (_lrsOutput_[0])[1] == 0)
345 ? 1L
346 : 0L)) {
348 "LRSWrapper< GUM_SCALAR >::H2V : asked for "
349 "Q-hull computation or not reading a vertex !");
350 } else
351 for (decltype(_dat_->n) i = 1, end = _dat_->n; i < end; i++)
353 }
354 } while (lrs_getnextbasis(&_dic_, _dat_, 0L));
355
356 auto vtx = Num.size();
358
359 for (decltype(vtx) i = 1; i <= vtx; i++) {
360 vertex[(i - 1) % _card_] = GUM_SCALAR(Num[i - 1] * 1.0 / Den[i - 1]);
361
362 if (i % _card_ == 0) {
363 _output_.push_back(vertex);
364 _vertices_++;
365 }
366 }
367
368 _freeLrs_();
369 }
void _getLRSWrapperOutput_(lrs_mp Nin, lrs_mp Din, std::vector< int64_t > &Num, std::vector< int64_t > &Den) const
Translate a single output from lrs.

References _card_, _dat_, _dic_, _freeLrs_(), _getLRSWrapperOutput_(), _initLrs_(), _lrsOutput_, _output_, _setUpStateNames_, _state_, _vertex_, _vertices_, gum::config(), GUM_ERROR, H2Vready, and gum::isCloseToOne().

Referenced by gum::credal::CredalNet< GUM_SCALAR >::intervalToCredal(), and gum::credal::lp::LpInterface< GUM_SCALAR >::solve().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ nextHInput()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::nextHInput ( )

Reset the wrapper for next computation for a H-representation with the same variable cardinality and number of inequalities.

Usefull when creating credal networks specified as intervals over modalities.

Reset wrapper state _state_ to it's previous state and clear output matrix _output_. Keeps the cardinality _card_ of the variable and therefore the input matrix _intput_ structure.

Definition at line 176 of file LrsWrapper_tpl.h.

176 {
177 _insertedModals_.clear();
178 _insertedVertices_.clear();
179 _output_.clear();
180 _vertex_.clear();
181 _vertex_.resize(_card_, 0);
182
183 _volume_ = 0;
184 _vertices_ = 0;
185
186 _getVolume_ = false;
187 _hull_ = false;
188 _polytope_ = false;
189
191 else if (_state_ == _states_::V2Hready) {
194 "LRSWrapper< GUM_SCALAR >::nextHInput : only for H-representation "
195 "as input. Previous state was : "
196 << _setUpStateNames_[static_cast< int >(_state_)]);
197 } else {
198 _input_.clear();
200 _card_ = 0;
201 _vertex_.clear();
202 }
203 }

References _card_, _getVolume_, _hull_, _input_, _insertedModals_, _insertedVertices_, _output_, _polytope_, _setUpStateNames_, _state_, _vertex_, _vertices_, _volume_, GUM_ERROR, H2Vready, Hup, none, V2Hready, and Vup.

Referenced by gum::credal::CredalNet< GUM_SCALAR >::intervalToCredal().

Here is the caller graph for this function:

◆ setUpH()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::setUpH ( const Size & card)

Sets up an H-representation.

Initialize input matrix _input_ to correct dimensions and wrapper state _state_ to _states_::Hup.

Parameters
cardA constant reference to the cardinality of the variable.

Definition at line 104 of file LrsWrapper_tpl.h.

104 {
105 if (card < 2)
107 "LRSWrapper< GUM_SCALAR >::setUpH : "
108 "cardinality must be at least 2");
109
110 tearDown();
111
114
116 _input_[card * 2][0] = 1;
117
118 _input_[card * 2 + 1] = std::vector< GUM_SCALAR >(card + 1, 1);
119 _input_[card * 2 + 1][0] = -1;
120
122
124
126
127 _card_ = (unsigned int)card;
128 }
void tearDown()
Reset the wrapper as if it was built.

References _card_, _input_, _output_, _state_, _vertex_, GUM_ERROR, Hup, and tearDown().

Referenced by gum::credal::CredalNet< GUM_SCALAR >::intervalToCredal(), and gum::credal::lp::LpInterface< GUM_SCALAR >::solve().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ setUpV()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::setUpV ( const Size & card,
const Size & vertices )

Sets up a V-representation.

Initialize input matrix _input_ to correct dimensions and wrapper state _state_ to _states_::Vup.

Parameters
cardA constant reference to the cardinality of the variable.
verticesA constant reference to the number of vertices of the polytope.

Definition at line 131 of file LrsWrapper_tpl.h.

131 {
132 if (card < 2)
134 "LRSWrapper< GUM_SCALAR >::setUpV : "
135 "cardinality must be at least 2");
136
137 if (vertices < 2)
139 "LRSWrapper< GUM_SCALAR >::setUpV : vertices "
140 "must be at least 2 to build a polytope");
141
142 tearDown();
143
146
148
150
151 _card_ = (unsigned int)card;
152 _vertices_ = (unsigned int)vertices;
153 }

References _card_, _input_, _output_, _state_, _vertices_, GUM_ERROR, tearDown(), and Vup.

Here is the call graph for this function:

◆ tearDown()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::tearDown ( )

Reset the wrapper as if it was built.

Reset wrapper state _state_ to _states_::none and clear all member datas.

Definition at line 156 of file LrsWrapper_tpl.h.

156 {
157 _input_.clear();
158 _output_.clear();
159 _vertex_.clear();
160 _insertedModals_.clear();
161
162 _insertedVertices_.clear();
163 _vertices_ = 0;
164
165 _volume_ = 0;
166
168 _card_ = 0;
169
170 _getVolume_ = false;
171 _hull_ = false;
172 _polytope_ = false;
173 }

References _card_, _getVolume_, _hull_, _input_, _insertedModals_, _insertedVertices_, _output_, _polytope_, _state_, _vertex_, _vertices_, _volume_, and none.

Referenced by setUpH(), and setUpV().

Here is the caller graph for this function:

◆ V2H()

template<GUM_Numeric GUM_SCALAR>
void gum::credal::LRSWrapper< GUM_SCALAR >::V2H ( )

V-representation to H-representation.

Warning
Not complete yet.

Computes the H-representation of a polytope from it's V-representation.

Definition at line 372 of file LrsWrapper_tpl.h.

372 {
375 "LRSWrapper< GUM_SCALAR >::V2H : fillV has "
376 "not been called with all vertices, current "
377 "state is still : "
379 }

References _setUpStateNames_, _state_, GUM_ERROR, and V2Hready.

Member Data Documentation

◆ _card_

template<GUM_Numeric GUM_SCALAR>
unsigned int gum::credal::LRSWrapper< GUM_SCALAR >::_card_
private

Cardinality of the variable.

Definition at line 134 of file LrsWrapper.h.

Referenced by LRSWrapper(), fillH(), fillMatrix(), fillV(), H2V(), nextHInput(), setUpH(), setUpV(), and tearDown().

◆ _dat_

template<GUM_Numeric GUM_SCALAR>
lrs_dat* gum::credal::LRSWrapper< GUM_SCALAR >::_dat_
private

Structure for holding static problem data of lrs.

Definition at line 198 of file LrsWrapper.h.

Referenced by _fill_(), _freeLrs_(), _initLrs_(), computeVolume(), elimRedundVrep(), and H2V().

◆ _dic_

template<GUM_Numeric GUM_SCALAR>
lrs_dic* gum::credal::LRSWrapper< GUM_SCALAR >::_dic_
private

Structure for holding current dictionary and indices of lrs.

Definition at line 195 of file LrsWrapper.h.

Referenced by _fill_(), _freeLrs_(), _initLrs_(), computeVolume(), elimRedundVrep(), and H2V().

◆ _getVolume_

template<GUM_Numeric GUM_SCALAR>
bool gum::credal::LRSWrapper< GUM_SCALAR >::_getVolume_
private

Definition at line 213 of file LrsWrapper.h.

Referenced by LRSWrapper(), _initLrs_(), computeVolume(), nextHInput(), and tearDown().

◆ _hull_

template<GUM_Numeric GUM_SCALAR>
bool gum::credal::LRSWrapper< GUM_SCALAR >::_hull_
private

Definition at line 215 of file LrsWrapper.h.

Referenced by LRSWrapper(), _initLrs_(), nextHInput(), and tearDown().

◆ _input_

template<GUM_Numeric GUM_SCALAR>
matrix gum::credal::LRSWrapper< GUM_SCALAR >::_input_
private

Input matrix - either a V-representation or an H-representation.

Definition at line 127 of file LrsWrapper.h.

Referenced by _fill_(), _initLrs_(), elimRedundVrep(), fillH(), fillMatrix(), fillV(), getInput(), nextHInput(), setUpH(), setUpV(), and tearDown().

◆ _insertedModals_

template<GUM_Numeric GUM_SCALAR>
std::unordered_set< int > gum::credal::LRSWrapper< GUM_SCALAR >::_insertedModals_
private

To keep track of which constraints over modalities have been inserted.

When the set is full, the state changes from up to ready.

Definition at line 138 of file LrsWrapper.h.

Referenced by fillH(), fillMatrix(), nextHInput(), and tearDown().

◆ _insertedVertices_

template<GUM_Numeric GUM_SCALAR>
std::vector< std::vector< GUM_SCALAR > > gum::credal::LRSWrapper< GUM_SCALAR >::_insertedVertices_
private

To keep track of inserted vertices and total.

When set is full, the state changes from up to ready.

Definition at line 146 of file LrsWrapper.h.

Referenced by fillV(), nextHInput(), and tearDown().

◆ _Lin_

template<GUM_Numeric GUM_SCALAR>
lrs_mp_matrix gum::credal::LRSWrapper< GUM_SCALAR >::_Lin_
private

Holds lrs input linearities if any are found.

Definition at line 206 of file LrsWrapper.h.

Referenced by _freeLrs_(), and _initLrs_().

◆ _lrsOutput_

template<GUM_Numeric GUM_SCALAR>
lrs_mp_vector gum::credal::LRSWrapper< GUM_SCALAR >::_lrsOutput_
private

One line of output of lrs : aither a ray, a vertex, a facet or a linearity.

Definition at line 203 of file LrsWrapper.h.

Referenced by _freeLrs_(), _initLrs_(), computeVolume(), and H2V().

◆ _oldCout_

template<GUM_Numeric GUM_SCALAR>
int gum::credal::LRSWrapper< GUM_SCALAR >::_oldCout_
mutableprivate

File descriptor of standard cout.

Lrs writes a lot of stuff on standard cout. oldCout is used to save the current cout before redirecting it to /dev/null when calling lrs. The standard cout is restored when lrs is done.

Definition at line 189 of file LrsWrapper.h.

◆ _output_

template<GUM_Numeric GUM_SCALAR>
matrix gum::credal::LRSWrapper< GUM_SCALAR >::_output_
private

Output matrix - either a V-representation or an H-representation.

Definition at line 131 of file LrsWrapper.h.

Referenced by elimRedundVrep(), getOutput(), H2V(), nextHInput(), setUpH(), setUpV(), and tearDown().

◆ _polytope_

template<GUM_Numeric GUM_SCALAR>
bool gum::credal::LRSWrapper< GUM_SCALAR >::_polytope_
private

Definition at line 217 of file LrsWrapper.h.

Referenced by LRSWrapper(), _initLrs_(), nextHInput(), and tearDown().

◆ _setUpStateNames_

template<GUM_Numeric GUM_SCALAR>
const char* gum::credal::LRSWrapper< GUM_SCALAR >::_setUpStateNames_[5]
private
Initial value:
= {
enumStringify(_states_::nHup),
enumStringify(_states_::nVup),
enumStringify(_states_::nH2Vready),
enumStringify(_states_::nV2Hready),
}
#define enumStringify(name)
Definition LrsWrapper.h:105

To print an enum field name instead of it's value.

Used with GUM_ERROR.

Definition at line 173 of file LrsWrapper.h.

Referenced by _initLrs_(), computeVolume(), elimRedundVrep(), fillH(), fillMatrix(), fillV(), H2V(), nextHInput(), and V2H().

◆ _state_

template<GUM_Numeric GUM_SCALAR>
_states_ gum::credal::LRSWrapper< GUM_SCALAR >::_state_
private

The current state of the LrsWrapper.

Definition at line 166 of file LrsWrapper.h.

Referenced by LRSWrapper(), _initLrs_(), computeVolume(), elimRedundVrep(), fillH(), fillMatrix(), fillV(), H2V(), nextHInput(), setUpH(), setUpV(), tearDown(), and V2H().

◆ _vertex_

template<GUM_Numeric GUM_SCALAR>
std::vector< GUM_SCALAR > gum::credal::LRSWrapper< GUM_SCALAR >::_vertex_
private

In case we have lower = upper for all modalities, a point probability, there is no need to use lrs.

Definition at line 150 of file LrsWrapper.h.

Referenced by fillH(), H2V(), nextHInput(), setUpH(), and tearDown().

◆ _vertices_

template<GUM_Numeric GUM_SCALAR>
unsigned int gum::credal::LRSWrapper< GUM_SCALAR >::_vertices_
private

The number of vertices of the polytope.

Definition at line 141 of file LrsWrapper.h.

Referenced by LRSWrapper(), elimRedundVrep(), fillV(), getVerticesNumber(), H2V(), nextHInput(), setUpV(), and tearDown().

◆ _volume_

template<GUM_Numeric GUM_SCALAR>
GUM_SCALAR gum::credal::LRSWrapper< GUM_SCALAR >::_volume_
private

The volume of the polytope, if computed, 0 otherwise.

Definition at line 169 of file LrsWrapper.h.

Referenced by LRSWrapper(), computeVolume(), getVolume(), nextHInput(), and tearDown().


The documentation for this class was generated from the following files: