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: sage-8.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:

Status badges

Description


Change History (22)

comment:1 Changed 4 years ago by Jeroen Demeyer

Branch: u/jdemeyer/avoid_calling_vertices___in_graph_isom_equivalent_non_edge_labeled_graph__

comment:2 Changed 4 years ago by Jeroen Demeyer

Authors: Jeroen Demeyer
Commit: 70e123b09b0516e08d8ba5364979384a003310cd
Status: newneeds_review

New commits:

70e123bAvoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:3 Changed 4 years ago by Travis Scrimshaw

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 edge-labeled directed graphs) and the DynkinDiagram.relabel method must take one parameter.

comment:4 Changed 4 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewneeds_work

comment:5 Changed 4 years ago by Jeroen Demeyer

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 Jeroen Demeyer

Dependencies: #27033
Status: needs_workneeds_review

comment:7 Changed 4 years ago by git

Commit: 70e123b09b0516e08d8ba5364979384a003310cd5ec5eb0d4dc1a04dd51e216949841933256f7174

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

a88dc2cMake relabel() of DynkinDiagram more compatible with GenericGraph
5ec5eb0Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:8 Changed 4 years ago by Jeroen Demeyer

Green patchbot!

comment:9 Changed 4 years ago by Travis Scrimshaw

Status: needs_reviewpositive_review

LGTM (assuming any further changes on #27033 do not affect this ticket).

comment:10 Changed 4 years ago by git

Commit: 5ec5eb0d4dc1a04dd51e216949841933256f717474cebb309f89834f83b959fb4258813d311619fa
Status: positive_reviewneeds_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:

74cebb3Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:11 Changed 4 years ago by Jeroen Demeyer

Status: needs_reviewpositive_review

I removed the commit #27033 from this ticket because that will likely change. But the dependency is still here, so it won't be merged before #27033.

comment:12 Changed 4 years ago by Jeroen Demeyer

Status: positive_reviewneeds_info

Let's wait until #27033 has positive review.

comment:13 Changed 4 years ago by git

Commit: 74cebb309f89834f83b959fb4258813d311619fa864f7de0a3bc8912b5cfd2adcebd7e7d0979289c

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

f360ac0Make relabel() of DynkinDiagram more compatible with GenericGraph
864f7deAvoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:14 Changed 4 years ago by Jeroen Demeyer

Status: needs_infoneeds_review

comment:15 Changed 4 years ago by Travis Scrimshaw

Status: needs_reviewpositive_review

LGTM. Thanks.

comment:16 Changed 4 years ago by Erik Bray

Milestone: sage-8.6sage-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:17 Changed 4 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

comment:18 Changed 4 years ago by Jeroen Demeyer

Dependencies: #27033#27033, #27027

comment:19 Changed 4 years ago by git

Commit: 864f7de0a3bc8912b5cfd2adcebd7e7d0979289c6cfcbb0d79e08eafea87f9a29f7fe7a0e4717fb3

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

6cfcbb0Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:20 Changed 4 years ago by Jeroen Demeyer

Dependencies: #27033, #27027
Status: needs_workneeds_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:21 Changed 4 years ago by Travis Scrimshaw

Status: needs_reviewpositive_review

Works for me.

comment:22 Changed 4 years ago by Volker Braun

Branch: u/jdemeyer/avoid_calling_vertices___in_graph_isom_equivalent_non_edge_labeled_graph__6cfcbb0d79e08eafea87f9a29f7fe7a0e4717fb3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.