Opened 4 years ago
Closed 3 years ago
#22455 closed defect (fixed)
_facet_adjacency_matrix not working correctly for nonfulldimensional polyhedra
Reported by:  cpegel  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  geometry  Keywords:  polyhedron facets, days88 
Cc:  jipilab, moritz, vdelecroix  Merged in:  
Authors:  Christoph Pegel, JeanPhilippe Labbé  Reviewers:  Vincent Delecroix, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  fb5bf91 (Commits, GitHub, GitLab)  Commit:  fb5bf91a020abee42a758723bd04abec416c8090 
Dependencies:  Stopgaps: 
Description (last modified by )
The method _facet_adjacency_matrix
of the Polyhedron
class produces a wrong matrix for polyhedra that are not of same dimension as their ambient space. For example,
sage: s = polytopes.simplex(2) sage: s._facet_adjacency_matrix() [0 1 1 1] [1 0 0 0] [1 0 0 0] [1 0 0 0]
while it should return
sage: s._facet_adjacency_matrix() [0 1 1] [1 0 1] [1 1 0]
The problem is that what is being checked is the ambient Hrepresentation of some face being of length 2, which is interpreted as "2 facets are intersecting". This approach doesn't work for codimension not equal to 0.
I have attached a proposed patch that takes codimension into account.
Attachments (1)
Change History (22)
comment:1 followup: ↓ 2 Changed 4 years ago by
 Cc jipilab added
comment:2 in reply to: ↑ 1 Changed 4 years ago by
comment:3 Changed 4 years ago by
 Status changed from new to needs_review
comment:4 followup: ↓ 7 Changed 4 years ago by
 Reviewers set to JeanPhilippe Labbé
 Status changed from needs_review to needs_work
Hi,
 You use
P
for the polyhedron. It should beself
(otherwise no test are going to pass)  By the same token, you improve the code because you are not computing the face lattice. Therefore the comment in the code should be removed and the description of the ticket (and the title) should be adapted.
 Is it certain that the equations always start the Hrepresentation? This should be a comment in the
set_adjacent
private function to explain why the indices are shifted.
I am not sure if getting rid of the equations is a good idea, because maybe one would like to use the matrix with the indices given by the Hrepresentation. Perhaps there could be an optional parameter that decides this, and the default could be that the equations are not included.
A last thing, it would be more practical for reviewing and testing that you submit the patch using git.
Instruction can be found here:
http://doc.sagemath.org/html/en/developer/index.html#gitforsagedevelopment
Let me know if you have problems or question regarding the procedures.
Thanks for the patch.
comment:5 Changed 4 years ago by
Oh, and you should provide your full name in the "Author" field.
Thanks!
comment:6 Changed 4 years ago by
comment:7 in reply to: ↑ 4 Changed 4 years ago by
Replying to jipilab:
 You use
P
for the polyhedron. It should beself
(otherwise no test are going to pass)
Right, I forgot to change P
to self
since I was just using this as a script local replacement when testing, thanks.
 By the same token, you improve the code because you are not computing the face lattice. Therefore the comment in the code should be removed and the description of the ticket (and the title) should be adapted.
Since the faces
method of the Polyhedron_base
class calls self.face_lattice()
, this still computes the whole face lattice. So it isn't an improvement regarding this.
 Is it certain that the equations always start the Hrepresentation? This should be a comment in the
set_adjacent
private function to explain why the indices are shifted.
I guess the best idea is to filter the Hrepresentation for inequalities, I'll try how this works out.
I am not sure if getting rid of the equations is a good idea, because maybe one would like to use the matrix with the indices given by the Hrepresentation. Perhaps there could be an optional parameter that decides this, and the default could be that the equations are not included.
I guess this is really the question of what facet_adjacency_matrix
is expected to return. In my opinion: a matrix with numbers of rows/columns equal to the number of facets, in order as they appear in Hrepresentation
. Sure it could have a parameter to get a matrix of size the same as the length of Hrepresentation
, what would be useful values in the corresponding rows/columns?
A last thing, it would be more practical for reviewing and testing that you submit the patch using git.
Instruction can be found here:
http://doc.sagemath.org/html/en/developer/index.html#gitforsagedevelopment
Let me know if you have problems or question regarding the procedures.
Alright, I'll look into it, thanks a lot.
Thanks for the patch.
Thanks for your careful review!
comment:8 Changed 4 years ago by
 Cc moritz added
comment:9 Changed 4 years ago by
 Branch set to u/jipilab/22455
comment:10 Changed 4 years ago by
 Cc vdelecroix added
 Commit set to 371749e2ea43d4563ecfcbb60b5587e546009741
 Keywords days88 added
 Status changed from needs_work to needs_review
comment:11 Changed 4 years ago by
doctest? There must be an example of what used to fail.
comment:12 Changed 4 years ago by
 Status changed from needs_review to needs_work
comment:13 Changed 4 years ago by
 Commit changed from 371749e2ea43d4563ecfcbb60b5587e546009741 to 3eb371114a9420b544afec58074dc81cbc78a3ea
Branch pushed to git repo; I updated commit sha1. New commits:
3eb3711  Added a doctest

comment:14 Changed 4 years ago by
 Description modified (diff)
comment:15 Changed 4 years ago by
 Reviewers changed from JeanPhilippe Labbé to Vincent Delecroix
 Status changed from needs_work to needs_review
comment:16 Changed 4 years ago by
ping!
comment:17 Changed 3 years ago by
 Commit changed from 3eb371114a9420b544afec58074dc81cbc78a3ea to fb5bf91a020abee42a758723bd04abec416c8090
Branch pushed to git repo; I updated commit sha1. New commits:
fb5bf91  Merge branch 'u/jipilab/22455' of trac.sagemath.org:sage into 22455

comment:18 Changed 3 years ago by
 Milestone changed from sage7.6 to sage8.2
comment:19 Changed 3 years ago by
 Reviewers changed from Vincent Delecroix to Vincent Delecroix, Frédéric Chapoton
 Status changed from needs_review to positive_review
ok
comment:20 Changed 3 years ago by
Cool! Merci!
comment:21 Changed 3 years ago by
 Branch changed from u/jipilab/22455 to fb5bf91a020abee42a758723bd04abec416c8090
 Resolution set to fixed
 Status changed from positive_review to closed
Is this ready for review?