Opened 9 years ago
Closed 6 years ago
#12916 closed enhancement (fixed)
DedekindMacNeil completion of finite posets
Reported by:  nthiery  Owned by:  sagecombinat 

Priority:  minor  Milestone:  sage6.5 
Component:  combinatorics  Keywords:  poset, lattice 
Cc:  sagecombinat  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  afbafea (Commits, GitHub, GitLab)  Commit:  afbafeac17420778c803e34e7ae2e3d0cbf05da6 
Dependencies:  Stopgaps: 
Description
The title says it all.
See also: http://en.wikipedia.org/wiki/Dedekind%E2%80%93MacNeille_completion
Attachments (1)
Change History (19)
comment:1 followup: ↓ 2 Changed 9 years ago by
comment:2 in reply to: ↑ 1 ; followup: ↓ 7 Changed 9 years ago by
Replying to chapoton:
I have made a small patch, in the sagecombinat queue, just using the naive algorithm and therefore not very efficient. Is this useful ? Should I put it here ?
Yes; I would even tend to get it into Sage as a provocation: any expert reading the code will think "yikes, *I* can do sooo much better". And will do it :)
comment:3 Changed 9 years ago by
 Priority changed from major to minor
comment:4 Changed 7 years ago by
 Branch set to u/chapoton/12916
 Commit set to 93cefff357a7942b4c7ea539f1d97c9b0e32acb7
New commits:
93cefff  trac #12916 : implements the DedekindMacNeil completion of posets

comment:5 Changed 7 years ago by
 Keywords poset lattice added
comment:6 Changed 7 years ago by
 Status changed from new to needs_review
comment:7 in reply to: ↑ 2 Changed 6 years ago by
 Status changed from needs_review to needs_info
Yes; I would even tend to get it into Sage as a provocation: any expert reading the code will think "yikes, *I* can do sooo much better". And will do it :)
I am precisely the kind of guy who thought that when reading the code, and I don't appreciate at all to see that you consider it a game to make us rewrite other people's hasty code, just because we do not stand such waste of computation. My time is not cheaper than anybody else's.
About this patch:
 The name of the methods that you define is not very informative:
set_of_upper_bounds/set_of_lower_bounds
feels like you will get ally
greater than a givenx
. It is more 'lower_bounds_of_set', but even then it feels a bit awkward. Is there a word in order theory to mean "all elements smaller than x" ? I can't even find a function that would return that for such a vertexx
 Computation of the set of cuts: look at the section entitled
Constructing the set of cuts
in the Wikipedia page that you provided. They say that it is equivalent to list all antichains of the Poset, and for that there is a.antichains_iterator
function. (I wonder how it compares with http://www.sagemath.org/doc/reference/graphs/sage/graphs/independent_sets.html, but that's another subject)
Nathann
comment:8 Changed 6 years ago by
 Commit changed from 93cefff357a7942b4c7ea539f1d97c9b0e32acb7 to 4321c96292f81ba516b825e5b387b7b3bcca07a4
comment:9 Changed 6 years ago by
Hello Nathann,
thanks for the input.
Here is a proposal for another algorithm, using maximal cliques of the incomparability graph of an auxiliary poset. Needs polishing. I do not know if this is faster than before, hopefully yes.
comment:10 Changed 6 years ago by
 Commit changed from 4321c96292f81ba516b825e5b387b7b3bcca07a4 to 2e80c6097ad12abe861ace36e22beb495115c567
Branch pushed to git repo; I updated commit sha1. New commits:
2e80c60  trac #12916 clean up

comment:11 followup: ↓ 12 Changed 6 years ago by
 Status changed from needs_info to needs_review
Ok, needs review again, I think, but I have not done any timings.
comment:12 in reply to: ↑ 11 Changed 6 years ago by
Wow! Excellent, a quite clean result :)
So, about this. I have a couple of comments:
 For very bad reasons, the output of
cliques_maximal
is... sorted. Which is a pure waste. If you want to avoid that you can callIndependentSets
directly.
http://www.sagemath.org/doc/reference/graphs/sage/graphs/independent_sets.html
 The good sideeffect of that is that you do not have to call 'incomparability_graph`, which would do some useless computations in your case (your poset has height two, so its 'incomparability graph' is the graph complement of its hasse diagram)
 Alternatively: during the creation of the aux poset, and instead of your double loop on
u/v
with a testu<=v
, you can do that:g = Graph(((u,0),(v,1)) for u,v in self.cover_relations_iterator())
and then callIndependentSet(complement=True,maximal=True)
when you compute the longest antichains. Advantages:
1) no doubleloop enumerating many pairs in vain 2) the complement is a graph complement (and
IndependentSet
computes this complement as a dense matrix, which is also totally faster).
 The auxiliary poset that you define has no reason to be a poset. I wouldn't care in general, but one of the problems with posets is that they are cached globally, and that every time you create one it will be cached/compared with posets that have been created in the past. Waste of time.
 About 'Set'. Well. I just never use them whenever I can avoid it
sage: e=[1,2,3] sage: %timeit Set(e) 10000 loops, best of 3: 26.5 µs per loop sage: %timeit set(e) 1000000 loops, best of 3: 226 ns per loop sage: %timeit frozenset(e) 1000000 loops, best of 3: 222 ns per loop
Here I do not know, as it is not for internal use only. Do what you think is best.
Ok, needs review again, I think, but I have not done any timings.
About the timings: I do not have any doubt that this algorithm is infintely faster than the previous one. It does what it should, without waste. The only possible waste of computations in your arlgorithm can be in:
 The call to
cliques_maximal
(and I don't mean the sorting problem)
 The construction of
Lattice
(MUCH slower than building a poset, because the creation of a lattice triggers the computation of the join/meet matrix, which is very wastefully implemented.
Your implementation, however, is both short and clean. Just good work.
Nathann
comment:13 Changed 6 years ago by
 Commit changed from 2e80c6097ad12abe861ace36e22beb495115c567 to 569526a5c4f50cb46cfb9b4bface7522fd1a8ba7
Branch pushed to git repo; I updated commit sha1. New commits:
569526a  trac #12916 better algo after reviewer's comments

comment:14 Changed 6 years ago by
 Commit changed from 569526a5c4f50cb46cfb9b4bface7522fd1a8ba7 to afbafeac17420778c803e34e7ae2e3d0cbf05da6
Branch pushed to git repo; I updated commit sha1. New commits:
afbafea  trac #12916 removed now longer used import of Set

comment:15 followup: ↓ 16 Changed 6 years ago by
Ok, thanks. Here is a better version, I hope. Seems to be faster indeed.
No longer uses Poset, Set or incomparability.
Now uses Graph and IndependentSets?
comment:16 in reply to: ↑ 15 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Yo !
Ok, thanks. Here is a better version, I hope. Seems to be faster indeed.
No longer uses Poset, Set or incomparability.
Now uses Graph and IndependentSets?
Passes tests, does the job, good to go!
Nathann
comment:17 Changed 6 years ago by
 Milestone changed from sagewishlist to sage6.5
comment:18 Changed 6 years ago by
 Branch changed from u/chapoton/12916 to afbafeac17420778c803e34e7ae2e3d0cbf05da6
 Resolution set to fixed
 Status changed from positive_review to closed
I have made a small patch, in the sagecombinat queue, just using the naive algorithm and therefore not very efficient. Is this useful ? Should I put it here ?