# [sage-support] graph.all_simple_paths bug?

19 views

### JStarx

Jan 28, 2012, 2:42:17 PM1/28/12
to sage-support
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

Jan 29, 2012, 8:24:31 PM1/29/12
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

----

### Keshav Kini

Jan 29, 2012, 11:29:29 PM1/29/12
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]]