Opened 4 years ago

Closed 4 years ago

#26801 closed enhancement (fixed)

py3: change sorting of neighbors labels in static_sparse_graph.pyx

Reported by: David Coudert Owned by:
Priority: major Milestone: sage-8.5
Component: graph theory Keywords: py3, graph
Cc: Travis Scrimshaw, Frédéric Chapoton Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 3ac1d73 (Commits, GitHub, GitLab) Commit: 3ac1d7305f746cc28650d329cd9eeef152b328dd
Dependencies: Stopgaps:

Status badges

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 4 years ago by David Coudert

Branch: public/26801_sorting_neighbors_in_init_short_digraph
Cc: Travis Scrimshaw Frédéric Chapoton added
Commit: 3ac1d7305f746cc28650d329cd9eeef152b328dd
Keywords: py3 graph added
Status: newneeds_review

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:

sage -t --long --warn-long 119.6 src/sage/graphs/generic_graph.py  # 77 doctests failed
sage -t --long --warn-long 119.6 src/sage/graphs/connectivity.pyx  # 5 doctests failed
sage -t --long --warn-long 119.6 src/sage/graphs/digraph.py  # 8 doctests failed
sage -t --long --warn-long 119.6 src/sage/graphs/base/graph_backends.pyx  # 1 doctest failed

Without this patch, we get

sage -t --long src/sage/graphs/generic_graph.py  # 78 doctests failed
sage -t --long src/sage/graphs/connectivity.pyx  # 49 doctests failed
sage -t --long src/sage/graphs/digraph.py  # 15 doctests failed
sage -t --long src/sage/graphs/base/graph_backends.pyx  # 5 doctests failed

New commits:

3ac1d73trac 26801: change sorting of neighbors in init_short_digraph

comment:2 Changed 4 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw

Green bot => positive review (unless Frédéric has some other comments).

comment:3 Changed 4 years ago by Frédéric Chapoton

Reviewers: Travis ScrimshawTravis Scrimshaw, Frédéric Chapoton
Status: needs_reviewpositive_review

ok, looks good to me too

comment:4 Changed 4 years ago by Volker Braun

Branch: public/26801_sorting_neighbors_in_init_short_digraph3ac1d7305f746cc28650d329cd9eeef152b328dd
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.