Opened 3 years ago

Closed 3 years ago

#27029 closed enhancement (fixed)

Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-8.7
Component: graph theory Keywords:
Cc: dcoudert 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 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/avoid_calling_vertices___in_graph_isom_equivalent_non_edge_labeled_graph__

comment:2 Changed 3 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Commit set to 70e123b09b0516e08d8ba5364979384a003310cd
  • Status changed from new to needs_review

New commits:

​70e123bAvoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:3 Changed 3 years ago by tscrim

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 3 years ago by tscrim

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

comment:5 Changed 3 years ago by jdemeyer

The problem is that DynkinDiagram_class decided to provide a relabel() method with a different interface than the base graph class.

comment:6 Changed 3 years ago by jdemeyer

  • Dependencies set to #27033
  • Status changed from needs_work to needs_review

comment:7 Changed 3 years ago by git

  • Commit changed from 70e123b09b0516e08d8ba5364979384a003310cd to 5ec5eb0d4dc1a04dd51e216949841933256f7174

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 3 years ago by jdemeyer

Green patchbot!

comment:9 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

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

comment:10 Changed 3 years ago by git

  • Commit changed from 5ec5eb0d4dc1a04dd51e216949841933256f7174 to 74cebb309f89834f83b959fb4258813d311619fa
  • Status changed from positive_review to 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:

​74cebb3Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()

comment:11 Changed 3 years ago by jdemeyer

  • Status changed from needs_review to positive_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 3 years ago by jdemeyer

  • Status changed from positive_review to needs_info

Let's wait until #27033 has positive review.

comment:13 Changed 3 years ago by git

  • Commit changed from 74cebb309f89834f83b959fb4258813d311619fa to 864f7de0a3bc8912b5cfd2adcebd7e7d0979289c

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 3 years ago by jdemeyer

  • Status changed from needs_info to needs_review

comment:15 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

LGTM. Thanks.

comment:16 Changed 3 years 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:17 Changed 3 years ago by jdemeyer

  • Status changed from positive_review to needs_work

comment:18 Changed 3 years ago by jdemeyer

  • Dependencies changed from #27033 to #27033, #27027

comment:19 Changed 3 years ago by git

  • Commit changed from 864f7de0a3bc8912b5cfd2adcebd7e7d0979289c to 6cfcbb0d79e08eafea87f9a29f7fe7a0e4717fb3

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 3 years ago by jdemeyer

  • Dependencies #27033, #27027 deleted
  • Status changed from needs_work to 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:21 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

Works for me.

comment:22 Changed 3 years ago by vbraun

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