Opened 8 years ago

Closed 8 years ago

#12385 closed defect (fixed)

Questionable semantics of DiGraph().all_simple_paths

Reported by: kini Owned by: kini
Priority: major Milestone: sage-5.0
Component: graph theory Keywords: digraphs graphs all_simple_paths
Cc: ncohen, abmasse Merged in: sage-5.0.beta4
Authors: Keshav Kini Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by kini)

See this sage-support thread.

The docstring of DiGraph().all_simple_paths starts with this paragraph:

       Returns a list of all the simple paths of self starting with one of
       the given vertices. A path is simple if no vertex occurs twice in
       it except possibly the starting and ending one. The paths are
       enumerated in increasing length order.

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:

  1. trac_12385-all-simple-paths.patch
  2. trac_12385_review.2.patch
  3. trac_12385-all-simple-paths.2.patch
  4. trac_12385-all-simple-paths.3.patch

Attachments (5)

trac_12385-all-simple-paths.patch (10.4 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage
trac_12385_review.patch (2.2 KB) - added by ncohen 8 years ago.
trac_12385-all-simple-paths.2.patch (3.0 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage
trac_12385_review.2.patch (2.2 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage
trac_12385-all-simple-paths.3.patch (19.3 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage

Download all attachments as: .zip

Change History (21)

comment:1 Changed 8 years ago by kini

  • Authors set to Keshav Kini
  • Cc ncohen abmasse added

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 make ptestlong on this patch now, though the file in question passes and search_src() tells me this function is not used by any other code, so I don't expect any doctest problems.

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:2 Changed 8 years ago by kini

  • Description modified (diff)
  • Keywords digraphs added
  • Summary changed from Questionable semantics of Graph().all_simple_paths to Questionable semantics of DiGraph().all_simple_paths

Whoops, sorry, this is a digraph method, not a graph method. I mistitled the ticket.

comment:3 Changed 8 years ago by kini

  • Status changed from new to needs_review

make ptestlong passes. Comments?

comment:4 Changed 8 years ago by ncohen

First that what you are doing is totally right, then that I will try to review the ticket today :-)

Nathann

comment:5 follow-up: Changed 8 years ago by ncohen

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

Changed 8 years ago by ncohen

comment:6 Changed 8 years ago by abmasse

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 in reply to: ↑ 5 Changed 8 years ago by kini

Replying to 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

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:8 Changed 8 years ago by kini

  • Description modified (diff)

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:9 Changed 8 years ago by kini

  • Description modified (diff)

Your commit message was weird so I fixed it :)

comment:10 Changed 8 years ago by kini

BTW, thanks Alexandre for writing the code in the first place :)

comment:11 Changed 8 years ago by kini

  • Description modified (diff)

comment:12 Changed 8 years ago by kini

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!

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:13 Changed 8 years ago by kini

  • Description modified (diff)

comment:14 Changed 8 years ago by ncohen

Weird loop, but it works :-)

If you are are also ok with it, you can set the ticket to "positive_review" !

Nathann

comment:15 Changed 8 years ago by kini

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

I wrote it, so I guess I'm OK with it :) Thanks!

comment:16 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.