graph relabel() assumes sortable vertices

[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).

2. 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.

CC: @dcoudert

Component: graph theory

Author: Jeroen Demeyer

Branch/Commit: a7eaec9

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/27027

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1,4 +1,10 @@
-This branch in `relabel()` should not rely on sorted vertices:
+There are several cases in `relabel()` which assume sorting of vertices. In some cases (when given a list/tuple) this makes sense and is hard to avoid.
+
+The following should be fixed though:
+
+1. `perm=None`. This should just relabel with integers from 0 to N-1.
+
+2. `perm` is a callable. This is easy to avoid, as the ordering of the vertices is not used in the code:
 
 ```
         elif callable(perm):

[jdemeyer]

Branch: u/jdemeyer/graph_relabel___assumes_sortable_vertices

[dcoudert]

comment:3

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:

4e3dbd7

Avoid sorting vertices in relabel()

[dcoudert]

Commit: 4e3dbd7

[sagetrac-git]

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

fe559c5

Avoid sorting vertices in relabel()

[sagetrac-git]

Changed commit from 4e3dbd7 to fe559c5

[jdemeyer]

comment:5

Update, still work in progress.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
-There are several cases in `relabel()` which assume sorting of vertices. In some cases (when given a list/tuple) this makes sense and is hard to avoid.
+There are several cases in `relabel()` which assume sorting of vertices. 
 
-The following should be fixed though:
+The following cases are fixed:
 
 1. `perm=None`. This should just relabel with integers from 0 to N-1.
 
@@ -11,3 +11,5 @@
             perm = dict( [ i, perm(i) ] for i in self.vertices() )
             complete_partial_function = False
 ```
+
+Furthermore, we allow arbitrary iterables to be given for relabeling instead of only `list` and `tuple`. This makes things with Python 3 where `range()` becomes an iterator.

[sagetrac-git]

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

6f92367

Avoid sorting vertices in relabel()

[sagetrac-git]

Changed commit from fe559c5 to 6f92367