#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:
----------------------------+-----------------------------------------------
Description changed by kini:
Old description:
> 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.
New description:
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.
----
Apply to `$SAGE_ROOT/devel/sage`:
1. [attachment:trac_12385-all-simple-paths.patch]
1. [attachment:trac_12385_review.patch]
1. [attachment:trac_12385-all-simple-paths.2.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12385#comment:8>
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.
