[sage-support] graph.all_simple_paths bug?

[JStarx]

Consider the following:

sage: Q = DiGraph({1: {2:'a'}, 2: {1: 'b', 3: 'c'}, 3: {2: 'd'}})
sage: Q.all_simple_paths([1], [2])
[[1, 2], [1, 2, 3, 2]]
sage: Q.all_simple_paths([2], [1])
[[2, 1]]

First, the documentation to all_simple_paths says that a simple path
is one in which no vertex appears twice *except possibly the starting
and ending one*. This is not what I understand to be a simple path,
why the exception for the starting and ending vertex?

Second, if there indeed should be such an exception, why isn't [2, 3,
2, 1] a simple path? It appears that sage is only letting the end
vertex repeat.

-Jim Stark

[Keshav Kini]

What I understand from that sentence in the documentation is that if the starting set and ending set share some vertex, you may get cycles in the output, and each cycles will have the same point at its beginning as at its end - specifically, a point which is in both the starting set and the ending set.

However, this doesn't explain how [1,2,3,2] is a path in which no vertex appears twice. It looks to me like 2 quite clearly appears twice. Looks like a bug.

-Keshav

----
Join us in #sagemath on irc.freenode.net !

[Keshav Kini]

I wrote up a trac ticket and made a patch: http://trac.sagemath.org/sage_trac/ticket/12385

With my patch, your code snippets evaluate as follows:

sage: Q = DiGraph({1: {2:'a'}, 2: {1: 'b', 3: 'c'}, 3: {2: 'd'}})
sage: Q.all_simple_paths([1], [2])

[[1, 2]]

sage: Q.all_simple_paths([2], [1])
[[2, 1]]