Dear poset fans,
I posted below the current log of the patch. Altogether, I am
essentially done, except for looking at the antichains optimizations,
and a couple issues to be discussed now:
- Currently P.hasse_diagram() returns a graph G whose nodes are the
elements of P (wrapped as elements of P; so one needs to do
x.element to actually get the original element). This graph is still
in the HasseDiagram class. The issue is that HasseDiagram's expect
their vertices to be 0,1,...,n-1, so most of the extra methods just
break.
Option 1: P.hasse_diagram() returns a plain digraph
Option 2: P.hasse_diagram() returns the internal HasseDiagram, with
vertices labelled 0,1,...,n
What do you prefer? I personally vote for 2; as a user, that's what
I would expect.
Another question is whether we want the vertices P.hasse_diagram()
to be wrapped or not. And if we are unhappy with the situation, is
still time to change this?
- There are many methods that are duplicated, depending on whether we
go up or down (order_ideal / order_filter, ...). It would make sense
to factor out the code, by using an option like:
sage: P.order_ideal(direction="up")
(of course keeping P.order_filter as a backward compatibility alias)
I have already used such an option for some of the new methods. What
would be good names for this option and its possible values?
sage: P.order_ideal(ideal = 'up') # resp. 'down'
sage: P.order_ideal(direction = 'ideal') # resp. 'filter'
- Do we want panyuschev_complement to accept such an option?
If yes, should the option describe the direction of the ideal or of
its complement?
- Should methods like order_ideal, order_ideal_generators,
panyushev_complement return set's, tuple's, list's, or Set's?
Currently it's some sort of a mix. I could be convinced to use Sets,
but don't have a strong opinion.
- Does anyone care if the hash function for posets changes? Otherwise
we could just use the default implementation provided by UniqueRepresentation.
Cheers,
Nicolas
------------------------------------------------------------------------------
Highlights
==========
- Adds new categories: Posets(), Lattices() and their finite variants
- Puts Posets(), Posets(n), Poset(...), LatticePoset(...) ... all in
the appropriate categories
- Fix a couple glitches caught by the generic tests (containment,
an_element, ...)
- Add unique representation to Posets
- Adds the following methods:
- order_ideal_generators, order_filter_generators
- is_poset_morphism, is_poset_isomorphism
- is_lattice_morphism
- panyushev_complement, panyushev_orbits
- Standardizes the comparison function names to P.lt(x,y) / le / gt / ge / ...
(TODO: finish)
- Changes the hash of poset elements to delegate the work to the hash
of the underlying element (typically much faster than using repr)
- Systematic renaming of __repr__ to _repr_ in all the Poset code
- Poset elements now have unique representation. This noticably
reduces the overhead of conversion from internal vertices and
elements. In the following an example posted by Christian on
sage-combinat-devel, P.antichains() used to take more than 6s before
the patch:
sage: P = Posets.DiamondPoset(18)
sage: %time A = P._hasse_diagram.antichains()
CPU times: user 0.63 s, sys: 0.00 s, total: 0.63 s
Wall time: 0.65 s
sage: %time A = P.antichains()
CPU times: user 1.05 s, sys: 0.02 s, total: 1.07 s
Wall time: 1.11 s
- As an experimental feature, one can construct facade posets::
sage: P = Poset(DiGraph({'d':['c','b'],'c':['a'],'b':['a']}),
... facade = True)
In this example, the elements of the posets remain plain strings::
sage: d,c,b,a = list(P)
sage: type(a)
<type 'str'>
Of course, those strings are not aware of `P`. So to compare two
such strings, one needs to query `P`::
sage: a < b
True
sage: P.lt(a,b)
False
which models the usual mathematical notation `a<_P b`.
Depends on: #10651 (empty set), #9065 (facade sets), #10938 (Set-issubset)
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
