Opened 5 years ago
Closed 5 years ago
#25080 closed enhancement (fixed)
code for Cartesian factorization of posets
Reported by:  Frédéric Chapoton  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  combinatorics  Keywords:  
Cc:  Jori Mäntysalo  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 5 years ago by
Branch:  → u/chapoton/25080 

Cc:  Jori Mäntysalo added 
Commit:  → aaafd6a148397470a9cb6350b50991fc4b8b1e85 
Description:  modified (diff) 
Status:  new → needs_review 
comment:2 Changed 5 years ago by
Commit:  aaafd6a148397470a9cb6350b50991fc4b8b1e85 → e1d1276ec1309b296a312bfc8cbc587d1981b947 

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

comment:3 Changed 5 years ago by
Status:  needs_review → 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:5 Changed 5 years ago by
Commit:  e1d1276ec1309b296a312bfc8cbc587d1981b947 → c5e9234572681e19ede6a4e4dfbbd510996c09b5 

Branch pushed to git repo; I updated commit sha1. New commits:
c5e9234  trac 25080 adding check that poset is connected

comment:6 Changed 5 years ago by
Commit:  c5e9234572681e19ede6a4e4dfbbd510996c09b5 → 4a72873d0c8a9bb4daebc0effc446e29c305b46f 

Branch pushed to git repo; I updated commit sha1. New commits:
4a72873  trac 25080 adding more tests

comment:7 Changed 5 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 5 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 5 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 5 years ago by
Commit:  4a72873d0c8a9bb4daebc0effc446e29c305b46f → 6ad6d4400abe1e32812683da1a8301283bdb199c 

Branch pushed to git repo; I updated commit sha1. New commits:
6ad6d44  trac 25080 change name to factor, other details

comment:11 Changed 5 years ago by
Status:  needs_work → needs_review 

All done.
There remains, maybe, the question of using LatticePoset
for the factors when handling products of lattices.
comment:12 Changed 5 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 5 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 5 years ago by
Reviewers:  → Jori Mäntysalo 

Status:  needs_review → 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 5 years ago by
Milestone:  sage8.2 → sage8.3 

comment:16 Changed 5 years ago by
Branch:  u/chapoton/25080 → 6ad6d4400abe1e32812683da1a8301283bdb199c 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
code for cartesian factorisation of posets