Make the face lattice of a polyhedron a lattice

[jipilab]

Currently, the output object of the method face_lattice is not a lattice but a finite poset. This is also a good opportunity to revamp the method Hasse_diagram_from_incidences which is ill-named.

[novoselt]

Is it ill-named or ill-implemented, if it is in need of a revamp?-)

[jipilab]

I'd say it is not an exclusive "or" in this case...!

The Hasse diagram is an oriented acyclic graph, whereas what is returned is a poset, not the Hasse diagram of that poset... So this is misleading. And I do not see why we could not readily return a LatticePoset? object if it is already. (Maybe there are some reasons not to do this?)

This function is very handy sometimes and could be used for (abstract) combinatorial polytopes.

[novoselt]

I'm not aware of any reasons to avoid LatticePoset. The current output is either inherited from the old implementation or it was the best I found when rewriting it. One thing I do remember however - some tricks were necessary to construct the poset object fast, naive call to the constructor was taking several times more time than computing that acyclic graph itself.

[jipilab]

Replying to novoselt:

I'm not aware of any reasons to avoid LatticePoset. The current output is either inherited from the old implementation or it was the best I found when rewriting it. One thing I do remember however - some tricks were necessary to construct the poset object fast, naive call to the constructor was taking several times more time than computing that acyclic graph itself.

Ah! Ok, good to know! It will be worth benchmarking the difference.

[chapoton]

New commits:

​4face89

make so that face lattice is a lattice

[novoselt]

So since I mentioned it before - was there any benchmarking/profiling looking into the speed of creating this lattice? It used to matter a lot to me when I was working with thousands of (quite small) polytopes.

[jmantysalo]

The comment

# In principle, it is recommended to use Poset or in this case perhaps
# even LatticePoset, but it seems to take several times more time
# than the above computation, makes unnecessary copies, and crashes.

can now be removed.

I suppose this is not going to change the speed (meets and joins will be lazy evaluated), but haven't tested that.

[git]

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

​8ab7591

fixing doctest

[chapoton]

Please, could someone who is interested do the benchmarking ?

[git]

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

​fd0d824

fixing mistake, plus fixing pyflakes warning

[git]

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

​3ff3b60

better handling of file / IOBase

[chapoton]

timings, before:

sage: P = polytopes.hypercube(4)
sage: %time P.face_lattice()
CPU times: user 44.7 ms, sys: 4.22 ms, total: 48.9 ms
Wall time: 40.8 ms
Finite poset containing 82 elements with distinguished linear extension
sage: P = polytopes.associahedron(['A',4])
sage: %time P.face_lattice()
CPU times: user 95.7 ms, sys: 8.17 ms, total: 104 ms
Wall time: 98.6 ms
Finite poset containing 198 elements with distinguished linear extension

and after

sage: P = polytopes.hypercube(4)
sage: %time P.face_lattice()
CPU times: user 33.4 ms, sys: 8.65 ms, total: 42.1 ms
Wall time: 37.9 ms
Finite lattice containing 82 elements with distinguished linear extension
sage: P = polytopes.associahedron(['A',4])
sage: %time P.face_lattice()
CPU times: user 96.1 ms, sys: 3.9 ms, total: 100 ms
Wall time: 95.6 ms
Finite lattice containing 198 elements with distinguished linear extension

[jmantysalo]

All seems to be OK.