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

asked 12 years ago

MaelstromYamato
107 ●3 ●4 ●10

updated 10 years ago

FrédéricC

5426 ●4 ●44 ●121

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?

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 ( 12 years ago )

add a comment

2 Answers

Sort by » oldest newest most voted

answered 12 years ago

Mike Hansen

4088 ●24 ●48 ●90

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.