#26887 closed enhancement (fixed)
Implement the class CombinatorialPolyhedron
Reported by:  ghkliem  Owned by:  ghkliem 

Priority:  major  Milestone:  sage8.9 
Component:  geometry  Keywords:  polytopes, FindPoly, f_vector, face lattice, edge graph, ridge graph 
Cc:  stumpc5, jipilab, tscrim  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Jeroen Demeyer, Travis Scrimshaw, Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  39a7099 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
We construct a class CombinatorialPolyhedron?, which collects several methods for polyhedra depending only on the combinatorial type. Actually, most of the methods will work for atomic, coatomic Eulerian lattices.
Computations can be much faster when avoiding creating explicitly the face lattice.
Example:
P = polytopes.permutahedron(6) P.f_vector()
On my machine this takes over 8s, but it should be a matter of ms. For permutahedron(7)
it takes forever and should also be a matter of ms.
Additionally, one can create the face_lattice much faster. The face_lattice of permutahedron(7)
should only take few seconds. This is done by creating of lists of all faces and then quickly checking inclusions.
The crucial speed up is obtained by creating bitvectors for the faces, each bit corresponding to a vertex. Intersection of faces is then only bitwiseand and subset check is (A & ~B == 0). Both steps only take one CPU step per 64/128/256 bits/vertices (depending on the processor). Otherwise the algorithm is pretty similar to current algorithm to create the hasse_diagram
, except that it avoids double counting (and hence can calculate the f_vector
) without an explicit list of all faces.
The ticket will prepare, but not use, SIMDinstructions. Enabling them will be a subject of #27103.
FOLLOWUPS:
 implement calculation of entries in the flagvector, this might be better, than the calculation in the face_lattice
 Improve the calculation of properties of polytopes that depend on the facelattice (fvector,edges, ridges, kfaces in general, edgegraph, etc.)
 Enable SIMDinstructions.
Attachments (2)
Change History (244)
comment:1 Changed 2 years ago by
 Branch set to u/ghkliem/improve_f_vector_etc__for_polytopes
comment:2 Changed 2 years ago by
 Commit set to d0dba618e853d21724639c3e59964fa0f6610a11
comment:3 Changed 2 years ago by
 Commit changed from d0dba618e853d21724639c3e59964fa0f6610a11 to 3f1600e34b4415e95bb4db84cedb04089f8af677
comment:4 Changed 2 years ago by
 Owner changed from (none) to ghkliem
comment:5 Changed 2 years ago by
 Summary changed from Improve f_vector etc. for polytopes to Improve f_vector, edges, ridges, dimension for polyhedra
comment:6 Changed 2 years ago by
 Keywords f_vector face_lattic added
comment:7 Changed 2 years ago by
 Component changed from combinatorics to geometry
comment:8 Changed 2 years ago by
 Commit changed from 3f1600e34b4415e95bb4db84cedb04089f8af677 to 03fe21ff70eee06eb6dc2db477a003b58997d3d5
comment:9 Changed 2 years ago by
 Commit changed from 03fe21ff70eee06eb6dc2db477a003b58997d3d5 to 24949d9b8cacba08e72b0c1c028e6a6b25f5c9ec
Branch pushed to git repo; I updated commit sha1. New commits:
99eda99  Before Renaming CombinatorialType to CombinatorialPolytope

7efe6a2  After Renaming CombinatorialType to CombinatorialPolytope

24949d9  This should be mostly done now. Some minor changes are missing, also documentation needs to be done'

comment:10 Changed 2 years ago by
 Commit changed from 24949d9b8cacba08e72b0c1c028e6a6b25f5c9ec to 8c5d21aba0921aae210bd28cd2e9c212ec3c0920
Branch pushed to git repo; I updated commit sha1. New commits:
8c5d21a  some minor changes

comment:11 Changed 2 years ago by
 Commit changed from 8c5d21aba0921aae210bd28cd2e9c212ec3c0920 to a63c68f1eb5212448fd7e949306fdd7c26f53ac2
Branch pushed to git repo; I updated commit sha1. New commits:
a63c68f  Preparing a function to get all kfaces

comment:12 Changed 2 years ago by
 Commit changed from a63c68f1eb5212448fd7e949306fdd7c26f53ac2 to 580980bbe979925797b02063bd28321dbd17efbd
Branch pushed to git repo; I updated commit sha1. New commits:
580980b  some work on generating all kfaces of the polyhedron

comment:13 Changed 2 years ago by
 Commit changed from 580980bbe979925797b02063bd28321dbd17efbd to 591ed2645b71f532d253e9ff55c5c484d362f252
Branch pushed to git repo; I updated commit sha1. New commits:
591ed26  hasse_diagram is mostly working now, it is much faster than the old hasse_diagram of polyhedron

comment:14 Changed 2 years ago by
 Description modified (diff)
 Keywords face lattice flag vector edge graph ridge grapg added; face_lattic removed
comment:15 Changed 2 years ago by
 Commit changed from 591ed2645b71f532d253e9ff55c5c484d362f252 to 576905d8901190c042bba4251bf80e2f2eb8ec0f
Branch pushed to git repo; I updated commit sha1. New commits:
576905d  flag vectors seem to work now

comment:16 Changed 2 years ago by
 Commit changed from 576905d8901190c042bba4251bf80e2f2eb8ec0f to 4a4171152dbdec4340328a52cb2b50f121f11176
Branch pushed to git repo; I updated commit sha1. New commits:
4a41711  changed the name from CombinatorialPolytope to CombinatorialPolyhedron

comment:17 Changed 2 years ago by
 Commit changed from 4a4171152dbdec4340328a52cb2b50f121f11176 to e3454704fe64cfadfb5c54897e60dde9d0ad4ed3
Branch pushed to git repo; I updated commit sha1. New commits:
e345470  This should be ready for review

comment:18 Changed 2 years ago by
 Status changed from new to needs_review
comment:19 Changed 2 years ago by
I'm not experienced at what point a ticket should change its status to "needs review". Of course there is still stuff that I can do by myself like documentation and comments.
I would definitely be grateful for comments and help at this point. At this point everything should work at least I'm not aware of any bugs.
comment:20 followup: ↓ 22 Changed 2 years ago by
As a start you can write examples (see the developer guide).
Next, it is not a very often not a good idea to write Python in C. It is hard to read and often difficult to do right (e.g. check memory allocation, ensure compatibility Python2/Python3). You should use Cython for that purpose, unless there is a very good reason for that.
As you use advanced CPU instructions you should check very carefully that your code does work on all architectures (ie Intel since Pentium II as well as AMD).
comment:21 Changed 2 years ago by
 Commit changed from e3454704fe64cfadfb5c54897e60dde9d0ad4ed3 to d897cd16dfab25e20936b4d67b0b5f7c393a48a2
Branch pushed to git repo; I updated commit sha1. New commits:
d897cd1  Added Examples, also fixed the empty Polyhedron

comment:22 in reply to: ↑ 20 ; followups: ↓ 23 ↓ 56 Changed 2 years ago by
I added examples.
I tried Cython, but didn't get the desired speedup. It was much faster than what is implemented in Polyhedron though. I started doing it in cython, but I couldn't get array access (via pointers) in a speed even close to C. Now with using intrinsics I'm close to 4 times as fast then without intrinsics. The crucial step in the algorithm is subset check as A & ~B == 0 for long bit vectors A and B.
We want to build a Database for Polytopes (similar to FindStat?) and thus we want to be able to fastly compute f_vectors even for large polytopes. This is the f_vector of a 20dimensional counter example to the Hirsch conjecture. It only takes about 3 minutes to calculate now:
(1, 36425, 364250, 1846226, 6234909, 15556845, 30191256, 46918071, 59410131, 61931131, 53428829, 38194318, 22569116, 10954980, 4322157, 1364130, 336525, 62752, 8419, 754, 40, 1)
In Cython I was able to calculate this vector (or more important the edge graph) in something like 3 hours, in C it took me 20 minutes. Then I started doing bitwise operations and intrinsics and it is now down to 3 minutes with AVX2.
As for the CPU instructions: I'm prechecking the compiler flags. So if nothing works it just falls back to computing with uint64_t which should work on any machine.
As for memory leaks: It seems to work fine now. Python calls the dealloc() function at closup and when deleting the class and clears all the alloced memeory in C.
Replying to vdelecroix:
As a start you can write examples (see the developer guide).
Next, it is not a very often not a good idea to write Python in C. It is hard to read and often difficult to do right (e.g. check memory allocation, ensure compatibility Python2/Python3). You should use Cython for that purpose, unless there is a very good reason for that.
As you use advanced CPU instructions you should check very carefully that your code does work on all architectures (ie Intel since Pentium II as well as AMD).
comment:23 in reply to: ↑ 22 ; followup: ↓ 24 Changed 2 years ago by
Replying to ghkliem:
I added examples.
I tried Cython, but didn't get the desired speedup.
That means that you don't know how to use Cython. Any C code can be written in plain Cython. Though I never said that you should rewrite everything using Cython. I am sorry if it was unclear. I adviced you to to rewrite the Python <> C gluing part. More precisely, the C code would better not involve any Python at all. And you may write an independent Cython file that will call the C code appropriately.
comment:24 in reply to: ↑ 23 Changed 2 years ago by
Replying to vdelecroix:
Replying to ghkliem:
I added examples.
I tried Cython, but didn't get the desired speedup.
That means that you don't know how to use Cython. Any C code can be written in plain Cython.
That is correct. I'm mostly happy if anything works at all. Once this is the case, I try to make it somewhat nice. It looked to me as if one was supposed to use memoryviews in Cython. They where the fastest working with plain C arrays. But then I couldn't initialize an array in a size determined at runtime. Anyway, as I understand having the code in C is not the problem here.
Though I never said that you should rewrite everything using Cython. I am sorry if it was unclear. I adviced you to to rewrite the Python <> C gluing part. More precisely, the C code would better not involve any Python at all. And you may write an independent Cython file that will call the C code appropriately.
This sounds very reasonable. I will do so. When I first started with this, I didn't use Cython in between, so my C code had to return a Python object. But it makes sense to build a Python object in an environment that was meant for this. Building tuples etc. was a pain in C and it did always feel like a workaround. I never gave it any second thought though.
comment:25 Changed 2 years ago by
 Cc jipilab added
comment:26 Changed 2 years ago by
 Commit changed from d897cd16dfab25e20936b4d67b0b5f7c393a48a2 to bc21ffa2b7e4058f01da08ecc86911c7dfab538a
Branch pushed to git repo; I updated commit sha1. New commits:
bc21ffa  Work toward cleaing up the Python <> C gluing part

comment:27 Changed 2 years ago by
 Milestone changed from sage8.5 to sage8.7
comment:28 Changed 2 years ago by
These doctests are not reproducible.
sage: P = polytopes.permutahedron(6) sage: %time CombinatorialPolyhedron(P).face_lattice(vertices=False,facets=False) CPU times: user 400 ms, sys: 20 ms, total: 420 ms Wall time: 380 ms Finite lattice containing 4684 elements sage: %time CombinatorialPolyhedron(P).face_lattice(vertices=True,facets=True) CPU times: user 2.48 s, sys: 60 ms, total: 2.54 s Wall time: 2.4 s Finite lattice containing 4684 elements sage: %time CombinatorialPolyhedron(P).face_lattice(vertices=True,facets=False) #default CPU times: user 1.87 s, sys: 48 ms, total: 1.92 s Wall time: 1.76 s Finite lattice containing 4684 elements
You should check that tests pass using sage t long FILENAME
.
comment:29 Changed 2 years ago by
 Status changed from needs_review to needs_work
The function CombinatorialPolyhedron::get_flag_number(PyObject* py_tuple)
and many others are very likely to crash Sage (e.g. you do not take care of any error handling). I strongly advice you to avoid any Python in C/C++. The conversion tuple > C++ vector is very easily done in Cython which automatically handles conversions and errors.
comment:30 Changed 2 years ago by
 Commit changed from bc21ffa2b7e4058f01da08ecc86911c7dfab538a to 152db94b0d7f496a7efab3f5afe33395e1e3baf1
comment:31 Changed 2 years ago by
 Commit changed from 152db94b0d7f496a7efab3f5afe33395e1e3baf1 to b78d53372e111e7a34f77aea3735effd66cd2b09
Branch pushed to git repo; I updated commit sha1. New commits:
b78d533  Initialization: Fixed Python <> C gluing

comment:32 followup: ↓ 33 Changed 2 years ago by
This doesn't build for me on OS X:
gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall Wnounused I./sage/geometry/polyhedron/combinatorial_polyhedron I/Users/jpalmier/Desktop/Sage/git/sage/local/include I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/sitepackages/numpy/core/include I/Users/jpalmier/Desktop/Sage/git/sage/src I/Users/jpalmier/Desktop/Sage/git/sage/src/sage/ext Ibuild/cythonized I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 c sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc o build/temp.macosx10.9x86_642.7/sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.o fnostrictaliasing DCYTHON_CLINE_IN_TRACEBACK=1 I/Users/jpalmier/Desktop/Sage/git/sage/local/include/m4ri I/Users/jpalmier/Desktop/Sage/git/sage/local/include g fPIC Wall O2 mmmx msse msse2 msse3 O3 march=native std=c++11 In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:3: In file included from /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/Python.h:88: /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:534:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj, /* Object */ ^~~~~~~~~ /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:553:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj /* Object */ ^~~~~~~~~ /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:575:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register const wchar_t *w, /* wchar_t buffer */ ^~~~~~~~~ /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:593:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register wchar_t *w, /* wchar_t buffer */ ^~~~~~~~~ In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:3: In file included from /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/Python.h:97: /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/stringobject.h:173:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj, /* string or Unicode object */ ^~~~~~~~~ /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/stringobject.h:174:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register char **s, /* pointer to buffer variable */ ^~~~~~~~~ /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/stringobject.h:175:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register Py_ssize_t *len /* pointer to length variable or NULL ^~~~~~~~~ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:129:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(edges); ^ [] ./sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.h:95:32: note: allocated with 'new[]' here unsigned int **edges = new unsigned int *[maxnumberedges]; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:130:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(ridges); ^ [] ./sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.h:96:33: note: allocated with 'new[]' here unsigned int **ridges = new unsigned int *[maxnumberedges]; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:131:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(incidences); ^ [] ./sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.h:97:38: note: allocated with 'new[]' here unsigned long **incidences = new unsigned long *[maxnumberincidences](); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:123:20: warning: unused variable 'j' [Wunusedvariable] unsigned int i,j; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:123:18: warning: unused variable 'i' [Wunusedvariable] unsigned int i,j; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:194:18: warning: unused variable 'dim' [Wunusedvariable] unsigned int dim = get_dimension(); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:272:18: warning: unused variable 'dim' [Wunusedvariable] unsigned int dim = get_dimension(); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:428:19: warning: unused variable 'n' [Wunusedvariable] unsigned long n; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:443:19: warning: unused variable 'n' [Wunusedvariable] unsigned long n; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:532:22: error: variablesized object may not be initialized int addfacearray[lenfaces] = { }; ^~~~~~~~ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:585:32: error: use of undeclared identifier 'aligned_alloc' nextfaces_creator[i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:607:32: error: use of undeclared identifier 'aligned_alloc' nextfaces_creator[i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:655:20: warning: unused variable 'j' [Wunusedvariable] unsigned int i,j; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:689:20: warning: unused variable 'j' [Wunusedvariable] unsigned int i,j; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:733:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(array); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:722:23: note: allocated with 'new[]' here uint64_t *array = new uint64_t [size_array](); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:719:20: warning: unused variable 'j' [Wunusedvariable] unsigned int i,j; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:720:18: warning: unused variable 'entry' [Wunusedvariable] unsigned int entry, position, value; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:791:9: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(saverarray); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:773:34: note: allocated with 'new[]' here unsigned long **saverarray = new unsigned long *[const_len]; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:800:13: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(saverarray); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:773:34: note: allocated with 'new[]' here unsigned long **saverarray = new unsigned long *[const_len]; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:834:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete (saverarray); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:773:34: note: allocated with 'new[]' here unsigned long **saverarray = new unsigned long *[const_len]; ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:883:9: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(old_facets_walker); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:867:43: note: allocated with 'new[]' here unsigned int *old_facets_walker = new unsigned int [size_three](); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:967:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(array); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:954:23: note: allocated with 'new[]' here uint64_t *array = new uint64_t [size_array](); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:993:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(array); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:979:23: note: allocated with 'new[]' here uint64_t *array = new uint64_t [size_array](); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1026:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(array); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1014:23: note: allocated with 'new[]' here uint64_t *array = new uint64_t [size_array](); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1049:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [Wmismatchednewdelete] delete(array); ^ [] sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1039:23: note: allocated with 'new[]' here uint64_t *array = new uint64_t [size_array](); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1163:31: error: use of undeclared identifier 'aligned_alloc' facets_allocator[i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1188:33: error: use of undeclared identifier 'aligned_alloc' vertices_allocator[i] = aligned_alloc(chunksize/8,length_of_face_in_facet_repr*chunksize/8); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1220:40: error: use of undeclared identifier 'aligned_alloc' newfaces_allocator[i][j] = aligned_alloc(chunksize/8,length_of_face*chunksize/8); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1270:64: error: use of undeclared identifier 'aligned_alloc' allfaces_allocator[dimension_to_allocate][i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8); ^ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1272:75: error: use of undeclared identifier 'aligned_alloc' allfaces_facet_repr_allocator[dimension_to_allocate][i] = aligned_alloc(chunksize/8,length_of_face_in_facet_repr*chunksize/8); ^ 29 warnings and 8 errors generated.
comment:33 in reply to: ↑ 32 Changed 2 years ago by
Thanks for going through the effort of building that on your machine.
It seems to me that there are the following issues:
 aligned_alloc as used by me only works for C++11 and needs a different header in C++17
 #include <Python.h> doesn't work at all, which it should, so this seems to be a seperate problem, this will go out, as all the functions requiring python objects where replaced
 new/delete works differently on C++17 or my version is just not clean, I will take a look at whats going on
Replying to jhpalmieri:
This doesn't build for me on OS X:
comment:34 Changed 2 years ago by
 Commit changed from b78d53372e111e7a34f77aea3735effd66cd2b09 to dc0455d6a48a040fffe6f70f2d1082e96855c4c3
comment:35 Changed 2 years ago by
I should have checked first..., this doesn't work
comment:36 Changed 2 years ago by
 Commit changed from dc0455d6a48a040fffe6f70f2d1082e96855c4c3 to 80f4e33dcecef1034f7edce36c112513b245d59d
Branch pushed to git repo; I updated commit sha1. New commits:
7557ecd  fixing the calculation of the dimension

e32d0f6  changed names of variables to not overload dimension of CombinatorialPolyhedron

80f4e33  Fixed issue: edges, ridges and incidences should be initialized in order for delete to work properly

comment:37 Changed 2 years ago by
 Commit changed from 80f4e33dcecef1034f7edce36c112513b245d59d to a89c37b4519548bb512dd5f9b6934cce0772b250
Branch pushed to git repo; I updated commit sha1. New commits:
a89c37b  More work with trivial Polyehedra, they should work now

comment:38 Changed 2 years ago by
++ EXAMPLE::
should be
++ EXAMPLES::
comment:39 Changed 2 years ago by
 Commit changed from a89c37b4519548bb512dd5f9b6934cce0772b250 to 0eedbb966da75f6f11bb0b03ff19dfe6a93cb4fb
Branch pushed to git repo; I updated commit sha1. New commits:
0eedbb9  fixed an issue with unbounded Polyhedra and CombinatorialPolyhedron.faces(0), also fixed Halfspaces

comment:40 Changed 2 years ago by
 Commit changed from 0eedbb966da75f6f11bb0b03ff19dfe6a93cb4fb to b37feb7c30468705d151fb58c501968ce07b2371
Branch pushed to git repo; I updated commit sha1. New commits:
b37feb7  all tests passed, however there are still examples missing starting at the function faces

comment:41 Changed 2 years ago by
 Commit changed from b37feb7c30468705d151fb58c501968ce07b2371 to 829ec2acbfbf3360c8b94184935a097541a744ef
comment:42 Changed 2 years ago by
 Commit changed from 829ec2acbfbf3360c8b94184935a097541a744ef to b513eb2a0e9b547297ef5c6ac4b9f95c1f1a184b
comment:43 Changed 2 years ago by
 Commit changed from b513eb2a0e9b547297ef5c6ac4b9f95c1f1a184b to a176af156c820c31791e1dcef05b3e62e70e5b25
comment:44 Changed 2 years ago by
 Commit changed from a176af156c820c31791e1dcef05b3e62e70e5b25 to a2f90adfbeba067766b7538cadd50830015eda41
Branch pushed to git repo; I updated commit sha1. New commits:
a2f90ad  corrected edges and ridges a polyhedron with two vertices

comment:45 Changed 2 years ago by
 Commit changed from a2f90adfbeba067766b7538cadd50830015eda41 to 46f95556da205a8b2cfe28c4aeeff807321714c1
Branch pushed to git repo; I updated commit sha1. New commits:
46f9555  added a macro to ensure aligned_alloc exists,

comment:46 Changed 2 years ago by
 Status changed from needs_work to needs_review
comment:47 followup: ↓ 50 Changed 2 years ago by
Still doesn't build on OS X:
gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall Wnounused I./sage/geometry/polyhedron/combinatorial_polyhedron I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7 I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/lib/python2.7/sitepackages/numpy/core/include I/Users/palmieri/Desktop/Sage_stuff/git/sage/src I/Users/palmieri/Desktop/Sage_stuff/git/sage/src/sage/ext Ibuild/cythonized I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7 c sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc o build/temp.macosx10.9x86_642.7/sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.o fnostrictaliasing DCYTHON_CLINE_IN_TRACEBACK=1 O3 march=native std=c++11 In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:13: In file included from /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/Python.h:88: /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:534:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj, /* Object */ ^~~~~~~~~ /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:553:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj /* Object */ ^~~~~~~~~ /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:575:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register const wchar_t *w, /* wchar_t buffer */ ^~~~~~~~~ /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:593:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register wchar_t *w, /* wchar_t buffer */ ^~~~~~~~~ In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:13: In file included from /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/Python.h:97: /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/stringobject.h:173:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj, /* string or Unicode object */ ^~~~~~~~~ /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/stringobject.h:174:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register char **s, /* pointer to buffer variable */ ^~~~~~~~~ /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/stringobject.h:175:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register Py_ssize_t *len /* pointer to length variable or NULL ^~~~~~~~~ sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:717:22: error: variablesized object may not be initialized int addfacearray[constlenfaces] = { }; ^~~~~~~~~~~~~ 7 warnings and 1 error generated.
Cython would be so much easier.
comment:48 Changed 2 years ago by
 Commit changed from 46f95556da205a8b2cfe28c4aeeff807321714c1 to 1971dd77286848ccb7f069c3b0f71feb7c197272
Branch pushed to git repo; I updated commit sha1. New commits:
6ae3dd4  Fixed issue with PopCount, PopCount requires header immintin, which was only included when AVX2 was availabe

05635c9  replace iterator.next() by next(iterator) in test for Python 3

1971dd7  removed geometry/all.py from ticket, removed geometry/polyhedron/base.py from ticket

comment:49 Changed 2 years ago by
 Commit changed from 1971dd77286848ccb7f069c3b0f71feb7c197272 to de57d7f3af7eb52f8ed2cee17184a6cbec3fb134
comment:50 in reply to: ↑ 47 Changed 2 years ago by
Should be fixed.
I don't know why I didn't remove Python.h, it sure wasn't needed anymore. (Except that it included stdint). However, the pure inclusion of the Python module in C should not give an error.
Replying to jhpalmieri:
Still doesn't build on OS X:
Cython would be so much easier.
For me, Cython was not easier. I couldn't get the things done the way I wanted. Once you know what should be done in C exactly, then it is probably easier. Now that I have written the code in C++, I could probably do it in Cython as well. When I searched for specific questions in Cython, I just couldn't get any result, but in C or C++ there are tons of helps on the web that helped me. I am a complete newbie in programming. It feels to me that I aquired at least half of my knowledge through this project. From Cython to C/C++ I had a speedup of about 20 on large Polytopes, probably just because translating it to pure C/C++ helped me better understand what the machine is doing and can be doing.
comment:51 Changed 2 years ago by
 Commit changed from de57d7f3af7eb52f8ed2cee17184a6cbec3fb134 to 882ce7189a0a1b4c6d29baaa6c01e13bb16f5c71
Branch pushed to git repo; I updated commit sha1. New commits:
882ce71  Interchanged long tests

comment:52 Changed 2 years ago by
 Commit changed from 882ce7189a0a1b4c6d29baaa6c01e13bb16f5c71 to f5c87d83fc288f0cde3767e39713a957dfbfa270
Branch pushed to git repo; I updated commit sha1. New commits:
f5c87d8  I missed a polytopes.Polyhedron(7), this was taken out now

comment:53 Changed 2 years ago by
 Commit changed from f5c87d83fc288f0cde3767e39713a957dfbfa270 to de03b8be97be9e77bfdbc27b142509cec353b947
comment:54 Changed 2 years ago by
 Description modified (diff)
 Summary changed from Improve f_vector, edges, ridges, dimension for polyhedra to Implement the class CombinatorialPolyhedron
comment:55 followup: ↓ 64 Changed 2 years ago by
 Status changed from needs_review to needs_work
Some purely technical points about the programming:
 We generally discourage putting
Extension
parameters inmodule_list.py
. Better use# distutils
declarations in Cython files. See https://cython.readthedocs.io/en/latest/src/userguide/source_files_and_compilation.html#sourcefilesandcompilation for examples.
march=native
is not acceptable since we want to distribute binaries. Moreover, it makes no sense to compile just this specific file withmarch=native
. If you want to addmarch=native
, it should probably be added as compilation flag for all packages (or at least for Python, such that it applies to all Python packages). If you want to go through with this, you should open a new ticket for that. Also note that the optionmarch=native
itself is not portable: there be a check that the compiler actually understands it.
 The
O3
option is the default, so that's redundant.
 You have very long lines in your sources. You should try to wrap them to less than 80 characters per line.
 You're adding a lot of C/Cython code without a single
sig_on
/sig_check
. That's suspicious as such code cannot be interrupted. See https://cysignals.readthedocs.io/en/latest/interrupt.html#interrupthandling
 While you're at it, you could also use the cysignals memory allocation functions instead of
PyMem_...
.
hasse_diagram.cc
contains various trivial functions which could easily be replaced by Cython. For example, the various accessor functions could be replaced by just accessing the attributes in Cython (this requires that the classCombinatorialPolyhedron
is actually declared in Cython). Alsodelete_CombinatorialPolyhedron(C)
could be replaced by justdel C
.
 This is just advice: it's also possible to just include the
.cc
file in the.pyx
file usingcdef extern from "hasse_diagram.cc"
. That way, you can avoid the.h
file and you give more optimization opportunities to the compiler, since everything is compiled in one C++ file.
 I'm very worried about portability: you seem to be using a lot of compilerspecific and CPUspecific code. I don't know whether anything will actually break, but there is a substantial risk.
 Typo:
memomory
>memory
comment:56 in reply to: ↑ 22 Changed 2 years ago by
Replying to ghkliem:
In Cython I was able to calculate this vector (or more important the edge graph) in something like 3 hours, in C it took me 20 minutes.
Just to add to what Vincent said: if your Cython code is substantially slower than your C/C++ code, you're doing it wrong. When using Cython properly, it should have the same speed as pure C/C++.
That being said, I'm not saying that you should use Cython instead of C++, just that you could.
comment:57 followup: ↓ 62 Changed 2 years ago by
Another minor comment: uint64_t_or_uint32_t
is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type like unsigned long
or size_t
?
comment:58 Changed 2 years ago by
 Commit changed from de03b8be97be9e77bfdbc27b142509cec353b947 to 2df5d2ef760981ae2cddc4e23b87021aeb6f20e4
comment:59 Changed 2 years ago by
 Commit changed from 2df5d2ef760981ae2cddc4e23b87021aeb6f20e4 to 0a95629eb7adeede726a1fdd1d8993ba72ff5eb6
Branch pushed to git repo; I updated commit sha1. New commits:
0a95629  corrected multiline comment

comment:60 Changed 2 years ago by
 Commit changed from 0a95629eb7adeede726a1fdd1d8993ba72ff5eb6 to 96c0a3551f09a96a6edd79a8eaccad846991e3f5
Branch pushed to git repo; I updated commit sha1. New commits:
96c0a35  Removed Compile arguments from module_list,

comment:61 Changed 2 years ago by
 Commit changed from 96c0a3551f09a96a6edd79a8eaccad846991e3f5 to ae08e2588ba48d1b36d2b34ff87f0689f9418ef9
Branch pushed to git repo; I updated commit sha1. New commits:
ae08e25  corrected memory

comment:62 in reply to: ↑ 57 ; followups: ↓ 63 ↓ 67 Changed 2 years ago by
Replying to jdemeyer:
Another minor comment:
uint64_t_or_uint32_t
is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type likeunsigned long
orsize_t
?
Any suggestions? Maybe 'uint64/32_t'? I don't like the name either...
Also, on 64bit machines, I really need to know that this is uint64_t. On 32bit machines that it is uint32_t. As far as I understand size_t can be anything. Also unsigned long should usually be uint64_t, but there is no guarantee on it. Is there?
comment:63 in reply to: ↑ 62 ; followup: ↓ 65 Changed 2 years ago by
Replying to ghkliem:
Replying to jdemeyer:
Another minor comment:
uint64_t_or_uint32_t
is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type likeunsigned long
orsize_t
?Any suggestions? Maybe 'uint64/32_t'? I don't like the name either...
Also, on 64bit machines, I really need to know that this is uint64_t. On 32bit machines that it is uint32_t. As far as I understand size_t can be anything. Also unsigned long should usually be uint64_t, but there is no guarantee on it. Is there?
There is no guaranty at all (e.g. look at the header of gmp where they define mp_limb_t
). I don't understand what is the problem with uint64_t
and uint32_t
... These are supposed to be standard and portable. Contrarily to unsigned long
or size_t
. Though I wonder why gmp avoid using them...
comment:64 in reply to: ↑ 55 ; followup: ↓ 69 Changed 2 years ago by
Thanks for the comments and help.
Replying to jdemeyer:
Some purely technical points about the programming:
 We generally discourage putting
Extension
parameters inmodule_list.py
. Better use# distutils
declarations in Cython files. See https://cython.readthedocs.io/en/latest/src/userguide/source_files_and_compilation.html#sourcefilesandcompilation for examples.
Done. Once I knew what to look for, I found a good example (combinat/partitions.pyx).
march=native
is not acceptable since we want to distribute binaries. Moreover, it makes no sense to compile just this specific file withmarch=native
. If you want to addmarch=native
, it should probably be added as compilation flag for all packages (or at least for Python, such that it applies to all Python packages). If you want to go through with this, you should open a new ticket for that. Also note that the optionmarch=native
itself is not portable: there be a check that the compiler actually understands it.
It took be a bit to figure this one out. A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).
If compiled by GCC >= 6 there would be multiple versions of the code available. At runtime the decision is made according to availability of the intrinsics. This way a build be used by different machines (e.g. Network Versions of it or binaries).
At compile time we can then decide for 64 or 32 bits and check wether it is compiled with GCC >= 6.
 The
O3
option is the default, so that's redundant.
Done.
 You have very long lines in your sources. You should try to wrap them to less than 80 characters per line.
I will take care of that.
 You're adding a lot of C/Cython code without a single
sig_on
/sig_check
. That's suspicious as such code cannot be interrupted. See https://cysignals.readthedocs.io/en/latest/interrupt.html#interrupthandling
combinat/partitions.pyx seems to be a good example. There this is done as well. I noticed this problem. When doing long calculations I had to kill sage the hard way, when I wanted to do so.
 While you're at it, you could also use the cysignals memory allocation functions instead of
PyMem_...
.
hasse_diagram.cc
contains various trivial functions which could easily be replaced by Cython. For example, the various accessor functions could be replaced by just accessing the attributes in Cython (this requires that the classCombinatorialPolyhedron
is actually declared in Cython). Alsodelete_CombinatorialPolyhedron(C)
could be replaced by justdel C
.
I honestly don't know how to do this. At the moment I am thinking about actually importing the class CombinatorialPolyhedron? in C++ a number of times with different macros. This way I avoid the multiversion function being decided on a low level, which would slow things done a lot and would break inlines etc. I could define the functions in the class a number of times, but this would make it even less readable.
Anyway, I'm still thinking about it and trying to figure out what to do.
 This is just advice: it's also possible to just include the
.cc
file in the.pyx
file usingcdef extern from "hasse_diagram.cc"
. That way, you can avoid the.h
file and you give more optimization opportunities to the compiler, since everything is compiled in one C++ file.
Great, I like this much better. For the extension thing, one was supposed to use a header. But now I'm able to work without it. I always found it a pain to work with header and cc.
 I'm very worried about portability: you seem to be using a lot of compilerspecific and CPUspecific code. I don't know whether anything will actually break, but there is a substantial risk.
See above. GCC sets up multiple functions and at runtime the correct function is being called. If one does not compile with GCC >= 6 then I suggest not using intrinsics at all.
There are not too many scenarios:
 AVX2 (maybe delete this, if there are no substantial losses doing it with AVXonly, however the instructions are easier with AVX2.)
 AVX, but not AVX2
 popcnt, but not AVX
 SSE4.1
 default
This is 64bit. I have to check out the scenarios for 32bit yet.
 Typo:
memomory
>memory
Done.
comment:65 in reply to: ↑ 63 Changed 2 years ago by
Replying to vdelecroix:
Replying to ghkliem:
Replying to jdemeyer:
Another minor comment:
uint64_t_or_uint32_t
is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type likeunsigned long
orsize_t
?Any suggestions? Maybe 'uint64/32_t'? I don't like the name either...
Also, on 64bit machines, I really need to know that this is uint64_t. On 32bit machines that it is uint32_t. As far as I understand size_t can be anything. Also unsigned long should usually be uint64_t, but there is no guarantee on it. Is there?
There is no guaranty at all (e.g. look at the header of gmp where they define
mp_limb_t
). I don't understand what is the problem withuint64_t
anduint32_t
... These are supposed to be standard and portable. Contrarily tounsigned long
orsize_t
. Though I wonder why gmp avoid using them...
I wasn't sure whether uint64_t is always available on 32bit machines. If this is the case, I can of course use it. In order to do popcount I need to do a pointer typecast, but that should be fine and the only problem then. Some patchbot gave me an error message about _mm_popcnt_u64 not being defined, which seems to be the case, if the machine is 32bit.
comment:66 Changed 2 years ago by
You probably know this, but just in case: on OS X, clang
is used, not gcc
.
comment:67 in reply to: ↑ 62 Changed 2 years ago by
Replying to ghkliem:
Also, on 64bit machines, I really need to know that this is uint64_t.
What's your definition of a 64bit machine (or 32bit machine)?
comment:68 followup: ↓ 70 Changed 2 years ago by
A more or less equivalent question: why do you really need to know that the type is uint64_t
on a 64bit machine and uint32_t
on a 32bit machine?
comment:69 in reply to: ↑ 64 ; followups: ↓ 71 ↓ 74 Changed 2 years ago by
Replying to ghkliem:
A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).
That's overthinking it for a generic math package like Sage. Almost all casual Sage users are not going to care how fast this code really runs.
But you probably misunderstood me: I didn't mean that march=native
was a bad idea, just that it should be enabled more carefully. And also not for this one specific file only, that would be just strange.
comment:70 in reply to: ↑ 68 ; followup: ↓ 72 Changed 2 years ago by
Replying to jdemeyer:
A more or less equivalent question: why do you really to know that the type is
uint64_t
on a 64bit machine anduint32_t
on a 32bit machine?
#if INTPTR_MAX == INT64_MAX
This is what I read somewhere. If this is for some reason is not set at all, it uses uint32_t and more important it will not call _mm_popcnt_u64
, which does not seem to be defined for 32bit machines, even if the processor has POPCNT. I figured this is why the following patchbot run failed:
comment:71 in reply to: ↑ 69 Changed 2 years ago by
Replying to jdemeyer:
Replying to ghkliem:
A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).
That's overthinking it for a generic math package like Sage. Almost all casual Sage users are not going to care how fast this code really runs.
Probably. The more important question is whether something can be calculated or not. If one then wants to generate e.g. the face_lattice
from the CombinatorialPolyhedron
, initalizing this is much slower than anything in this module.
But you probably misunderstood me: I didn't mean that
march=native
was a bad idea, just that it should be enabled more carefully. And also not for this one specific file only, that would be just strange.
So what you are suggesting is the following(?): Leave it as it is and delete march=native
. This should then somehow be added to Sage's build process (as an option?), so that one can build a more effective version, if one wants to. The prebuild binaries might then take 4times as long, but are stable.
This would then also be a portable way of using intrinsics, such that when in any other module it seems helpful, one can just copypaste from this code.
comment:72 in reply to: ↑ 70 ; followup: ↓ 73 Changed 2 years ago by
Replying to ghkliem:
Replying to jdemeyer:
A more or less equivalent question: why do you really to know that the type is
uint64_t
on a 64bit machine anduint32_t
on a 32bit machine?
#if INTPTR_MAX == INT64_MAX
That solves your problem: in that case, the type uint64_t_or_uint32_t
that you're looking for is uintptr_t
.
comment:73 in reply to: ↑ 72 Changed 2 years ago by
Replying to jdemeyer:
Replying to ghkliem:
Replying to jdemeyer:
A more or less equivalent question: why do you really to know that the type is
uint64_t
on a 64bit machine anduint32_t
on a 32bit machine?
#if INTPTR_MAX == INT64_MAX
That solves your problem: in that case, the type
uint64_t_or_uint32_t
that you're looking for isuintptr_t
.
When googling something as uintptr_t
, it seems like nothing is guaranteed. Also it seems like uint64_t
is always available. The only problem was with the _mm_popcnt_u64
. Maybe I just do a typecast there and replace uint64_t_or_uint32_t
by uint64_t
again.
comment:74 in reply to: ↑ 69 Changed 2 years ago by
Replying to jdemeyer:
Replying to ghkliem:
A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).
That's overthinking it for a generic math package like Sage. Almost all casual Sage users are not going to care how fast this code really runs.
But you probably misunderstood me: I didn't mean that
march=native
was a bad idea, just that it should be enabled more carefully. And also not for this one specific file only, that would be just strange.
The question wether march=native
can be included is now subject of the ticket #27122.
comment:75 Changed 2 years ago by
 Commit changed from ae08e2588ba48d1b36d2b34ff87f0689f9418ef9 to 61dae2c3ff721a0d8a3619f7d43f8dd2fb8bacc3
Branch pushed to git repo; I updated commit sha1. New commits:
61dae2c  Converted base.pyx to PEP 8

comment:76 Changed 2 years ago by
 Description modified (diff)
 Keywords grapg removed
comment:77 Changed 2 years ago by
I suppose it makes sense to disable all the intrinsics for this ticket (not done yet) and enable them later (#27103). This way this ticket does not depend on #27122.
Also, if there is anything not working with CombinatorialPolyhedron
once march=native
gets enabled, this would produce an error message for ticket #27122, which I would like to prevent from happening.
comment:78 Changed 2 years ago by
 Commit changed from 61dae2c3ff721a0d8a3619f7d43f8dd2fb8bacc3 to 95ac8adf2689c6dd1cebffc015038db35cddc141
Branch pushed to git repo; I updated commit sha1. New commits:
95ac8ad  removed Header file hasse_diagram.cc

comment:79 Changed 2 years ago by
 Commit changed from 95ac8adf2689c6dd1cebffc015038db35cddc141 to 759e024e429805d9e07431c207879d555449e1e1
Branch pushed to git repo; I updated commit sha1. New commits:
759e024  actual remove in git

comment:80 Changed 2 years ago by
 Commit changed from 759e024e429805d9e07431c207879d555449e1e1 to 6fd5f55050fc2383848a0cc1d1591ddcda0bcd3f
comment:81 Changed 2 years ago by
It seems like everything boils down to a face iterator.
At least in C++ there doesn't seems to be a difference between the previous f_vector
calculation and the calculation now being done by iterating over all faces and then adding at the correct dimension.
I guess the correct 'subclass' of CombinatorialPolyhedron
should then be an iterator and not a copy of itself in C++.
I guess I could do it all in Cython using PyMem_Malloc
etc. However, as this does not support any overalignment, the iterator would need more memory then needed. But this seems to be ok. About 30kB extra memory for the iterator over a 20dimensional Polyhedron with 40 facets. However, when recording all faces of this, the overhead might be almost as big as the actual data size. Then again, why would you want a list of 400 million faces, if you have an iterator.
comment:82 Changed 2 years ago by
 Commit changed from 6fd5f55050fc2383848a0cc1d1591ddcda0bcd3f to 34bec35a724be4a00c044d44a89ccf66dadb071d
Branch pushed to git repo; I updated commit sha1. New commits:
34bec35  the index of the faces changed, so the doctest needs an update

comment:83 Changed 2 years ago by
 Commit changed from 34bec35a724be4a00c044d44a89ccf66dadb071d to cf249ff788fb9972e59f51f8ff2753fa47b5edf5
comment:84 Changed 2 years ago by
 Commit changed from cf249ff788fb9972e59f51f8ff2753fa47b5edf5 to 6751885eba7ae1713085bc8e562345a54c1c616a
Branch pushed to git repo; I updated commit sha1. New commits:
6751885  the user can now correctly interupt

comment:85 Changed 2 years ago by
 Commit changed from 6751885eba7ae1713085bc8e562345a54c1c616a to abe18eb43a601863cbff7ac8587b2915c780069c
Branch pushed to git repo; I updated commit sha1. New commits:
abe18eb  some work towards replacing ridges

comment:86 Changed 2 years ago by
 Commit changed from abe18eb43a601863cbff7ac8587b2915c780069c to b14909932d9529794a223b198febca9f0fbebf91
Branch pushed to git repo; I updated commit sha1. New commits:
b149099  calculation of the f_vector is now done mostly in main class `CombinatorialPolyhedron`

comment:87 Changed 2 years ago by
 Commit changed from b14909932d9529794a223b198febca9f0fbebf91 to 6ce801cb4bfb7f0738c32507158612eeed6f3717
Branch pushed to git repo; I updated commit sha1. New commits:
0b76897  edges updated

ef84927  updated calculating the ridges

c1cac5c  Tests added, that edges() and ridges() can indeed be interrupted

0b80d3f  added calculation of f_vector while doing the edges

b46b81e  improved speed of getting vertex repr by only considering nonzero entries

6ce801c  upgraded the face iterator

comment:88 Changed 2 years ago by
 Commit changed from 6ce801cb4bfb7f0738c32507158612eeed6f3717 to f3b95783ef8610eaf27d6425eb7e4fe4139ddb33
comment:89 Changed 2 years ago by
 Commit changed from f3b95783ef8610eaf27d6425eb7e4fe4139ddb33 to 6ac0773f5486a5d1cb68635edb0c893ca7fb980a
comment:90 Changed 2 years ago by
 Commit changed from 6ac0773f5486a5d1cb68635edb0c893ca7fb980a to c3f4ef19796738befea316a0bf9162a74bb422d9
Branch pushed to git repo; I updated commit sha1. New commits:
c3f4ef1  the FaceLattice works now, also removed CombinatorialPolyhedron.flag() for later ticket

comment:91 Changed 2 years ago by
 Description modified (diff)
 Keywords flag vector removed
New commits:
c3f4ef1  the FaceLattice works now, also removed CombinatorialPolyhedron.flag() for later ticket

comment:92 Changed 2 years ago by
 Commit changed from c3f4ef19796738befea316a0bf9162a74bb422d9 to 2ce8561b52996dcffc3e8b5aa77303acafb889ea
Branch pushed to git repo; I updated commit sha1. New commits:
dea4f5b  I never used the Bitrepresentation of the vertices, so I got rid of it

3832480  replaced versions of faces(1) and faces(dimension), also the Bitrepresentation of vertices stays in for returning the vertices

422e2ea  removed the cppCombinatorialPolyhedron from CombinatorialPolyhedron

e61dbfd  removed hasse_diagram.cc

2ce8561  simplified helper.cc

comment:93 Changed 2 years ago by
This ticket is now pretty much where I want it to be. I still need to go through everything and make comments and clean up.
Even though everything got longer now, I think the structure is a lot easier. There is two main tools now:
A FaceIterator
. This is not a proper iterator, as I want it to be flexible with the output. But basically it iterates over all faces and for each face one can get output like its dimension or facetrepresentation. The FaceIterator
is used to calculate the f_vector
, edges
, ridges
etc. Also it calculates ListOfAllFaces
.
ListOfAllFaces
is a list of all faces ordered by dimension. Once all faces are initialized, one can sort the levelsets, as to calculated quickly the actual facelattice
.
There are some more classes like ListOfFaces
. This can be used to e.g. store all facets in BitRepresentation. The nice thing about it is, that it automatically takes care of the memory allocated. So when creating a ListOfFaces
, one can use void **
without having to worry about the memory allocation.
The methods actually defined in C++ now, should be easy to understand. There are mostly there, because C I can do something as #define chunktype uint64_t
and C will not complain about an unknown datatype chunktype
.
comment:94 Changed 2 years ago by
 Cc tscrim added
It might be worth adding some timings against the current stateoftheart implementation in polymake
to show how fast this implementation really is. One striking example is
sage: P = polytopes.permutahedron(7) sage: P1 = CombinatorialPolyhedron(P) sage: facets_lst = map(list,P1.facets(names=False)) sage: P2 = polymake("my $P = new Polytope(VERTICES_IN_FACETS=>%s);"%facets_lst) sage: %time P1.f_vector() CPU times: user 125 ms, sys: 0 ns, total: 125 ms Wall time: 125 ms (1, 5040, 15120, 16800, 8400, 1806, 126, 1) sage: %time P2.F_VECTOR CPU times: user 39 ms, sys: 4.71 ms, total: 43.7 ms Wall time: 13.4 s 5040 15120 16800 8400 1806 126
This is, of course, just a workaround to access polymake directly from within sage (it requires the experimental package polymake
to be installed). The same computation in a freshly installed polymake3.2
took roughly the same time.
I am not sure how to include this into the doctests because the difference only becomes strikingly visible when polymake
takes at least seconds.
@Travis: I would appreciate if you could have a look at this ticket and the implementation in C / Cython :)
comment:95 followups: ↓ 99 ↓ 101 ↓ 122 Changed 2 years ago by
A very general question: How much of this are you actually using stuff that is within Sage (and Cython)? In particular, I am wondering if there is a benefit to separating this out into a little standalone package that gets included in Sage with some linking. To me, you could leave the features that use parts of Sage, e.g., ridge_graph
, in the Sage implementation part, but have a good part of it independent.
typo? partitions_c.cc
> hasse_diagram.cc
?
# The actual algorithm is implemented in the C++ file partitions_c.cc
typo: (Knwon
(also that parenthetical should not be its own sentence but combined with the previous one).
Name conflict:
from cpython cimport array import array
For _data
and _memory
, could you be more specific than a void
pointer?
In ListOfFaces
, self.data()
> self._data
, especially since it is internal (and data()
is not inlined, but it should be, as with any cdef
simple accessors).
Do you really need the class ListOfListOfFaces
? That seems like a bit of overkill as it only is used in 1 place and not for anything useful.
Python convention for error messages should be start with a lowercase letter and no fullstop/period at the end.
You should not have get_next_level
wrapped in a sig_on
/sig_off
. That should do its own signal handling.
Instead of blank catching of exceptions to return 2
, you should use the builtin Cython syntax to raise errors: e.g., in integer.pyx
:
cpdef int _cmp_(left, right) except 2:
I do not think how you are handling the memory is the best way. For example, let us consider _calculate_f_vector
. Instead of catching an exception raised by that function (which you would make it return an int
and have except 1:
) in f_vector
and letting that code free the memory before propagating the error up, you have a big try/except inside the _calculate_f_vector
, which then returns okay, and have f_vector
create a new error.
Any cdef
that is a void
cannot raise an error; see the parenthetical above.
You should make a .pxd
file with the relevant cdef
class and methods set there. It works like a header file and allows people to cimport
objects. So that way people can make subclasses in different files.
I might have more comments, but these are what I got from a quick lookover.
comment:96 Changed 2 years ago by
 Commit changed from 2ce8561b52996dcffc3e8b5aa77303acafb889ea to 7e7147d6d1543459011517017820083e902e08cc
comment:97 Changed 2 years ago by
 Commit changed from 7e7147d6d1543459011517017820083e902e08cc to 1e0f36f94fced98928c556b872a58888584e737e
Branch pushed to git repo; I updated commit sha1. New commits:
1e0f36f  fixed the order of facets in __reduce__(), fixed a bug in face_iter for some polyhedra

comment:98 followup: ↓ 118 Changed 2 years ago by
I agree with Travis that error checking could be much improved: use error return values.
Also, instead of using sig_malloc
and then checking for NULL
, use check_malloc
which automatically does that check. Even better, replace sig_malloc(a * sizeof(T))
by check_allocarray(a, sizeof(T))
.
comment:99 in reply to: ↑ 95 ; followup: ↓ 100 Changed 2 years ago by
Replying to tscrim:
Name conflict:
from cpython cimport array import array
As far as I can tell, this isn't even used anywhere.
comment:100 in reply to: ↑ 99 Changed 2 years ago by
Replying to jdemeyer:
Replying to tscrim:
Name conflict:
from cpython cimport array import arrayAs far as I can tell, this isn't even used anywhere.
Yes, this can go out now. I copied this from the documentation: https://cython.readthedocs.io/en/latest/src/tutorial/array.html.
comment:101 in reply to: ↑ 95 Changed 2 years ago by
Replying to tscrim:
For
_data
and_memory
, could you be more specific than avoid
pointer?
I can do so. This was due to a wrong assumption. It turns out (not suprisingly I guess) that
_mm256_testc_si256((two),(one));
takes just as long as
one = _mm256_load_si256((const __m256i*)&(A)); two = _mm256_load_si256((const __m256i*)&(B)); _mm256_testc_si256((two),(one));
So I can use uint64_t
until I actually need registers and than load them directly. This also explains, why people out there don't save stuff in formats like __m256i *
.
comment:102 followup: ↓ 107 Changed 2 years ago by
Also, this ListOfListOfPointers
and ListOfFaces
stuff seems to be reinventing the wheel. For example, since you're using C++ anyway, you could use std::vector<>
or whatever. There is also sage.ext.memory_allocator.MemoryAllocator
which seems to have some overlap with what you need.
comment:103 followup: ↓ 104 Changed 2 years ago by
I consider these small accessor methods unpythonic:
cdef size_t nr_lists(self): return self._nr_lists
What's wrong with just calling the attribute nr_lists
and accessing that directly?
comment:104 in reply to: ↑ 103 Changed 2 years ago by
Replying to jdemeyer:
I consider these small accessor methods unpythonic:
cdef size_t nr_lists(self): return self._nr_listsWhat's wrong with just calling the attribute
nr_lists
and accessing that directly?
This is what I wanted to do from the start. But it didnt' work. No idea why. I probably had some mistake, which I corrected when setting up those small accessors. Now I removed all small accessors and everything works great.
comment:105 Changed 2 years ago by
 Commit changed from 1e0f36f94fced98928c556b872a58888584e737e to 0edfd3f2a3b8c3b76f997ed20f46dd9048a5ade9
Branch pushed to git repo; I updated commit sha1. New commits:
0edfd3f  removed small accessors

comment:106 Changed 2 years ago by
Replace
from libc cimport stdint ctypedef stdint.uint64_t uint64_t
by
from libc.stdint cimport uint64_t
comment:107 in reply to: ↑ 102 ; followups: ↓ 109 ↓ 110 Changed 2 years ago by
Replying to jdemeyer:
Also, this
ListOfListOfPointers
andListOfFaces
stuff seems to be reinventing the wheel. For example, since you're using C++ anyway, you could usestd::vector<>
or whatever. There is alsosage.ext.memory_allocator.MemoryAllocator
which seems to have some overlap with what you need.
I need 32byte aligned memory for ListOfFaces
. I actually don't need it exactly for this ticket, as I want to disable intrinsics for now, but eventually I want it.
sage.ext.memory_allocator.MemoryAllocator
seems to be great for ListOfPointers
. I couldn't get 32byte aligned to work with any prebuild solution. This doesn't mean anything of course.
I had the impression that its somehow nice to allocate the memory in cython instead of some extern C file.
comment:108 Changed 2 years ago by
 Commit changed from 0edfd3f2a3b8c3b76f997ed20f46dd9048a5ade9 to f15883df872cb694d6f6aa33c59f256b671681e3
comment:109 in reply to: ↑ 107 Changed 2 years ago by
Replying to ghkliem:
I had the impression that its somehow nice to allocate the memory in cython instead of some extern C file.
Yes indeed. But you can use the standard C++ library in Cython: https://cython.readthedocs.io/en/latest/src/userguide/wrapping_CPlusPlus.html#standardlibrary
I'm not saying that this is a good or bad solution. Just that it's possible.
comment:110 in reply to: ↑ 107 ; followup: ↓ 113 Changed 2 years ago by
Replying to ghkliem:
sage.ext.memory_allocator.MemoryAllocator
seems to be great forListOfPointers
. I couldn't get 32byte aligned to work with any prebuild solution.
If MemoryAllocator
works great except for the alignment, you could add alignment support to MemoryAllocator
.
comment:111 Changed 2 years ago by
Speaking of alignment: why are you not using https://en.cppreference.com/w/c/memory/aligned_alloc or http://man7.org/linux/manpages/man3/posix_memalign.3.html
comment:112 followup: ↓ 123 Changed 2 years ago by
Since you're using divisions, I strongly recommend to add
from __future__ import division
to make sure that your code works fine when using Python 3 divisions.
comment:113 in reply to: ↑ 110 Changed 2 years ago by
Replying to jdemeyer:
Replying to ghkliem:
sage.ext.memory_allocator.MemoryAllocator
seems to be great forListOfPointers
. I couldn't get 32byte aligned to work with any prebuild solution.If
MemoryAllocator
works great except for the alignment, you could add alignment support toMemoryAllocator
.
I should do this. I already love MemoryAllocator
. It's so easy. Then again, I might only appreciate it, because I though about what needs to be done.
comment:114 Changed 2 years ago by
 Commit changed from f15883df872cb694d6f6aa33c59f256b671681e3 to f534fae3c98b7e0ac5f6912924e9ddc0060b44f5
comment:115 Changed 2 years ago by
 Commit changed from f534fae3c98b7e0ac5f6912924e9ddc0060b44f5 to f3fe6988308c7b0ea333b837e482d46feedac185
Branch pushed to git repo; I updated commit sha1. New commits:
f3fe698  removed ListOfListOfFaces

comment:116 Changed 2 years ago by
 Commit changed from f3fe6988308c7b0ea333b837e482d46feedac185 to 887db29d8c5f120fc210ec0db1fd73097c8871ed
Branch pushed to git repo; I updated commit sha1. New commits:
887db29  actually removed the class ListOfListOfFaces, not just all instances,

comment:117 Changed 2 years ago by
 Commit changed from 887db29d8c5f120fc210ec0db1fd73097c8871ed to f10c90ab6e2bf65bd71dc55ec0d9a5520c0d2d1c
Branch pushed to git repo; I updated commit sha1. New commits:
087957d  replaced void * by uint64_t *

70559ee  moved is_equal from helper.cc to base.pyx

6691d1e  added tests for face_lattice

bf2a8af  moved find_face to cython

98048e6  moved sort from helper.cc to base.pyx

f10c90a  Preparing: Filling BitRepresentations of Vertices and Facets in Cython, this makes it a lot easier

comment:118 in reply to: ↑ 98 Changed 2 years ago by
Replying to jdemeyer:
I agree with Travis that error checking could be much improved: use error return values.
Also, instead of using
sig_malloc
and then checking forNULL
, usecheck_malloc
which automatically does that check. Even better, replacesig_malloc(a * sizeof(T))
bycheck_allocarray(a, sizeof(T))
.
In char_from_incidence
and get_vertices_from_incidence_matrix2
I have tried doing it correctly. char_from_incidence
returns 1 on success and 0 means that something went wrong. get_vertices_from_incidence_matrix2
returns a CythonObject and so it es okay not to do the except
?
comment:119 Changed 2 years ago by
For anything returning a Python object, you cannot add an except
value. That's only for C return types.
comment:120 Changed 2 years ago by
 Commit changed from f10c90ab6e2bf65bd71dc55ec0d9a5520c0d2d1c to 22026c6c2c1865381732e50171a8265bdf4f3abb
comment:121 Changed 2 years ago by
 Commit changed from 22026c6c2c1865381732e50171a8265bdf4f3abb to c012d0c1e9618adc06f4f99c26f6599ead639676
Branch pushed to git repo; I updated commit sha1. New commits:
d9cc21a  Updated the face_length/length_of_face, it is now in terms of uint64_t, which should be more natural, also base.pyx knows almost nothing about chunksize now

828689b  face_length and length_of_face are now face_length

c012d0c  Improved errors, Keyboard interrupt should work fine now

comment:122 in reply to: ↑ 95 ; followup: ↓ 124 Changed 2 years ago by
Replying to tscrim:
You should not have
get_next_level
wrapped in asig_on
/sig_off
. That should do its own signal handling.
How am I going to do this? I changed it to do its own signal handling, but that made everything slow down. To be more precise: Calculating the f_vector
of the 20dimensional counterexample now takes 3m 39s instead of 2m 57s. Just adding
#include <csignal>
and
void inline signalHandler( int signum ) { // setting a variable, so I can catch the signal later interrupt = 1; }
and
signal(SIGINT, signalHandler);
(I commented out the check for interrupt
, to be certain its just this.) What am I doing wrong? What is the advantage of this approach over sig_on
/sig_off
thats worth this increase in time?
comment:123 in reply to: ↑ 112 ; followup: ↓ 125 Changed 2 years ago by
Replying to jdemeyer:
Since you're using divisions, I strongly recommend to add
from __future__ import divisionto make sure that your code works fine when using Python 3 divisions.
Good thing I checked, what this actually means. I do want floor division. So this is not what I want, is it? Instead I should us //
for "floor division"? I don't think there is a single instance, where I use "true division".
comment:124 in reply to: ↑ 122 ; followup: ↓ 129 Changed 2 years ago by
Replying to ghkliem:
Replying to tscrim:
You should not have
get_next_level
wrapped in asig_on
/sig_off
. That should do its own signal handling.
I'm also confused with the comment by Travis. get_next_level
is implemented in C, so I do think that using sig_on
and sig_off
(like it used to be) makes sense.
comment:125 in reply to: ↑ 123 Changed 2 years ago by
Replying to ghkliem:
Instead I should us
//
for "floor division"?
If you need floor division, then you should use //
indeed. You should still keep the from __future__ import division
to catch mistakes (if you mistakenly use /
instead of //
it will behave the same on Python 2 and Python 3).
comment:126 Changed 2 years ago by
 Commit changed from c012d0c1e9618adc06f4f99c26f6599ead639676 to a1aa1c8f941e966d82a9efd522753d1334b71e90
Branch pushed to git repo; I updated commit sha1. New commits:
a1aa1c8  Documentation + updated division to be floor division

comment:127 Changed 2 years ago by
 Commit changed from a1aa1c8f941e966d82a9efd522753d1334b71e90 to d31bd2bc702919d65fb1e6fa879e312f033a976d
Branch pushed to git repo; I updated commit sha1. New commits:
d31bd2b  added base.pyx

comment:128 Changed 2 years ago by
 Commit changed from d31bd2bc702919d65fb1e6fa879e312f033a976d to e5346e5233406369d86fd4f61e5b04460e341f5d
Branch pushed to git repo; I updated commit sha1. New commits:
e5346e5  saved base.pyx

comment:129 in reply to: ↑ 124 Changed 2 years ago by
Replying to jdemeyer:
Replying to ghkliem:
Replying to tscrim:
You should not have
get_next_level
wrapped in asig_on
/sig_off
. That should do its own signal handling.I'm also confused with the comment by Travis.
get_next_level
is implemented in C, so I do think that usingsig_on
andsig_off
(like it used to be) makes sense.
What Jeroen initially said was correct, I meant for it to have sig_on
/sig_off
inside the function, but I misread that it was implemented in C. So you can disregard that comment.
(Sorry for my delayed response, I have been traveling and busy.)
comment:130 Changed 2 years ago by
 Commit changed from e5346e5233406369d86fd4f61e5b04460e341f5d to 1d74cf81ad85fcbe0ac008c0c07d54173f3f3399
Branch pushed to git repo; I updated commit sha1. New commits:
1d74cf8  Updated error messages

comment:131 Changed 2 years ago by
 Commit changed from 1d74cf81ad85fcbe0ac008c0c07d54173f3f3399 to 143cb5af73761dfc13a9a8fdc8c56dd9d5914b95
comment:132 Changed 2 years ago by
 Commit changed from 143cb5af73761dfc13a9a8fdc8c56dd9d5914b95 to 621f2c3a082b8417c26bf4e34821c28bc7f0b364
comment:133 Changed 2 years ago by
 Commit changed from 621f2c3a082b8417c26bf4e34821c28bc7f0b364 to b9ffa15788e3429cb2e4290c46ec5e247fe47429
Branch pushed to git repo; I updated commit sha1. New commits:
b9ffa15  checking for NULL, when adding a face

comment:134 Changed 2 years ago by
 Commit changed from b9ffa15788e3429cb2e4290c46ec5e247fe47429 to ce1789e8eae99847f3665d73cd9ede600e46998d
Branch pushed to git repo; I updated commit sha1. New commits:
ce1789e  coding conventions

comment:135 Changed 2 years ago by
 Commit changed from ce1789e8eae99847f3665d73cd9ede600e46998d to c16fccc35175e67b05261a02b913b3ae29baade2
Branch pushed to git repo; I updated commit sha1. New commits:
c16fccc  one / too much

comment:136 followup: ↓ 139 Changed 2 years ago by
Two general comments:
 You have a huge number of commits. At some point, it would be good to squash everything into one commit.
 Don't forget to set the ticket back to needs_review if you want it reviewed.
comment:137 Changed 2 years ago by
 Commit changed from c16fccc35175e67b05261a02b913b3ae29baade2 to deb5977d117ec4c4be1cc5bfac9e6fda85633387
Branch pushed to git repo; I updated commit sha1. New commits:
deb5977  it should be mostly clean now

comment:138 Changed 2 years ago by
 Branch changed from u/ghkliem/improve_f_vector_etc__for_polytopes to public/26887
 Commit changed from deb5977d117ec4c4be1cc5bfac9e6fda85633387 to b73c335e50ab93c8ec5ba2a96c4198b9d589f478
New commits:
b73c335  added a class class CombinatorialPolyhedron

comment:139 in reply to: ↑ 136 Changed 2 years ago by
Replying to jdemeyer:
Two general comments:
 You have a huge number of commits. At some point, it would be good to squash everything into one commit.
 Don't forget to set the ticket back to needs_review if you want it reviewed.
Wasn't sure how to exactly squash pushed commits, but I guess restarting a clean branch does the job.
comment:140 Changed 2 years ago by
 Status changed from needs_work to needs_review
comment:141 Changed 2 years ago by
 Commit changed from b73c335e50ab93c8ec5ba2a96c4198b9d589f478 to f1ad61b753d526049013ec2d61a762e7576ae15e
Branch pushed to git repo; I updated commit sha1. New commits:
f1ad61b  corrected blocks

comment:142 Changed 2 years ago by
How come that patchbots use completely different versions of the files then claimed?
I keep getting messages containing errors with chunktype
in helper.cc. I removed this a while ago and the current branch shouldn't even know that chunktype
ever existed.
BuildFailed? 8.7.beta4 Ubuntu/18.04/x86_64/3.13.0123generic/44e979ad077a 20190218 20:09:03 log shortlog
comment:143 Changed 2 years ago by
The patchbot page contains all builds for a particular ticket, even old ones. I agree that it's not obvious to see whether a patchbot run is from the current commit or an earlier one.
comment:144 Changed 2 years ago by
 Dependencies set to #27292
This should eventually use the functions added by #27292.
comment:145 followups: ↓ 146 ↓ 176 Changed 2 years ago by
 Status changed from needs_review to needs_work
I have lots of small comments while reading this code:
 It would makes things easier to understand if you really removed the vectorization stuff instead of just commenting it out. That way, we can completely focus the review on the generic code (without needing the worry about the commentedout parts). More generally, remove commentedout code like
# cdef tuple lists_facet_repr #might need this for flagvector
 It's really hard to understand what all the code does: I'm missing some kind of "big picture" documentation to explain what this is all about. For example, when I see
cdef class FaceIterator: cdef uint64_t *face cdef int current_dimension, dimension, record_dimension, lowest_dimension cdef MemoryAllocator _mem cdef uint64_t ***newfaces2 cdef tuple newfaces_lists cdef uint64_t ***newfaces cdef uint64_t **forbidden cdef size_t *nr_faces cdef size_t *nr_forbidden cdef int *first_time cdef size_t yet_to_yield, face_length, nr_facets, nr_vertices cdef size_t *output1 cdef size_t *output2 cdef int nr_lines
I don't want to review this anymore. You really need to add a lot more comments.
 The Cython doctests are hard to read: all the output just comes at the end and it's difficult to see which code produced it. You could instead define a bunch of test functions (either in the doctest or in the Cython sources) and then call those from Python.
 I sometimes wonder if it wouldn't be easier to abstract some things in C++ or Python classes, for example using something like
std::vector<uint64_t>
orarray.array
instead ofuint64_t*
.
 Do you really need
vertex_to_bit_dictionary
? It's probably more efficient to replacevertex_to_bit_dictionary[i]
by an inline functioncdef inline uint64_t vertex_to_bit_dictionary(int i): return (<uint64_t>1) << (64  i  1)
 In
char_from_tuple
(and other similar functions), please useexcept 1
for exceptions andreturn 0
in the nonexceptional case. Then you don't even need to writereturn 0
since that's the default.
 Typos
lenght
>length
 In various places, you use
int
as indices while most other places usesize_t
. Is there a reason for that? Note that Python typically usesPy_ssize_t
for loops like that.
return int(bitcount)
is converting a Csize_t
to a Pythonint
to a Cint
. Justreturn bitcount
should be sufficient.
 There is no point at all to put
sig_check()
right aftersig_off()
or right beforesig_on()
.
 Is there a good reason to implement
face_iter
andfaces
separately? Isn't it sufficient to have the iterator only?
comment:146 in reply to: ↑ 145 ; followup: ↓ 147 Changed 2 years ago by
Thanks for the comments.
Replying to jdemeyer:
I have lots of small comments while reading this code:
 It would makes things easier to understand if you really removed the vectorization stuff instead of just commenting it out. That way, we can completely focus the review on the generic code (without needing the worry about the commentedout parts). More generally, remove commentedout code like
# cdef tuple lists_facet_repr #might need this for flagvector
Ok, I will do that. In #27103 I already added that code as a comment. I just did some timings comparing the current sage, polymake and the new code with intrinsics and without: Yes the intrinsics are nice, as they give a speedup of a factor of 23 for the iterator. But its nothing in comparison to the gain of that ticket without intrinsics in comparison to standing algorithms.
 It's really hard to understand what all the code does: I'm missing some kind of "big picture" documentation to explain what this is all about. For example, when I see
cdef class FaceIterator: cdef uint64_t *face cdef int current_dimension, dimension, record_dimension, lowest_dimension cdef MemoryAllocator _mem cdef uint64_t ***newfaces2 cdef tuple newfaces_lists cdef uint64_t ***newfaces cdef uint64_t **forbidden cdef size_t *nr_faces cdef size_t *nr_forbidden cdef int *first_time cdef size_t yet_to_yield, face_length, nr_facets, nr_vertices cdef size_t *output1 cdef size_t *output2 cdef int nr_linesI don't want to review this anymore. You really need to add a lot more comments.
In CombinatorialPolyhedron.f_vector
there is a small description of the basic algorithm. Maybe it is of help.
I will add comments to all those variable declarations.
 The Cython doctests are hard to read: all the output just comes at the end and it's difficult to see which code produced it. You could instead define a bunch of test functions (either in the doctest or in the Cython sources) and then call those from Python.
I just saw, how you did that in #27292. Makes sense.
 I sometimes wonder if it wouldn't be easier to abstract some things in C++ or Python classes, for example using something like
std::vector<uint64_t>
orarray.array
instead ofuint64_t*
.
Without intrinsics this seems to be a good approach. However, I have now idea how to force array.array or vector to keep alignment. Also I never change the size of the uint64_t*
.
 Do you really need
vertex_to_bit_dictionary
? It's probably more efficient to replacevertex_to_bit_dictionary[i]
by an inline functioncdef inline uint64_t vertex_to_bit_dictionary(int i): return (<uint64_t>1) << (64  i  1)
 In
char_from_tuple
(and other similar functions), please useexcept 1
for exceptions andreturn 0
in the nonexceptional case. Then you don't even need to writereturn 0
since that's the default.
 Typos
lenght
>length
 In various places, you use
int
as indices while most other places usesize_t
. Is there a reason for that? Note that Python typically usesPy_ssize_t
for loops like that.
I got a warning about comparison of unsigned and signed integer. This is how I "solved" it. Cython seems to translate len()
to a signed integer, then I get warnings.
So Py_ssize_t
is a good type for an index in there? Or just leave it up to the compiler?
return int(bitcount)
is converting a Csize_t
to a Pythonint
to a Cint
. Justreturn bitcount
should be sufficient.
 There is no point at all to put
sig_check()
right aftersig_off()
or right beforesig_on()
.
Didn't know if sig_on()
whould catch an already existing Interrupt.
 Is there a good reason to implement
face_iter
andfaces
separately? Isn't it sufficient to have the iterator only?
I don't care. I just figured, that people want a faces()
anyway. To me, there is no need to that function. Partly, its there because of historic reasons.
comment:147 in reply to: ↑ 146 ; followup: ↓ 148 Changed 2 years ago by
Replying to ghkliem:
So
Py_ssize_t
is a good type for an index in there?
Py_ssize_t
is the type of len(something)
in Python. So, if you're doing something like for i in range(len(something))
, then indeed use cdef Py_ssize_t i
.
I don't care. I just figured, that people want a
faces()
anyway.
What if you're looking for one face with a specific property, or counting each face with a given property? Then you don't need to generate a list of all faces.
In general, Python seems to move away from returning lists of things to returning views/iterators. For example, range()
is an iterator in Python 3 but a list in Python 2.
comment:148 in reply to: ↑ 147 Changed 2 years ago by
Replying to jdemeyer:
Replying to ghkliem:
So
Py_ssize_t
is a good type for an index in there?
Py_ssize_t
is the type oflen(something)
in Python. So, if you're doing something likefor i in range(len(something))
, then indeed usecdef Py_ssize_t i
.I don't care. I just figured, that people want a
faces()
anyway.What if you're looking for one face with a specific property, or counting each face with a given property? Then you don't need to generate a list of all faces.
I am aware of advantages of an iterator.
This raises again the question of wether my construction makes sense and I am almost certain, there is a better way of doing so:
So I have a FaceIterator
that can swiftly go to next face (and return its dimension on default). Before jumping to the next face, we can also grab the vertexrepresentation, facetrepresentation. In the future it might be nice to add more functions, but so much for now.
At the moment I have a complicated method CombinatorialPolyhedron.face_iter()
that yields information of each face depending on a bunch of arguments. But I am almost certain, that this is not a good way of doing it. Probably I should return FaceIterator
, which is an iterator. What's a good way of implementing an iterator, that can return various outputs? I'm thinking of something like
sage: cython(''' ....: from sage.rings.integer import Integer ....: cdef class FaceIterator: ....: cdef size_t nr_faces ....: cdef size_t i ....: def __init__(self, number): ....: self.nr_faces = number ....: self.i = 0 ....: ....: def __iter__(self): ....: return self ....: ....: def __next__(self): ....: current = Integer(self.i) ....: self.i += 1 ....: if self.i > self.nr_faces: ....: raise StopIteration ....: else: ....: return Integer(current) ....: ....: next = __next__ ....: ....: def give_facet_repr(self): ....: # some actual calculation happening here ....: return 'this is the facet repr of the current face' ....: ....: def give_vertex_repr(self): ....: # some calculation here ....: return 'this is the vertex_repr' ....: ....: def skip_a_face(self): ....: # what I'm thinking about is the option ....: # of not visiting any faces of the current face ....: self.i += 1 ....: ''') sage: a = FaceIterator(20) sage: next(a) 0 sage: next(a) 1 sage: a.skip_a_faces() sage: a.skip_a_faces() sage: next(a) 4 sage: a.give_facet_repr() 'this is the facet repr of the current face' sage: a.give_vertex_repr() 'this is the vertex_repr'
I guess I know how to do this, but I don't know, if this any good.
This way the user would actually be able to use the face iterator + I don't have to think of all possible outputs when creating CombinatorialPolyhedron.face_iter()
. One can easily add more outputs like constructing the facets
of the current face, or return a CombinatorialPolyhedron
which is the current face etc.
At the moment, such extensions would be hard to do.
One could also yield a something like CombinatorialFace
, but I'm a bit worried about the overhead. Also things like "do not revisit subfaces" (i.e. when the face is simplicial and there is really no point in doing so) or setting a maximal dimension etc. are not possible.
In general, Python seems to move away from returning lists of things to returning views/iterators. For example,
range()
is an iterator in Python 3 but a list in Python 2.
comment:149 Changed 2 years ago by
Another thing I could do to make life easier: Split this ticket in a number of tickets as good as possible.
So for this ticket there could be "only" the class CombinatorialPolyhedron
with a FaceIterator
that calculates the f_vector
.
Follow up tickets would be
edges
andridges
hasse_diagram
/face_lattice
 maybe even all those accesors in
FaceIterator
How about it? This would remove at least 1000 lines in the current code for later.
comment:150 Changed 2 years ago by
 Commit changed from f1ad61b753d526049013ec2d61a762e7576ae15e to 71c6d7a400c3c7db3f1c27be559a5d50619fe56d
comment:151 Changed 2 years ago by
Can you still have meaningful tests here with it being split? Although I think we have mostly gone through the code currently here already. So I am not sure there will be too much merit in splitting it, but maybe someone else has a different idea.
comment:152 Changed 2 years ago by
Ok, I leave the stuff in there.
I will however return FaceIterator
with the method face_iter()
. This should make it much easier.
Also the dual/polar decision will be on call of face_iter.
comment:153 Changed 2 years ago by
 Commit changed from 71c6d7a400c3c7db3f1c27be559a5d50619fe56d to 6052b6138d488608c5ba11ea05525648aea1b4ee
Branch pushed to git repo; I updated commit sha1. New commits:
6052b61  FaceIterator is an actual iterator now

comment:154 Changed 2 years ago by
 Status changed from needs_work to needs_review
Mainly I just changed FaceIterator
to be an iterator. This also helped my remove most cython examples.
FaceIterator
and ListOfAllFaces
should take care of the special cases themselves now.
CombinatorialPolyhedron
almost doesn't know anything about dual anymore. This is a way to initialize FaceIterator
.
comment:155 Changed 2 years ago by
 Commit changed from 6052b6138d488608c5ba11ea05525648aea1b4ee to c30e60d74f700fc389e2e2b36a2ce005ca44f02d
Branch pushed to git repo; I updated commit sha1. New commits:
c30e60d  fixed allocation of array

comment:156 Changed 2 years ago by
 Commit changed from c30e60d74f700fc389e2e2b36a2ce005ca44f02d to e8309e4c706335d981a70ed67bdaa7ea96a3ca13
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e8309e4  fixed allocation of array

comment:157 Changed 2 years ago by
Please do not use
++ sage: it.next()
but
next(it)
for compatibility with python3.
comment:158 followup: ↓ 160 Changed 2 years ago by
Do you recommend to also remove next = __next__
then?
comment:159 Changed 2 years ago by
 Commit changed from e8309e4c706335d981a70ed67bdaa7ea96a3ca13 to 6a55fa5dadad4d97182d55334a985bdab6e34f37
Branch pushed to git repo; I updated commit sha1. New commits:
6a55fa5  it.next() > next(it), also fixed face_lattice_facet_repr for trivial cases

comment:160 in reply to: ↑ 158 Changed 2 years ago by
Replying to jdemeyer:
Do you recommend to also remove
next = __next__
then?
I guess Cython takes care of that automatically. I read somewhere, that one should do that and indeed this seems to be true for defining a Python iterator class.
comment:161 followup: ↓ 165 Changed 2 years ago by
I am going through the doc right now.
A general issue I noticed:
INPUT:  `foo`  lorem ipsum + ``foo``  lorem ipsum
so it is formatted as code and not latex. There might be other cases in the docstrings themselves that should be code formatted. These bullet points for INPUT:
do not, by general Sage convention, end in a period/fullstop.
Another general issue, three .
's are needed here:
Traceback (most recent call last):  .. + ... ValueError: entries of `tup` are not distinct
Typo: `ouput`
Instead of doing the next(it)
a bunch of times, how about doing
sage: [next(it) for _ in range(14)] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
The algorithm to visit all proper faces exactly once is roughly  equivalent to: + equivalent to::  faces = [set(facet) for facet in self.facets()]  ComputeNextStep(facets, []) + faces = [set(facet) for facet in self.facets()] + ComputeNextStep(facets, [])
(This will not be executed as code as there is no leading sage:
.)
Similar comment for the ALGORITHM:
block in FaceIterator
's classlevel docstring.
You can use bint
for dual
in FaceIterator.__init__
.
I would drop the An
from the repr of FaceIterator
(this is another general convention we mostly stick to).
raise StopIteration() +raise StopIteration
Returns the length of the vertex_repr. +Return the length of the :meth:`vertex_repr`.
and similar for facet_repr
.
You should use Return
instead of Returns
(I think the former is called the definitive form of the verb). (I think this is a PEP8 thing; at the very least it is a Sage convention.)
The tests for vertex_repr_length
and facet_repr_length
I would say are not so meaningful. I think better tests would be to check it against it.length_vertex_repr() == len(it.vertex_repr())
.
You might find the .. WARNING::
environment useful for the next_face()
docstring.
It is good to add a TestSuite(foo).run()
call in the __init__
method doctests.
This is malformatted:
* ``nr_lines``  for bounded Polyhedra, this should be the  default: ``None``. For unbounded Polyhedra, this needs to be set  to the correct nr of lines, i.e. the the maximum nr of lines with  linearly independent directions in the Polyehdron. + default: ``None``. For unbounded Polyhedra, this needs to be set + to the correct nr of lines, i.e. the the maximum nr of lines with + linearly independent directions in the Polyehdron.
* ``unbounded``  for bounded Polyhedra, this should be the  default ``None``. For unbounded Polyhedra, this needs to be set  to the correct nr of lines, i.e. the the maximum nr of lines with  linearly independent directions in the Polyehdron. + default ``None``. For unbounded Polyhedra, this needs to be set + to the correct nr of lines, i.e. the the maximum nr of lines with + linearly independent directions in the Polyehdron.
It is good to spell things out in the doc IMO:
Specifying the nr of lines is important:: +Specifying the number of lines is important::
There's a few places you use f_vector
that is plain formatted. I think you either should use `f`vector
/fvector
or ``f_vector``
.
If `names` is set to True, then names of the vertices are used. +If ``names`` is ``True``, then names of the vertices are used.
In general, do not feel the need to stick to 80 chars/line in code for things like
self._f_vector = \ tuple(Integer(f_vector[dim+1i]) for i in range(dim+2))
as I think it makes the code harder to read.
I might have more comments later, but that is what I got for now.
comment:162 followup: ↓ 163 Changed 2 years ago by
According to the patchbots, the build is failing on a few different platforms.
comment:163 in reply to: ↑ 162 ; followup: ↓ 166 Changed 2 years ago by
Replying to jhpalmieri:
According to the patchbots, the build is failing on a few different platforms.
The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring lenfaces
as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere #include "Python.h."
gives trouble on OS X with C++17. Now its only a warning and not an error though.
Both Ubuntu patchbots (44e979ad077a and quasar) use an old version of the files. I don't know why. chunktype
has long been removed from helper.cc
.
comment:164 Changed 2 years ago by
 Commit changed from 6a55fa5dadad4d97182d55334a985bdab6e34f37 to 9f421825ae6eaa4bc800b978ba7e9d529434a0fc
Branch pushed to git repo; I updated commit sha1. New commits:
9f42182  improved documentation mostly

comment:165 in reply to: ↑ 161 Changed 2 years ago by
Thanks, went through the entire document and tried to fix all of those issues.
Replaced int
by bint
wherever I use only True
and False
anyway.
Added __reduce__
with and NotImplementedError
to the ListOfFaces
, FaceIterator
and ListOfAllFaces
. One could try to implement that, but I don't see an advantage of that.
Replying to tscrim:
I am going through the doc right now.
comment:166 in reply to: ↑ 163 ; followup: ↓ 167 Changed 2 years ago by
Replying to ghkliem:
Replying to jhpalmieri:
According to the patchbots, the build is failing on a few different platforms.
The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring
lenfaces
as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere#include "Python.h."
gives trouble on OS X with C++17. Now its only a warning and not an error though.
I'm confused: if it's fixed, why does the build fail?
Executing 21 commands (using 1 thread) [ 1/21] gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall Wnounused Isage/geometry/polyhedron/combinatorial_polyhedron I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/sitepackages/cysignals I/Users/jpalmier/Desktop/Sage/git/sage/local/include I/Users/jpalmier/Desktop/Sage/git/sage/src/sage/ext I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/sitepackages/numpy/core/include Ibuild/cythonized I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 c build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp o build/temp.macosx10.9x86_642.7/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.o fnostrictaliasing DCYTHON_CLINE_IN_TRACEBACK=1 std=c++11 In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:47: In file included from ../local/include/python2.7/Python.h:88: ../local/include/python2.7/unicodeobject.h:534:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj, /* Object */ ^~~~~~~~~ ../local/include/python2.7/unicodeobject.h:553:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj /* Object */ ^~~~~~~~~ ../local/include/python2.7/unicodeobject.h:575:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register const wchar_t *w, /* wchar_t buffer */ ^~~~~~~~~ ../local/include/python2.7/unicodeobject.h:593:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register wchar_t *w, /* wchar_t buffer */ ^~~~~~~~~ In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:47: In file included from ../local/include/python2.7/Python.h:97: ../local/include/python2.7/stringobject.h:173:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register PyObject *obj, /* string or Unicode object */ ^~~~~~~~~ ../local/include/python2.7/stringobject.h:174:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register char **s, /* pointer to buffer variable */ ^~~~~~~~~ ../local/include/python2.7/stringobject.h:175:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [Wdeprecatedregister] register Py_ssize_t *len /* pointer to length variable or NULL ^~~~~~~~~ In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:3621: build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/helper.cc:207:22: error: variablesized object may not be initialized int addfacearray[constlenfaces  1] = { }; ^~~~~~~~~~~~~~~~~ 7 warnings and 1 error generated. [ 2/21] gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall Wnounused I./sage/cpython I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/sitepackages/cypari2 I./sage/libs/ntl I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/sitepackages/cysignals I/Users/jpalmier/Desktop/Sage/git/sage/local/include I/Users/jpalmier/Desktop/Sage/git/sage/src/sage/ext I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/sitepackages/numpy/core/include Ibuild/cythonized I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 c build/cythonized/sage/rings/complex_arb.c o build/temp.macosx10.9x86_642.7/build/cythonized/sage/rings/complex_arb.o fnostrictaliasing DCYTHON_CLINE_IN_TRACEBACK=1 std=c99 error: command 'gcc' failed with exit status 1 make[4]: *** [sage] Error 1
comment:167 in reply to: ↑ 166 ; followup: ↓ 174 Changed 2 years ago by
Replying to jhpalmieri:
Replying to ghkliem:
Replying to jhpalmieri:
According to the patchbots, the build is failing on a few different platforms.
The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring
lenfaces
as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere#include "Python.h."
gives trouble on OS X with C++17. Now its only a warning and not an error though.I'm confused: if it's fixed, why does the build fail?
In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:3621: build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/helper.cc:207:22: error: variablesized object may not be initialized int addfacearray[constlenfaces  1] = { };
This line is not part of helper.cc anymore. I have no idea, why the patchbot uses an old version.
comment:168 followup: ↓ 170 Changed 2 years ago by
Running doctests with ID 20190227151715308038d2. Git branch: patchbot/ticket_merged Using optional=ccache,dochtml,memlimit,mpir,python2,sage Doctesting entire Sage library. Sorting sources by runtime so that slower doctests are run first.... Doctesting 3799 files using 2 threads. sage t long src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pxd [0 tests, 0.00 s] sage t long src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx ********************************************************************** File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 736, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension Failed example: calculate_dimension(facets) Exception raised: Traceback (most recent call last): File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 671, in _run self.compile_and_execute(example, compiler, test.globs) File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 1095, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension[4]>", line 1, in <module> calculate_dimension(facets) File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 723, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6467) cpdef int calculate_dimension(ListOfFaces faces) except 2: File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 783, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6419) return calculate_dimension_loop(faces.data, nr_faces, faces.face_length) File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 838, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6675) return calculate_dimension_loop(newfaces2data, new_nr_faces, face_length) + 1 File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 830, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6648) sig_on() SignalError: Segmentation fault ********************************************************************** File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 738, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension Failed example: calculate_dimension(vertices) Exception raised: Traceback (most recent call last): File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 671, in _run self.compile_and_execute(example, compiler, test.globs) File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 1095, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension[5]>", line 1, in <module> calculate_dimension(vertices) File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 723, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6467) cpdef int calculate_dimension(ListOfFaces faces) except 2: File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 783, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6419) return calculate_dimension_loop(faces.data, nr_faces, faces.face_length) File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 838, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6675) return calculate_dimension_loop(newfaces2data, new_nr_faces, face_length) + 1 File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 830, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6648) sig_on() SignalError: Segmentation fault ********************************************************************** File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 766, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension Failed example: for _ in range(10): points = tuple(tuple(randint(1000,1000) for _ in range(10)) for _ in range(randint(3,15))) P = Polyhedron(vertices=points) facets = get_facets_from_incidence_matrix(P.incidence_matrix()) vertices = get_vertices_from_incidence_matrix(P.incidence_matrix()) d1 = P.dimension() d2 = calculate_dimension(facets) d3 = calculate_dimension(vertices) if not d1 == d2 == d3: print('calculation_dimension() seems to be incorrect') Exception raised: Traceback (most recent call last): File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 671, in _run self.compile_and_execute(example, compiler, test.globs) File "/local/sagepatchbot/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 1095, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension[8]>", line 8, in <module> d2 = calculate_dimension(facets) File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 723, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6467) cpdef int calculate_dimension(ListOfFaces faces) except 2: File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 783, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6419) return calculate_dimension_loop(faces.data, nr_faces, faces.face_length) File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 838, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6675) return calculate_dimension_loop(newfaces2data, new_nr_faces, face_length) + 1 File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 830, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6648) sig_on() SignalError: Segmentation fault Killed due to segmentation fault **********************************************************************
This has me wondering, what went wrong.
Probably, I should have included
#include <cstdlib> using namespace std;
in helper.cc
in order for calloc
to work the way I use it. Also I should probably return 1
if calloc
returns NULL
and add except 1
to get_next_level
. Woudn't give a nice error message yet, but at least prevent thing from crashing if calloc
returns NULL
.
Alternatively I could still try to allocate the memory with int ommitfacearray[lenfaces1]
and pass lenfaces
to get_next_level
as const size_t
.
A third way would be to allocate the memory with int *ommitfacearray = new int[lenfaces1]
and still have lenfaces
be of type const size_t
.
A fourth way, would be to allocate the memory in Cython and pass it to the function. Then one could also allocate the array only once for an entire FaceIterator
.
Is my guess for the Segmentation fault
even likely?
comment:169 Changed 2 years ago by
 Commit changed from 9f421825ae6eaa4bc800b978ba7e9d529434a0fc to 687d0032794306c563430f03391fac3ba7bf9419
Branch pushed to git repo; I updated commit sha1. New commits:
687d003  replaced calloc by new[]

comment:170 in reply to: ↑ 168 ; followup: ↓ 171 Changed 2 years ago by
new[]
worked fine before, so I tried that. I hope this solves the issue.
I did some googling and got the impression, that calloc
etc. is not really the C++ way of doing it.
Btw, helper.cc doesn't use anything C++specific anymore, so if necessary I could switch to C again. At the moment I don't think it matters.
Replying to ghkliem:
comment:171 in reply to: ↑ 170 Changed 2 years ago by
Replying to ghkliem:
new[]
worked fine before, so I tried that. I hope this solves the issue.I did some googling and got the impression, that
calloc
etc. is not really the C++ way of doing it.
Yes, that is my understanding: you should use new[]
and delete[]
in C++.
Btw, helper.cc doesn't use anything C++specific anymore, so if necessary I could switch to C again. At the moment I don't think it matters.
My understanding is that it does make some minor differences (with compile time, optimization, standards, etc.), but usually not anything noticeable at this scale. Although if it is all pure C except for the malloc
vs. new[]
, I might consider going back to pure C. Yet I have not been in the C/C++ game for a little while and would never classify myself as an expert, so someone who is more knowledgeable in that realm, please correct me if I am wrong.
comment:172 Changed 2 years ago by
One of my colleges just gave me some input on readability.
I will go through the code again and improve readability.
comment:173 Changed 2 years ago by
 Status changed from needs_review to needs_work
As mentioned above, I will try to make the comments more readable. (Writing complete English sentences. More intuitive positions of comments. Etc.)
I will probably also change a few names as facet_repr()
> set_facet_repr()
and then call the corresponding attribute maybe just facet_repr
. Maybe add _current_face
to both.
I have no intentions of changing any actual code, other than renaming (if I think a new name is more descriptive). Maybe I should create a mapping table of renamings?
comment:174 in reply to: ↑ 167 Changed 2 years ago by
Replying to ghkliem:
Replying to jhpalmieri:
Replying to ghkliem:
Replying to jhpalmieri:
According to the patchbots, the build is failing on a few different platforms.
The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring
lenfaces
as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere#include "Python.h."
gives trouble on OS X with C++17. Now its only a warning and not an error though.I'm confused: if it's fixed, why does the build fail?
In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:3621: build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/helper.cc:207:22: error: variablesized object may not be initialized int addfacearray[constlenfaces  1] = { };This line is not part of helper.cc anymore. I have no idea, why the patchbot uses an old version.
It looks like I stumbled over the same problem at my machine. I changed function names in helper.cc
and sage build would completely ignore those changes. Meaning I couldn't use the functions by their new names, but I could use them by their old names.
Somewhere helper.cc
was cached and it was constantly taken from there.
Deleting the cashed files in
src/build/cythonized/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron
and
sage/src/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron
seems to be the solution. The patchbots don't do that I assume.
What's going on?
comment:175 Changed 2 years ago by
I saw this, too, and after deleting those files, this built on my OS X box. I don't know if they are supposed to be cleaned up automatically somehow or not.
comment:176 in reply to: ↑ 145 Changed 2 years ago by
There seem to be scenarios where KeyboardInterrupt
cause sage to crash. It will not use CPU anymore, so somehow it seems to work. But it will look exactly like a failed interrupt, so nothing works anymore in that session.
It seems to happen between 010 percent of the time, when trying to interrupt:
sage: from itertools import combinations sage: N = combinations(range(200),199) sage: C = CombinatorialPolyhedron(N) sage: C.dimension() 199 sage: C.f_vector()
I have tried to figure it out, but I have no idea, what could have happened.
comment:177 Changed 2 years ago by
 Commit changed from 687d0032794306c563430f03391fac3ba7bf9419 to f8a201e41ffc28d9903499988aed2f86db2dee17
Branch pushed to git repo; I updated commit sha1. New commits:
f8a201e  Improved comments all through base.pyx

comment:178 Changed 2 years ago by
 Status changed from needs_work to needs_review
I hope this is easier to read now. I actually went through all the files.
At the moment the tests with alarm
are unstable.
I don't know why. Can anyone figure it out. Or should I just remove them? Especially CombinatorialPolyhedron.f_vector()
seems to be pretty easy to trace.
If anyone cares, here is a list of some of the more important renamings I did:
CountFaceBits > count_atoms facet_repr_from_bitrep > bit_repr_to_coatom_repr char_from_tuple > vertex_list_to_bit_repr char_from_incidence > incidences_to_bit_repr forbidden > visited_all nr_forbidden > nr_visited_all get_facets_from_incidence_matrix > incidence_matrix_to_bit_repr_of_facets get_vertices_from_incidence_matrix > incidence_matrix_to_bit_repr_of_vertices get_facets_bitrep_from_facets_tuple > facets_tuple_to_bit_repr_of_facets get_vertices_bitrep_from_facets_tuple > facets_tuple_to_bit_repr_of_vertices vertex_repr_from_bitrep > bit_repr_to_vertex_list FaceIterator.record_dimension > FaceIterator.request_dimension FaceIterator.yet_to_yield > FaceIterator.yet_to_visit FaceIterator.atom_repr_face > FaceIterator.atom_repr FaceIterator.coatom_repr_face > FaceIterator.coatom_repr FaceIterator.atom_repr > FaceIterator.set_atom_repr FaceIterator.coatom_repr > FaceIterator.set_coatom_repr ListOfAllFaces.atom_repr_face > ListOfAllFaces.atom_repr ListOfAllFaces.coatom_repr_face > ListOfAllFaces.coatom_repr ListOfAllFaces.atom_repr > ListOfAllFaces.set_atom_repr ListOfAllFaces.coatom_repr > ListOfAllFaces.set_coatom_repr ListOfAllFaces.incidence_is_initialized > ListOfAllFaces.is_incidence_initialized
comment:179 Changed 2 years ago by
 Commit changed from f8a201e41ffc28d9903499988aed2f86db2dee17 to df43a2d5391a8c78db78e66a6ab3556a1e1b8689
Branch pushed to git repo; I updated commit sha1. New commits:
df43a2d  improved pseudocode Algorithm in ``FaceIterator``

comment:180 Changed 2 years ago by
 Commit changed from df43a2d5391a8c78db78e66a6ab3556a1e1b8689 to b73e53c9b172eb0b53b0895f49f79b5c6eaac65e
Branch pushed to git repo; I updated commit sha1. New commits:
b73e53c  Corrected a mathematical error in explonation.

comment:181 followup: ↓ 182 Changed 2 years ago by
Is there anything else I should do at this point?
For some reason, I accidentally added my notes and old files. I removed them in git
again. But I don't think its worth a push for now.
I see two open problems at the moment:
 Unstable interrupts in the tests. Remove the tests or fix it. Maybe this issue of an interrupt not completing might not even be caused by me.
 The C++ files are not recompiled when they change (at least not always). I can add a syntax error and the compiler will not notice.
I was thinking about changing the way, I get all the incidences again. This wouldn't be a mayor change, but still a change. Right now, I'm intersecting every face with every facet to get all incidences. It would suffice to intersect every face with all "siblings" of some fixed parent. Then again, the examples I could compute with 30GB of RAM all took less than 10 minutes. And then it seems to me, it is almost impossible to obtain any useful information from a Hasse diagram of that size. So I'm not sure, if there is even use to optimization at this end. Unless, somebody thinks this should be optimized if possible, I'll leave it as it is. It's at least almost as fast in creating the face lattice as polymake the way it is.
comment:182 in reply to: ↑ 181 Changed 2 years ago by
comment:183 Changed 2 years ago by
 Commit changed from b73e53c9b172eb0b53b0895f49f79b5c6eaac65e to 12038d392fc1dba2a34fe27ce0732eb2481104d9
Branch pushed to git repo; I updated commit sha1. New commits:
12038d3  removed notes and old files again

Changed 2 years ago by
Comparison of runtime in comparison to polymake, given only the vertexfacet incidence matrix
comment:184 Changed 2 years ago by
I gave a talk today in the seminar of Michael Joswig's work group.
I added the explanation of the algorithm in pictures. Maybe this is of help. I think it is much better to comprehend than my pseudo code.
I also added the runtime comparison to polymake from the vertexfacet incidences matrix.
I would be thankful for a review and/or comments on what to improve.
Btw, the tests involving alarm
are still unstable and sometimes fail. Maybe the interrupt is just not stable. But, maybe I also did some mistake. I don't know. There is no desperate need for the tests from my perspective.
comment:185 Changed 2 years ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:186 Changed 2 years ago by
@jdemeyer, @tscrim: I would appreciate this ticket to be merged soon so that we can move forward with the project. Do you have any additional critiques to be taken into account or is this ready to go?
Anyway, thanks a lot for your previous work on this ticket!
comment:187 followups: ↓ 193 ↓ 197 Changed 2 years ago by
Main comment:
 the file
base.pyx
is huge. It would be nice to split it.
Technical comments
 no need to inherit from
SageObject
(this is useful if you want your objects to interact with other Sage objects which is is not the case)  why
calculate_dimension
is not a method ofListOfFaces
? nr_vertices
sometimes return a SageInteger and sometimes a Python int (becauselen(X)
returns a Python integer)set_request_dimension
is a weird name Are we supposed to change
set_request_dimension
during iteration as followssage: P = polytopes.cuboctahedron() sage: C = CombinatorialPolyhedron(P) sage: it = C.face_iter() sage: next(it) 0 sage: it.set_request_dimension(2) sage: next(it) 2 sage: it.set_request_dimension(1) sage: next(it) 1
if not thisrequest_dimension
would better be set in the constructor (__init__
), if yes then it should be documented what does this do. get_dimension
is a weird name. It would better be more explicitcurrent_face_dimension
or something similar (no need for the wordget
)
doc of combinatorial_polyhedron/base.pyx
 the first line would better be the title of the module (eg look like
rings/integer.pyx
) [...] works on every lattice that is obtained by from [...]
 Could you precise what the sentence
Representations in this module:
mean. Do you mean that it is the terminology you use in this module? The first bit represent
>represents
we started with
>we started from
 I would rather use
compute
rather thancalculate
 polyhedron used as a noun as no need to be upper cased
Polyhedron
>polyhedron
comment:188 followup: ↓ 192 Changed 2 years ago by
small optimization: use smallInteger
instead of Integer
(this does not create new integer objects but rather uses preallocated small integer objects)
comment:189 Changed 2 years ago by
Might be faster then
>Might be faster than
comment:190 Changed 2 years ago by
 Status changed from needs_review to needs_work
comment:191 Changed 2 years ago by
 Commit changed from 12038d392fc1dba2a34fe27ce0732eb2481104d9 to db48cb0226defdd76dbdc2d7e316a284b9b4fde4
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
9a97096  corrected blocks

a3672a1  FaceIterator is an actual iterator now

3fae342  fixed allocation of array

32eb8d4  it.next() > next(it), also fixed face_lattice_facet_repr for trivial cases

08d49c0  improved documentation mostly

2223ce5  replaced calloc by new[]

a9a052e  Improved comments all through base.pyx

ef7af54  improved pseudocode Algorithm in ``FaceIterator``

4a09a21  Corrected a mathematical error in explonation.

db48cb0  removed notes and old files again

comment:192 in reply to: ↑ 188 ; followup: ↓ 195 Changed 2 years ago by
This is doing a typecast, as it assumes (signed) long
as input.
I'm using size_t
in most cases. But I guess for my use case this is just fine.
Replying to vdelecroix:
small optimization: use
smallInteger
instead ofInteger
(this does not create new integer objects but rather uses preallocated small integer objects)
comment:193 in reply to: ↑ 187 ; followup: ↓ 194 Changed 2 years ago by
Replying to vdelecroix:
Technical comments
 no need to inherit from
SageObject
(this is useful if you want your objects to interact with other Sage objects which is is not the case)
"All objects in Sage should derive from the Cython extension class SageObject
"
http://doc.sagemath.org/html/en/developer/coding_in_python.html?highlight=sageobject
Now I'm a bit confused. The way I understand this now, is that any class a user is intended to see needs to be a SageObject
. Some Cython class way in the background does not need that.
In my case CombinatorialPolyhedron
and FaceIterator
should be SageObjects
, but other classes do not have to be?
comment:194 in reply to: ↑ 193 Changed 2 years ago by
Replying to ghkliem:
Replying to vdelecroix:
Technical comments
 no need to inherit from
SageObject
(this is useful if you want your objects to interact with other Sage objects which is is not the case)"All objects in Sage should derive from the Cython extension class
SageObject
" http://doc.sagemath.org/html/en/developer/coding_in_python.html?highlight=sageobject
This is a very naive generality, I opened #27683
Now I'm a bit confused. The way I understand this now, is that any class a user is intended to see needs to be a
SageObject
. Some Cython class way in the background does not need that.In my case
CombinatorialPolyhedron
andFaceIterator
should beSageObjects
, but other classes do not have to be?
The SageObject
is indeed good for uservisible classes.
comment:195 in reply to: ↑ 192 Changed 2 years ago by
Replying to ghkliem:
This is doing a typecast, as it assumes
(signed) long
as input.I'm using
size_t
in most cases. But I guess for my use case this is just fine.
Indeed, for the range of integers you look at you are very far from the overflow.
comment:196 Changed 2 years ago by
 Commit changed from db48cb0226defdd76dbdc2d7e316a284b9b4fde4 to 1a128f25dbabf6aab69fc37e4e20f7141ce8f3cb
Branch pushed to git repo; I updated commit sha1. New commits:
1a128f2  split the file

comment:197 in reply to: ↑ 187 ; followup: ↓ 198 Changed 2 years ago by
Replying to vdelecroix:
Main comment:
 the file
base.pyx
is huge. It would be nice to split it.
Done.
Technical comments
 no need to inherit from
SageObject
(this is useful if you want your objects to interact with other Sage objects which is is not the case) why
calculate_dimension
is not a method ofListOfFaces
?nr_vertices
sometimes return a SageInteger and sometimes a Python int (becauselen(X)
returns a Python integer)set_request_dimension
is a weird name Are we supposed to change
set_request_dimension
during iteration as followssage: P = polytopes.cuboctahedron() sage: C = CombinatorialPolyhedron(P) sage: it = C.face_iter() sage: next(it) 0 sage: it.set_request_dimension(2) sage: next(it) 2 sage: it.set_request_dimension(1) sage: next(it) 1if not thisrequest_dimension
would better be set in the constructor (__init__
), if yes then it should be documented what does this do.
I guess this has to go there.
get_dimension
is a weird name. It would better be more explicitcurrent_face_dimension
or something similar (no need for the wordget
)doc of
combinatorial_polyhedron/base.pyx
 the first line would better be the title of the module (eg look like
rings/integer.pyx
)
should I name the module geometry/polyhedron/combinatorial_polyhedorn/combinatorial_polyhedron.pyx
then?
comment:198 in reply to: ↑ 197 Changed 2 years ago by
Replying to ghkliem:
doc of
combinatorial_polyhedron/base.pyx
 the first line would better be the title of the module (eg look like
rings/integer.pyx
)should I name the module
geometry/polyhedron/combinatorial_polyhedorn/combinatorial_polyhedron.pyx
then?
The name of the file is fine. I was referring to the first line in the file
+CombinatorialPolyhedron gathers several algorithms of Polyhedra depending only +on the vertexfacet incidences.
that should be
Combinatorial polyhedron This module gathers algorithms for polyhedra that only depends on the vertexfacet incidences.
comment:199 Changed 2 years ago by
 Commit changed from 1a128f25dbabf6aab69fc37e4e20f7141ce8f3cb to 9b69f506441ea60af9a6c3c078359c533def1a13
comment:200 Changed 2 years ago by
 Status changed from needs_work to needs_review
comment:201 Changed 2 years ago by
 Commit changed from 9b69f506441ea60af9a6c3c078359c533def1a13 to 4e8fd8c582f29960f6fcf5808a0cab0d0daf5b57
Branch pushed to git repo; I updated commit sha1. New commits:
4e8fd8c  correct hyperlinks

comment:202 Changed 2 years ago by
How do I check if all links in the docstrings work?
comment:203 followup: ↓ 205 Changed 2 years ago by
 Branch changed from public/26887 to public/26887bis
 Commit changed from 4e8fd8c582f29960f6fcf5808a0cab0d0daf5b57 to 611099f6ebb69e71dc590af00f150bc2e154a116
 Status changed from needs_review to needs_work
This comment concerns only CombinatorialPolyhedron
in base.pxd
and base.pyx
I added a small commit on top of your branch which just consists of documentation modifications. You might want to review my changes. When they are important, I discuss them below. In a second commit I upgraded the method facets
to avoid iterating twice through the faces. You are free to use the commit as you wish and I put them an a distinct branch.
The sentence
# Edges, ridges and incidences are stored in a pointer of pointers. # This number determines how many edges are stored in ``edges[0]``, # how many ridges are stored in ``ridges[0]`` etc. cdef size_t _length_edges_list
is a bit unclear. Do you mean that the arrays pointed at _edges[0]
, _ridges[0]
and _face_lattice_incidences[0]
have the same length?
The attribute _mem_tuple
is not used. What is it inteded for?
Why this very ambiguous terminology
 Vertices  ``[vertices, rays, lines]`` of the polyhedron.
In PPL
the use the word *generators* for this (as opposed to *constraints* for equalities and inequalities).
This is very cryptic
:class:`~sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator`:: sage: C.face_iter() Iterator over the proper faces of a polyhedron of dimension 4 sage: C.face_iter(2) Iterator over the 2faces of a polyhedron of dimension 4
The above doctest is mostly intended for a user reading the documentation. As a user, I tried the naive
sage: P = polytopes.hypercube(4) sage: C = CombinatorialPolyhedron(P) sage: for f in C.face_iter(): ....: print(f)
and was quite disappointed to see a list of integers. I think that at this point in the documentation, it is much better to provide a concrete example of computations. If the access to face_iter
is already for an advanced user then you can just remove the example.
In the documentation of the ComintorialPolyhedron
class you had three examples dealing with the fact that nr_lines
is mandatory. I removed the two last and made them inside TESTS
. You can freely remove them if you feel they are useless.
is_Polyhedron
(line 275) and is_LatticePolytope
(line 288) are old style coding from when Sage was created. Just use straight isinstance
.
At lines 299
else: # Input is different from ``Polyhedron`` and ``LatticePolytope``. if nr_lines is None: # bounded polyhedron
it is possible that the user specified nr_lines=0
in which case you might also want to set self._unbounded = False
. Also, when nr_lines < 0
you would better raise a ValueError
.
At line 324, the sentence is incomplete
# At the moment this test only works for input being
At line 346, the following test is not exhaustive enough
elif isinstance(data, Integer):
as it will not catch Python integers
sage: CombinatorialPolyhedron(3r) Traceback (most recent call last): ... TypeError: argument 2 to map() must support iteration
You should be using
sage: import numbers sage: isinstance(3r, numbers.Integral) True sage: isinstance(3, numbers.Integral) True
On the class Polyhedron
the howmanyarethere methods are called
n_vertices
, n_rays
, n_lines
, n_inequalities
(with alias n_facets
), n_equations
while you choose nr_vertices
, nr_facets
. Why this difference?
line 625627
return Integer(self._length_Vrep) else: return Integer(len(self.vertices()))
line 737
return Integer(self._nr_facets)
you can use smallInteger
New commits:
72ac3b0  documentation fix

611099f  Do not iterate twice for CombinatorialPolyhedron.facets()

comment:204 Changed 2 years ago by
 Branch changed from public/26887bis to public/26887
Looks good to me.
comment:205 in reply to: ↑ 203 Changed 2 years ago by
Thanks.
About names: There are a number of names that should probably changed to be consistent with the (up to date) naming conventions.
How do I call the methods that get the vertices/rays/lines of a face? How do I call the method that gets the facets it is contained in?
I will change nr_... to n_... all through the files eventually.
Replying to vdelecroix:
This comment concerns only
CombinatorialPolyhedron
inbase.pxd
andbase.pyx
I added a small commit on top of your branch which just consists of documentation modifications. You might want to review my changes. When they are important, I discuss them below. In a second commit I upgraded the method
facets
to avoid iterating twice through the faces. You are free to use the commit as you wish and I put them an a distinct branch.The sentence
# Edges, ridges and incidences are stored in a pointer of pointers. # This number determines how many edges are stored in ``edges[0]``, # how many ridges are stored in ``ridges[0]`` etc. cdef size_t _length_edges_listis a bit unclear. Do you mean that the arrays pointed at
_edges[0]
,_ridges[0]
and_face_lattice_incidences[0]
have the same length?
I will make this more precise. _edges[0][0] represents the first index of the first edge _edges[0][1] the second of the first _edges[1][0] the first of the second and so on. _edges[0] stores a total of up _length_edges_list length.
I want to avoid jumping through memory like crazy, but I also want to avoid using too large chunks of continuous memory. Hence this intermediate solution.
The attribute
_mem_tuple
is not used. What is it inteded for?
It is used. The MemoryAllocators? that store edges, ridges and face_lattice_incidences get put there. The module first calculates the edges and on success copies the data. Only then does it also copy the MemoryAllocator?. Otherwise, the memory is free again.
Why this very ambiguous terminology
 Vertices  ``[vertices, rays, lines]`` of the polyhedron.In
PPL
the use the word *generators* for this (as opposed to *constraints* for equalities and inequalities).
In FaceIterator
I use atoms (which might be generators or constraints depending on whether we do the dual approach or not).
I was thinking about this and then figured that Vrepresentation is a pretty bad name for [vertices, rays, lines]
anyway.
I don't care. I can change this at some point.
This is very cryptic
:class:`~sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator`:: sage: C.face_iter() Iterator over the proper faces of a polyhedron of dimension 4 sage: C.face_iter(2) Iterator over the 2faces of a polyhedron of dimension 4The above doctest is mostly intended for a user reading the documentation. As a user, I tried the naive
sage: P = polytopes.hypercube(4) sage: C = CombinatorialPolyhedron(P) sage: for f in C.face_iter(): ....: print(f)and was quite disappointed to see a list of integers. I think that at this point in the documentation, it is much better to provide a concrete example of computations. If the access to
face_iter
is already for an advanced user then you can just remove the example.
No it was not intended to be for an advanced user. I will try setting up the result of the iterater as a class CombinatorialFace
just like with Polyhedron.faces
. If this does not have a noticable effect on runtime, I think this is the much better solution.
This would also make FaceIterator
smaller.
In the documentation of the
ComintorialPolyhedron
class you had three examples dealing with the fact thatnr_lines
is mandatory. I removed the two last and made them insideTESTS
. You can freely remove them if you feel they are useless.
is_Polyhedron
(line 275) andis_LatticePolytope
(line 288) are old style coding from when Sage was created. Just use straightisinstance
.
What do I do for matrix? isinstance(M,sage.matrix.matrix0.Matrix)?
At lines 299
else: # Input is different from ``Polyhedron`` and ``LatticePolytope``. if nr_lines is None: # bounded polyhedronit is possible that the user specified
nr_lines=0
in which case you might also want to setself._unbounded = False
. Also, whennr_lines < 0
you would better raise aValueError
.
By nr_lines=0
, I mean that the Polyhedron is unbounded. Maybe this is not a good choice and I should put unbounded as an extra argument for the input.
At line 324, the sentence is incomplete
# At the moment this test only works for input beingAt line 346, the following test is not exhaustive enough
elif isinstance(data, Integer):as it will not catch Python integers
sage: CombinatorialPolyhedron(3r) Traceback (most recent call last): ... TypeError: argument 2 to map() must support iterationYou should be using
sage: import numbers sage: isinstance(3r, numbers.Integral) True sage: isinstance(3, numbers.Integral) True
Thanks. I wasn't aware of this at all. In particual I didn't know of the nice solution. Somewhere else I do a try: if a == Integer(a)
...
On the class
Polyhedron
the howmanyarethere methods are calledn_vertices
,n_rays
,n_lines
,n_inequalities
(with aliasn_facets
),n_equations
while you choosenr_vertices
,nr_facets
. Why this difference?
Historic. I changed at at findpoly.org now to be consistent with Polyhedron. I should change this.
line 625627
return Integer(self._length_Vrep) else: return Integer(len(self.vertices()))line 737
return Integer(self._nr_facets)you can use
smallInteger
New commits:
72ac3b0 documentation fix
611099f Do not iterate twice for CombinatorialPolyhedron.facets()
comment:206 Changed 2 years ago by
 Commit changed from 611099f6ebb69e71dc590af00f150bc2e154a116 to d38e1300355722815880dbd633863dd4d1b54173
Branch pushed to git repo; I updated commit sha1. New commits:
d38e130  added combinatorial face

comment:207 Changed 2 years ago by
 Commit changed from d38e1300355722815880dbd633863dd4d1b54173 to ca606656ddadfd4da9f98a74d0406b967a825698
Branch pushed to git repo; I updated commit sha1. New commits:
ca60665  improved docstring in list_of_all_faces

comment:208 Changed 2 years ago by
 Status changed from needs_work to needs_review
I moved some of the methods to CombinatorialFace
now. This should be much nicer for a regular user to handle. The iterator returns something that one can use.
comment:209 Changed 2 years ago by
does not build, see patchbot reports
comment:210 Changed 2 years ago by
 Commit changed from ca606656ddadfd4da9f98a74d0406b967a825698 to abe00b66751c26f756b7b247064f8db01d5b0f0e
Branch pushed to git repo; I updated commit sha1. New commits:
abe00b6  fixed small issues

comment:211 followups: ↓ 212 ↓ 217 Changed 23 months ago by
Just some small things. I am likely to accept a positive review on next round.
 You use custom bitsets. Why not using the one provided in SageMath
sage.data_structures/bitest.[pxi,pxd]
? Most of it already uses optimized routines from GMP.
 The name
ListOfAllFaces
sounds really strange.
 It would be good to simplfy and uniformize string representations
 CombinatorialPolyhedron
Combinatorial type of a polyhedron of dimension 4 with 16 vertices
would better beA 4dimensional combinatorial polyhedron with 16 vertices
 FaceIterator
Iterator over the 2faces of a polyhedron of dimension 4
would better beIterator over the 2faces of a 4dimensional combinatorial polyhedron
 CombinatorialFace
Combinatorial type of a 2dimensional face of a 3dimensional polyhedron
would better beA 2dimensional face of 3dimensional combinatorial polyhedron
 CombinatorialPolyhedron
 in
face_iterator.pyx
andlist_of_faces.pyx
there is no need to redefine the terminology already used inbase.pyx
. Just make a reference to the module.
 If the error at line 2012 in of
base.pyx
can happen in a normal run it should be doctested. If not, replace it with aRuntimeError
.
 The module title should be words (not ListOfAllFaces or ListOfFaces)
comment:212 in reply to: ↑ 211 Changed 23 months ago by
Replying to vdelecroix:
Just some small things. I am likely to accept a positive review on next round.
 You use custom bitsets. Why not using the one provided in SageMath
sage.data_structures/bitest.[pxi,pxd]
? Most of it already uses optimized routines from GMP.
I wasn't aware of this at all. At some point I was looking for it but didn't find it.
To compute the fvector etc. very fast, it seems to be important to not allocate any memory at all during the iteration (I actually should move the one alloc in get_next_level
to a global property in FaceIterator
as it will speed things up by about 4 percent).
In order to make this all work, I would have to use bitset_t
directly.
I guess I could. At the moment, it doesn't seem to me that the code will get a lot easier. Instead of allocating my memory with MemoryAllocator
I would then allocate it with Bitset
. The advantage of reinventing the wheel is that I could later enable intrinsics, which would give a speedup of at least 2 on many computers. I don't know how important this is.
 The name
ListOfAllFaces
sounds really strange.
 It would be good to simplfy and uniformize string representations
 CombinatorialPolyhedron
Combinatorial type of a polyhedron of dimension 4 with 16 verticeswould better beA 4dimensional combinatorial polyhedron with 16 vertices FaceIterator
Iterator over the 2faces of a polyhedron of dimension 4would better beIterator over the 2faces of a 4dimensional combinatorial polyhedron CombinatorialFace
Combinatorial type of a 2dimensional face of a 3dimensional polyhedronwould better beA 2dimensional face of 3dimensional combinatorial polyhedron
 in
face_iterator.pyx
andlist_of_faces.pyx
there is no need to redefine the terminology already used inbase.pyx
. Just make a reference to the module.
 If the error at line 2012 in of
base.pyx
can happen in a normal run it should be doctested. If not, replace it with aRuntimeError
.
This type of error is mostly meant for the case of an interrupt happening (in this case it will not be raised though). I don't expect this to happen ever.
 The module title should be words (not ListOfAllFaces or ListOfFaces)
comment:213 followup: ↓ 214 Changed 23 months ago by
It would be good to simplfy and uniformize string representations
Here are two more issues with the repr:
sage: P = Polyhedron(ieqs=[[0,1]]); P A 1dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex and 1 ray sage: CombinatorialPolyhedron(P) Combinatorial type of a polyhedron of dimension 1 with 1 vertices
Why do you suppress the information about the ray here?
sage: P = Polyhedron(ieqs=[[0,1,0]]); P A 2dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex, 1 ray, 1 line
This is correct if we consider P to be the product of a single ray starting from the origin and a line. But this polyhedron itself does not have a onedimensional face (aka vertex) in the usual definition of faces. On the other hand,
sage: CombinatorialPolyhedron(P) Combinatorial type of a polyhedron of dimension 2 with 0 vertices
is correct, but suppresses the information about rays and lines.
Also, might it be worth being able to provide the information about atoms, coatoms and ignored facets (if any) in the lattice that is used to iterate through all faces?
comment:214 in reply to: ↑ 213 ; followups: ↓ 215 ↓ 221 Changed 23 months ago by
Replying to stumpc5:
It would be good to simplfy and uniformize string representations
Here are two more issues with the repr:
sage: P = Polyhedron(ieqs=[[0,1]]); P A 1dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex and 1 ray sage: CombinatorialPolyhedron(P) Combinatorial type of a polyhedron of dimension 1 with 1 verticesWhy do you suppress the information about the ray here?
sage: P = Polyhedron(ieqs=[[0,1,0]]); P A 2dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex, 1 ray, 1 lineThis is correct if we consider P to be the product of a single ray starting from the origin and a line. But this polyhedron itself does not have a onedimensional face (aka vertex) in the usual definition of faces. On the other hand,
sage: CombinatorialPolyhedron(P) Combinatorial type of a polyhedron of dimension 2 with 0 verticesis correct, but suppresses the information about rays and lines.
I could just add it, I guess.
Also, might it be worth being able to provide the information about atoms, coatoms and ignored facets (if any) in the lattice that is used to iterate through all faces?
Can you be more precise? I don't get what you want.
Should I store the information somewhere, if one does ignore_subfaces
?
What do you mean by provide the information about atoms and coatoms?
comment:215 in reply to: ↑ 214 ; followup: ↓ 216 Changed 23 months ago by
Replying to ghkliem:
Can you be more precise? I don't get what you want.
Sorry  I meant to ask you to provide methods atoms
, coatoms
and ( ignored_facet
or facet_at_infinity
). Also, it is worth pointing in the documentation to the description of the algorithm in the paper so that it becomes clear what atoms and coatoms are.
comment:216 in reply to: ↑ 215 Changed 23 months ago by
Replying to stumpc5:
Replying to ghkliem:
Can you be more precise? I don't get what you want.
Sorry  I meant to ask you to provide methods
atoms
,coatoms
and (ignored_facet
orfacet_at_infinity
). Also, it is worth pointing in the documentation to the description of the algorithm in the paper so that it becomes clear what atoms and coatoms are.
At the moment the FaceIterator
is just an Iterator with two extra methods (that manipulate iteration). I don't know, how much sense it makes, to provide more methods.
The method ignored_facet
does not make any sense at the moment. For an unbounded polyhedron, there is no facet at infinity as part of the input. Not providing the facet at infinity works as well (and this is the way the Iterator is set up).
One could add a method, that provides the faces that are currently ignored.
While the iterator knows coatoms (and their names) it doesn't know the atoms (only their names). The atoms are calculated along the way (while the names for the indices might have been provided). Adding such a method isn't a big deal, but it's not there at the moment.
comment:217 in reply to: ↑ 211 ; followup: ↓ 218 Changed 23 months ago by
Replying to vdelecroix:
Just some small things. I am likely to accept a positive review on next round.
 The name
ListOfAllFaces
sounds really strange.
Can we agree on a name, before I change it?
This class stores all faces of the polyhedron to generate then all cover relations for the face lattice. Possibly in the future it can also calculate a specified flag vector.
What would be a good name for it?
FaceLattice(Creator)
, CoverRelations
. I can't think of a better name at the moment.
comment:218 in reply to: ↑ 217 ; followup: ↓ 220 Changed 23 months ago by
Replying to ghkliem:
Replying to vdelecroix:
Just some small things. I am likely to accept a positive review on next round.
 The name
ListOfAllFaces
sounds really strange.Can we agree on a name, before I change it?
This class stores all faces of the polyhedron to generate then all cover relations for the face lattice. Possibly in the future it can also calculate a specified flag vector.
What would be a good name for it?
FaceLattice(Creator)
,CoverRelations
. I can't think of a better name at the moment.
A name closer to the initial one is PolyhedronFaces
. If this object contains all the information about the lattice, then PolyhedronFaceLattice
is even better.
comment:219 Changed 23 months ago by
 Status changed from needs_review to needs_work
comment:220 in reply to: ↑ 218 Changed 23 months ago by
Replying to vdelecroix:
then
PolyhedronFaceLattice
is even better.
I like it.
I will be working in the comments now. Might take some time, as I'm only able to work 5 minutes at a time or so (or at night).
comment:221 in reply to: ↑ 214 Changed 23 months ago by
I now give the number of facets. This seems more natural to me, as this is how CombinatorialPolyhedron
is constructed from the facets.
This seems to be more meaningful for many unbounded polyhedra as well (unless one wants to count lowest dimensional proper faces as "vertices").
Also it seems hard to determine the difference between vertices and rays from an incidence matrix.
At the moment this module is not optimized for unbounded polyhedra, but I guess this should be left for later (e.g. the vertices are recalculated every time).
Replying to ghkliem:
Replying to stumpc5:
It would be good to simplfy and uniformize string representations
Here are two more issues with the repr:
sage: P = Polyhedron(ieqs=[[0,1]]); P A 1dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex and 1 ray sage: CombinatorialPolyhedron(P) Combinatorial type of a polyhedron of dimension 1 with 1 verticesWhy do you suppress the information about the ray here?
sage: P = Polyhedron(ieqs=[[0,1,0]]); P A 2dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex, 1 ray, 1 lineThis is correct if we consider P to be the product of a single ray starting from the origin and a line. But this polyhedron itself does not have a onedimensional face (aka vertex) in the usual definition of faces. On the other hand,
sage: CombinatorialPolyhedron(P) Combinatorial type of a polyhedron of dimension 2 with 0 verticesis correct, but suppresses the information about rays and lines.
I could just add it, I guess.
Also, might it be worth being able to provide the information about atoms, coatoms and ignored facets (if any) in the lattice that is used to iterate through all faces?
Can you be more precise? I don't get what you want. Should I store the information somewhere, if one does
ignore_subfaces
? What do you mean by provide the information about atoms and coatoms?
comment:222 Changed 23 months ago by
 Commit changed from abe00b66751c26f756b7b247064f8db01d5b0f0e to 87653135948037f4e385a8cb0896379cda1608d6
Branch pushed to git repo; I updated commit sha1. New commits:
8765313  A number of small edits.

comment:223 Changed 23 months ago by
 Status changed from needs_work to needs_review
I think I took care of above comments.
comment:224 Changed 23 months ago by
 Reviewers set to Jeroen Demeyer, Travis Scrimshaw, Vincent Delecroix
I propose to move forward and set to positive review. If nobody objects, I will do so later today.
comment:225 followup: ↓ 226 Changed 23 months ago by
I don't want to slow this ticket down by any means. Anyways, isn't the following two times the same combinatorial polyhedron
sage: def KunzCone(m): ....: V = ZZ^(m1) ....: B = V.basis() ....: ieqs = [ [0] + list(B[i1]+B[j1]B[(i+j1) % m]) for j in [1 .. m1] for i in [1 .. j] if i+j != m] ....: return Polyhedron(ieqs=ieqs, backend="normaliz") sage: P = KunzCone(5) sage: Q1 = CombinatorialPolyhedron(P) sage: Q1 Combinatorial type of a polyhedron of dimension 4 with 1 vertices sage: Q2 = CombinatorialPolyhedron(Q1.facets(names=False)) sage: Q2 Combinatorial type of a polyhedron of dimension 4 with 9 vertices sage: Q1.f_vector(); Q2.f_vector() (1, 1, 8, 14, 8, 1) (1, 1, 8, 14, 8, 1)
and can thus only have either 1 or 9 vertices (whatever the definition of vertices might be)?
As said, I would positive about letting this passas it is really strong computationalwiseand postpone any minor issues into new tickets.
comment:226 in reply to: ↑ 225 ; followup: ↓ 227 Changed 23 months ago by
The representation has changed to give the number of facets now. So this output won't happen like this anymore.
Anyway, one has to set the correct nr_lines
, when giving a list of facets for an unbounded polyhedron.
if the polyhedron is unbounded, then rays and lines and the extra argument
nr_lines
are required
It his hard to determine from a list, which elements of the Vrepresentation
are actually vertices and which are rays (and in one instance it is impossible to distinct between nr_lines = 0
and nr_lines = 1
just from this input, hence the requirement).
If the polyhedron is not unbounded, than the algorithm can just proceed on the polar polyhedron, this is not possible in the unbounded case.
Replying to stumpc5:
I don't want to slow this ticket down by any means. Anyways, isn't the following two times the same combinatorial polyhedron
sage: def KunzCone(m): ....: V = ZZ^(m1) ....: B = V.basis() ....: ieqs = [ [0] + list(B[i1]+B[j1]B[(i+j1) % m]) for j in [1 .. m1] for i in [1 .. j] if i+j != m] ....: return Polyhedron(ieqs=ieqs, backend="normaliz") sage: P = KunzCone(5) sage: Q1 = CombinatorialPolyhedron(P) sage: Q1 Combinatorial type of a polyhedron of dimension 4 with 1 vertices sage: Q2 = CombinatorialPolyhedron(Q1.facets(names=False)) sage: Q2 Combinatorial type of a polyhedron of dimension 4 with 9 vertices sage: Q1.f_vector(); Q2.f_vector() (1, 1, 8, 14, 8, 1) (1, 1, 8, 14, 8, 1)and can thus only have either 1 or 9 vertices (whatever the definition of vertices might be)?
As said, I would positive about letting this passas it is really strong computationalwiseand postpone any minor issues into new tickets.
comment:227 in reply to: ↑ 226 Changed 23 months ago by
I think the input arguments should be more intuitive. I also think this should happen in a follow up ticket.
Instead of doing it all over n_lines
, one should have another argument is_bounded
.
I think this is easier to use.
Replying to ghkliem:
The representation has changed to give the number of facets now. So this output won't happen like this anymore.
Anyway, one has to set the correct
nr_lines
, when giving a list of facets for an unbounded polyhedron.
if the polyhedron is unbounded, then rays and lines and the extra argument
nr_lines
are required
It his hard to determine from a list, which elements of the
Vrepresentation
are actually vertices and which are rays (and in one instance it is impossible to distinct betweennr_lines = 0
andnr_lines = 1
just from this input, hence the requirement). If the polyhedron is not unbounded, than the algorithm can just proceed on the polar polyhedron, this is not possible in the unbounded case.Replying to stumpc5:
I don't want to slow this ticket down by any means. Anyways, isn't the following two times the same combinatorial polyhedron
sage: def KunzCone(m): ....: V = ZZ^(m1) ....: B = V.basis() ....: ieqs = [ [0] + list(B[i1]+B[j1]B[(i+j1) % m]) for j in [1 .. m1] for i in [1 .. j] if i+j != m] ....: return Polyhedron(ieqs=ieqs, backend="normaliz") sage: P = KunzCone(5) sage: Q1 = CombinatorialPolyhedron(P) sage: Q1 Combinatorial type of a polyhedron of dimension 4 with 1 vertices sage: Q2 = CombinatorialPolyhedron(Q1.facets(names=False)) sage: Q2 Combinatorial type of a polyhedron of dimension 4 with 9 vertices sage: Q1.f_vector(); Q2.f_vector() (1, 1, 8, 14, 8, 1) (1, 1, 8, 14, 8, 1)and can thus only have either 1 or 9 vertices (whatever the definition of vertices might be)?
As said, I would positive about letting this passas it is really strong computationalwiseand postpone any minor issues into new tickets.
comment:228 Changed 23 months ago by
 Status changed from needs_review to positive_review
comment:229 Changed 23 months ago by
Please move any further discussion to new tickets.
comment:230 Changed 23 months ago by
 Dependencies #27292 deleted
comment:231 followup: ↓ 232 Changed 22 months ago by
 Status changed from positive_review to needs_work
Fails on e.g. Debian 8:
[sagelib8.8] [ 98/495] gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall Wnounused fPIC I/home/buildbot/slave/sage_git/build/local/include/python2.7 c sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc o build/temp.linuxi6862.7/sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.o [sagelib8.8] In file included from /usr/include/c++/4.9/cstdint:35:0, [sagelib8.8] from sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:13: [sagelib8.8] /usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the std=c++11 or std=gnu++11 compiler options. [sagelib8.8] #error This file requires compiler and library support for the \ [sagelib8.8] ^ [sagelib8.8] sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:27:22: error: ‘is_subset’ declared as an ‘inline’ variable
comment:232 in reply to: ↑ 231 ; followup: ↓ 233 Changed 22 months ago by
As far as I know there are two ways of solving this.
Either use the macro __cplusplus
to determine the c++ version and not use inline
if it is not available. (This would be a quick fix I guess).
Use std=c++11
as compile argument.
Any opinions?
Replying to vbraun:
Fails on e.g. Debian 8:
[sagelib8.8] [ 98/495] gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall Wnounused fPIC I/home/buildbot/slave/sage_git/build/local/include/python2.7 c sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc o build/temp.linuxi6862.7/sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.o [sagelib8.8] In file included from /usr/include/c++/4.9/cstdint:35:0, [sagelib8.8] from sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:13: [sagelib8.8] /usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the std=c++11 or std=gnu++11 compiler options. [sagelib8.8] #error This file requires compiler and library support for the \ [sagelib8.8] ^ [sagelib8.8] sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:27:22: error: ‘is_subset’ declared as an ‘inline’ variable
comment:233 in reply to: ↑ 232 Changed 22 months ago by
Replying to ghkliem:
As far as I know there are two ways of solving this.
Either use the macro
__cplusplus
to determine the c++ version and not useinline
if it is not available. (This would be a quick fix I guess).Use
std=c++11
as compile argument.Any opinions?
Add the std=c++11
option to the concerned extension
Extension('sage.geometry.polyhedron.combinatorial_polyhedron.bit_vector_operations.cc', sources = ['sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc'], extra_compile_args=['std=c++11']),
comment:234 Changed 22 months ago by
 Commit changed from 87653135948037f4e385a8cb0896379cda1608d6 to 39a70997144faad3c3656770fb17de1e6c4805eb
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
092c916  split list_of_faces, fixed imports etc.

46d54b3  added documentation and examples to each module

8ee84ce  correct hyperlinks

3869c1f  documentation fix

938b04c  Do not iterate twice for CombinatorialPolyhedron.facets()

e6d5b08  added combinatorial face

69e28ba  improved docstring in list_of_all_faces

1e2a52b  fixed small issues

e298ed0  A number of small edits.

39a7099  added compile argument std=c++11

comment:235 Changed 22 months ago by
 Status changed from needs_work to needs_review
added compile argument, this should work now (also #27987 fixes already a bug in the unbounded case)
Thanks for all the help, btw.
comment:236 Changed 22 months ago by
 Status changed from needs_review to positive_review
comment:237 Changed 22 months ago by
 Milestone changed from sage8.8 to sage8.9
comment:238 Changed 22 months ago by
 Branch changed from public/26887 to 39a70997144faad3c3656770fb17de1e6c4805eb
 Resolution set to fixed
 Status changed from positive_review to closed
comment:239 Changed 21 months ago by
 Commit 39a70997144faad3c3656770fb17de1e6c4805eb deleted
This triggers a new failing doctest with python3sage:
sage t long src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx ********************************************************************** File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 937, in sage.geometry.polyhedron.combinatorial_polyhedron.base.CombinatorialPolyhedron.edge_graph Failed example: G.degree() Expected: [4, 3, 4, 3, 4] Got: [3, 4, 4, 3, 4]
comment:240 Changed 21 months ago by
I have made #28153 for the py3 problem, please review.
comment:241 followup: ↓ 242 Changed 21 months ago by
Some attributes like bitrep_vertices
might have been an unfortunate choice:
As they are accessed by other classes, I'm forced to compute e.g. bitrep_vertices
on initialization. If CombinatorialPolyhedron
was ever to be a parent of Polyhedron_base
(see #10777), this would force a polyhedron to compute the incidence matrix right away.
From my understanding, the decorator @lazy_attribute
is not available for extension types directly. I'm thinking of changing those attributes to methods, such that there is a method bitrep_facets
and an attribute _bitrep_facets
. This way one can later change this to be lazily evaluated.
Any thoughts?
comment:242 in reply to: ↑ 241 Changed 21 months ago by
Replying to ghkliem:
[...]
Please don't post messages waiting for an answer on a closed ticket. Discussion is closed. Open a new ticket and start a discussion there if something is wrong.
the branch is almost empty (no meaningful changes)
New commits:
first push test