Opened 4 months ago

Closed 3 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 4 months ago by dcoudert

  • 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

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 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

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

comment:3 Changed 4 months ago by chapoton

  • 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 3 months ago by vbraun

  • Branch changed from public/26801_sorting_neighbors_in_init_short_digraph to 3ac1d7305f746cc28650d329cd9eeef152b328dd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.