#12385: Questionable semantics of DiGraph().all_simple_paths
----------------------------+-----------------------------------------------
Reporter: kini | Owner: kini
Type: defect | Status: new
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:
----------------------------+-----------------------------------------------
Changes (by kini):
* keywords: graphs all_simple_paths => digraphs graphs all_simple_paths
Old description:
> 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.
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.
--
Comment:
Whoops, sorry, this is a digraph method, not a graph method. I mistitled
the ticket.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12385#comment:2>
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.
