ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 29 May 2012 10:57:24 +0200How to find the path of the maximal distance between two vertices on a complete digraph?https://ask.sagemath.org/question/9000/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](http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html#flows) example which is nice but it is not the same type of problem. How can I use sage to find the longest path?
Fri, 25 May 2012 14:06:58 +0200https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/Comment by MaelstromYamato for <p>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:</p>
<p><code>sage: g = graphs.CompleteGraph(5).to_directed()</code></p>
<p>I have seen a <a href="http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html#flows">maximal flow</a> example which is nice but it is not the same type of problem. How can I use sage to find the longest path?</p>
https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?comment=19739#post-id-19739In 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?Fri, 25 May 2012 16:27:40 +0200https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?comment=19739#post-id-19739Answer by Nathann for <p>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:</p>
<p><code>sage: g = graphs.CompleteGraph(5).to_directed()</code></p>
<p>I have seen a <a href="http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html#flows">maximal flow</a> example which is nice but it is not the same type of problem. How can I use sage to find the longest path?</p>
https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?answer=13616#post-id-13616From 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_(graph_theory)
Or its longest path ? http://en.wikipedia.org/wiki/Longest_path_problem
One is very easily solved, the other one is NP Hard. And Sage knows how to do both.
NathannSat, 26 May 2012 11:25:59 +0200https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?answer=13616#post-id-13616Answer by Mike Hansen for <p>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:</p>
<p><code>sage: g = graphs.CompleteGraph(5).to_directed()</code></p>
<p>I have seen a <a href="http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html#flows">maximal flow</a> example which is nice but it is not the same type of problem. How can I use sage to find the longest path?</p>
https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?answer=13615#post-id-13615One 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](http://trac.sagemath.org/sage_trac/ticket/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.
Sat, 26 May 2012 01:32:08 +0200https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?answer=13615#post-id-13615Comment by MaelstromYamato for <p>One way to do the general case uses the <code>all_paths</code> method:</p>
<pre><code>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]]
</code></pre>
<p>There is also a <code>longest_path</code> method that takes source and destination as input parameters, but there seems to be a bug with directed graphs. I've made this <a href="http://trac.sagemath.org/sage_trac/ticket/13019">#13019</a>.</p>
<p>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.</p>
https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?comment=19731#post-id-19731That was a wonderful explanation of the solution. Thank you!!!Tue, 29 May 2012 10:57:24 +0200https://ask.sagemath.org/question/9000/how-to-find-the-path-of-the-maximal-distance-between-two-vertices-on-a-complete-digraph/?comment=19731#post-id-19731