LatticePoset: Antidoubling, part 2

[jmantysalo]

This patch adds a backend function to see if a lattice is constructible with Alan Day's doubling construction of convex subsets.

To be added to frontend #22648 later.

[jmantysalo]

New commits:

​79faf90

Another "antidoubling" function.

[jmantysalo]

Arghs, the example is incorrect. Example from ​http://www.math.hawaii.edu/~jb/inflation.pdf page 8 shows how to construct a lattice by doubling a non-convex set ("Reppe's lattice"), but begins with a 9-element lattice that is not constructible by any doubling.

[git]

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

​a80e877

Correct example.

[jmantysalo]

Now a correct example. It is done with

L = Posets.BooleanLattice(3)
L = L.day_doubling([1,3])

def double_no_check(self, S):
    S_ = [self._element_to_vertex(e) for e in S]

    g = self.hasse_diagram()
    g.relabel(lambda e: (e, 0))

    for e in S:
        g.add_edge((e, 0), (e, 1))
        for e_up in self.upper_covers(e):
            if e_up in S:
                g.add_edge((e, 1), (e_up, 1))
            else:
                g.delete_edge((e, 0), (e_up, 0))
                g.add_edge((e, 1), (e_up, 0))

    return LatticePoset(g)

L = double_no_check(L, [(3, 1), (6, 0), (2, 0), (5, 0), (1, 1), (4, 0)])

where (3, 0) shows that the subset to double is not convex.

I may be that there is no smaller example of a lattice costructible by doublings of some subset but not constructible by doublings of convex subset.

[git]

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

​ee37ec5

Merge branch 'develop' into t/22693/antidoubling-part-2

[jmantysalo]

Is there something I can do to make reviewing easier?

[jmantysalo]

Travis? The code is quite direct implementation from the paper.

[tscrim]

One little thing:

-                for ji in congs_ji[cong]:
-                    if self.is_lequal(ji, mi):
-                        return False
+                if any(self.is_lequal(ji, mi) for ji in congs_ji[cong]):
+                    return False

IMO this is cleaner (and I think it might be marginally faster). Otherwise LGTM.

[git]

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

​cf697dd	Merge branch 'develop' into t/22693/antidoubling-part-2
​8597c98	for-loop to any-clause.

[jmantysalo]

Replying to tscrim:

One little thing:

Done. (And tested, just to be sure...)

[tscrim]

Thanks.