Opened 5 years ago
Closed 5 years ago
#20769 closed enhancement (fixed)
LatticePoset: Orthocomplements, part 1
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  combinatorics  Keywords:  
Cc:  kdilks  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  9095e24 (Commits, GitHub, GitLab)  Commit:  9095e24c3fdc670db0f3b569ebc628e0bbe2b4c1 
Dependencies:  Stopgaps: 
Description
This patch will add an iterator over orthocomplements of the Hasse diagram of a lattice. (Part 2 will be interface in lattices.py
.)
This was somewhat untrivial to do, hence so much tests.
Change History (17)
comment:1 Changed 5 years ago by
 Branch set to u/jmantysalo/orthocompletion
comment:2 Changed 5 years ago by
 Commit set to 9a48b1ce1f2370f4d28d6e1eea1d4be79f982e1c
 Status changed from new to needs_review
comment:3 Changed 5 years ago by
 Commit changed from 9a48b1ce1f2370f4d28d6e1eea1d4be79f982e1c to b28a9766435ba79a6014a69f4dca114cce51c7fa
Branch pushed to git repo; I updated commit sha1. New commits:
b28a976  Correction of an error on some special cases.

comment:4 Changed 5 years ago by
This was still slightly more complicated than I guessed first.
New commits:
b28a976  Correction of an error on some special cases.

comment:5 Changed 5 years ago by
 Cc kdilks added
Kevin, I haven't asked you for a review in some time... This one might be a little tricky.
comment:6 Changed 5 years ago by
typos:
compelements
and
possible orthocomplemet
comment:7 Changed 5 years ago by
 Commit changed from b28a9766435ba79a6014a69f4dca114cce51c7fa to 51d4fd0e5ef01b019826b75f1ceb99603586ec18
Branch pushed to git repo; I updated commit sha1. New commits:
51d4fd0  Two typos.

comment:8 Changed 5 years ago by
Btw, here is a bad case for this algorithm, if somebody wants to optimize this:
V = VectorSpace(GF(3), 4) X = flatten([list(V.subspaces(d)) for d in range(V.dimension()+1)]) L = LatticePoset( (X, attrcall("is_subspace")) ) H = L._hasse_diagram
comment:9 followup: ↓ 10 Changed 5 years ago by
At last, I have time to look at things. Preliminary comments:
 There should be some sort of definition as to what an orthocomplement is.
 Correction to corner cases has a typo (ortohocomplement).
 This seems to be assuming that the elements of your poset are the integers 1...n . Even if constructing the Hasse diagram ends up assigning a labeling to the elements so the code works, it won't be clear to the user what the output has to do with their original lattice.
 Orthocomplementations are only defined on complemented lattices. I'm not sure if
is_complemented_lattice()
exists or is computationally feasible (TODO?). At the very least the documentation should indicate that the code might be returning the empty list for either reason. Even if a check is computationally difficult, it should probably be included with an optional parameter to skip checking.
comment:10 in reply to: ↑ 9 ; followup: ↓ 16 Changed 5 years ago by
Replying to kdilks:
At last, I have time to look at things. Preliminary comments:
 There should be some sort of definition as to what an orthocomplement is.
More logical place would be in "interface part" in lattices.py
, I think.
 Correction to corner cases has a typo (ortohocomplement).
OK, I'll correct that.
 This seems to be assuming that the elements of your poset are the integers 1...n . Even if constructing the Hasse diagram ends up assigning a labeling to the elements so the code works, it won't be clear to the user what the output has to do with their original lattice.
Again, this should be on interface part (#20817). I think that we must assume that a user reading docs for internal class like HasseDiagram
mostly knows what to do.
 Orthocomplementations are only defined on complemented lattices. I'm not sure if
is_complemented_lattice()
exists or is computationally feasible (TODO?).
We do have is_complemented
at lattices.py
, and it is just O(n^2)
after computing the meets and joins (which is O(n^2.5)
. But this function detects noncomplemented lattices indirectly. (Btw, the code for complements is broken at corner case, see #20727.)
comment:11 Changed 5 years ago by
docstring of sage.combinat.posets.hasse_diagram.HasseDiagram.orthocomplementations_iterator:17: WARNING: Literal block expected; none found.
this is because ALGORITHM should take just one colon
comment:12 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:13 Changed 5 years ago by
 Commit changed from 51d4fd0e5ef01b019826b75f1ceb99603586ec18 to 5d87fe4f41870a1865effa140e4e626b3433fd39
Branch pushed to git repo; I updated commit sha1. New commits:
5d87fe4  Remove second colon from ALGORITHM::

comment:14 Changed 5 years ago by
 Commit changed from 5d87fe4f41870a1865effa140e4e626b3433fd39 to 9095e24c3fdc670db0f3b569ebc628e0bbe2b4c1
Branch pushed to git repo; I updated commit sha1. New commits:
9095e24  Typo

comment:15 Changed 5 years ago by
 Status changed from needs_work to needs_review
OK, now reported errors are corrected.
comment:16 in reply to: ↑ 10 Changed 5 years ago by
 Reviewers set to Kevin Dilks
 Status changed from needs_review to positive_review
comment:17 Changed 5 years ago by
 Branch changed from u/jmantysalo/orthocompletion to 9095e24c3fdc670db0f3b569ebc628e0bbe2b4c1
 Resolution set to fixed
 Status changed from positive_review to closed
Ready for a review. Not necessarily easy one.
New commits:
Added orthocomplements_iterator()