Opened 6 years ago
Closed 5 years ago
#17693 closed enhancement (fixed)
mutable poset: a data structure for asymptotic expressions
Reported by:  dkrenn  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  asymptotic expansions  Keywords:  asymptotics 
Cc:  behackl, cheuberg, jmantysalo  Merged in:  
Authors:  Daniel Krenn  Reviewers:  Benjamin Hackl, Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  a0b3d7b (Commits)  Commit:  a0b3d7bce3325e271e53b0a83047a6f80ac28a22 
Dependencies:  Stopgaps: 
Description
The aim of this ticket is to implement a data structure which is to be used within an asymptotic expression (see MetaTicket #17601). This mutable poset stores elements together with its successors and predecessors. Those data is updated when a new element is inserted or an element is removed. It offers a couple of efficient routines for manipulations (all of which will be needed for the asymptotic expression).
Change History (51)
comment:1 Changed 6 years ago by
 Branch set to u/dkrenn/asy/mutable_poset
comment:2 Changed 6 years ago by
 Commit set to e2f884f56743c7d8780586c4b04b3d2e8242ce73
comment:3 followup: ↓ 7 Changed 6 years ago by
 Cc jmantysalo added
A mutable poset class should be stored in sage.combinat.posets
.
Nathann
comment:4 Changed 6 years ago by
This series of comments are the result of an email discussion. Its aim is to give a better understanding of the needs of the data structure used in an asymptotic expression.
An example of an asymptotic expression in say 2 variables (n>oo, t>oo) is
A = n^3*t^2 + 42*n^2*t^2 + 3*n*t^4 + O(t)
This is stored in the mutable poset in the following way: the elements of the poset are exactly the summands of the expression above. This means
sage: A.data # or however this may be called poset(n^3*t^2, 42*n^2*t^2, 3*n*t^4, O(t))
The growth of these summands is partially ordered:
a) n^3*t^2 >= n^2*t^2
b) n^3*t^2 >= t
c) n^2*t^2 >= t
d) n*t^4 >= t
The mutable poset stores/caches the direct successors/predecessors, i.e., only the relations a), c), d), but not b), since this follows by transitivity out of a) and c). Thus, for the example above, we have the following information stored
poset  term O(t) successors: n^3*t^2, 42*n^2*t^2, 3*n*t^4 no predecessors  term 3*n*t^4 no successors predecessors: O(t)  term 42*n^2*t^2 successors: n^3*t^2 predecessors: O(t)  term n^3*t^2 no successors predecessors: 42*n^2*t^2
comment:5 Changed 6 years ago by
We want to perform arithmetic with asymptotic expressions, in particular we need to do efficiently: 1) addition (and multiplication) 2) merging/absorbing terms, e.g.
n^4 + 2*n^2 + 3*n + O(1) + O(n^2) = n^4 + O(n^2)
or
O(n*t) + n + t = O(n*t)
3) removing elements of the poset, because of 2)
To make them efficent, we store successors and predecessors of each element in the poset. These are updated when inserting/removing elements.
Note that an asymptotic expression can contain several Oterms, e.g.
O(n^3 t^2) + O(n^4 t^1) + O(n^2 t^3)
is a valid expression. In the poset each Oterm is a minimal element and they are all pairwise incomparable (thus, the O terms will be an antichain in the poset). Anyhow, nonOterms be be compareable to other elements, e.g. in
3*n*t + O(n) + O(t)
we have n*t >= n
and n*t >= t
.
We also need to deal with situations where we want to insert an
element of the same growth: E.g. 4n+3n = 7n
, 4n+O(n) = O(n)
,
thus, the elements themselves can change during addition. When
merging/absorbing and working with OTerms with explicit
Oconstants, this also occurrs frequently (even with terms of
different growth).
comment:6 Changed 6 years ago by
Note that all the terms (individual summands) support one operation, namely these can be multiplied, maybe coercion is used, e.g.
4*n^2*t * O(n) > O(n^2*t) * O(n) > O(n^3*t)
Thus we have monoids here. "Addition" of terms is more complicated since not always possible. E.g.
n + O(t) = n + O(t)
But since this is an operation we want to have, the data structure has to take this into consideration.
Here an example of the addition of two asymptotic expressions, to see what the poset should do:
B = n^2*t + n + O(1) C = n*t^2 + O(n)
Steps in computing B + C:
1) calculate: B.poset union C.poset This gives
poset(n^2*t, n, O(1), n*t^2, O(n)).
2) simplify: returns
poset(n^2*t, n*t^2, O(n))
To achieve this, we have to search for what can be "absorbed" by the
Oterm O(n)
. These are exactly all the predecessors of O(n)
(not only
the direct, but also the predecessors of the predecessors...)
Thus some kind of caching of predecessors is necessary, but "cache"
has to be updated when modifying the poset.
Note that this data structure does a preprocessing of its relations, which is definitely good for nonsmall instances. At the moment this class should provide an interface for the needed routines. A fine tuning (w.r.t. speed optimization for various sizes) can be done later (if the performance is too bad).
To conclude, the data structure needed in an asymptotic expression needs to deal with dynamic changes (mutability) and do some caching to provide efficient methods. And it needs to do more than a poset which is made mutable. In particular, it has to provide the methods for the above mentioned merging and absorbing.
comment:7 in reply to: ↑ 3 ; followup: ↓ 8 Changed 6 years ago by
Replying to ncohen:
A mutable poset class should be stored in
sage.combinat.posets
.
This class has nothing to do with combinatorics, therefore I am against sage.combinat
. And it implements a data structure and we have sage.data_structures
, so it seems the right place.
comment:8 in reply to: ↑ 7 ; followups: ↓ 9 ↓ 11 ↓ 12 Changed 6 years ago by
This class has nothing to do with combinatorics, therefore I am against
sage.combinat
. And it implements a data structure and we havesage.data_structures
, so it seems the right place.
Graphs are a data structure, they are in graphs/. Incidence Structures are data structure, and they are in combinat/designs. Matrices are a data structure, and they are in matrix/. Posets and Hasse Diagrams are a data structure, and they are in combinat/posets/.
Also, you wrote in your branch a 'todo note' to implement in your MutablePoset
data structure that 20+ methods from the current Posets should be implemented for your new class: the proper way to do that would be to inherit them from posets.
Could you also explain what "shells" are, and how they differ from the 'facade' boolean argument of Posets ?
Thanks,
Nathann
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 6 years ago by
Replying to ncohen:
Also, you wrote in your branch a 'todo note' to implement in your
MutablePoset
data structure that 20+ methods from the current Posets should be implemented for your new class: the proper way to do that would be to inherit them from posets.
A FinitePoset
inherits from Parent
and my understanding is that parents must be immutable.
Thus, IMHO, this mutable poset here should not inherit from FinitePoset
.
comment:10 in reply to: ↑ 9 Changed 6 years ago by
A
FinitePoset
inherits fromParent
and my understanding is that parents must be immutable.
Indeed, but it may actually be time to change that. We are also having problem with this, because apparently the construction of Parent/UniqueRepresentation
instances is known to be very slow, and you "should not build too many of them at once" or it will slow code down a lot.
That is what is already preventing us from implementing a proper iterator over all nonisomorphic posets of a given size: this operation creates too many parents and is the bottleneck in the computations.
If it seems that you are bothered by the same thing, it gives all the more reasons to make that change.
Nathann
comment:11 in reply to: ↑ 8 Changed 6 years ago by
Replying to ncohen:
Could you also explain what "shells" are, and how they differ from the 'facade' boolean argument of Posets ?
There are similarities between shells and facades, but a facade is something in Sage that represent other things and again uses parents/elements (thus immutable). It has welldefined properties and there is even a category for facade sets. The shells in the mutable poset are more like a container for the elements. Ideally a user of the poset does not need them at all (and only a few MutablePoset?methods use them). They are only used inside the posetalgorithms. At one point I thought about making shells and the related methods private, but never did this...
comment:12 in reply to: ↑ 8 ; followup: ↓ 13 Changed 6 years ago by
Replying to ncohen:
Graphs are a data structure
No, graphs are mathematical objects. "a binary symmetric matrix implemented using bitsets" (which could be used for dense graphs) is a data structure.
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Graphs are a data structure
No, graphs are mathematical objects.
I was not thinking of a graph as it is defined in a book, but of Sage's graphs. I should have said "the Graph class" probably.
Nathann
comment:14 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/mutable_poset to u/dkrenn/asy/mutableposet
 Commit changed from e2f884f56743c7d8780586c4b04b3d2e8242ce73 to 1c6b196bac8386f97bb6234a8442040dd52e8b2d
Last 10 new commits:
143dfea  write method element

b348d14  improve/extend docstrings

520bb00  conditional iterations for shells

e443f7e  rename element_exists_hook to merge_hook

b79f1bc  introduce can_merge and rename merge_hook to merge

82ed0f3  a couple of minor rewritings to make the code and doctests nicer

13d4a36  write mergemethods

8584f57  write __len__

a1678ed  remove TODOlist of methods (list is now in separat branch)

1c6b196  write methods for maximal/minimal elements

comment:15 followup: ↓ 16 Changed 5 years ago by
If union()
does same thing as disjoint_union()
in posets and in graphs, please change name accordingly. It seems unnecessary to have INPUT
part at all, if the function has no arguments at all.
Just my two cents. I would give three, if I would have more time.
comment:16 in reply to: ↑ 15 ; followup: ↓ 18 Changed 5 years ago by
Replying to jmantysalo:
If
union()
does same thing asdisjoint_union()
in posets and in graphs, please change name accordingly.
No, it does not do the same. Union takes only one instance of equal elements, whereas disjoint_union makes each one of the equal elements distinct.
It seems unnecessary to have
INPUT
part at all, if the function has no arguments at all.
The developer guide
http://doc.sagemath.org/html/en/developer/coding_basics.html#documentationstrings
says
An INPUT and an OUTPUT block describing the input/output of the function. This is not optional.
Therefore skipping one of these blocks seems to be against the rules (and hopefully helps avoiding the confusion of a missing input block).
Just my two cents. I would give three, if I would have more time.
Many thanks for all your cents.
Best, Daniel
comment:17 Changed 5 years ago by
 Commit changed from 1c6b196bac8386f97bb6234a8442040dd52e8b2d to 19fd1556a56a6d250ca464c385e7960ac715b2ae
Branch pushed to git repo; I updated commit sha1. New commits:
19fd155  allow merge to go over all elements

comment:18 in reply to: ↑ 16 ; followup: ↓ 20 Changed 5 years ago by
Replying to dkrenn:
Replying to jmantysalo:
If
union()
does same thing asdisjoint_union()
in posets and in graphs  
No, it does not do the same.
OK.
It seems unnecessary to have
INPUT
part at all, if the function has no arguments at all.The developer guide says
An INPUT and an OUTPUT block describing the input/output of the function. This is not optional.
True. But I don't think if it has been thinked that "no input" must be documented. Is it in other places? Or should this part of developer guide be changed?
And should for example docstring of .cardinality()
really contain OUTPUT
block saying that output type is sage's Integer
?
comment:19 Changed 5 years ago by
 Status changed from new to needs_review
comment:20 in reply to: ↑ 18 ; followup: ↓ 21 Changed 5 years ago by
Replying to jmantysalo:
The developer guide says
An INPUT and an OUTPUT block describing the input/output of the function. This is not optional.
True. But I don't think if it has been thinked that "no input" must be documented. Is it in other places? Or should this part of developer guide be changed?
I would keep it. (At the moment) the developer guide says to include it and I find it very nice to have constistent docstrings starting with oneliner, INPUT, OUTPUT, more details, EXAMPLES, ...
(And: there are other places.)
And should for example docstring of
.cardinality()
really containOUTPUT
block saying that output type is sage'sInteger
?
What do you suggest?
comment:21 in reply to: ↑ 20 Changed 5 years ago by
Replying to dkrenn:
Replying to jmantysalo:
The developer guide says
An INPUT and an OUTPUT block describing the input/output of the function. This is not optional.
True. But I don't think if it has been thinked that "no input" must be documented. Is it in other places? Or should this part of developer guide be changed?
I would keep it. (At the moment) the developer guide says to include it and I find it very nice to have constistent docstrings starting with oneliner, INPUT, OUTPUT, more details, EXAMPLES, ...
This is discussed at #19041. But don't let this stop coding  Sage will propably never get finished so that questions like this would have The Final Answer.
And should for example docstring of
.cardinality()
really containOUTPUT
block saying that output type is sage'sInteger
?What do you suggest?
Every cardinality()
should return Integer
. For other integervalued functions there were discussion about int
vs. Integer
without consensus.
I don't know. For input it is explicitly said that the docstring can say "x in integer", not "x must be Integer
or int
". These are hard questions, as what is "clear" varies from one person to other.
comment:22 Changed 5 years ago by
 Commit changed from 19fd1556a56a6d250ca464c385e7960ac715b2ae to ceb0b37bc7640f4300962a89eabefe5abc7263d1
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2863321  allow merge to go over all elements

9391c78  derive MutablePoset from object (instead of SageObject)

70859d7  cleanup: delete toset since not yet implemented

d647d95  write map and mapped

e64cbd8  mapping argument for .copy()

c28749c  bring map and mapped back to work and use new copyconstruction

ceb0b37  fix bug in merge

comment:23 Changed 5 years ago by
Last 10 new commits:
8584f57  write __len__

a1678ed  remove TODOlist of methods (list is now in separat branch)

1c6b196  write methods for maximal/minimal elements

2863321  allow merge to go over all elements

9391c78  derive MutablePoset from object (instead of SageObject)

70859d7  cleanup: delete toset since not yet implemented

d647d95  write map and mapped

e64cbd8  mapping argument for .copy()

c28749c  bring map and mapped back to work and use new copyconstruction

ceb0b37  fix bug in merge

comment:24 Changed 5 years ago by
 Component changed from misc to asymptotic expansions
comment:25 followup: ↓ 29 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/mutableposet to u/behackl/asy/mutableposet
 Commit changed from ceb0b37bc7640f4300962a89eabefe5abc7263d1 to c1f8877b7dcea0e1c677d350d7f5d41be02169c8
 Status changed from needs_review to needs_work
Hello!
I reviewed this ticket, and here are my comments:
MutablePoset
,MutablePosetShell
: derived fromobject
vs.SageObject
?is_null
,is_oo
: is there some usecase for thereverse
keyword? Forpredecessor
andsuccessor
: this is clear, as it makes the code easier. However, I think that areverse
keyword foris_null
andis_oo
is rather irritating. doctests for
MutablePosetShell.le
: shouldn't doctests likeelem1 <= elem2
be marked as indirect? MutablePosetShell._copy_all_linked_
: 1st sentence should be a short description. Likewise forMutablePosetShell._iter_depth_first_visit_
andMutablePosetShell._iter_topological_visit_
. sorted_set_by_tuple, is_MutablePoset: are these functions really necessary? Both are only used once within the whole file. The occurrence of
sorted_set_by_tuple
can be easily replaced by[...].join(repr(e) for e in sortedshells if e in shell.successors(rev))
and the occurrence of is_MutablePoset
can be replaced by a simple isinstance
call.
MutablePoset.shells
: I do not understand the usecase of thereverse
keyword. Can it be removed?MutablePoset.add
: I think that a comment (in the code) that roughly explains what the passage beginning withfor reverse in (False, True):
does would be nice. It took me quite some time to understand and verify the functionality of this block.MutablePoset.discard
: why isn't this simply an alias ofMutablePoset.remove
? Asremove
has no return value,discard
cannot have one either, if that was the intention. Is there a particular reason for naming the parameters for all the set operations like
MutablePoset.union
,MutablePoset.difference
etc.left
andright
, instead ofself
andother
? IMHO, this disguises that the function can be called asP.union(Q)
.  Regarding all set operations: currently, it is not clear from the documentation that all set operations are performed on the set of keys. This causes something like
sage: PR.<x> = ZZ[] sage: P = MutablePoset(key=lambda k: len(k.list())) sage: P.add(42*x) sage: P.add(21*x^2) sage: Q = MutablePoset(key=lambda k: len(k.list())) sage: Q.add(1111*x) sage: P, Q (poset(42*x, 21*x^2), poset(1111*x)) sage: Q.is_subset(P) True sage: Q.union(P) poset(1111*x, 21*x^2)
and so on. In principle, I don't see this as a problemhowever, I'd state this explicitly in each of these set operation functions.
MutablePoset.mapped
: why is this function needed? Purely for semantical reasons? I'd move the doctests toMutablePoset.copy
.MutablePosetShell._copy_all_linked_
: is the memoization using theid
of the object a standard procedure? I thought about it, but I'm not entirely sure that this isn't a potential error source.
Side note: the MutablePoset
is the central data structure in our AsymptoticExpansions framework (cf. #17601). In this context, the functionality has been tested extensivelyand some peculiarities (like the map
function etc.) are motivated by this application.
Also, I've made a few reviewer commits concerning the documentation; the branch is attached.
As soon as the points I've raised in the comments above are discussed, this would be a positive_review
from my side.
Benjamin
Last 10 new commits:
e64cbd8  mapping argument for .copy()

c28749c  bring map and mapped back to work and use new copyconstruction

ceb0b37  fix bug in merge

525bf3c  Merge branch 'u/dkrenn/asy/mutableposet' of git://trac.sagemath.org/sage into 6.9.beta5

bf1928f  remove unused import

98a7939  print something > print(something)

2a7ab88  several improvements to documentation (language, structure)

a4c43b7  fixed two examplesblocks

a867d3a  indentation (PEP 8)

c1f8877  improved errors and added two doctests

comment:26 Changed 5 years ago by
Benjamin, please put your name to reviewersfield. Otherwise Volker will reject this.
comment:27 Changed 5 years ago by
 Reviewers set to Benjamin Hackl
Thanks for the reminder, Jori!
Benjamin
comment:28 Changed 5 years ago by
 Branch changed from u/behackl/asy/mutableposet to u/dkrenn/asy/mutableposet
comment:29 in reply to: ↑ 25 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/mutableposet to u/behackl/asy/mutableposet
Replying to behackl:
MutablePoset
,MutablePosetShell
: derived fromobject
vs.SageObject
?
object
.
is_null
,is_oo
: is there some usecase for thereverse
keyword? Forpredecessor
andsuccessor
: this is clear, as it makes the code easier. However, I think that areverse
keyword foris_null
andis_oo
is rather irritating.
Keyword deleted.
 doctests for
MutablePosetShell.le
: shouldn't doctests likeelem1 <= elem2
be marked as indirect?
Yes, I've marked them.
MutablePosetShell._copy_all_linked_
: 1st sentence should be a short description. Likewise forMutablePosetShell._iter_depth_first_visit_
andMutablePosetShell._iter_topological_visit_
.
Rewritten.
 sorted_set_by_tuple, is_MutablePoset: are these functions really necessary? Both are only used once within the whole file. The occurrence of
sorted_set_by_tuple
can be easily replaced by[...].join(repr(e) for e in sortedshells if e in shell.successors(rev))and the occurrence of
is_MutablePoset
can be replaced by a simpleisinstance
call.
sorted_set_by_tuple
: Deleted and replaced.
is_MutablePoset
: seems to be a standard convention to use it in Sage; see a lot of other modules.
MutablePoset.shells
: I do not understand the usecase of thereverse
keyword. Can it be removed?
I agree; deleted.
MutablePoset.add
: I think that a comment (in the code) that roughly explains what the passage beginning withfor reverse in (False, True):
does would be nice. It took me quite some time to understand and verify the functionality of this block.
I've added a comment.
MutablePoset.discard
: why isn't this simply an alias ofMutablePoset.remove
? Asremove
has no return value,discard
cannot have one either, if that was the intention.
See Python's set (the same behavior there).
 Is there a particular reason for naming the parameters for all the set operations like
MutablePoset.union
,MutablePoset.difference
etc.left
andright
, instead ofself
andother
? IMHO, this disguises that the function can be called asP.union(Q)
.
Changed all to self/other.
 Regarding all set operations: currently, it is not clear from the documentation that all set operations are performed on the set of keys. This causes something like
sage: PR.<x> = ZZ[] sage: P = MutablePoset(key=lambda k: len(k.list())) sage: P.add(42*x) sage: P.add(21*x^2) sage: Q = MutablePoset(key=lambda k: len(k.list())) sage: Q.add(1111*x) sage: P, Q (poset(42*x, 21*x^2), poset(1111*x)) sage: Q.is_subset(P) True sage: Q.union(P) poset(1111*x, 21*x^2)and so on. In principle, I don't see this as a problemhowever, I'd state this explicitly in each of these set operation functions.
I've added a note in all these functions.
MutablePoset.mapped
: why is this function needed? Purely for semantical reasons? I'd move the doctests toMutablePoset.copy
.
It is a shortcut for using copy with the mapping argument (since this is a nonstandard argument for a copy method, including a separate method with an approriate name seems to be a good choice)
MutablePosetShell._copy_all_linked_
: is the memoization using theid
of the object a standard procedure? I thought about it, but I'm not entirely sure that this isn't a potential error source.
Yes it is standard; see (all) deepcopy routines.
Also, I've made a few reviewer commits concerning the documentation; the branch is attached.
Crossreviewed. Thanks.
comment:30 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:31 Changed 5 years ago by
 Branch changed from u/behackl/asy/mutableposet to u/dkrenn/asy/mutableposet
 Commit changed from c1f8877b7dcea0e1c677d350d7f5d41be02169c8 to 1d52f6c6351e6eb9e92c6033b12e09c4754b8110
Last 10 new commits:
39ae466  correct oo, null

fd7c881  Applies > Apply in oneline of docstring

dabad1f  remove reverse in is_{nulloo} since not needed

33c4102  mark doctests in .le as indirect

b31fac8  rewrite a couple of oneline descriptions

17e921f  remove sorted_set_by_tuple

7af4b6b  remove reverse keyword from shells

a49a20d  add comment in code to make it clear what happens

89b8209  change left/right to self/other

1d52f6c  add a note to the set operations methods

comment:32 followup: ↓ 33 Changed 5 years ago by
Hello Daniel,
I crossreviewed your changes and have one last open question:
 Is there a particular reason for deriving this from
object
instead ofSageObject
? Because the documentation of SageObject states that "Every object that can end up being returned to the user should inherit from SageObject."
Other than that, this is positive_review
from my side; AFAIK cheuberg also wanted to crossreview this ticket, so I'll not set this to positive_review
yet.
Benjamin
comment:33 in reply to: ↑ 32 Changed 5 years ago by
Replying to behackl:
 Is there a particular reason for deriving this from
object
instead ofSageObject
? Because the documentation of SageObject states that "Every object that can end up being returned to the user should inherit from SageObject."
Ok, then SageObject
it is :)
comment:34 followup: ↓ 36 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/mutableposet to u/behackl/asy/mutableposet
 Commit changed from 1d52f6c6351e6eb9e92c6033b12e09c4754b8110 to 3b3b2fb607a6fe8b20419170bf935d494af1efca
A short remark on this change of mind:
When deriving these classes from SageObject
instead of object
, and merging this ticket into #19083 (the cleanupticket of our AsymptoticRing
), doctests were failing because we call A(poset)
with an AsymptoticRing
A
there, which causes some peculiarities in _coerce_map_from_
.
In any case, we fixed these problems there, so this can be properly derived from SageObject
.
This concludes my review; cheuberg is in the process of reading the code. I'll leave setting this to positive_review
to him.
Benjamin
Last 10 new commits:
fd7c881  Applies > Apply in oneline of docstring

dabad1f  remove reverse in is_{nulloo} since not needed

33c4102  mark doctests in .le as indirect

b31fac8  rewrite a couple of oneline descriptions

17e921f  remove sorted_set_by_tuple

7af4b6b  remove reverse keyword from shells

a49a20d  add comment in code to make it clear what happens

89b8209  change left/right to self/other

1d52f6c  add a note to the set operations methods

3b3b2fb  object > SageObject

comment:35 Changed 5 years ago by
 Branch changed from u/behackl/asy/mutableposet to u/cheuberg/asy/mutableposet
comment:36 in reply to: ↑ 34 ; followup: ↓ 39 Changed 5 years ago by
 Commit changed from 3b3b2fb607a6fe8b20419170bf935d494af1efca to f7bce7e8aff4e25a23b57d1052ff13df302120e5
 Milestone changed from sage6.5 to sage6.9
 Reviewers changed from Benjamin Hackl to Benjamin Hackl, Clemens Heuberger
 Status changed from needs_review to needs_work
Replying to behackl:
This concludes my review; cheuberg is in the process of reading the code. I'll leave setting this to
positive_review
to him.
I read the documentation and the code. I pushed a few reviewer commits. I have a number of rather minor issues with the documentation which I ask you to fix in order facilitate future maintainance of the code. In three instances, I propose alternative implementations, which might be more readable or slightly more efficient.
 Please add
.. seealso::
blocks between corresponding methods of shell and poset as well as between the accessor methods (keys, elements, shells)  there is an empty "Introduction" section at the beginning of the module documentation, the next heading "Example" is on the same level.
 this module was written as part of the asymptotic expansion effort. In contrast to the asymptotic expansion, it does not have the "experimental" decorator. I'd feel more comfortable having it, at least until a larger portion of the asymptotic expansions have been merged.
MutablePoset.__init__
accepts a list of elements. This could be used in several doctests (in particular, in the set operations) as an abbreviation.MutablePosetShell.__init__
: shall we check thatelement is not None
? Otherwise, handling of special elements would probably be affected.MutablePosetShell.key
: I do not understand the sentence "The element is converted by the poset to the key".MutablePosetShell.key
: I am surprised that the key is not cached. I imagine that many comparisons will be needed in the lifetime of aMutablePoset
, and in every case, the property key has to be resolved, which calls the property poset, which callsget_key
of the poset.MutablePosetShell.__repr__
: The note box in the docstring is surprising at this point: reading the source file from the top, this is the first point where the representation of the data is explained, after guessing it fromis_special
,is_oo
,is_null
above. I think that it would be better to document these conventions closer to the top, perhaps in the__init__
method or perhaps only as a comment in the source code.MutablePosetShell.__repr__
: The code replicates the behaviour ofis_null
andis_oo
. As the__repr__
method is hardly time critical, I'd prefer usingis_null
andis_oo
, here and thus hiding the internal convention.MutablePosetShell.le
: the note box could be simplified by suppressing implementation details and speaking about the special elements.MutablePosetShell.le
:right <= left
: neitherright
norleft
are defined here.MutablePosetShell.le
: the partif other.element is None
could be simplified toreturn not other.successors()
asself
is already known not to be special here.MutablePosetShell.le
: If this is time critical,self._predecessors_
could be used instead ofself.predecessors()
.MutablePosetShell.eq
: note box, see above.MutablePosetShell.eq
: emphasize that elements with equal keys are considered equal? Currently, this information is somewhat hidden in the note box which at first glance only seems to explain handling of special elements.MutablePosetShell._copy_all_linked_
: Short description: "Return a copy of all shells" does not correspond to the actual return value, which is only the copy of this shell.MutablePosetShell._copy_all_linked_
: the interplay between this method andMutablePoset._copy_shells_
is not well documented: in particular,poset
in_copy_all_linked_
is only used for setting the containing poset, but not for actual inserting into this poset.MutablePosetShell._copy_all_linked_
: I do not understand why you testoo == P.oo
: I think thatoo
is an element of the new posetQ
. Sooo is Q.oo
would be more interesting? The current test demonstrates that the poset is not used in comparison, so that would rather belong to.eq
?MutablePosetShell._search_covers_
: what is the role ofself
in this method? It trivially influences the return value, but what else?MutablePosetShell._search_covers_
: The explanation of the return value is unclear to me. Is the sentence "Note that..." meant to be a complete description? Does it change ifreverse
is set?MutablePosetShell._search_covers_
: I think that the notions of "upper cover" and "lower cover" need a brief definition; I did not find them in Wikipedia andsage.combinat.posets.posets.FinitePoset.upper_covers
defines the notion.MutablePosetShell._search_covers_
: According to Wikipedia, a cover is what is called an upper cover here. This is in contrast to the default behaviour here.MutablePosetShell._search_covers_
: what is the difference between this method and.predecessors
? Is the shell necessarily an element of the poset? If not, then there should be a doctest covering this case.MutablePosetShell.covers
: "originate" is somewhat foreign to the description of the poset.MutablePosetShell.covers
: "which are at most the given shell": should that be "which are less than the given shell"?MutablePosetShell.covers
see comments onMutablePosetShell._search_covers_
.MutablePosetShell.covers
: I think that the following would be an equivalent implementation of this method, which does not need a helper function with side effects.if self == shell: return set() covers = set().union(*(e.covers(shell, reverse) for e in self.successors(reverse) if e.le(shell, reverse))) if covers: return covers else: return set([self])
(pushed as branchu/cheuberg/asy/mutableposetcover
)MutablePosetShell._iter_depth_first_visit_
: document the role of self in this method (only shells>=
this shell are visited).MutablePosetShell.iter_depth_first
: document the role of self in this method (only shells>=
this shell are visited).MutablePosetShell._iter_topological_visit_
: document the role of self in this method (only shells<=
this shell are visited, emphasize the contrast to depth first.).MutablePosetShell.iter_topological_first
: document the role of self in this method (only shells<=
this shell are visited, emphasize the contrast to depth first.).MutablePosetShell.iter_topological_sort
, last example: functionC
is defined, but not used.MutablePosetShell.merge
: explain what merge is, in particular, that this is defined when constructing the poset.MutablePosetShell.merge
: I am surprised thatcheck=True
leads to a silent failure instead of an exception and thatposet._merge_ is None
does not raise an exception. Document and test this behaviour?MutablePosetShell.merge
: what is the difference betweenposet.remove
andposet.discard
?MutablePosetShell.merge
: document that the merge function resulting inNone
leads to deletion of the element.MutablePosetShell.merge
: document that the merge function must not change the position of the element in the poset.MutablePoset.__init__
: Clarify the role ofkey
: in particular,key
does not only influence sorting, but that no two elements are allowed to have the same key.MutablePoset.__len__
: Clarify thatnull
andoo
are not counted.MutablePoset.shells_topological
: The sentence "If this is None, no sorting according to the representation string occurs." is unclear to me, in particular the role of the representation string.MutablePoset.keys_topological
: Due to the chosen key, some of the elements added to the poset are ignored. I do not know why this is demonstrated here.MutablePoset.repr
: INPUT section is incomplete.MutablePoset.repr_full
: INPUT section is incomplete.MutablePoset.add
: the loopfor reverse in (False, True)
simplifies in the second iteration: as all pairs of elements(s, l)
withnew
coverings
andl
coveringnew
have already been broken up whilereverse=False
. Thus it might be more straightforward to do it only once, not usingreverse
at all and saving a few intersections:new._predecessors_ = self.null.covers(new, reverse=False) new._successors_ = self.oo.covers(new, reverse=True) for s in new.predecessors(): for l in s.successors().intersection(new.successors()): l.predecessors().remove(s) s.successors().remove(l) s.successors().add(new) for l in new.successors(): l.predecessors().add(new)
(pushed as branchu/cheuberg/asy/mutableposetadd
)MutablePoset.remove
: the loop over all (not necessarily direct) successors via the depth first search iterator seems to be rather inefficient, especially if the poset is large. I propose an alternative based on the order relation and not based on the data structure:for upper in shell.successors(): upper.predecessors().remove(shell) for lower in shell.predecessors(): lower.successors().remove(shell) for upper in shell.successors(): if not any(s <= upper for s in lower.successors()): lower.successors().add(upper) upper.predecessors().add(lower)
(pushed as branchu/cheuberg/asy/mutableposetremove
)MutablePoset.remove
,MutablePoset.discard
: add "see also blocks", but also an explanation of the difference betweendiscard
andremove
. I guess that both methods are available due to some compatibility concern (in that case, please add a remark in the code or the docstring). Otherwise, I'd suggest removingdiscard
, removing the parameterraise_key_error
and let the user catch the exception.MutablePoset.pop
: removekey=lambda c: c
from this example as it is not pertinent topop
.MutablePoset.pop
: mention that special elements cannot be popped.MutablePoset.pop
: IMHO you can remove the first four line (thetry:
block deletingkwargs['include_special']
) because settingkwargs['include_special'] = False
should result in the same result.MutablePoset.union
: The doctestP.union(P, Q, Q, P)
neither fits the description "a poset" or "an iterable of future elements".MutablePoset.union
: the word "union" sounds symmetric, however, due to keys and merge functions, it might not be commutative. The note box is not helpful for me.MutablePoset.union
: the TODO box fromunion_update
also applies here.MutablePoset.union_update
: why is the semantics ofother
different w.r.tunion
, but has the same description? It would seem more logical to me ifunion
would simply call copy and then pass its argument toupdate_union
and let the latter function sort out the iterators?MutablePoset.difference
andMutablePoset.difference_update
: see comments onunion
andunion_update
MutablePoset.intersection
andMutablePoset.intersection_update
: see comments onunion
andunion_update
MutablePoset.intersection_update
: how can theAttributeError
occur? After all,self
is aMutablePoset
, so the methodkeys
will be available unless something very strange happens ...MutablePoset.merge
: documentation ofreverse
: what is the default direction?MutablePoset.merge
: add doctest forRuntimeError
.MutablePoset.merge
: document thatcan_merge
is applied in the sense of the condition of depth first iteration, i.e., oncecan_merge
fails, the successors are no longer tested. This is some kind of monotonicity condition oncan_merge
.MutablePoset.merge
: it should be mentioned somewhere that this (at first sight strange) merge magic is motivated by asymptotic expansions.MutablePoset.map
: IMHO the example does alter the keys, because the key was the identity map here.MutablePoset.mapping
: does the map have to be key preserving as in the methodmap
? Is this method actually needed, see also the recent discussion on inplace vs. noninplace operations on sagedevel?
New commits:
8de4188  Trac #17693: minor language adjustments

740852e  Trac #17693: command instead of description for short descriptions

347656c  Trac #17693: language adjustment: whether instead of if

4774baa  Trac #17693: corrections in documentation

fe5d2f1  Trac #17693: additional doctest

e4f1fea  Trac #17693: fix indentations and whitespace

254951d  Trac #17693: add keyword in doctest for clarity

f7bce7e  Trac #17693: remove superfluous doctest

comment:37 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/mutableposet to u/dkrenn/asy/mutableposet
comment:38 Changed 5 years ago by
 Commit changed from f7bce7e8aff4e25a23b57d1052ff13df302120e5 to 3c69f6be24c5776593d3e067d8c723cd5c192e8e
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
34e34dc  Trac #17693, comment 36, 1923: improve docstring of covers (former _search_covers_)

490c223  Trac #17693, comment 36, 2831: document role of self

3de0a1d  Trac #17693, comment 36, 33: explicitly mention merge and can_merge at top of docstring

485b46f  Trac #17693, comment 36, 34: raise exceptions when merge is not possible

d5d6bec  check=False in MutablePoset.merge since checked already before

6da3db1  Trac #17693, comment 36, 37: extend doc to mention more explicitly that merge is not allowed to change keys

f1e9f9e  Trac #17693, comment 36, 38: clarify parameter key

ae0cad9  Trac #17693, comment 36, 60: mention motivation asymptoic expansions in merge method

ec15597  Trac #17693: alternative implementation add

3c69f6b  Merge remotetracking branch 'origin/u/cheuberg/asy/mutableposetadd' into t/17693/asy/mutableposet

comment:39 in reply to: ↑ 36 ; followup: ↓ 43 Changed 5 years ago by
Replying to cheuberg:
I read the documentation and the code. I pushed a few reviewer commits.
Crossreviewed. One commit added.
I have a number of rather minor issues with the documentation which I ask you to fix in order facilitate future maintainance of the code. In three instances, I propose alternative implementations, which might be more readable or slightly more efficient.
Thanks; see my comments below.
 Please add
.. seealso::
blocks between corresponding methods of shell and poset as well as between the accessor methods (keys, elements, shells)
Done.
 there is an empty "Introduction" section at the beginning of the module documentation, the next heading "Example" is on the same level.
Deleted.
 this module was written as part of the asymptotic expansion effort. In contrast to the asymptotic expansion, it does not have the "experimental" decorator. I'd feel more comfortable having it, at least until a larger portion of the asymptotic expansions have been merged.
Activated it; it seems (for some (to me) unknown reason) the warning appears now in every doctest and not only once in the file. Thus, deactivated it again; and I am for keeping it this way.
MutablePoset.__init__
accepts a list of elements. This could be used in several doctests (in particular, in the set operations) as an abbreviation.
Good idea. Done.
MutablePosetShell.__init__
: shall we check thatelement is not None
? Otherwise, handling of special elements would probably be affected.
MutablePosetShell? is typically used by the MutablePoset?; and there, adding a None
element is forbidden (see :meth:add
).
MutablePosetShell.key
: I do not understand the sentence "The element is converted by the poset to the key".
Rewritten.
MutablePosetShell.key
: I am surprised that the key is not cached. I imagine that many comparisons will be needed in the lifetime of aMutablePoset
, and in every case, the property key has to be resolved, which calls the property poset, which callsget_key
of the poset.
Now it is cached (see also follow up ticket #19281).
MutablePosetShell.__repr__
: The note box in the docstring is surprising at this point: reading the source file from the top, this is the first point where the representation of the data is explained, after guessing it fromis_special
,is_oo
,is_null
above. I think that it would be better to document these conventions closer to the top, perhaps in the__init__
method or perhaps only as a comment in the source code.
Added a note in the class description.
MutablePosetShell.__repr__
: The code replicates the behaviour ofis_null
andis_oo
. As the__repr__
method is hardly time critical, I'd prefer usingis_null
andis_oo
, here and thus hiding the internal convention.
Rewritten.
MutablePosetShell.le
: the note box could be simplified by suppressing implementation details and speaking about the special elements.
Done.
MutablePosetShell.le
:right <= left
: neitherright
norleft
are defined here.
Rewritten.
MutablePosetShell.le
: the partif other.element is None
could be simplified toreturn not other.successors()
asself
is already known not to be special here.
True; rewritten.
MutablePosetShell.le
: If this is time critical,self._predecessors_
could be used instead ofself.predecessors()
.
Changed.
MutablePosetShell.eq
: note box, see above.
Simplified.
MutablePosetShell.eq
: emphasize that elements with equal keys are considered equal? Currently, this information is somewhat hidden in the note box which at first glance only seems to explain handling of special elements.
Rewritten note box.
MutablePosetShell._copy_all_linked_
: Short description: "Return a copy of all shells" does not correspond to the actual return value, which is only the copy of this shell.
Rewritten.
MutablePosetShell._copy_all_linked_
: the interplay between this method andMutablePoset._copy_shells_
is not well documented: in particular,poset
in_copy_all_linked_
is only used for setting the containing poset, but not for actual inserting into this poset.
Extended description of parameter poset
.
MutablePosetShell._copy_all_linked_
: I do not understand why you testoo == P.oo
: I think thatoo
is an element of the new posetQ
.
oo == P.oo
tests that Q.oo
is mapped to P.oo
.
So
oo is Q.oo
would be more interesting?
oo is Q.oo
is False
since oo
is not in Q
, but just a copy of the oo
in P
with parentposet Q
. Inserting this into Q
is done in _copy_shells_
.
The current test demonstrates that the poset is not used in comparison, so that would rather belong to
.eq
?
I do not understand what you mean (but it is already late...).
MutablePosetShell._search_covers_
: what is the role ofself
in this method? It trivially influences the return value, but what else?
_search_covers_
does not exist anymore (see 27).
MutablePosetShell._search_covers_
: The explanation of the return value is unclear to me. Is the sentence "Note that..." meant to be a complete description? Does it change ifreverse
is set?
_search_covers_
does not exist anymore (see 27).
MutablePosetShell._search_covers_
: I think that the notions of "upper cover" and "lower cover" need a brief definition; I did not find them in Wikipedia andsage.combinat.posets.posets.FinitePoset.upper_covers
defines the notion.
_search_covers_
does not exist anymore (see 27). Incooperated in covers
.
MutablePosetShell._search_covers_
: According to Wikipedia, a cover is what is called an upper cover here. This is in contrast to the default behaviour here.
_search_covers_
does not exist anymore (see 27).
MutablePosetShell._search_covers_
: what is the difference between this method and.predecessors
? Is the shell necessarily an element of the poset? If not, then there should be a doctest covering this case.
_search_covers_
does not exist anymore (see 27). Incooperated in covers
.
MutablePosetShell.covers
: "originate" is somewhat foreign to the description of the poset.
Rewritten.
MutablePosetShell.covers
: "which are at most the given shell": should that be "which are less than the given shell"?
Rewritten.
MutablePosetShell.covers
see comments onMutablePosetShell._search_covers_
.
Rewritten.
MutablePosetShell.covers
: I think that the following would be an equivalent implementation of this method, which does not need a helper function with side effects.if self == shell: return set() covers = set().union(*(e.covers(shell, reverse) for e in self.successors(reverse) if e.le(shell, reverse))) if covers: return covers else: return set([self])(pushed as branchu/cheuberg/asy/mutableposetcover
)
Merged and minor simplification.
MutablePosetShell._iter_depth_first_visit_
: document the role of self in this method (only shells>=
this shell are visited).
Documented.
MutablePosetShell.iter_depth_first
: document the role of self in this method (only shells>=
this shell are visited).
Documented.
MutablePosetShell._iter_topological_visit_
: document the role of self in this method (only shells<=
this shell are visited, emphasize the contrast to depth first.).
Documented.
MutablePosetShell.iter_topological_first
: document the role of self in this method (only shells<=
this shell are visited, emphasize the contrast to depth first.).
Documented.
MutablePosetShell.iter_topological_sort
, last example: functionC
is defined, but not used.
Deleted.
MutablePosetShell.merge
: explain what merge is, in particular, that this is defined when constructing the poset.
Documented.
MutablePosetShell.merge
: I am surprised thatcheck=True
leads to a silent failure instead of an exception and thatposet._merge_ is None
does not raise an exception. Document and test this behaviour?
Behavior changed.
MutablePosetShell.merge
: what is the difference betweenposet.remove
andposet.discard
?
See Python's set.
MutablePosetShell.merge
: document that the merge function resulting inNone
leads to deletion of the element.
Done.
MutablePosetShell.merge
: document that the merge function must not change the position of the element in the poset.
Mentioned this more explicitly in docs
MutablePoset.__init__
: Clarify the role ofkey
: in particular,key
does not only influence sorting, but that no two elements are allowed to have the same key.
Done.
MutablePoset.__len__
: Clarify thatnull
andoo
are not counted.
Done.
MutablePoset.shells_topological
: The sentence "If this is None, no sorting according to the representation string occurs." is unclear to me, in particular the role of the representation string.
Rewritten.
MutablePoset.keys_topological
: Due to the chosen key, some of the elements added to the poset are ignored. I do not know why this is demonstrated here.
Removed.
MutablePoset.repr
: INPUT section is incomplete.
Completed.
MutablePoset.repr_full
: INPUT section is incomplete.
Completed.
MutablePoset.add
: the loopfor reverse in (False, True)
simplifies in the second iteration: as all pairs of elements(s, l)
withnew
coverings
andl
coveringnew
have already been broken up whilereverse=False
. Thus it might be more straightforward to do it only once, not usingreverse
at all and saving a few intersections:new._predecessors_ = self.null.covers(new, reverse=False) new._successors_ = self.oo.covers(new, reverse=True) for s in new.predecessors(): for l in s.successors().intersection(new.successors()): l.predecessors().remove(s) s.successors().remove(l) s.successors().add(new) for l in new.successors(): l.predecessors().add(new)(pushed as branchu/cheuberg/asy/mutableposetadd
)
Merged and crossreviewed....ok.
MutablePoset.remove
: the loop over all (not necessarily direct) successors via the depth first search iterator seems to be rather inefficient, especially if the poset is large. I propose an alternative based on the order relation and not based on the data structure:for upper in shell.successors(): upper.predecessors().remove(shell) for lower in shell.predecessors(): lower.successors().remove(shell) for upper in shell.successors(): if not any(s <= upper for s in lower.successors()): lower.successors().add(upper) upper.predecessors().add(lower)(pushed as branchu/cheuberg/asy/mutableposetremove
)
This needs comparisons of the elements, but one of the main ideas of this data structure is that comparisions are only needed for inserting an element into the poset and none needed once it is inside. Thus I am for keeping the current solution. However, I am fine with introducing (now or at any point later) an algorithm option which makes it possible to select different removing algorithms depending on the situation.
MutablePoset.remove
,MutablePoset.discard
: add "see also blocks", but also an explanation of the difference betweendiscard
andremove
. I guess that both methods are available due to some compatibility concern (in that case, please add a remark in the code or the docstring). Otherwise, I'd suggest removingdiscard
, removing the parameterraise_key_error
and let the user catch the exception.
Python's set has both, remove
and discard
. Thus this mutable poset should have it as well.
Noteblock added. Seealso added.
MutablePoset.pop
: removekey=lambda c: c
from this example as it is not pertinent topop
.
Done.
MutablePoset.pop
: mention that special elements cannot be popped.
Done.
MutablePoset.pop
: IMHO you can remove the first four line (thetry:
block deletingkwargs['include_special']
) because settingkwargs['include_special'] = False
should result in the same result.
Deleted.
MutablePoset.union
: The doctestP.union(P, Q, Q, P)
neither fits the description "a poset" or "an iterable of future elements".
Rewritten INPUTblock
MutablePoset.union
: the word "union" sounds symmetric, however, due to keys and merge functions, it might not be commutative. The note box is not helpful for me.
Note added/changed.
MutablePoset.union
: the TODO box fromunion_update
also applies here.
Copied.
MutablePoset.union_update
: why is the semantics ofother
different w.r.tunion
, but has the same description? It would seem more logical to me ifunion
would simply call copy and then pass its argument toupdate_union
and let the latter function sort out the iterators?
Indeed. Code rewritten.
MutablePoset.difference
andMutablePoset.difference_update
: see comments onunion
andunion_update
Done.
MutablePoset.intersection
andMutablePoset.intersection_update
: see comments onunion
andunion_update
Done.
MutablePoset.intersection_update
: how can theAttributeError
occur? After all,self
is aMutablePoset
, so the methodkeys
will be available unless something very strange happens ...
True. Code simplified.
MutablePoset.merge
: documentation ofreverse
: what is the default direction?
Documented.
MutablePoset.merge
: add doctest forRuntimeError
.
Added.
MutablePoset.merge
: document thatcan_merge
is applied in the sense of the condition of depth first iteration, i.e., oncecan_merge
fails, the successors are no longer tested. This is some kind of monotonicity condition oncan_merge
.
Added note.
MutablePoset.merge
: it should be mentioned somewhere that this (at first sight strange) merge magic is motivated by asymptotic expansions.
Mentioned.
MutablePoset.map
: IMHO the example does alter the keys, because the key was the identity map here.
Example changed.
MutablePoset.mapping
: does the map have to be key preserving as in the methodmap
? Is this method actually needed, see also the recent discussion on inplace vs. noninplace operations on sagedevel?
Added a note on keyorder preservation.
I think having MutablePoset.mapping
is useful (from a ui point of view) since one would not naturally thinks that the copy
method has a parameter for applying a mapping function.
comment:40 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:41 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/mutableposet to u/cheuberg/asy/mutableposet
comment:42 Changed 5 years ago by
 Commit changed from 3c69f6be24c5776593d3e067d8c723cd5c192e8e to 4deddbd1a09e0e60273797cb89becdc651325b9c
comment:43 in reply to: ↑ 39 ; followup: ↓ 45 Changed 5 years ago by
 Status changed from needs_review to needs_work
Thank you for your changes. I added three commits. See my remaining comments below.
Replying to dkrenn:
Replying to cheuberg:
 this module was written as part of the asymptotic expansion effort. In contrast to the asymptotic expansion, it does not have the "experimental" decorator. I'd feel more comfortable having it, at least until a larger portion of the asymptotic expansions have been merged.
Activated it; it seems (for some (to me) unknown reason) the warning appears now in every doctest and not only once in the file. Thus, deactivated it again; and I am for keeping it this way.
ok.
MutablePosetShell.key
: I am surprised that the key is not cached. I imagine that many comparisons will be needed in the lifetime of aMutablePoset
, and in every case, the property key has to be resolved, which calls the property poset, which callsget_key
of the poset.Now it is cached (see also follow up ticket #19281).
I rather thought about calling key
in __init__
as I guess that the key will be needed at least once in the lifetime of every MutablePosetShell
.
MutablePosetShell._copy_all_linked_
: I do not understand why you testoo == P.oo
: I think thatoo
is an element of the new posetQ
.
oo == P.oo
tests thatQ.oo
is mapped toP.oo
.
wouldn't oo.is_oo
do it without comparing shells of different posets, which might be confusing?
So
oo is Q.oo
would be more interesting?
oo is Q.oo
isFalse
sinceoo
is not inQ
, but just a copy of theoo
inP
with parentposetQ
.
that would be good to test (and comment on).
Inserting this into
Q
is done in_copy_shells_
.The current test demonstrates that the poset is not used in comparison, so that would rather belong to
.eq
?I do not understand what you mean (but it is already late...).
I mean that shells e
and f
might be equal even if they do belong to different posets; this might be an interesting doctest or example for equality.
MutablePosetShell._search_covers_
: According to Wikipedia, a cover is what is called an upper cover here. This is in contrast to the default behaviour here.
_search_covers_
does not exist anymore (see 27).
This does not solve the problem.
What about renaming the method covers
to lower_covers
(and adapting the docstring slightly, removing "upper " from the onesentencedescription as well as from the definition?) For symmetry, a method upper_covers
would be nice.
MutablePoset.remove
: the loop over all (not necessarily direct) successors via the depth first search iterator seems to be rather inefficient, especially if the poset is large. I propose an alternative based on the order relation and not based on the data structure:for upper in shell.successors(): upper.predecessors().remove(shell) for lower in shell.predecessors(): lower.successors().remove(shell) for upper in shell.successors(): if not any(s <= upper for s in lower.successors()): lower.successors().add(upper) upper.predecessors().add(lower)(pushed as branchu/cheuberg/asy/mutableposetremove
)This needs comparisons of the elements, but one of the main ideas of this data structure is that comparisions are only needed for inserting an element into the poset and none needed once it is inside. Thus I am for keeping the current solution. However, I am fine with introducing (now or at any point later) an algorithm option which makes it possible to select different removing algorithms depending on the situation.
This should be discussed when more benchmarking results are available. I opened #19300 for that.
MutablePoset.difference
andMutablePoset.difference_update
: see comments onunion
andunion_update
Done.
removed comment on noncommutativity because difference
is noncommutative by definition.
MutablePoset.intersection
andMutablePoset.intersection_update
: see comments onunion
andunion_update
Done.
Remove comment on noncommutativity? merge does not play a role here, and keys might be covered in the previous sentence?
MutablePoset.update_union
: "Due to keys and a merge function... this operation might not be commutative": This method is noncommutative by definition, asself
is changed andother
is not. So perhaps: "left.update_union(right)
" and "right.update_union(left)
might result in different posets"? The same for otherupdate_...
methods where noncommutativity might be surprising.
comment:44 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/mutableposet to u/dkrenn/asy/mutableposet
comment:45 in reply to: ↑ 43 Changed 5 years ago by
 Commit changed from 4deddbd1a09e0e60273797cb89becdc651325b9c to 4e73b4576e1e949b7257d858fbeb958152df9f66
Replying to cheuberg:
Thank you for your changes. I added three commits. See my remaining comments below.
Crossreview...ok.
MutablePosetShell.key
: I am surprised that the key is not cached. I imagine that many comparisons will be needed in the lifetime of aMutablePoset
, and in every case, the property key has to be resolved, which calls the property poset, which callsget_key
of the poset.Now it is cached (see also follow up ticket #19281).
I rather thought about calling
key
in__init__
as I guess that the key will be needed at least once in the lifetime of everyMutablePosetShell
.
Oh...yes, I agree; changed.
MutablePosetShell._copy_all_linked_
: I do not understand why you testoo == P.oo
: I think thatoo
is an element of the new posetQ
.
oo == P.oo
tests thatQ.oo
is mapped toP.oo
.
wouldn't
oo.is_oo
do it without comparing shells of different posets, which might be confusing?
True. Changed.
So
oo is Q.oo
would be more interesting?
oo is Q.oo
isFalse
sinceoo
is not inQ
, but just a copy of theoo
inP
with parentposetQ
.that would be good to test (and comment on).
Inserted.
Inserting this into
Q
is done in_copy_shells_
.The current test demonstrates that the poset is not used in comparison, so that would rather belong to
.eq
?I do not understand what you mean (but it is already late...).
I mean that shells
e
andf
might be equal even if they do belong to different posets; this might be an interesting doctest or example for equality.
Now I understand what you mean. Inserted a doctest there.
MutablePosetShell._search_covers_
: According to Wikipedia, a cover is what is called an upper cover here. This is in contrast to the default behaviour here.
_search_covers_
does not exist anymore (see 27).This does not solve the problem.
What about renaming the method
covers
tolower_covers
(and adapting the docstring slightly, removing "upper " from the onesentencedescription as well as from the definition?) For symmetry, a methodupper_covers
would be nice.
Good idea; changed and inserted upper_covers
.
MutablePoset.intersection
andMutablePoset.intersection_update
: see comments onunion
andunion_update
Done.
Remove comment on noncommutativity? merge does not play a role here, and keys might be covered in the previous sentence?
Removed.
MutablePoset.update_union
: "Due to keys and a merge function... this operation might not be commutative": This method is noncommutative by definition, asself
is changed andother
is not. So perhaps: "left.update_union(right)
" and "right.update_union(left)
might result in different posets"? The same for otherupdate_...
methods where noncommutativity might be surprising.
Changed.
New commits:
f7bd83a  Trac #17693, comment 43, 7: do caching of key in __init__

a554d69  rac #17693, comment 43, 18: use .is_oo to test for oo in doctest

3ac7ed1  rac #17693, comment 43, 18: add a doctest "oo is Q.oo"

2f675b3  Trac #17693, comment 43, 18: add a doctest in eq (comparing elements in different posets)

f064a3b  Trac #17693, comment 43, 22: covers > lower_covers, upper_covers

bea925c  Trac #17693, comment 43, 55: remove comment on noncommutativity

4e73b45  Trac #17693, comment 43, 63: extend/rewrite noncommutativity note

comment:46 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:47 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/mutableposet to u/cheuberg/asy/mutableposet
comment:48 Changed 5 years ago by
 Commit changed from 4e73b4576e1e949b7257d858fbeb958152df9f66 to a0b3d7bce3325e271e53b0a83047a6f80ac28a22
comment:49 followup: ↓ 50 Changed 5 years ago by
 Status changed from needs_review to positive_review
Added three final reviewer commits.
Doctests pass, documentation builds, documentation seems to be fine, code seems to be fine.
comment:50 in reply to: ↑ 49 Changed 5 years ago by
Replying to cheuberg:
Added three final reviewer commits.
Thanks; checked.
Doctests pass, documentation builds, documentation seems to be fine, code seems to be fine.
:)
comment:51 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/mutableposet to a0b3d7bce3325e271e53b0a83047a6f80ac28a22
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
addmethod: allow cancellation of elements
moved hook from add to __init__
rename: value > element > shell
write method element
improve/extend docstrings
conditional iterations for shells
rename element_exists_hook to merge_hook
introduce can_merge and rename merge_hook to merge
a couple of minor rewritings to make the code and doctests nicer
write mergemethods