Opened 6 years ago
Closed 6 years ago
#17023 closed enhancement (fixed)
Adding width() function to poset
Reported by:  jmantysalo  Owned by:  

Priority:  minor  Milestone:  sage6.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 )
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 6 years ago by
 Cc ncohen added
comment:2 Changed 6 years ago by
comment:3 followup: ↓ 4 Changed 6 years ago by
Fast catch! So there is no function for maximum match at graphs available for wrapping?
comment:4 in reply to: ↑ 3 Changed 6 years ago by
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 6 years ago by
 Branch set to u/ncohen/17023
 Status changed from new to needs_review
comment:6 Changed 6 years ago by
 Commit set to 50e349b5255c0efd24b4f152d7bc0f3d17ae85bd
comment:7 Changed 6 years ago by
 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 6 years ago by
 Commit changed from 50e349b5255c0efd24b4f152d7bc0f3d17ae85bd to 235fc282be25432da0f3e224ffab6ac9c7c5f5e5
Branch pushed to git repo; I updated commit sha1. New commits:
235fc28  trac #17023: Reviwer's remarks

comment:9 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:10 Changed 6 years ago by
Seems to work. I checked extreme cases: empty poset, oneelement 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 6 years ago by
 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:
99f8ed0  trac #17023 code and doc formatting + one ref

comment:12 followup: ↓ 15 Changed 6 years ago by
About "return" vs. "returns" on documentation: at least http://legacy.python.org/dev/peps/pep0008/#documentationstrings shows example with "return". There was also some discussion about this at sagedevel list at last month. Hence I think that Nathan's code follows style manual.
comment:13 followup: ↓ 16 Changed 6 years ago by
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 followup: ↓ 18 Changed 6 years ago by
How fast is connected_components()
on graphs? Because this can be done simply by summing widths of connected subposets.
If posets are more "chainlike", then simply looking antichains seems to be faster. For posets more "antichainlike" 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 6 years ago by
About "return" vs. "returns" on documentation: at least http://legacy.python.org/dev/peps/pep0008/#documentationstrings shows example with "return". There was also some discussion about this at sagedevel 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 ; followup: ↓ 17 Changed 6 years ago by
I did some timings. It seems that for something like
P=Posets.RandomPoset(100,0.15)
or so it is faster to runmax(len(x) for x in P.antichains())
thanP.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 6 years ago by
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 6 years ago by
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 "chainlike", then simply looking antichains seems to be faster. For posets more "antichainlike" 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 linelooking posets, for you don't have any graphs to copy around, ...
Nathann
comment:19 Changed 6 years ago by
You are right, on average connected posets are far more common than nonconnected. Hence this should be like it now is.
Duh, should I try to understand theorem and read the code...
comment:20 followup: ↓ 21 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
 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 6 years ago by
 Reviewers set to Frédéric Chapoton, Jori Mäntysalo
comment:24 Changed 6 years ago by
 Milestone changed from sagewishlist to sage6.4
comment:25 Changed 6 years ago by
 Branch changed from public/ticket/17023 to 99f8ed04511d4422eb0874a5332132b4058d8e34
 Resolution set to fixed
 Status changed from positive_review to closed
I am writing this code right now.