Opened 7 months ago
Closed 7 months ago
#26801 closed enhancement (fixed)
py3: change sorting of neighbors labels in static_sparse_graph.pyx
Reported by: | dcoudert | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.5 |
Component: | graph theory | Keywords: | py3, graph |
Cc: | tscrim, chapoton | Merged in: | |
Authors: | David Coudert | Reviewers: | Travis Scrimshaw, Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | 3ac1d73 (Commits) | Commit: | 3ac1d7305f746cc28650d329cd9eeef152b328dd |
Dependencies: | Stopgaps: |
Description
Many doctests are failing in Python 3 due to the operation neighbor_label.sort()
in method init_short_digraph
of static_sparse_graph.pyx
.
In the short_digraph
data structure, the neighbors of a vertex are sorted by increasing integer value. This can be useful for some algorithms...
neighbor_label
is a list of tuples (int, object)
used only when edges are labeled and that we want to store these labels. Clearly, when the graph has no multiple edges, is suffices to sort neighbor_label
according the integer values. When the graph has multiple edges, there is so far no need for sorting the labels of the edges between a given pair of vertices, and furthermore no assumption is documented on this ordering.
Also, this patch changes the sorting to sort using the integer values only.
Change History (4)
comment:1 Changed 7 months ago by
- Branch set to public/26801_sorting_neighbors_in_init_short_digraph
- Cc tscrim chapoton added
- Commit set to 3ac1d7305f746cc28650d329cd9eeef152b328dd
- Keywords py3 graph added
- Status changed from new to needs_review
comment:2 Changed 7 months ago by
- Reviewers set to Travis Scrimshaw
Green bot => positive review (unless Frédéric has some other comments).
comment:3 Changed 7 months ago by
- Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Frédéric Chapoton
- Status changed from needs_review to positive_review
ok, looks good to me too
comment:4 Changed 7 months ago by
- Branch changed from public/26801_sorting_neighbors_in_init_short_digraph to 3ac1d7305f746cc28650d329cd9eeef152b328dd
- Resolution set to fixed
- Status changed from positive_review to closed
Applying this patch over 8.5.beta6 compiled for Python3, we reduce the number of failing doctests in
connectivity.pyx
from 49 to 5. The files for which progresses are observed are:Without this patch, we get
New commits:
trac 26801: change sorting of neighbors in init_short_digraph