#27027 closed defect (fixed)

graph relabel() assumes sortable vertices

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-8.7
Component: graph theory Keywords: py3, graph
Cc: dcoudert Merged in:
Authors: Jeroen Demeyer Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: a7eaec9 (Commits) Commit: a7eaec9a42dbdc6839fca59d2f42c8e1f07e6c07
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

There are several cases in relabel() which assume sorting of vertices.

The following cases are fixed:

  1. perm=None. This should just relabel with integers from 0 to N-1 in an arbitrary order (as the documentation already says).
  1. perm is a callable. This is easy to avoid, as the ordering of the vertices is not used in the code:
            elif callable(perm):
                perm = dict( [ i, perm(i) ] for i in self.vertices() )
                complete_partial_function = False
    

This broke several functions which did assume a particular ordering for G.relabel(perm=None). Those are fixed by using G.relabel(perm=range(G.order())) instead.

Furthermore, we allow arbitrary iterables to be given for relabeling instead of only list and tuple. This improves things with Python 3 where range() becomes an iterator.

Change History (31)

comment:1 Changed 11 months ago by jdemeyer

  • Description modified (diff)
  • Summary changed from graph relabel() with callable should not sort vertices to graph relabel() assumes sortable vertices

comment:2 Changed 11 months ago by jdemeyer

  • Branch set to u/jdemeyer/graph_relabel___assumes_sortable_vertices

comment:3 Changed 11 months ago by dcoudert

  • Commit set to 4e3dbd7ca700fb7eec96e234e706897b0c04ac6a

You could use G.relabel(list(range(G.order()))) instead of G.relabel(list(range(len(G)))).

In generic_graph.py, you changed the doctest G.relabel(return_map=True) == expecting. Isn't it risky to do that ? the ordering of the keys of a dictionary might differ in py2 and py3, no ?


New commits:

4e3dbd7Avoid sorting vertices in relabel()

comment:4 Changed 11 months ago by git

  • Commit changed from 4e3dbd7ca700fb7eec96e234e706897b0c04ac6a to fe559c5525eb5ca2f275f847c32e1869b9cbecea

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

fe559c5Avoid sorting vertices in relabel()

comment:5 Changed 11 months ago by jdemeyer

Update, still work in progress.

comment:6 Changed 11 months ago by jdemeyer

  • Description modified (diff)

comment:7 Changed 11 months ago by git

  • Commit changed from fe559c5525eb5ca2f275f847c32e1869b9cbecea to 6f92367a436e9e71999a26ec6c7dee1246f9f347

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

6f92367Avoid sorting vertices in relabel()

comment:8 Changed 11 months ago by jdemeyer

  • Description modified (diff)

comment:9 Changed 11 months ago by jdemeyer

  • Description modified (diff)

comment:10 Changed 11 months ago by jdemeyer

  • Status changed from new to needs_review

comment:11 Changed 11 months ago by jdemeyer

  • Description modified (diff)

comment:12 Changed 11 months ago by git

  • Commit changed from 6f92367a436e9e71999a26ec6c7dee1246f9f347 to ab00c175178632d7dd1835bc618fa08bf5253aa8

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

ab00c17Avoid sorting vertices in relabel()

comment:13 Changed 11 months ago by jdemeyer

Green patchbot!

comment:14 follow-up: Changed 11 months ago by dcoudert

  • Reviewers set to David Coudert

Unless I'm mistaken, range is an iterator in py3. Therefore, we cannot do G.relabel(range(G.order())) (several places). Or we must add a specific rule for iterators.

comment:15 in reply to: ↑ 14 Changed 11 months ago by jdemeyer

Replying to dcoudert:

Or we must add a specific rule for iterators.

Indeed. This is what I did in this patch.

comment:16 Changed 11 months ago by dcoudert

  • Keywords py3 graph added
  • Status changed from needs_review to positive_review

For me this patch is good to go. I did several tests without detecting any hidden issue.

comment:17 Changed 11 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:18 Changed 11 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:19 Changed 11 months ago by jdemeyer

The issue in src/sage/combinat/cluster_algebra_quiver/quiver.py was already fixed by #26985.

So I'm just reverting any changes to that file.

comment:20 Changed 11 months ago by git

  • Commit changed from ab00c175178632d7dd1835bc618fa08bf5253aa8 to a7eaec9a42dbdc6839fca59d2f42c8e1f07e6c07

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

a7eaec9Avoid sorting vertices in relabel()

comment:21 Changed 11 months ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:22 Changed 11 months ago by jdemeyer

  • Status changed from needs_review to positive_review

At least one green patchbot, so I'm restoring positive review.

comment:23 Changed 11 months ago by dcoudert

OK

comment:24 Changed 11 months ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long src/sage/combinat/root_system/coxeter_matrix.py
**********************************************************************
File "src/sage/combinat/root_system/coxeter_matrix.py", line 1041, in sage.combinat.root_system.coxeter_matrix.recognize_coxeter_type_from_matrix
Failed example:
    CoxeterMatrix(CoxeterType(['A',10,1]).coxeter_graph()).coxeter_type()
Expected:
    Coxeter type of ['A', 10, 1]
Got:
    Coxeter type of ['A', 10, 1] relabelled by {0: 2, 1: 3, 2: 4, 3: 5, 4: 6, 5: 7, 6: 8, 7: 9, 8: 10, 9: 0, 10: 1}
**********************************************************************
1 item had failures:
   1 of  39 in sage.combinat.root_system.coxeter_matrix.recognize_coxeter_type_from_matrix
    [181 tests, 1 failure, 0.51 s

comment:25 Changed 11 months ago by jdemeyer

  • Dependencies set to #27033

comment:26 Changed 11 months ago by jdemeyer

This failure is caused by interactions with #27029. It doesn't happen by itself.

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

comment:27 Changed 11 months ago by jdemeyer

  • Dependencies changed from #27033 to #27029

comment:28 Changed 11 months ago by jdemeyer

  • Dependencies #27029 deleted
  • Status changed from needs_work to positive_review

comment:29 Changed 11 months ago by dcoudert

I'm a bit lost here... at least, I don't have errors when testing this ticket alone.

comment:30 Changed 11 months ago by jdemeyer

As I said, it's because of this ticket together with #27029.

comment:31 Changed 11 months ago by vbraun

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