Revision history [back]
 | 1 | initial version |
One way to do the general case uses the all_paths method:
sage: [path for path in g.all_paths(0,1) if len(path) == 5]
[[0, 2, 3, 4, 1], [0, 2, 4, 3, 1], [0, 3, 2, 4, 1], [0, 3, 4, 2, 1], [0, 4, 2, 3, 1], [0, 4, 3, 2, 1]]
sage: [path for path in g.all_paths(0,1) if len(path) == 4]
[[0, 2, 3, 1], [0, 2, 4, 1], [0, 3, 2, 1], [0, 3, 4, 1], [0, 4, 2, 1], [0, 4, 3, 1]]
sage: [path for path in g.all_paths(0,1) if len(path) == 3]
[[0, 2, 1], [0, 3, 1], [0, 4, 1]]
sage: [path for path in g.all_paths(0,1) if len(path) == 2]
[[0, 1]]
There is also a longest_path method that takes source and destination as input parameters, but there seems to be a bug with directed graphs. I've made this #13019.
At the theoretical level, the problem is really easy for this specific graph since there are edges between all the vertices. Thus, you can just pick the endpoints and take any permutation of the remaining vertices (or subset of them) to get a path of a fixed length.
