-
-
Notifications
You must be signed in to change notification settings - Fork 512
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Enumeration of cycles in directed graphs #8273
Comments
comment:1
Will add the patch soon. |
comment:2
As you may see in the patch file, I added the digraph.py and generic_graph.py files so that it appear in the generated documentation. However, there are a lot of warnings... What should we do about it? Correct it in that ticket? |
comment:3
Nathann Cohen wrote: Hello !!! I just took a quick look at your patch :
Thank you for your comments ! I will indeed add some comments in the code so that everyone can understand what it does. As for the first comment, I think it is better not to compute the strongly connected components in the private function |
comment:4
Hello !!! It would be good to get (cheaply) rid of this "bug" happening when the vertices are in no non-trivial strongly connected components... Perhaps some other parameter meant to be used only internally, in this case too... But this would mean a lot of them in the end :-) I continued to read some parts of your code, and have some other remarks :
I'll give a look again at your next version of the patch... Each time I get more used to what it does :-) Nathann |
comment:5
Hello, Nathann ! I do not know much about iterators, but...
For two reasons: (1) I want to iterate cycles with increasing length and what you propose breaks this property. (2) There is no guarantee that I also added three functions which iterate over paths. Note that the code is almost the same, but for sake of efficienty, it seems better to me not to intersect it. The main reason is that when you want to enumerate unrooted cycles, there is a very fast way to verify that (just check that the starting vertex of the current path is the smallest in the path). Therefore, I prefered to separate the two functions. Thank you for the useful comments ! Also, if you prefer me to break the patch into two smaller ones, just tell me, I'll do it. I'll upload the patch in a short while. |
Attachment: trac_8273_digraphs_cycles_enumerations-abm.patch.gz New patch taking into account Nathann's comments |
comment:6
The patch has been uploaded. I removed doc reference changes since some warnings occurred and I believe it should be done in another patch. My modifications seemed correct concerning the documentation. Now needing review ! |
comment:7
Several comments :
Short of this, your patch is fine... Next update will definitely be a positive review ! I did not update the patch myself as there were several questions I did not know how to solve myself, so sorry if some comments are clearly minor ones... :-) Have fuuuuuuun ! Nathann |
comment:8
Hello, Nathann ! Don't say sorry, your comments are very welcome and are clearly pertinent ! Several comments :
Done. It was an old comment I forgot to delete.
Done. I noticed it while writing the code, but I was too lazy to do it. It turned out to be very simple, so I'm glad you mentionned it.
Done. Thanks for the information !
There is no argument vertex in
Done. You are right. The meaning of
The reason I put this flag is that I want the function I'll upload a patch in a short while. |
Apply on top of the main patch |
comment:9
Attachment: trac_8273_with_heap-abm.patch.gz I uploaded another patch that include your comments. Needs review ! |
comment:10
It just needs merging now... Very nice work ! :-) Nathann |
Changed author from abmasse to Alexandre Blondin Massé |
Reviewer: Nathann Cohen |
Merged: sage-4.3.4.alpha0 |
comment:12
Merged in this order: Alexandre: you should place a sensible commit message in your patch together with the ticket number. |
comment:13
Yes, thank you, Minh, you're right ! Someone made me notice it some time ago and I thought I had done it for all my patchs, but it looks like I forgot some. It won't happen again I hope. |
In many graph-theoretical problems, it is important to understand the cycles structure of undirected graphs as well as directed ones. Therefore, I suggest three functions that allow one to iterate over all cycles of a directed graph (I might be interested in writing some functions for undirected graphs, but I prefer to have these ones validated before I do so).
The first and main function is called
cycles_iterator(...)
and allows one to iterate over all cycles satisfying conditions according to the following parameters:simple
(a boolean). When set to True, only the starting and ending vertex may be repeated in the cycledistinct
(also a boolean). When set to True, then all equivalent cycles are merged into one cycle. Equivalent cycles are cycles differing only from their starting vertex, such as[0,1,2,0]
and[1,2,0,1]
.initial_vertices
(an iterable). Specify the only allowed starting vertices of the cycles.max_length
(an integer). The maximum length of cycles. Useful especially when a graph contains a very large number of cycles and one wants to compute smaller ones.The two other function are merely calling
cycles_iterator(...)
with some of the above parameters fixed.CC: @nathanncohen @rlmill @sagetrac-sage-combinat
Component: graph theory
Keywords: cycle, enumeration
Author: Alexandre Blondin Massé
Reviewer: Nathann Cohen
Merged: sage-4.3.4.alpha0
Issue created by migration from https://trac.sagemath.org/ticket/8273
The text was updated successfully, but these errors were encountered: