Ask Your Question
0

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

asked 2012-05-25 07:06:58 -0600

MaelstromYamato gravatar image

updated 2015-01-23 14:51:02 -0600

FrédéricC gravatar image

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 gravatar imageMaelstromYamato ( 2012-05-25 09:27:40 -0600 )edit

2 answers

Sort by » oldest newest most voted
1

answered 2012-05-25 18:32:08 -0600

Mike Hansen gravatar image

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.

edit flag offensive delete link more

Comments

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

MaelstromYamato gravatar imageMaelstromYamato ( 2012-05-29 03:57:24 -0600 )edit
0

answered 2012-05-26 04:25:59 -0600

Nathann gravatar image

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

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-05-25 07:06:58 -0600

Seen: 1,078 times

Last updated: May 26 '12