Opened 5 years ago

Closed 5 years ago

#17023 closed enhancement (fixed)

Adding width() function to poset

Reported by: jmantysalo Owned by:
Priority: minor Milestone: sage-6.4
Component: combinatorics Keywords:
Cc: ncohen Merged in:
Authors: Nathann Cohen Reviewers: Frédéric Chapoton, Jori Mäntysalo
Report Upstream: N/A Work issues:
Branch: 99f8ed0 (Commits) Commit: 99f8ed04511d4422eb0874a5332132b4058d8e34
Dependencies: Stopgaps:

Description (last modified by chapoton)

Add a .width() -- i.e. number of elements in the longest antichain -- to poset. Seems to have polynomial time algorithm based on Dilworth's Theorem.

Change History (25)

comment:1 Changed 5 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 5 years ago by ncohen

I am writing this code right now.

comment:3 follow-up: Changed 5 years ago by jmantysalo

Fast catch! So there is no function for maximum match at graphs available for wrapping?

comment:4 in reply to: ↑ 3 Changed 5 years ago by ncohen

Fast catch! So there is no function for maximum match at graphs available for wrapping?

There is, but I want to do the job properly.

You can get the width with len(Graph(your_poset.hasse_diagram().transitive_closure()).independent_set()) in the meantime.

Nathann

comment:5 Changed 5 years ago by ncohen

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/17023
  • Status changed from new to needs_review

comment:6 Changed 5 years ago by git

  • Commit set to 50e349b5255c0efd24b4f152d7bc0f3d17ae85bd

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

ad47132trac #16909: transitive_closure() and mutable graphs
711236ctrac #16909: Merged with 6.4.beta3
50e349btrac #17023: Poset.width and Poset.dilworth_decomposition

comment:7 Changed 5 years ago by jmantysalo

  • Status changed from needs_review to needs_work

If height() has description "Return the height (number of elements in the longest chain) of the poset.", then I think that this should have

"Return the height (number of elements in the longest antichain) of the poset.

For information about algorithm, see :wikipedia:Dilworth's_theorem."

Because Dilworth's theorem is not really part of function definition but an implementation detail.

comment:8 Changed 5 years ago by git

  • Commit changed from 50e349b5255c0efd24b4f152d7bc0f3d17ae85bd to 235fc282be25432da0f3e224ffab6ac9c7c5f5e5

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

235fc28trac #17023: Reviwer's remarks

comment:9 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:10 Changed 5 years ago by jmantysalo

Seems to work. I checked extreme cases: empty poset, one-element poset, chains and antichains, all poset of size n up to n=7 and few thousand random posets with varying parameters.

Reading code is propably best done with someone wiser than I am.

One line descriptions should have a dot at the end, because they are full sentences.

comment:11 Changed 5 years ago by chapoton

  • Branch changed from u/ncohen/17023 to public/ticket/17023
  • Commit changed from 235fc282be25432da0f3e224ffab6ac9c7c5f5e5 to 99f8ed04511d4422eb0874a5332132b4058d8e34

Hello,

I made a few little changes. Not a review, sorry.


New commits:

99f8ed0trac #17023 code and doc formatting + one ref

comment:12 follow-up: Changed 5 years ago by jmantysalo

About "return" vs. "returns" on documentation: at least http://legacy.python.org/dev/peps/pep-0008/#documentation-strings shows example with "return". There was also some discussion about this at sage-devel -list at last month. Hence I think that Nathan's code follows style manual.

comment:13 follow-up: Changed 5 years ago by jmantysalo

I did some timings. It seems that for something like P=Posets.RandomPoset(100,0.15) or so it is faster to run max(len(x) for x in P.antichains()) than P.width(). On the other hand the measured complexity of .width() seems to be polynomial as it should.

I will do more test on faster computer, this was done quickly with an oooold machine.

comment:14 follow-up: Changed 5 years ago by jmantysalo

How fast is connected_components() on graphs? Because this can be done simply by summing widths of connected subposets.

If posets are more "chain-like", then simply looking antichains seems to be faster. For posets more "antichain-like" it is much faster to use this new .width() method. Where is the turning point? Can there be some heuristic based on ratio of number of edges to number of vertices?

comment:15 in reply to: ↑ 12 Changed 5 years ago by ncohen

About "return" vs. "returns" on documentation: at least http://legacy.python.org/dev/peps/pep-0008/#documentation-strings shows example with "return". There was also some discussion about this at sage-devel -list at last month. Hence I think that Nathan's code follows style manual.

I think that it follows manual, for not so long ago one of my patches was set to 'needs_work' because I wrote "returns" instead of "return". I do not care if the convention changes at every review for as long as I am not the one who writes the commits.

Nathann

comment:16 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by ncohen

I did some timings. It seems that for something like P=Posets.RandomPoset(100,0.15) or so it is faster to run max(len(x) for x in P.antichains()) than P.width(). On the other hand the measured complexity of .width() seems to be polynomial as it should.

Seems that random posets have a very very small width O_o

Nathann

comment:17 in reply to: ↑ 16 Changed 5 years ago by jmantysalo

Replying to ncohen:

Seems that random posets have a very very small width O_o

Actually this has been thinked already. Brinkmann & McKay? says at the end of paper Posets on up to 16 points "Our results do not show this behaviour, emphasizing again that the convergence of posets to their asymptotic behaviour is quite slow." Hence no help from that.

comment:18 in reply to: ↑ 14 Changed 5 years ago by ncohen

Hello !

How fast is connected_components() on graphs? Because this can be done simply by summing widths of connected subposets.

What do you mean ? If the poset is not connected you can indeed split it and compute the result on each connected components but I don't think the code I implemented will run any faster because of that. It would decrease the number of antichains though. But add an element superior to all others in your posets and you lost connectivity for the very same width.

If posets are more "chain-like", then simply looking antichains seems to be faster. For posets more "antichain-like" it is much faster to use this new .width() method. Where is the turning point? Can there be some heuristic based on ratio of number of edges to number of vertices?

Well, maybe there is some algorithm to recognize posets with width <=2. And we already have a is_chain for width 1. Also, I think that something like

len(Graph(posets.ChainPoset(6).hasse_diagram().transitive_closure()).independent_set())

should be a bit faster than enumerating the antichains. Even though enumerating the antichains may be faster for very very line-looking posets, for you don't have any graphs to copy around, ...

Nathann

comment:19 Changed 5 years ago by jmantysalo

You are right, on average connected posets are far more common than non-connected. Hence this should be like it now is.

Duh, should I try to understand theorem and read the code...

comment:20 follow-up: Changed 5 years ago by jmantysalo

I read the code. As a side not, almost all examples use "P =", you have used "p =".

But as far as I can say, code seems to do what it should. I think this could be marked as positive review after trivial modifications like "returns" vs. "return".

comment:21 in reply to: ↑ 20 Changed 5 years ago by ncohen

I read the code. As a side not, almost all examples use "P =", you have used "p =".

Pleaaaaaase let's not have a rule about upper/lower case T_T

But as far as I can say, code seems to do what it should. I think this could be marked as positive review after trivial modifications like "returns" vs. "return".

Frédéric ? Could you remove the 's' you added ?

Nathann

comment:22 Changed 5 years ago by chapoton

  • Description modified (diff)
  • Status changed from needs_review to positive_review

I think the s in the list of methods should stay there for coherence of this list.

As there is no s in the first line of the new functions, things are good as they are.

LGTM. Let us not lose time on stupid things.

comment:23 Changed 5 years ago by chapoton

  • Reviewers set to Frédéric Chapoton, Jori Mäntysalo

comment:24 Changed 5 years ago by jmantysalo

  • Milestone changed from sage-wishlist to sage-6.4

comment:25 Changed 5 years ago by vbraun

  • Branch changed from public/ticket/17023 to 99f8ed04511d4422eb0874a5332132b4058d8e34
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.