Opened 8 years ago

Closed 8 years ago

# DiGraph.period: new method

Reported by: Owned by: cheuberg major sage-6.4 graph theory period, directed graph, is_aperiodic dkrenn, skropf, ncohen Clemens Heuberger Nathann Cohen N/A fa18a7d fa18a7d1606930b2b7aeb0490ebf8adc8b8d9c60

New method to compute the period of a directed graph. A graph is aperiodic if its period equals 1.

I took the implementation of NetworkX' function `is_aperiodic` (wrapped in `DiGraph` since #16062), rewrote it into `DiGraph` and replaced the final check `g == 1` by returning the period.

### comment:1 Changed 8 years ago by cheuberg

• Status changed from new to needs_review

### comment:2 Changed 8 years ago by chapoton

Please do not put the seealso on just one line, but rather do

```.. SEEALSO::

:meth:`is_aperiodic`
```

### comment:3 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:4 Changed 8 years ago by git

• Commit changed from c8b0ff6deb12a11da157a9285c2701086315bd7e to 34d8b48c31f241bc6d033a6b856d7c43eeb49723

Branch pushed to git repo; I updated commit sha1. New commits:

 ​34d8b48 `new paragraph in ".. SEEALSO:: " block`

### comment:5 follow-up: ↓ 7 Changed 8 years ago by ncohen

Helllooooooooooooooooooo !!!

Could you make it work for "all" graphs, not only strongly connected ones ?

It is not that hard: `d.strongly_connected_components()` returns the list of strongly connected components. You can call it at the beginning of the function, and run your algorithm for one vertex per connected component (and take the gcd of all that).

Note that it replaces your call to `is_strongly_connected`, for if the list has length 1... So it does not cost more for the strongly connected case, and it makes it work for all other graphs.

Also, could you add a "seealso" from "is_aperiodic" to your new function ?

Thanks !

Nathann

### comment:6 Changed 8 years ago by git

• Commit changed from 34d8b48c31f241bc6d033a6b856d7c43eeb49723 to 92b69ce48df97a065594dd05c8795c0d20e68349

Branch pushed to git repo; I updated commit sha1. New commits:

 ​6aaeec1 `Extended the method to the case of non-strongly-connected digraphs` ​92b69ce `Added a "SEEALSO" to .period into .is_aperiodic()`

### comment:7 in reply to: ↑ 5 ; follow-up: ↓ 8 Changed 8 years ago by cheuberg

Could you make it work for "all" graphs, not only strongly connected ones ?

It is not that hard: `d.strongly_connected_components()` returns the list of strongly connected components. You can call it at the beginning of the function, and run your algorithm for one vertex per connected component (and take the gcd of all that).

I used `d.strongly_connected_components_subgraphs`: otherwise, we might follow a path from one connected component to another and either have to live with dealing with a component twice or check that this does not happen.

Also, could you add a "seealso" from "is_aperiodic" to your new function ?

done.

### comment:8 in reply to: ↑ 7 ; follow-up: ↓ 10 Changed 8 years ago by ncohen

• Reviewers set to Nathann Cohen

Hello !

I used `d.strongly_connected_components_subgraphs`: otherwise, we might follow a path from one connected component to another and either have to live with dealing with a component twice or check that this does not happen.

Hmmm... `:-/`

The thing with `strongly_connected_components_subgraphs` is that it triggers copies of the graph, even if the original graph is strongly connected `:-/`

Also, could you add a "seealso" from "is_aperiodic" to your new function ?

done.

Thanks.

Well, then I agree with your code and unless you plan to do something about the "speed" remark you can set the code to `positive_review` !

Nathann

### comment:9 Changed 8 years ago by git

• Commit changed from 92b69ce48df97a065594dd05c8795c0d20e68349 to 41f060716bdc12ac11d0e444a8d7e027da3a9328

Branch pushed to git repo; I updated commit sha1. New commits:

 ​41f0607 `rewrote to avoid copying subgraphs.`

### comment:10 in reply to: ↑ 8 Changed 8 years ago by cheuberg

The thing with `strongly_connected_components_subgraphs` is that it triggers copies of the graph, even if the original graph is strongly connected `:-/`

well, we move away from my initial intention of having code which only minimally deviates from the NetworkX code for `is_aperiodic` and does what I need it for `;-)`.

So, new proposal: no more subgraphs copying; I now force staying in the same component by a hash lookup where the hash used for the levels is re-used.

### comment:11 Changed 8 years ago by ncohen

Hello !

Thanks for your modifications. I added a commit on top of yours at public/16791 which does two things:

1) creates an "alias" for the dictionary level. This is just to make the way you use this dictionary to test containment in the scc clearer

2) I decreased the level of indentation of the inner code by using a "continue"

3) I added a "if" to save some time when `g=1`

Now it is your turn to review my code. As usual, if there is anything you don't like, just say it ! `:-)`

Nathann

### comment:12 Changed 8 years ago by cheuberg

• Branch changed from u/cheuberg/graphs/period to public/16791
• Commit changed from 41f060716bdc12ac11d0e444a8d7e027da3a9328 to fa18a7d1606930b2b7aeb0490ebf8adc8b8d9c60
• Description modified (diff)

Thank you, cross-reviewed your code. These changes are fine for me.

### comment:13 Changed 8 years ago by ncohen

• Status changed from needs_review to positive_review

### comment:14 Changed 8 years ago by vbraun

• Branch changed from public/16791 to fa18a7d1606930b2b7aeb0490ebf8adc8b8d9c60
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.