#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, GitHub, GitLab) | Commit: | 207fe9eb69e52ce710e523236351af58387ea525 |
Dependencies: | Stopgaps: |
Description (last modified by )
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 years ago by
- Branch set to public/26869_is_periodic
- Commit set to 207fe9eb69e52ce710e523236351af58387ea525
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 3 years ago by
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 years ago by
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 years ago by
- 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 years ago by
- Branch changed from public/26869_is_periodic to 207fe9eb69e52ce710e523236351af58387ea525
- Resolution set to fixed
- Status changed from positive_review to closed
comment:6 Changed 3 years ago by
- Milestone changed from sage-8.5 to sage-8.6
This tickets were closed as fixed after the Sage 8.5 release.
New commits:
trac #26869: fix is_aperiodic