#12916: Dedekind-MacNeil completion of finite posets
-------------------------+-------------------------------------------------
Reporter: | Owner: sage-combinat
nthiery | Status: needs_review
Type: | Milestone: sage-wishlist
enhancement | Resolution:
Priority: minor | Merged in:
Component: | Reviewers:
combinatorics | Work issues:
Keywords: | Commit:
poset, lattice | 2e80c6097ad12abe861ace36e22beb495115c567
Authors: | Stopgaps:
Frédéric Chapoton |
Report Upstream: N/A |
Branch: |
u/chapoton/12916 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (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
--
Ticket URL: <http://trac.sagemath.org/ticket/12916#comment:12>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
