Opened 3 months ago

Closed 3 months 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) Commit: f360ac0a9d46afafd6c76cd3625bac0ba19633e9
Dependencies: Stopgaps:

Description (last modified by 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()))
  1. return_map is not supported.

Change History (22)

comment:1 Changed 3 months ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/27033

comment:2 Changed 3 months ago by jdemeyer

  • Commit set to a88dc2c9cbd2b2754d7b49629e4eb2facd2f93ab
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

a88dc2cMake relabel() of DynkinDiagram more compatible with GenericGraph

comment:3 Changed 3 months ago by jdemeyer

Green patchbot!

comment:4 follow-ups: Changed 3 months ago by tscrim

  • 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 in reply to: ↑ 4 Changed 3 months ago by 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.

Last edited 3 months ago by jdemeyer (previous) (diff)

comment:6 Changed 3 months ago by 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?

comment:7 follow-up: Changed 3 months ago by 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.

Last edited 3 months ago by nthiery (previous) (diff)

comment:8 Changed 3 months ago by 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.

Last edited 3 months ago by nthiery (previous) (diff)

comment:9 in reply to: ↑ 7 ; follow-ups: Changed 3 months ago by 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.

comment:10 in reply to: ↑ 9 Changed 3 months ago by 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.

Last edited 3 months ago by nthiery (previous) (diff)

comment:11 in reply to: ↑ 9 ; follow-up: Changed 3 months ago by 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)?

comment:12 follow-up: Changed 3 months ago by 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.

comment:13 in reply to: ↑ 11 Changed 3 months ago by 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.

comment:14 in reply to: ↑ 12 Changed 3 months ago by 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.

comment:15 Changed 3 months ago by 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
  1. incidence structures
  1. graphs (various classes)

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

  1. Dynkin diagrams

B2. always not in-place

  1. constellations
  1. posets
  1. anything else involving root systems (various classes)
  1. matroids

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

comment:16 Changed 3 months ago by git

  • Commit changed from a88dc2c9cbd2b2754d7b49629e4eb2facd2f93ab to f1dccbfbfe27d1ec4523aa470e27a635fa03d588

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f1dccbfMake relabel() of DynkinDiagram more compatible with GenericGraph

comment:17 Changed 3 months ago by jdemeyer

  • Description modified (diff)

comment:18 in reply to: ↑ 4 Changed 3 months ago by 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.

comment:19 Changed 3 months ago by git

  • Commit changed from f1dccbfbfe27d1ec4523aa470e27a635fa03d588 to f360ac0a9d46afafd6c76cd3625bac0ba19633e9

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f360ac0Make relabel() of DynkinDiagram more compatible with GenericGraph

comment:20 Changed 3 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Thank you. Sorry for being problematic with this.

comment:21 Changed 3 months ago by embray

  • Milestone changed from sage-8.6 to 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 3 months ago by vbraun

  • Branch changed from u/jdemeyer/ticket/27033 to f360ac0a9d46afafd6c76cd3625bac0ba19633e9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.