Opened 4 years ago

Closed 3 years ago

#22455 closed defect (fixed)

_facet_adjacency_matrix not working correctly for non-fulldimensional polyhedra

Reported by: cpegel Owned by:
Priority: major Milestone: sage-8.2
Component: geometry Keywords: polyhedron facets, days88
Cc: jipilab, moritz, vdelecroix Merged in:
Authors: Christoph Pegel, Jean-Philippe Labbé Reviewers: Vincent Delecroix, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: fb5bf91 (Commits, GitHub, GitLab) Commit: fb5bf91a020abee42a758723bd04abec416c8090
Dependencies: Stopgaps:

Status badges

Description (last modified by jipilab)

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 H-representation 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)

facet-adjacency-fix.patch (1.2 KB) - added by cpegel 4 years ago.
proposed patch

Download all attachments as: .zip

Change History (22)

comment:1 follow-up: Changed 4 years ago by jipilab

  • Cc jipilab added

Is this ready for review?

comment:2 in reply to: ↑ 1 Changed 4 years ago by cpegel

Replying to jipilab:

Is this ready for review?

Yes.

comment:3 Changed 4 years ago by jipilab

  • Status changed from new to needs_review

comment:4 follow-up: Changed 4 years ago by jipilab

  • Reviewers set to Jean-Philippe Labbé
  • Status changed from needs_review to needs_work

Hi,

  • You use P for the polyhedron. It should be self (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 H-representation. 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#git-for-sage-development

Let me know if you have problems or question regarding the procedures.

Thanks for the patch.

comment:5 Changed 4 years ago by jipilab

Oh, and you should provide your full name in the "Author" field.

Thanks!

comment:6 Changed 4 years ago by cpegel

  • Authors set to Christoph Pegel

Changed 4 years ago by cpegel

proposed patch

comment:7 in reply to: ↑ 4 Changed 4 years ago by cpegel

Replying to jipilab:

  • You use P for the polyhedron. It should be self (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 H-representation. 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#git-for-sage-development

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 moritz

  • Cc moritz added

comment:9 Changed 4 years ago by jipilab

  • Branch set to u/jipilab/22455

comment:10 Changed 4 years ago by jipilab

  • Cc vdelecroix added
  • Commit set to 371749e2ea43d4563ecfcbb60b5587e546009741
  • Keywords days88 added
  • Status changed from needs_work to needs_review

I added a git branch containing the changes in the patch file.


New commits:

371749eApplied patch

comment:11 Changed 4 years ago by vdelecroix

doctest? There must be an example of what used to fail.

comment:12 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:13 Changed 4 years ago by git

  • Commit changed from 371749e2ea43d4563ecfcbb60b5587e546009741 to 3eb371114a9420b544afec58074dc81cbc78a3ea

Branch pushed to git repo; I updated commit sha1. New commits:

3eb3711Added a doctest

comment:14 Changed 4 years ago by jipilab

  • Description modified (diff)

comment:15 Changed 4 years ago by jipilab

  • Authors changed from Christoph Pegel to Christoph Pegel, Jean-Philippe Labbé
  • Reviewers changed from Jean-Philippe Labbé to Vincent Delecroix
  • Status changed from needs_work to needs_review

comment:16 Changed 4 years ago by jipilab

ping!

comment:17 Changed 3 years ago by git

  • Commit changed from 3eb371114a9420b544afec58074dc81cbc78a3ea to fb5bf91a020abee42a758723bd04abec416c8090

Branch pushed to git repo; I updated commit sha1. New commits:

fb5bf91Merge branch 'u/jipilab/22455' of trac.sagemath.org:sage into 22455

comment:18 Changed 3 years ago by vdelecroix

  • Milestone changed from sage-7.6 to sage-8.2

comment:19 Changed 3 years ago by chapoton

  • 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 jipilab

Cool! Merci!

comment:21 Changed 3 years ago by vbraun

  • Branch changed from u/jipilab/22455 to fb5bf91a020abee42a758723bd04abec416c8090
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.