Changes between Version 58 and Version 59 of Ticket #26640


Ignore:
Timestamp:
02/23/19 10:33:11 (8 weeks ago)
Author:
dcoudert
Comment:

We have now drastically reduced the dependency to .vertices() and .edges() in the graph module (except in doctests, but we can specify sort=True/False).

We must now identify the tasks to do and schedule the work.

Some issues to take care of in the graph module:

  • #22349 Deprecate sorting of methods .vertices() and .edges().
    • methods using matrices: adjacency_matrix, distance_matrix, etc. For all these methods, we can now give as input an ordering of the vertices that will be used to order rows and columns. Currently, we use .vertices() by default. If we switch to list(G) by default, we have to check that it's not breaking algorithms using these matrices.
    • methods using .relabel(). We must check that changing the default ordering of vertices/edges is safe. Should be ok, but we never know...
    • methods for isomorphisms were we also have issues with labels (see e.g. #27232 although the case is certainly beyond what we should reasonably do).
  • Deprecate sorting of vertex labels in method iterator_edges of base/sparse_graph.pyx (so of the vertices of an edge). Deprecating this behavior is certainly a hard task. A first step could be to order the vertices according internal integer value, thus ensuring that (u, v) will always be ordered the same way.

And of course, changes done here will certainly break many methods in other modules...

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #26640 – Description

    v58 v59  
    33
    44'''Major issues'''
    5 - methods `.vertices()` and `.edges()` use sort by default
     5- #22349 Deprecate sorting of methods `.vertices()` and `.edges()`
    66- direct comparison of vertex labels (e.g., in method `iterator_edges` of `base/sparse_graph.pyx`)
    7 - all `min_spanning_tree` methods sort edges before returning the result - #26940 is attempt to stop sorting returned list of edges
     7- methods using matrices: `adjacency_matrix`, `distance_matrix`, etc. For all these methods, we can now give as input an ordering of the vertices that will be used to order rows and columns. Currently, we use `.vertices()` by default. If we switch to `list(G)` by default, we have to check that it's not breaking algorithms using these matrices.
     8- sort used in methods for checking isomorphisms w/wo edge labels
    89
    910
    1011'''Needs work''':
    11 - #26800        py3: bug with canonical_label
     12- #22349        Deprecate sorting of Graph vertices and edges by default
     13- #26800        py3: bug with `canonical_label`
    1214- #27232        `is_permutation_of` broken for matrices over cyclotomic fields -- this is due to `is_isomorphic` in graphs.
    1315
    1416
    1517'''Needs review''':
     18- #27135        pep8 in `digraph_generators.py` (part 2)
     19- #27137        pep8 in `digraph_generators.py` (part 4)
     20- #27138        pep8 in `digraph_generators.py` (part 5)
    1621- #27160        py3: fix doctests in `hyperbolicity` and `graph_coloring`
    1722- #27170        py3: fix 14 doctests in `digraph.py`