How to find the path of the maximal distance between two vertices on a complete digraph?

asked 2012-05-25 14:06:58 +0200

MaelstromYamato
107 ●3 ●4 ●10

updated 2015-01-23 21:51:02 +0200

5125 ●3 ●43 ●111

I was wondering how can I find the path of the maximal distance between two vertices on a complete digraph. Suppose the digraph has 5 vertices:

sage: g = graphs.CompleteGraph(5).to_directed()

I have seen a maximal flow example which is nice but it is not the same type of problem. How can I use sage to find the longest path?

edit retag flag offensive close merge delete

Comments

In general, I would also like to find if the complete digraph has n vertices, how can I find the path(s) from any two vertices of distance (n-1), (n-2), ..., 2?

MaelstromYamato ( 2012-05-25 16:27:40 +0200 )edit

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2012-05-26 01:32:08 +0200

Mike Hansen

4068 ●24 ●48 ●89

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.