19 views

Skip to first unread message

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

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

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 !

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 !

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]]

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])

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

[[2, 1]]

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu