id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
12385 Questionable semantics of DiGraph().all_simple_paths kini kini "See [https://groups.google.com/d/topic/sage-support/zVmqCIv82zI/discussion 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. [attachment:trac_12385-all-simple-paths.patch]
1. [attachment:trac_12385_review.2.patch]
1. [attachment:trac_12385-all-simple-paths.2.patch]
1. [attachment:trac_12385-all-simple-paths.3.patch]" defect closed major sage-5.0 graph theory fixed digraphs graphs all_simple_paths ncohen abmasse sage-5.0.beta4 Keshav Kini Nathann Cohen N/A