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

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 close merge delete

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?

( 2012-05-25 09:27:40 -0600 )edit

Sort by » oldest newest most voted

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.

more

That was a wonderful explanation of the solution. Thank you!!!

( 2012-05-29 03:57:24 -0600 )edit

From your question I have no idea of what you are looking for..

May it be the diameter of a graph ? http://en.wikipedia.org/wiki/Distance... Or its longest path ? http://en.wikipedia.org/wiki/Longest_...

One is very easily solved, the other one is NP Hard. And Sage knows how to do both.

Nathann

more