Opened 6 years ago

Closed 3 years ago

#12916 closed enhancement (fixed)

Dedekind-MacNeil completion of finite posets

Reported by: nthiery Owned by: sage-combinat
Priority: minor Milestone: sage-6.5
Component: combinatorics Keywords: poset, lattice
Cc: sage-combinat Merged in:
Authors: Frédéric Chapoton Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: afbafea (Commits) Commit: afbafeac17420778c803e34e7ae2e3d0cbf05da6
Dependencies: Stopgaps:

Description

Attachments (1)

trac_12916_completion_by_cuts-fc.patch (3.7 KB) - added by chapoton 4 years ago.
a naive implementation

Download all attachments as: .zip

Change History (19)

comment:1 follow-up: Changed 5 years ago by chapoton

I have made a small patch, in the sage-combinat queue, just using the naive algorithm and therefore not very efficient. Is this useful ? Should I put it here ?

comment:2 in reply to: ↑ 1 ; follow-up: Changed 5 years ago by nthiery

Replying to chapoton:

I have made a small patch, in the sage-combinat 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 5 years ago by chapoton

  • Priority changed from major to minor

Changed 4 years ago by chapoton

a naive implementation

comment:4 Changed 4 years ago by chapoton

  • Branch set to u/chapoton/12916
  • Commit set to 93cefff357a7942b4c7ea539f1d97c9b0e32acb7

New commits:

93ceffftrac #12916 : implements the Dedekind-MacNeil completion of posets

comment:5 Changed 3 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Keywords poset lattice added

comment:6 Changed 3 years ago by chapoton

  • Status changed from new to needs_review

comment:7 in reply to: ↑ 2 Changed 3 years ago by ncohen

  • 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 all y greater than a given x. 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 vertex x
  • 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

Last edited 3 years ago by ncohen (previous) (diff)

comment:8 Changed 3 years ago by git

  • Commit changed from 93cefff357a7942b4c7ea539f1d97c9b0e32acb7 to 4321c96292f81ba516b825e5b387b7b3bcca07a4

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

11975a0Merge branch 'u/chapoton/12916' into 6.5.b5
4321c96trac #12916 another algorithm, using auxiliary poset

comment:9 Changed 3 years ago by chapoton

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 3 years ago by git

  • Commit changed from 4321c96292f81ba516b825e5b387b7b3bcca07a4 to 2e80c6097ad12abe861ace36e22beb495115c567

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

2e80c60trac #12916 clean up

comment:11 follow-up: Changed 3 years ago by chapoton

  • 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 3 years ago by ncohen

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 call IndependentSets directly.

http://www.sagemath.org/doc/reference/graphs/sage/graphs/independent_sets.html

  • The good side-effect 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 test u<=v, you can do that: g = Graph(((u,0),(v,1)) for u,v in self.cover_relations_iterator()) and then call IndependentSet(complement=True,maximal=True) when you compute the longest antichains. Advantages:

1) no double-loop 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 3 years ago by git

  • Commit changed from 2e80c6097ad12abe861ace36e22beb495115c567 to 569526a5c4f50cb46cfb9b4bface7522fd1a8ba7

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

569526atrac #12916 better algo after reviewer's comments

comment:14 Changed 3 years ago by git

  • Commit changed from 569526a5c4f50cb46cfb9b4bface7522fd1a8ba7 to afbafeac17420778c803e34e7ae2e3d0cbf05da6

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

afbafeatrac #12916 removed now longer used import of Set

comment:15 follow-up: Changed 3 years ago by chapoton

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 3 years ago by ncohen

  • 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 3 years ago by jdemeyer

  • Milestone changed from sage-wishlist to sage-6.5

comment:18 Changed 3 years ago by vbraun

  • Branch changed from u/chapoton/12916 to afbafeac17420778c803e34e7ae2e3d0cbf05da6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.