Changes between Initial Version and Version 2 of Ticket #12385


Ignore:
Timestamp:
01/30/12 04:24:02 (10 years ago)
Author:
kini
Comment:

Whoops, sorry, this is a digraph method, not a graph method. I mistitled the ticket.

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 to Questionable semantics of DiGraph().all_simple_paths
    • Property Authors changed from to Keshav Kini
  • Ticket #12385 – Description

    initial v2  
    11See [https://groups.google.com/d/topic/sage-support/zVmqCIv82zI/discussion this sage-support thread].
    22
    3 The docstring of `Graph().all_simple_paths` starts with this paragraph:
     3The docstring of `DiGraph().all_simple_paths` starts with this paragraph:
    44
    55{{{
     
    1010}}}
    1111
    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.
     12In 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.
    1313
    1414Another 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.