Opened 4 years ago

Closed 4 years ago

# py3: improve is_aperiodic to fix doctests

Reported by: Owned by: David Coudert major sage-8.6 graph theory py3, graph Travis Scrimshaw, Frédéric Chapoton, Paul Mercat David Coudert Travis Scrimshaw N/A 207fe9e 207fe9eb69e52ce710e523236351af58387ea525

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`).

### comment:1 Changed 4 years ago by David Coudert

Branch: → public/26869_is_periodic → 207fe9eb69e52ce710e523236351af58387ea525 modified (diff) new → needs_review

New commits:

 ​207fe9e `trac #26869: fix is_aperiodic`

### comment:2 Changed 4 years ago by Travis Scrimshaw

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

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 4 years ago by Travis Scrimshaw

Reviewers: → Travis Scrimshaw needs_review → positive_review

That is good enough for me. Thank you.

### comment:5 Changed 4 years ago by Volker Braun

Branch: public/26869_is_periodic → 207fe9eb69e52ce710e523236351af58387ea525 → fixed positive_review → closed

### comment:6 Changed 4 years ago by Erik Bray

Milestone: sage-8.5 → sage-8.6

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

Note: See TracTickets for help on using tickets.