DiGraph.period: new method

[cheuberg]

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.

[chapoton]

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

.. SEEALSO::

    :meth:`is_aperiodic`

[git]

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

​34d8b48

new paragraph in ".. SEEALSO:: " block

[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

[git]

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()

[cheuberg]

Replying to ncohen:

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.

[ncohen]

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

[git]

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

​41f0607

rewrote to avoid copying subgraphs.

[cheuberg]

Replying to ncohen:

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.

[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

[cheuberg]

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