Opened 3 months ago

Closed 3 months ago

Last modified 3 months ago

#26869 closed enhancement (fixed)

py3: improve is_aperiodic to fix doctests

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.6
Component: graph theory Keywords: py3, graph
Cc: tscrim, chapoton, mercatp Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 207fe9e (Commits) Commit: 207fe9eb69e52ce710e523236351af58387ea525
Dependencies: Stopgaps:

Description (last modified by dcoudert)

The current implementation of is_aperiodic uses networkx and it yields an error in Python3 (due to a deprecation warning).

As we have method period that computes the period of a digraph, it suffices to check whether the period is 1 or not. This way, we don't pay the conversion to networkx anymore, and we avoid the failing doctests in digraph.py and in static_sparse_graph.pyx (calls is_aperiodic).

Change History (6)

comment:1 Changed 3 months ago by dcoudert

  • Branch set to public/26869_is_periodic
  • Commit set to 207fe9eb69e52ce710e523236351af58387ea525
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

207fe9etrac #26869: fix is_aperiodic

comment:2 Changed 3 months ago by tscrim

How does the timing compare between the two methods? I am inclined to still accept this change, but I am a little curious how things compare.

comment:3 Changed 3 months ago by dcoudert

The example is maybe too small, but without this patch:

sage: g = DiGraph({0: [1, 4], 1: [2], 2: [0], 4: [0]})
sage: %timeit g.is_aperiodic()
The slowest run took 7.37 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 56 µs per loop

With this patch

sage: g = DiGraph({0: [1, 4], 1: [2], 2: [0], 4: [0]})
sage: %timeit g.is_aperiodic()
The slowest run took 4.61 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 31 µs per loop

In fact, the period is very similar to the one in networkx. So we save the conversion to networkx.

comment:4 Changed 3 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

That is good enough for me. Thank you.

comment:5 Changed 3 months ago by vbraun

  • Branch changed from public/26869_is_periodic to 207fe9eb69e52ce710e523236351af58387ea525
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:6 Changed 3 months ago by embray

  • Milestone changed from sage-8.5 to sage-8.6

This tickets were closed as fixed after the Sage 8.5 release.

Note: See TracTickets for help on using tickets.