Changes between Initial Version and Version 2 of Ticket #12385
 Timestamp:
 01/30/12 04:24:02 (10 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #12385
 Property Cc ncohen abmasse added
 Property Keywords digraphs added

Property
Summary
changed from
Questionable semantics of Graph().all_simple_paths
toQuestionable semantics of DiGraph().all_simple_paths

Property
Authors
changed from
to
Keshav Kini

Ticket #12385 – Description
initial v2 1 1 See [https://groups.google.com/d/topic/sagesupport/zVmqCIv82zI/discussion this sagesupport thread]. 2 2 3 The docstring of ` Graph().all_simple_paths` starts with this paragraph:3 The docstring of `DiGraph().all_simple_paths` starts with this paragraph: 4 4 5 5 {{{ … … 10 10 }}} 11 11 12 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.12 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. 13 13 14 14 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 nondisjoint sets, you are likely asking for cycles to be included.