Opened 6 years ago

Closed 6 years ago

#22456 closed enhancement (fixed)

LatticePoset: Add subdirect decomposition

Reported by: Jori Mäntysalo Owned by:
Priority: major Milestone: sage-8.0
Component: combinatorics Keywords:
Cc: Martin Rubey, Travis Scrimshaw Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 3c8d86a (Commits, GitHub, GitLab) Commit: 3c8d86af00bd5ec2345059be0c1b7a29dafc3cc0
Dependencies: Stopgaps:

Status badges

Description

Add a function that computes the subdirect decomposition of a lattice.

Change History (10)

comment:1 Changed 6 years ago by Jori Mäntysalo

Branch: u/jmantysalo/latticeposet__add_subdirect_decomposition

comment:2 Changed 6 years ago by Jori Mäntysalo

Cc: Martin Rubey Travis Scrimshaw added
Commit: 65f4c8c59d7a0f3ee84f55a6ad1ebe5aa020d97f
Status: newneeds_review

Some test code:

set_random_seed(321)
N = 100

for i in range(N):
    L = Posets.RandomLattice(randint(10, 20), 0.997)
    Ld = L.subdirect_decomposition()

    if not L.is_subdirectly_reducible():
        if len(Ld) != 1:
            print("Error 1")
            raise AssertionError

    else:
        for Lf in Ld:
            if Lf.is_subdirectly_reducible():
                print("Error 2")
                raise AssertionError

        Lp = LatticePoset({0: []})
        for Lf in Ld:
            Lp = Lp.product(Lf)
        try:
            next(Lp.isomorphic_sublattices_iterator(L))
        except StopIteration:
            print("Error 3")
            raise AssertionError

for i in range(N):
    Lp = LatticePoset({0: []})
    for j in range(3):
        L = Posets.ChainPoset(3)
        while L.is_subdirectly_reducible():
            L = Posets.RandomLattice(7, 0.98)
        Lp = Lp.product(L)
    if len(Lp.subdirect_decomposition()) != 3:
        raise AssertionError

print("Seems to work")

New commits:

65f4c8cAdd subdirect_decomposition().

comment:3 Changed 6 years ago by git

Commit: 65f4c8c59d7a0f3ee84f55a6ad1ebe5aa020d97fa55cc6eeb125b37b7a4327a4943e986ad1bcfd49

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

a55cc6eMerge branch 'develop' into t/22456/latticeposet__add_subdirect_decomposition

comment:4 Changed 6 years ago by Travis Scrimshaw

LGTM modulo this little change:

             low = L.lower_covers(e)
             if len(low) == 1:  # a join-irreducible element
-                C[e] = congs[max(e, key=lambda x: cong_ji._element_to_vertex(x))]
-            if len(low) > 1:  # "extending" congruence to avoid re-computation
+                C[e] = congs[max(e, key=cong_ji._element_to_vertex)]
+            elif low:  # "extending" congruence to avoid re-computation
                 low_0 = min(low, key=lambda x: C[x].number_of_subsets())
                 for new_pair in e:

comment:5 Changed 6 years ago by git

Commit: a55cc6eeb125b37b7a4327a4943e986ad1bcfd49680628695b486702af7f8136c14bc6f7ab7b600e

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

6806286Minor code change.

comment:6 in reply to:  4 Changed 6 years ago by Jori Mäntysalo

Status: needs_reviewneeds_work

Replying to tscrim:

C[e] = congs[max(e, key=cong_ji._element_to_vertex)]

Good point, I didn't notice this one.

elif low:  # "extending" congruence to avoid re-computation

Well, OK. Not sure if minimal speedup is worth slightly harder code to understand, len(x) == 1 and len(x) > 1 is cleaner solution.

Compiling and testing, so not ready for review just now.

comment:7 Changed 6 years ago by git

Commit: 680628695b486702af7f8136c14bc6f7ab7b600e3c8d86af00bd5ec2345059be0c1b7a29dafc3cc0

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

3c8d86aA typo in code.

comment:8 Changed 6 years ago by Jori Mäntysalo

Status: needs_workneeds_review

Now ready.

comment:9 Changed 6 years ago by Travis Scrimshaw

Milestone: sage-7.6sage-8.0
Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Looks good, thank you.

comment:10 Changed 6 years ago by Volker Braun

Branch: u/jmantysalo/latticeposet__add_subdirect_decomposition3c8d86af00bd5ec2345059be0c1b7a29dafc3cc0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.