-
-
Notifications
You must be signed in to change notification settings - Fork 453
-
-
Notifications
You must be signed in to change notification settings - Fork 453
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
Questionable semantics of DiGraph().all_simple_paths #12385
Comments
Author: Keshav Kini |
comment:1
Here's a patch which implements the first suggestion in the ticket description. The original ticket seems to be #8273 so I'm CCing the author and reviewer of that ticket. Doing a |
apply to $SAGE_ROOT/devel/sage |
This comment has been minimized.
This comment has been minimized.
Changed keywords from graphs all_simple_paths to digraphs graphs all_simple_paths |
comment:2
Attachment: trac_12385-all-simple-paths.patch.gz Whoops, sorry, this is a digraph method, not a graph method. I mistitled the ticket. |
comment:3
|
comment:4
First that what you are doing is totally right, then that I will try to review the ticket today Nathann |
comment:5
Hellooooo !!! Hmmm... I was a bit worried at your path.count(path[-1]) What do you think of the alternative version I attach ? In this one I check whether the path is a cycle before adding it to the queue. This way a "neighbor in path" is sufficient. I also do not understand why you removed the "if trivial" from before the loop to put it inside. It would be a waste to "test" trivial at each loop, and also to test len(path) > 1 when we know it will always be true after some step, wouldn't it ? Tell me what you think Nathann |
Attachment: trac_12385_review.patch.gz |
comment:6
Hi, Keshav and Nathann, Thank you, Keshav, for finding that bug, I'm sorry we missed it the first time. Since Nathann has already started the review, I'll let him finish it (I don't even have the last Sage version installed on my computer). By the way, the title "Questionable semantics of DiGraph().all_simple_paths" could be replaced by "Wrong semantics of DiGraph().all_simple_paths" :-) Alexandre |
comment:7
Replying to @nathanncohen:
Can you explain? I think the same expression was used in the old code.
Nice! It's definitely better. I don't know why I avoided touching that last loop. Of course that is the better place to do this logic.
Well, part of it was a mistake - I meant to put the check for But you're right, it's possible to make this better by moving the condition check in the |
Attachment: trac_12385-all-simple-paths.2.patch.gz apply to $SAGE_ROOT/devel/sage |
This comment has been minimized.
This comment has been minimized.
Attachment: trac_12385_review.2.patch.gz apply to $SAGE_ROOT/devel/sage |
This comment has been minimized.
This comment has been minimized.
comment:9
Your commit message was weird so I fixed it :) |
comment:10
BTW, thanks Alexandre for writing the code in the first place :) |
This comment has been minimized.
This comment has been minimized.
comment:12
Here's a documentation patch which changes the stated definition of simple paths as well (to the one I added to the description). I also took the opportunity to enforce PEP 8 in the functions I touched, with the exception of doctest input lines (because of #10458 which I really need to get back to one of these days...). Patch below! |
Attachment: trac_12385-all-simple-paths.3.patch.gz apply to $SAGE_ROOT/devel/sage |
This comment has been minimized.
This comment has been minimized.
comment:14
Weird loop, but it works If you are are also ok with it, you can set the ticket to "positive_review" ! Nathann |
Reviewer: Nathann Cohen |
comment:15
I wrote it, so I guess I'm OK with it :) Thanks! |
Merged: sage-5.0.beta4 |
See this sage-support thread.
The docstring of
DiGraph().all_simple_paths
starts with this paragraph:In short, the
DiGraph().all_simple_paths
function deems paths of the form[a, b, c, b]
to be simple. This is not true according to the generally accepted definition of a simple path. I suspect the intent of the author was to allow paths of the form[b, c, b]
(i.e. paths which are actually cycles), which seems reasonable.Another possibility would be to use the definition found on Wikipedia, namely that a simple path must not have any repeated vertices, and that a "simple cycle" is a path whose first vertex is its last vertex but has no other vertex repetitions. In this case the function should exclude both paths of the form
[a, b, c, b]
and paths of the form[b, c, b]
. But I don't see that this is very useful. The function allows you to specify sets of starting and ending points for the paths you want returned, and if you specify non-disjoint sets, you are likely asking for cycles to be included.Incidentally, a definition that matches what is given in the first paragraph above is this: a "simple path" in a directed graph is a sequence of arcs such that the head of each arc is the tail of the next arc in the sequence, and no two arcs share the same head or the same tail.
Apply to
$SAGE_ROOT/devel/sage
:CC: @nathanncohen @sagetrac-abmasse
Component: graph theory
Keywords: digraphs graphs all_simple_paths
Author: Keshav Kini
Reviewer: Nathann Cohen
Merged: sage-5.0.beta4
Issue created by migration from https://trac.sagemath.org/ticket/12385
The text was updated successfully, but these errors were encountered: