#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.
>
> ----
>
> 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]
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.
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]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12385#comment:11>
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.
