Hello,
For a project I am working on with a collaborator, I have the extreme points and the rays of a polyhedron. I have to obtain the facetious representation of this polyhedron. That is, I want a simple V to H conversion.
I have been working with polymake so far. My working code is:
#include <polymake/Main.h> #include <polymake/Matrix.h> #include <polymake/SparseMatrix.h> #include <polymake/Rational.h> using namespace polymake; int main(int argc, const char* argv[]) { try { Main pm; pm.set_application("polytope"); BigObject p("Polytope<Rational>"); std::vectorstd::string CoordinateLabels = { "extravar", "x1", "x2", "x3", "x4", "x5", "x6"}; std::vector<std::vector<Int>> Points; std::vector<Int> point; point = { 1,0,1,1,0,0,1 }; Points.push_back(point); point = { 1,1,0,0,1,1,0 }; Points.push_back(point); point = { 1,0,0,1,1,0,1 }; Points.push_back(point); point = { 1,1,0,0,1,1,0 }; Points.push_back(point); point = { 1,0,1,1,0,0,1 }; Points.push_back(point); point = { 1,1,0,0,1,1,0 }; Points.push_back(point); point = { 1,0,1,1,0,0,1 }; Points.push_back(point); point = { 1,0,0,0,1,1,1 }; Points.push_back(point); point = { 0,1,0,0,0,0,0 }; Points.push_back(point); point = { 0,0,1,0,0,0,0 }; Points.push_back(point); point = { 0,0,0,1,0,0,0 }; Points.push_back(point); point = { 0,0,0,0,1,0,0 }; Points.push_back(point); point = { 0,0,0,0,0,1,0 }; Points.push_back(point); point = { 0,0,0,0,0,0,1 }; Points.push_back(point); p.take("VERTICES") << Points; const Matrix<Rational> f = p.give("FACETS"); cout << "facets" << endl << f << endl; cout << "Dimension of the facets matrix are " << f.rows() << " and " << f.cols() << endl; cout << "Printing the facets for easy reading" << endl; for (int i = 0; i < f.rows(); i++) { cout << " Facet " << i << ": "; Rational rhs = f(i, 0); for (int j = 1; j < f.cols(); j++) { Rational coef = f(i, j); if (coef.is_zero() == false) { cout << " + (" << coef << " " << CoordinateLabels[j] << ") "; } } cout << " >= - (" << rhs << ")" << endl; } const Matrix<Rational> affine_hull = p.give("AFFINE_HULL"); cout << "affine hull" << endl << affine_hull << endl; cout << "Dimension of the affine hull matrix are " << affine_hull.rows() << " and " << affine_hull.cols() << endl; cout << "Printing the affine hull for easy reading" << endl; for (int i = 0; i < affine_hull.rows(); i++) { printf("AffineHull %d: ", i); Rational rhs = affine_hull(i, 0); for (int j = 1; j < affine_hull.cols(); j++) { Rational coef = affine_hull(i, j); if (coef.is_zero() == false) { cout << " + (" << coef << " " << CoordinateLabels[j] << ") "; } } cout << " = - (" << rhs << ")" << endl; } } catch (const std::exception& ex) { std::cerr << "ERROR: " << ex.what() << endl; return 1; } return 0; }
The code can also be seen on godbolt at : https://godbolt.org/z/Ko7zq4z64
The output of the above program is:
polymake: used package ppl The Parma Polyhedra Library ([[wiki:external_software#PPL]]): A C++ library for convex polyhedra and other numerical abstractions. http://www.cs.unipr.it/ppl/
facets -1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 -1 0 1 0 1 0 0 -1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 -1 1 0 0 0 0 1 0 0 0 0 0 0 1 -1 0 0 0 1 0 1 -1 0 0 0 0 1 1 1 0 0 0 0 0 0
Dimension of the facets matrix are 13 and 7 Printing the facets for easy reading Facet 0: + (1 x3) + (1 x5) >= - (-1) Facet 1: + (1 x3) >= - (0) Facet 2: + (1 x2) >= - (0) Facet 3: + (1 x2) + (1 x4) >= - (-1) Facet 4: + (1 x3) + (1 x4) >= - (-1) Facet 5: + (1 x4) >= - (0) Facet 6: + (1 x5) >= - (0) Facet 7: + (1 x1) >= - (0) Facet 8: + (1 x1) + (1 x6) >= - (-1) Facet 9: + (1 x6) >= - (0) Facet 10: + (1 x4) + (1 x6) >= - (-1) Facet 11: + (1 x5) + (1 x6) >= - (-1) Facet 12: >= - (1) affine hull
Dimension of the affine hull matrix are 0 and 7 Printing the affine hull for easy reading I have two queries:
(1) Is there a simple example that shows how the equivalent of the above functionality can be obtained in PPL via C/C+ code? I have looked at the PPL user manual, but I have to admit that it is quite forbidding in its size and details and it is not fully clear where in the document complete C/C++ examples are. I admit that this is possibly my lack of delving too deep into the manual.
I also notice that Polymake has solved this problem by calling PPL behind the scenes.
(2) Can the PPL code I write on Linux/WSL be used on a Windows Machine as well? I ask this because this is not a possibility in Polymake. Indeed, I was guided towards PPL as a result of my query on the Polymake forum. Polymake code cannot run on a Windows machine. I was wondering if PPL has this capability as suggested there. Please see that discussion at:
https://forum.polymake.org/viewtopic.php?f=8&p=3919
Thanks. Tryer