Opened 4 years ago
Closed 4 years ago
#25080 closed enhancement (fixed)
code for Cartesian factorization of posets
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  combinatorics  Keywords:  
Cc:  jmantysalo  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  6ad6d44 (Commits, GitHub, GitLab)  Commit:  6ad6d4400abe1e32812683da1a8301283bdb199c 
Dependencies:  Stopgaps: 
Description (last modified by )
as a very useful tool to have
Change History (16)
comment:1 Changed 4 years ago by
 Branch set to u/chapoton/25080
 Cc jmantysalo added
 Commit set to aaafd6a148397470a9cb6350b50991fc4b8b1e85
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Commit changed from aaafd6a148397470a9cb6350b50991fc4b8b1e85 to e1d1276ec1309b296a312bfc8cbc587d1981b947
Branch pushed to git repo; I updated commit sha1. New commits:
e1d1276  adding doi

comment:3 Changed 4 years ago by
 Status changed from needs_review to needs_work
Fails with disconnected posets, see posets.AntichainPoset(4).factorize()
. Works with the empty poset, but a test for the corner case would be nice.
Maybe this is the best name for this function; however, what will be the name for the converse of ordinal product?
I think that a factor of a lattice is always a lattice. Or is it? Got to think about this later.
E: Also, a test where the underlying undirected graph can be factorized, but the poset can not, would be nice.
comment:4 Changed 4 years ago by
Wrong indentation in the reference, i.e. may break Sphinx.
comment:5 Changed 4 years ago by
 Commit changed from e1d1276ec1309b296a312bfc8cbc587d1981b947 to c5e9234572681e19ede6a4e4dfbbd510996c09b5
Branch pushed to git repo; I updated commit sha1. New commits:
c5e9234  trac 25080 adding check that poset is connected

comment:6 Changed 4 years ago by
 Commit changed from c5e9234572681e19ede6a4e4dfbbd510996c09b5 to 4a72873d0c8a9bb4daebc0effc446e29c305b46f
Branch pushed to git repo; I updated commit sha1. New commits:
4a72873  trac 25080 adding more tests

comment:7 Changed 4 years ago by
Thanks for the comments, Jori.
For the name, my favorite choice would be just "factor". Other possibilies are "factor_cartesian" and "factor_ordinal" ; or maybe "cartesian_factor" and "ordinal_factor".
For the lattice property, I think this holds for the factors, and the same for MeetSemiLattice?, etc. But I do not feel any need for that.
comment:8 Changed 4 years ago by
See http://www.phy.olemiss.edu/~luca/Topics/p/poset_types.html: "Prime poset: One such that all its autonomous subsets are trivial." Is this the same concept with different words? If not, should that be mentioned in OUTPUT
section?
Maybe "factor" or "factorize" is good, as also plain "product" means the Cartesian product.
Is it really a ValueError
to run this with unconnected posets? IMO it should be seen as a missing implementation, as an unconnected poset can be a Cartesian product of two posets.
comment:9 Changed 4 years ago by
Error in seealsolink, cartesian_product() should be product().
Also there is now two seealsoblocks in product(), and it seems a little strange.
comment:10 Changed 4 years ago by
 Commit changed from 4a72873d0c8a9bb4daebc0effc446e29c305b46f to 6ad6d4400abe1e32812683da1a8301283bdb199c
Branch pushed to git repo; I updated commit sha1. New commits:
6ad6d44  trac 25080 change name to factor, other details

comment:11 Changed 4 years ago by
 Status changed from needs_work to needs_review
All done.
There remains, maybe, the question of using LatticePoset
for the factors when handling products of lattices.
comment:12 Changed 4 years ago by
Thanks. Now, to the code. When is if A1 != B1:
evaluated as true? I guess you have implemented an algorithm to factor general digraph, and for poset you don't need all of that.
comment:13 Changed 4 years ago by
The idea is to check that every little square is a commutative square. There are certainly better ways than what I did quickly. The A1 != B1
test is meant to check that parallel arrows in one square go the same way.
The algorithm would possibly work for simple digraphs with no 2cycles. Given this restricted domain, I think it is best to keep it here for the moment.
comment:14 Changed 4 years ago by
 Reviewers set to Jori Mäntysalo
 Status changed from needs_review to positive_review
OK, I'll mark this as positive review. (Change milestone when 8.3 is available.)
I don't see how there could be parallel arrows when the graph is the Hasse diagram of some poset. However, almost all the time is spent in factoring undirected graph, so this makes no real difference.
Output type for lattices can be changed later.
There are some shortcuts that could be used: for example the numbers of minimal elements must not be a prime. Also the number of edges in the Hasse diagram can show that a poset can't be a Cartesian product etc. However, all this can also be added later.
comment:15 Changed 4 years ago by
 Milestone changed from sage8.2 to sage8.3
comment:16 Changed 4 years ago by
 Branch changed from u/chapoton/25080 to 6ad6d4400abe1e32812683da1a8301283bdb199c
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
code for cartesian factorisation of posets