Opened 5 years ago

Closed 5 years ago

#20769 closed enhancement (fixed)

LatticePoset: Orthocomplements, part 1

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.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:

Status badges

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 jmantysalo

  • Branch set to u/jmantysalo/orthocompletion

comment:2 Changed 5 years ago by jmantysalo

  • Commit set to 9a48b1ce1f2370f4d28d6e1eea1d4be79f982e1c
  • Status changed from new to needs_review

Ready for a review. Not necessarily easy one.


New commits:

9a48b1cAdded orthocomplements_iterator()

comment:3 Changed 5 years ago by git

  • Commit changed from 9a48b1ce1f2370f4d28d6e1eea1d4be79f982e1c to b28a9766435ba79a6014a69f4dca114cce51c7fa

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

b28a976Correction of an error on some special cases.

comment:4 Changed 5 years ago by jmantysalo

This was still slightly more complicated than I guessed first.


New commits:

b28a976Correction of an error on some special cases.

comment:5 Changed 5 years ago by jmantysalo

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

typos:

compelements

and

possible orthocomplemet

comment:7 Changed 5 years ago by git

  • Commit changed from b28a9766435ba79a6014a69f4dca114cce51c7fa to 51d4fd0e5ef01b019826b75f1ceb99603586ec18

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

51d4fd0Two typos.

comment:8 Changed 5 years ago by jmantysalo

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 follow-up: Changed 5 years ago by 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.
  • 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 ; follow-up: Changed 5 years ago by jmantysalo

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 non-complemented lattices indirectly. (Btw, the code for complements is broken at corner case, see #20727.)

Last edited 5 years ago by jmantysalo (previous) (diff)

comment:11 Changed 5 years ago by chapoton

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 kdilks

  • Status changed from needs_review to needs_work

comment:13 Changed 5 years ago by git

  • Commit changed from 51d4fd0e5ef01b019826b75f1ceb99603586ec18 to 5d87fe4f41870a1865effa140e4e626b3433fd39

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

5d87fe4Remove second colon from ALGORITHM::

comment:14 Changed 5 years ago by git

  • Commit changed from 5d87fe4f41870a1865effa140e4e626b3433fd39 to 9095e24c3fdc670db0f3b569ebc628e0bbe2b4c1

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

9095e24Typo

comment:15 Changed 5 years ago by jmantysalo

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

  • Reviewers set to Kevin Dilks
  • Status changed from needs_review to positive_review

comment:17 Changed 5 years ago by vbraun

  • Branch changed from u/jmantysalo/orthocompletion to 9095e24c3fdc670db0f3b569ebc628e0bbe2b4c1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.