Opened 4 years ago
Closed 4 years ago
#27029 closed enhancement (fixed)
Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
Reported by:  Jeroen Demeyer  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  graph theory  Keywords:  
Cc:  David Coudert  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  6cfcbb0 (Commits, GitHub, GitLab)  Commit:  6cfcbb0d79e08eafea87f9a29f7fe7a0e4717fb3 
Dependencies:  Stopgaps: 
Description
Change History (22)
comment:1 Changed 4 years ago by
Branch:  → u/jdemeyer/avoid_calling_vertices___in_graph_isom_equivalent_non_edge_labeled_graph__ 

comment:2 Changed 4 years ago by
Authors:  → Jeroen Demeyer 

Commit:  → 70e123b09b0516e08d8ba5364979384a003310cd 
Status:  new → needs_review 
comment:3 Changed 4 years ago by
This breaks stuff in root systems:
sage t long src/sage/combinat/root_system/extended_affine_weyl_group.py # 404 doctests failed sage t long src/sage/combinat/root_system/cartan_type.py # 6 doctests failed sage t long src/sage/categories/magmas.py # 3 doctests failed sage t long src/sage/combinat/root_system/fundamental_group.py # 118 doctests failed sage t long src/doc/en/thematic_tutorials/lie/affine.rst # 1 doctest failed
It looks like it has to do with computing the orbit of 0
in the Dynkin diagram (think special edgelabeled directed graphs) and the DynkinDiagram.relabel
method must take one parameter.
comment:4 Changed 4 years ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → needs_work 
comment:5 Changed 4 years ago by
The problem is that DynkinDiagram_class
decided to provide a relabel()
method with a different interface than the base graph class.
comment:6 Changed 4 years ago by
Dependencies:  → #27033 

Status:  needs_work → needs_review 
comment:7 Changed 4 years ago by
Commit:  70e123b09b0516e08d8ba5364979384a003310cd → 5ec5eb0d4dc1a04dd51e216949841933256f7174 

comment:9 Changed 4 years ago by
Status:  needs_review → positive_review 

LGTM (assuming any further changes on #27033 do not affect this ticket).
comment:10 Changed 4 years ago by
Commit:  5ec5eb0d4dc1a04dd51e216949841933256f7174 → 74cebb309f89834f83b959fb4258813d311619fa 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:
74cebb3  Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:11 Changed 4 years ago by
Status:  needs_review → positive_review 

comment:12 Changed 4 years ago by
Status:  positive_review → needs_info 

Let's wait until #27033 has positive review.
comment:13 Changed 4 years ago by
Commit:  74cebb309f89834f83b959fb4258813d311619fa → 864f7de0a3bc8912b5cfd2adcebd7e7d0979289c 

comment:14 Changed 4 years ago by
Status:  needs_info → needs_review 

comment:16 Changed 4 years ago by
Milestone:  sage8.6 → sage8.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 sagepending or sagewishlist.
comment:17 Changed 4 years ago by
Status:  positive_review → needs_work 

comment:18 Changed 4 years ago by
Dependencies:  #27033 → #27033, #27027 

comment:19 Changed 4 years ago by
Commit:  864f7de0a3bc8912b5cfd2adcebd7e7d0979289c → 6cfcbb0d79e08eafea87f9a29f7fe7a0e4717fb3 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6cfcbb0  Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:20 Changed 4 years ago by
Dependencies:  #27033, #27027 

Status:  needs_work → needs_review 
New attempt. The code is now closer to what it used to be: whenever the set of vertices (in any order) equals range(G.order())
, I don't relabel. I also added a comment why:
# Do not relabel if the set of vertices is equal to the set # range(n). This helps to ensure that *equal* graphs on range(n) # yield *equal* (not just isomorphic) canonical labelings. This # is just a convenience, there is no mathematical meaning.
comment:22 Changed 4 years ago by
Branch:  u/jdemeyer/avoid_calling_vertices___in_graph_isom_equivalent_non_edge_labeled_graph__ → 6cfcbb0d79e08eafea87f9a29f7fe7a0e4717fb3 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()