#12385: Questionable semantics of Graph().all_simple_paths
----------------------------+-----------------------------------------------
Reporter: kini | Owner: kini
Type: defect | Status: new
Priority: major | Milestone: sage-5.0
Component: graph theory | Keywords: graphs all_simple_paths
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
See [https://groups.google.com/d/topic/sage-support/zVmqCIv82zI/discussion
this sage-support thread].
The docstring of `Graph().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 `Graph().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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12385>
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.
