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: sage-8.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:

Status badges

Description (last modified by Frédéric Chapoton)

as a very useful tool to have

Change History (16)

comment:1 Changed 5 years ago by Frédéric Chapoton

Branch: u/chapoton/25080
Cc: Jori Mäntysalo added
Commit: aaafd6a148397470a9cb6350b50991fc4b8b1e85
Description: modified (diff)
Status: newneeds_review

New commits:

aaafd6acode for cartesian factorisation of posets

comment:2 Changed 5 years ago by git

Commit: aaafd6a148397470a9cb6350b50991fc4b8b1e85e1d1276ec1309b296a312bfc8cbc587d1981b947

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

e1d1276adding doi

comment:3 Changed 5 years ago by Jori Mäntysalo

Status: needs_reviewneeds_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.

Last edited 5 years ago by Jori Mäntysalo (previous) (diff)

comment:4 Changed 5 years ago by Jori Mäntysalo

Wrong indentation in the reference, i.e. may break Sphinx.

comment:5 Changed 5 years ago by git

Commit: e1d1276ec1309b296a312bfc8cbc587d1981b947c5e9234572681e19ede6a4e4dfbbd510996c09b5

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

c5e9234trac 25080 adding check that poset is connected

comment:6 Changed 5 years ago by git

Commit: c5e9234572681e19ede6a4e4dfbbd510996c09b54a72873d0c8a9bb4daebc0effc446e29c305b46f

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

4a72873trac 25080 adding more tests

comment:7 Changed 5 years ago by Frédéric Chapoton

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 Jori Mäntysalo

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 Jori Mäntysalo

Error in seealso-link, cartesian_product() should be product().

Also there is now two seealso-blocks in product(), and it seems a little strange.

comment:10 Changed 5 years ago by git

Commit: 4a72873d0c8a9bb4daebc0effc446e29c305b46f6ad6d4400abe1e32812683da1a8301283bdb199c

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

6ad6d44trac 25080 change name to factor, other details

comment:11 Changed 5 years ago by Frédéric Chapoton

Status: needs_workneeds_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 Jori Mäntysalo

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 Frédéric Chapoton

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 2-cycles. Given this restricted domain, I think it is best to keep it here for the moment.

comment:14 Changed 5 years ago by Jori Mäntysalo

Reviewers: Jori Mäntysalo
Status: needs_reviewpositive_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 Jori Mäntysalo

Milestone: sage-8.2sage-8.3

comment:16 Changed 5 years ago by Volker Braun

Branch: u/chapoton/250806ad6d4400abe1e32812683da1a8301283bdb199c
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.