Make relabel() of DynkinDiagram more compatible with GenericGraph

[jdemeyer]

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:

1. 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 to range(G.order()))

2. return_map is not supported.

[jdemeyer]

New commits:

​a88dc2c

Make relabel() of DynkinDiagram more compatible with GenericGraph

[jdemeyer]

Green patchbot!

[tscrim]

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.

[jdemeyer]

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.

[tscrim]

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?

[nthiery]

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.

[tscrim]

There is some precedence for DynkinDiagram acting like a mutable object, e.g., with its add_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.

[jdemeyer]

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.

[nthiery]

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.

[nthiery]

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)?

[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. So that change would break that compatibility, and presumably this would break generic code about cartan types.

[jdemeyer]

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.

[jdemeyer]

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.

[jdemeyer]

I did a search of relabel() methods on various combinatorial objects. There are various behaviours:

A. in-place by default, allowing not in-place

1. cluster algebra quivers

2. incidence structures

3. graphs (various classes)

B1. not in-place by default, allowing in-place

1. Dynkin diagrams

B2. always not in-place

1. constellations

2. posets

3. anything else involving root systems (various classes)

4. matroids

I don't know what to conclude from this...

[git]

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

[jdemeyer]

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.

[git]

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

[tscrim]

Thank you. Sorry for being problematic with this.

[embray]

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.