#12385: Questionable semantics of DiGraph().all_simple_paths
----------------------------+-----------------------------------------------
Reporter: kini | Owner: kini
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: graph theory | Keywords: digraphs graphs all_simple_paths
Work_issues: | Upstream: N/A
Reviewer: | Author: Keshav Kini
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Comment(by kini):
Replying to [comment:5 ncohen]:
> Hmmm... I was a bit worried at your path.count(path[-1]) `^^;`
Can you explain? I think the same expression was used in the old code.
> 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.
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.
> 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 ?
Well, part of it was a mistake - I meant to put the check for `trivial`
after the check for `len(path)`. Because of the lazy evaluation of boolean
operators in Python (`a and b` skips checking `b` if `a` is false, etc.),
this would still make `trivial` be evaluated only once, and would reduce
the number of `yield` statements in the code, making it "easier to read",
theoretically. Also I made it so that `len(path)` would only be checked
for each path with a desired endpoint, not every single path.
But you're right, it's possible to make this better by moving the
condition check in the `while` loop to somewhere in the middle of the body
rather than at the top. Patch attached! (Or will be after I post this
comment.) I made some other changes too, such as inverting the loop and
if/else in your code to check `simple` on every good incomplete path
rather than every candidate extension. It would be best if `simple` and
`trivial` could be declared as constant so that Python could optimize away
all these checks. Or maybe it already knows this, since we don't assign
any values to those variables... how smart is Python, anyway? I think I am
getting stuck in the premature optimization trap... :P
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12385#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
