Opened 8 years ago
Closed 8 years ago
#16791 closed enhancement (fixed)
DiGraph.period: new method
Reported by:  cheuberg  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  graph theory  Keywords:  period, directed graph, is_aperiodic 
Cc:  dkrenn, skropf, ncohen  Merged in:  
Authors:  Clemens Heuberger  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  fa18a7d (Commits, GitHub, GitLab)  Commit:  fa18a7d1606930b2b7aeb0490ebf8adc8b8d9c60 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (14)
comment:1 Changed 8 years ago by
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
comment:3 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:4 Changed 8 years ago by
 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 followup: ↓ 7 Changed 8 years ago by
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
 Commit changed from 34d8b48c31f241bc6d033a6b856d7c43eeb49723 to 92b69ce48df97a065594dd05c8795c0d20e68349
comment:7 in reply to: ↑ 5 ; followup: ↓ 8 Changed 8 years ago by
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.
comment:8 in reply to: ↑ 7 ; followup: ↓ 10 Changed 8 years ago by
 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
 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
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 reused.
comment:11 Changed 8 years ago by
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
 Branch changed from u/cheuberg/graphs/period to public/16791
 Commit changed from 41f060716bdc12ac11d0e444a8d7e027da3a9328 to fa18a7d1606930b2b7aeb0490ebf8adc8b8d9c60
 Description modified (diff)
Thank you, crossreviewed your code. These changes are fine for me.
comment:13 Changed 8 years ago by
 Status changed from needs_review to positive_review
comment:14 Changed 8 years ago by
 Branch changed from public/16791 to fa18a7d1606930b2b7aeb0490ebf8adc8b8d9c60
 Resolution set to fixed
 Status changed from positive_review to closed
Please do not put the seealso on just one line, but rather do