On Tue, Mar 22, 2011 at 01:21:44PM -0400, Christian Stump wrote:
> > 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?
>
> I think wrapping them is fine in the hasse diagram, I think usually
> people should use the poset itself and not the hasse diagram. To be
> honest, I don't even see a reason for having a hasse diagram at all,
> why not doing everything in poset, and taking the hasse diagram only
> for printing?
Hmm, running a discussion by e-mail is tricky. I should have clarified
a couple points first. I'll take the following running example:
sage: P = Poset([['a','b','c'], [['a','b'],['a','c']]])
sage: P.cover_relations()
[[a, c], [a, b]]
- Currently, the elements of a poset are wrapped. So if I do:
sage: a,b,c = P
Then a is not the string 'a' but an object wrapping it to make it
officially an element of P:
sage: type(a)
<class
'sage.combinat.posets.elements.FinitePoset_with_category.element_class'>
sage: a.parent() is P
True
So to recover the string 'a', I need to do:
sage: a.element
'a'
In many cases this is convenient; however we have all run into
situations where this is *really* annoying. The purpose of the
'facade' option is to avoid this:
sage: P = Poset([['a','b','c'], [['a','b'],['a','c']]], facade=True)
sage: a,b,c = P
sage: type(a)
<type 'str'>
So, up to checking that everything works smoothly (please bang hard
on it), this problem is solved.
- In the current implementation of FinitePoset the internal data
structure of a poset is its Hasse diagram, stored as an instance of
a subclass HasseDiagram of DiGraph:
sage: P._hasse_diagram
Hasse diagram of a poset containing 3 elements
sage: type(P._hasse_diagram).mro()
[<class 'sage.combinat.posets.hasse_diagram.HasseDiagram'>,
<class 'sage.graphs.digraph.DiGraph'>, ...]
Its vertices are labelled by 0,...,n-1:
sage: P._hasse_diagram.vertices()
[0, 1, 2]
To be complete, this HasseDiagram also contains a matrix m such
that m[i,j]=1 <=> i<=j:
sage: P._hasse_diagram._leq_matrix
[1 1 1]
[0 1 0]
[0 0 1]
The rationale for using 0,...,n-1 is that this makes the code
simpler and quite faster, in particular when the elements of the
poset are large objects with expensive hash function. That's a
standard approach in the Sage library (see e.g. Mike's patch to
have permutation groups with any domain, or Florent's
FiniteSetMaps).
In principle, this is completely transparent to the user, and in
particular independent of the wrapping issue above. Martin: if you
have a counter example, please provide it so that we can fix it!
Most of the algorithmic is currently implemented in
HasseDiagram. As pointed out by Christian, this is annoying because
for each such algorithm there are two functions; one in
HasseDiagram doing the real job, and one in Poset calling that of
HasseDiagram.
Now, all of the above are just implementation details. Thanks to
encapsulation we could change that, without changing the user
interface. One of the point of extracting categories for posets is
to open the door for alternative implementations of posets using a
different data structure. In short, Christian, you are welcome to
refactor that in a later patch :-)
- One of the very basic question that a mathematician wants to ask to
a finite poset is its Hasse diagram, that is the digraph of its
cover relations (e.g. as Christian points out, to view it). This is
the purpose of the hasse_diagram() method, and has nothing to do
with the internal data structure above. This is why I argue for
keeping the following behaviour:
sage: P = Poset([['a','b','c'], [['a','b'],['a','c']]])
sage: G = P.hasse_diagram()
sage: G.edges()
[(a, c, None), (a, b, None)]
but on the other hand to make G a plain DiGraph. Indeed we
currently have:
sage: G
Hasse diagram of a poset containing 3 elements
which is a broken object because HasseDiagram expects its vertices
to be 0,...,n-1:
sage: G.order_ideal('a')
------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component
Ouch! It's even worse than I thought :-)
Remains the question of whether we would want alternatively to have
the vertices of G not wrapped (mind the quotes):
sage: G.edges()
[('a', 'c', None), ('a', 'b', None)]
But I am fine with keeping it as is; anyway I for myself will
mostly use facade posets now :-)
> > - 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 would keep order_idael and order_filter, I have the impression,
> everything else just causes misunderstandings.
Well, I for myself always think in term of upper or lower ideals; each
time I have to translate this in terms of order ideal or order filter,
I need to lookup the documentation or wikipedia to know which is which :-)
But this is not the question; I am sure happy to keep both functions
if that is clearer for other users. However, from an implementation
point of view I would like to write the algorithmic only once, using a
function with an option. Hence my quest for a good name.
> > 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?
> The panyushev_complement is an operation on antichains, so I would
> prefer not to have such an option.
(a bit of context: the "Panyushev" complement of an antichain `A` in a
poset `P` is the antichain of the smallest elements of `P` which do
not lie in the order ideal of `A`)
There is a fundamental assymetry in this definition; the dual
operation (the highest element in the order filter of A) is as
meaningful. Actually this is the one I need in my calculations :-) So
I insist on having an option.
Another question is what should be the name for this method. I admit
that I would not have stumbled on it if I had not reviewed your patch.
It's a classical operation (and applying it repeatedly probably also
is, though I don't have a ref right now); so I am not sure calling it
Panyushev complement means much outside of the context of root posets.
Anyone suggestions? antichain_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.
>
> I also had this problem already, I would either vote for set's or
> Set's. As set is faster, that's maybe the right thing to do.
Yep. On the other hand they are not hashable. And they are not sage
objects, so one can't use e.g. s.cardinality(). That could make
particular sense for order_ideal's of which we probably will want to
implement lazy variants when investigating large/infinite posets.
At the end of the day, I guess the right thing to do would be to make
Set's as fast as sets :-)
Cheers,
Nicolas
--
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.
