[sage-support] graph.all_simple_paths bug?

19 views
Skip to first unread message

JStarx

unread,
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

unread,
Jan 29, 2012, 8:24:31 PM1/29/12
to sage-s...@googlegroups.com
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

unread,
Jan 29, 2012, 11:29:29 PM1/29/12
to sage-s...@googlegroups.com
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]]

Reply all
Reply to author
Forward
0 new messages