Opened 4 years ago
Closed 4 years ago
#27033 closed enhancement (fixed)
Make relabel() of DynkinDiagram more compatible with GenericGraph
Reported by: | jdemeyer | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.7 |
Component: | combinatorics | Keywords: | |
Cc: | tscrim, nthiery | Merged in: | |
Authors: | Jeroen Demeyer | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | f360ac0 (Commits, GitHub, GitLab) | Commit: | f360ac0a9d46afafd6c76cd3625bac0ba19633e9 |
Dependencies: | Stopgaps: |
Description (last modified by )
DynkinDiagram_class
is a derived class of GenericGraph
. It specializes the relabel()
method of GenericGraph
, but it changes the interface. Generally, it is expected that a method in a derived class keeps (possibly extends) the API of the base class.
Concretely, we fix the following issues:
- A permutation is required to be given. This is in contrast to
GenericGraph.relabel()
which allows no permutation (in that case, vertices will be relabelled torange(G.order())
)
return_map
is not supported.
Change History (22)
comment:1 Changed 4 years ago by
Branch: | → u/jdemeyer/ticket/27033 |
---|
comment:2 Changed 4 years ago by
Commit: | → a88dc2c9cbd2b2754d7b49629e4eb2facd2f93ab |
---|---|
Description: | modified (diff) |
Status: | new → needs_review |
comment:4 follow-ups: 5 18 Changed 4 years ago by
Cc: | nthiery added |
---|
I believe Nicolas has a better sense of what we want from DynkinDiagram
, but here is my understanding. The reason it is a subclass, as opposed to a wrapper, is many of the methods would be simple punts to the corresponding DiGraph
object, and it is a digraph, albeit with special properties. I do agree with trying to keep the API as much as possible. Yet, we want it to behave more like a immutable object, so I think we should keep the default for inplace=False
. So 1 and 2 are good with me, but I think 3 needs to be reconsidered.
comment:5 Changed 4 years ago by
Regardless of the reason of DynkinDiagram_class
being a subclass of GenericGraph
, the effect is that generic code relies on the behaviour of relabel()
. For example, the reason for breakage in #27029 is that the generic isomorphism check for graphs at some point calls G.relabel()
. The code expects this to be an in-place relabeling.
So if you don't like my solution to make inplace=True
the default, I still feel that the problem needs to be solved. One alternative is to have no default and always require inplace
to be given.
comment:6 Changed 4 years ago by
I see your point. I definitely do not want to always specify an inplace
. What about always specifying inplace
when the relabel
is called in functions indicated by doctests that fail otherwise? As I write that, I don't feel like it is a good solution.
I'm not quite sure what the path forward is. Nicolas, do you have any thoughts on this?
comment:7 follow-up: 9 Changed 4 years ago by
Hmm, that's indeed a bit delicate.
One thing that sounds clear to me is that DynkinDiagrams? should be immutable objects (once constructed). Which means that inplace relabeling should be invalid. Then it feels silly to be forced to pass an "inplace=False".
How does relabel and isomorphism tests handle immutable graphs?
Maybe the root of the evil is that DynkinDiagrams? are not really graphs, and should instead contain a graph in the data structure. That would be a big change though, and also not super convenient to run graph questions on a Dynkin Diagram. Another root of the evil might be that for our various Cartan datum (DynkinDiagrams? & the like) which are immutable, we should have used ct.relabeled()
(noun) rather than
ct.relabel()
(verb). Again a non trivial thing to change.
comment:8 Changed 4 years ago by
There is some precedence for
DynkinDiagram
acting like a mutable object, e.g., with itsadd_edge
method.
Indeed; but as far as I remember this is always at "construction time" when the to be constructed diagram can be built from an existing one by doing some small edits: make a copy, do a couple edits, and then freeze the result forever. We could revisit our Dynkin diagrams to always set them as immutable once constructed.
comment:9 follow-ups: 10 11 Changed 4 years ago by
Replying to nthiery:
Hmm, that's indeed a bit delicate.
One thing that sounds clear to me is that DynkinDiagrams? should be immutable objects (once constructed).
Just curious: why it is clear that dynkin diagrams should be immutable but graphs not? Because that's really what this ticket is about: that graphs and dynkin diagrams behave differently even though the first is a superclass of the second.
How does relabel and isomorphism tests handle immutable graphs?
It makes a copy and then relabels that copy in-place.
comment:10 Changed 4 years ago by
Just curious: why it is clear that dynkin diagrams should be immutable but graphs not? Because that's really what this ticket is about: that graphs and dynkin diagrams behave differently even though the first is a superclass of the second.
My answer is going to be more art than science :-)
In most use cases, Dynkin diagram are used to model mathematical objects from which computations will be done. On the other hand, graphs are often used more as a data structure on which algorithm will be run. Also, Dynkin diagrams tend to be small, and the overhead of having to create copies is not an issue. Whereas graphs can be big and you would not want to be forced to do such copies at every step of the execution of an algorithm.
That's roughly the same situation as for our polynomials which are always immutable, whereas our matrices can be mutable or not depending on the use case.
comment:11 follow-up: 13 Changed 4 years ago by
How does relabel and isomorphism tests handle immutable graphs?
It makes a copy and then relabels that copy in-place.
Ok. If our Dynkin diagrams would be flagged as immutable, would this resolve the original issue? (up to maybe having to reset the immutable flag)?
comment:12 follow-up: 14 Changed 4 years ago by
For the record: the main reason that I am reluctant to change the interface for "relabel" is that Dynkin diagrams are special case of cartan types: they are in the CartanType_abstract
class where relabel is defined to not take argument and return a new object. So that change would break that compatibility, and presumably this would break generic code about cartan types.
comment:13 Changed 4 years ago by
Replying to nthiery:
Ok. If our Dynkin diagrams would be flagged as immutable, would this resolve the original issue?
No, because the original issue is that generic graph code expects G.relabel()
to relabel in-place. If they would be immutable, then an exception would be raised by this disallowed in-place relabelling.
comment:14 Changed 4 years ago by
Replying to nthiery:
For the record: the main reason that I am reluctant to change the interface for "relabel" is that Dynkin diagrams are special case of cartan types: they are in the
CartanType_abstract
class where relabel is defined to not take argument and return a new object.
I see what you mean: we have
class DynkinDiagram_class(DiGraph, CartanType_abstract)
where both subclasses (DiGraph
and CartanType_abstract
) have a relabel()
method which happens to be incompatible.
comment:15 Changed 4 years ago by
I did a search of relabel()
methods on various combinatorial objects. There are various behaviours:
A. in-place by default, allowing not in-place
- cluster algebra quivers
- incidence structures
- graphs (various classes)
B1. not in-place by default, allowing in-place
- Dynkin diagrams
B2. always not in-place
- constellations
- posets
- anything else involving root systems (various classes)
- matroids
I don't know what to conclude from this...
comment:16 Changed 4 years ago by
Commit: | a88dc2c9cbd2b2754d7b49629e4eb2facd2f93ab → f1dccbfbfe27d1ec4523aa470e27a635fa03d588 |
---|
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f1dccbf | Make relabel() of DynkinDiagram more compatible with GenericGraph
|
comment:17 Changed 4 years ago by
Description: | modified (diff) |
---|
comment:18 Changed 4 years ago by
Replying to tscrim:
So 1 and 2 are good with me, but I think 3 needs to be reconsidered.
OK, I reverted changes to 3. If certain relabel()
calls fail, we'll just need to fix them.
comment:19 Changed 4 years ago by
Commit: | f1dccbfbfe27d1ec4523aa470e27a635fa03d588 → f360ac0a9d46afafd6c76cd3625bac0ba19633e9 |
---|
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f360ac0 | Make relabel() of DynkinDiagram more compatible with GenericGraph
|
comment:20 Changed 4 years ago by
Reviewers: | → Travis Scrimshaw |
---|---|
Status: | needs_review → positive_review |
Thank you. Sorry for being problematic with this.
comment:21 Changed 4 years ago by
Milestone: | sage-8.6 → sage-8.7 |
---|
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.
comment:22 Changed 4 years ago by
Branch: | u/jdemeyer/ticket/27033 → f360ac0a9d46afafd6c76cd3625bac0ba19633e9 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
New commits:
Make relabel() of DynkinDiagram more compatible with GenericGraph