Opened 8 years ago

Closed 8 years ago

#16791 closed enhancement (fixed)

DiGraph.period: new method

Reported by: cheuberg Owned by:
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by 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.

Change History (14)

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:

34d8b48new paragraph in ".. SEEALSO:: " block

comment:5 follow-up: 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:

6aaeec1Extended the method to the case of non-strongly-connected digraphs
92b69ceAdded a "SEEALSO" to .period into .is_aperiodic()

comment:7 in reply to: ↑ 5 ; follow-up: Changed 8 years ago by 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.

comment:8 in reply to: ↑ 7 ; follow-up: 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:

41f0607rewrote to avoid copying subgraphs.

comment:10 in reply to: ↑ 8 Changed 8 years ago by 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.

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.