ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 21 Aug 2013 13:07:08 -0500Finding all shortest paths between given (specific) pair of verticeshttp://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/I am working with graphs in sage and need a method of finding all shortest paths between some pair (or all pairs) of vertices.
Note that it is important to have all shortest paths registred, not just one, as seen in many Bellman-Ford/Dijkstra implementations (for instance Graph.shortest_path_all_pairs or networkx.algorithms.shortest_paths.all_pairs_shortest_path), and not just a number of those paths.
I am also satisfied with only a list of "optimal" predecessors... as long as the list is complete.
Thank you for answers!Tue, 09 Jul 2013 00:45:53 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/Answer by Morgoth for <p>I am working with graphs in sage and need a method of finding all shortest paths between some pair (or all pairs) of vertices. </p>
<p>Note that it is important to have all shortest paths registred, not just one, as seen in many Bellman-Ford/Dijkstra implementations (for instance Graph.shortest_path_all_pairs or networkx.algorithms.shortest_paths.all_pairs_shortest_path), and not just a number of those paths. </p>
<p>I am also satisfied with only a list of "optimal" predecessors... as long as the list is complete.</p>
<p>Thank you for answers!</p>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?answer=15236#post-id-15236The method, suggested by Nathann is the following:
for v in G.vertices():
for u in G.vertices():
predec_list[u][v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
Given such list (p_l), it is easy to recursively construct a list of shortest paths from vertex a to vertex b, as follows:
def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
-------------------------------------
rickhg12hs: here is my code snippet. This works for me :) Make sure to have networkx imported.
def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= {}
for v in G.vertices():
for u in G.vertices():
predec_list[u,v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
return predec_list
def shortest_path_d(G):
a_p= { "init":0}
p_l = list_of_predecessors(G)
for u in G.vertices():
for v in G.vertices():
a_p[(u,v)]=s_p_d(p_l,u,v)
del a_p["init"]
return a_p
def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return rMon, 15 Jul 2013 03:07:51 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?answer=15236#post-id-15236Comment by Morgoth for <p>The method, suggested by Nathann is the following:</p>
<pre><code> for v in G.vertices():
for u in G.vertices():
predec_list[u][v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
</code></pre>
<p>Given such list (p_l), it is easy to recursively construct a list of shortest paths from vertex a to vertex b, as follows:</p>
<pre><code>def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
<hr/>
<p>rickhg12hs: here is my code snippet. This works for me :) Make sure to have networkx imported. </p>
<pre><code>def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= {}
for v in G.vertices():
for u in G.vertices():
predec_list[u,v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
return predec_list
def shortest_path_d(G):
a_p= { "init":0}
p_l = list_of_predecessors(G)
for u in G.vertices():
for v in G.vertices():
a_p[(u,v)]=s_p_d(p_l,u,v)
del a_p["init"]
return a_p
def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17239#post-id-17239Hello! The all_dist dictionary comes from "distance_all_pairs" method, mentioned by Nathann. If you add something like "all_dist = G.distance_all_pairs()" in the beginning, it should work. If you wish, I can publish full code here, but I would rather not, since I am not really sage master myself :)Fri, 26 Jul 2013 00:50:30 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17239#post-id-17239Comment by rickhg12hs for <p>The method, suggested by Nathann is the following:</p>
<pre><code> for v in G.vertices():
for u in G.vertices():
predec_list[u][v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
</code></pre>
<p>Given such list (p_l), it is easy to recursively construct a list of shortest paths from vertex a to vertex b, as follows:</p>
<pre><code>def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
<hr/>
<p>rickhg12hs: here is my code snippet. This works for me :) Make sure to have networkx imported. </p>
<pre><code>def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= {}
for v in G.vertices():
for u in G.vertices():
predec_list[u,v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
return predec_list
def shortest_path_d(G):
a_p= { "init":0}
p_l = list_of_predecessors(G)
for u in G.vertices():
for v in G.vertices():
a_p[(u,v)]=s_p_d(p_l,u,v)
del a_p["init"]
return a_p
def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17277#post-id-17277Sorry, I'm a graph theory noob. Where does all_dist come from? [The above snippet crashes.]Mon, 15 Jul 2013 17:27:43 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17277#post-id-17277Comment by rickhg12hs for <p>The method, suggested by Nathann is the following:</p>
<pre><code> for v in G.vertices():
for u in G.vertices():
predec_list[u][v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
</code></pre>
<p>Given such list (p_l), it is easy to recursively construct a list of shortest paths from vertex a to vertex b, as follows:</p>
<pre><code>def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
<hr/>
<p>rickhg12hs: here is my code snippet. This works for me :) Make sure to have networkx imported. </p>
<pre><code>def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= {}
for v in G.vertices():
for u in G.vertices():
predec_list[u,v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
return predec_list
def shortest_path_d(G):
a_p= { "init":0}
p_l = list_of_predecessors(G)
for u in G.vertices():
for v in G.vertices():
a_p[(u,v)]=s_p_d(p_l,u,v)
del a_p["init"]
return a_p
def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17238#post-id-17238Defining all_dist as above isn't quite enough to make the code work (still crashes). Wish @Nathann would post a complete minimum working example (MWE). Perhaps @tmonteil would be kind enough to provide a MWE for the method of @Nathann.Fri, 26 Jul 2013 09:22:56 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17238#post-id-17238Comment by Morgoth for <p>The method, suggested by Nathann is the following:</p>
<pre><code> for v in G.vertices():
for u in G.vertices():
predec_list[u][v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
</code></pre>
<p>Given such list (p_l), it is easy to recursively construct a list of shortest paths from vertex a to vertex b, as follows:</p>
<pre><code>def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
<hr/>
<p>rickhg12hs: here is my code snippet. This works for me :) Make sure to have networkx imported. </p>
<pre><code>def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= {}
for v in G.vertices():
for u in G.vertices():
predec_list[u,v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
return predec_list
def shortest_path_d(G):
a_p= { "init":0}
p_l = list_of_predecessors(G)
for u in G.vertices():
for v in G.vertices():
a_p[(u,v)]=s_p_d(p_l,u,v)
del a_p["init"]
return a_p
def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17161#post-id-17161there you go :)Wed, 14 Aug 2013 10:33:03 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17161#post-id-17161Comment by rickhg12hs for <p>The method, suggested by Nathann is the following:</p>
<pre><code> for v in G.vertices():
for u in G.vertices():
predec_list[u][v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
</code></pre>
<p>Given such list (p_l), it is easy to recursively construct a list of shortest paths from vertex a to vertex b, as follows:</p>
<pre><code>def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
<hr/>
<p>rickhg12hs: here is my code snippet. This works for me :) Make sure to have networkx imported. </p>
<pre><code>def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= {}
for v in G.vertices():
for u in G.vertices():
predec_list[u,v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]
return predec_list
def shortest_path_d(G):
a_p= { "init":0}
p_l = list_of_predecessors(G)
for u in G.vertices():
for v in G.vertices():
a_p[(u,v)]=s_p_d(p_l,u,v)
del a_p["init"]
return a_p
def s_p_d(p_l,a,b):
r=[]
if p_l[a,b]==[a]:
r.append([a,b])
else:
for i in p_l[a,b]:
for j in s_p_d(p_l,a,i):
j.append(b)
r.append(j)
return r
</code></pre>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17134#post-id-17134Took me a while to see that this produces the shortest path for all pairs. Nice!Wed, 21 Aug 2013 13:07:08 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17134#post-id-17134Answer by Nathann for <p>I am working with graphs in sage and need a method of finding all shortest paths between some pair (or all pairs) of vertices. </p>
<p>Note that it is important to have all shortest paths registred, not just one, as seen in many Bellman-Ford/Dijkstra implementations (for instance Graph.shortest_path_all_pairs or networkx.algorithms.shortest_paths.all_pairs_shortest_path), and not just a number of those paths. </p>
<p>I am also satisfied with only a list of "optimal" predecessors... as long as the list is complete.</p>
<p>Thank you for answers!</p>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?answer=15211#post-id-15211You can easily find the list of all predecessors : just call the "distance_all_pairs" method, and you can then get all predecessors of x in a shortest `u-v` path as the list of all neighbors `p` of `x` such that `d(u,p)+1+d(x,v)=d(u,v)`.
NathannTue, 09 Jul 2013 02:28:14 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?answer=15211#post-id-15211Comment by Morgoth for <p>You can easily find the list of all predecessors : just call the "distance_all_pairs" method, and you can then get all predecessors of x in a shortest <code>u-v</code> path as the list of all neighbors <code>p</code> of <code>x</code> such that <code>d(u,p)+1+d(x,v)=d(u,v)</code>.</p>
<p>Nathann</p>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17283#post-id-17283I do not know how to paste the code here, therefore I wrote an answer below.Mon, 15 Jul 2013 02:57:05 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17283#post-id-17283Comment by rickhg12hs for <p>You can easily find the list of all predecessors : just call the "distance_all_pairs" method, and you can then get all predecessors of x in a shortest <code>u-v</code> path as the list of all neighbors <code>p</code> of <code>x</code> such that <code>d(u,p)+1+d(x,v)=d(u,v)</code>.</p>
<p>Nathann</p>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17294#post-id-17294Would you show a minimum working example so that the answer implementation is clear(er)?Thu, 11 Jul 2013 19:31:15 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17294#post-id-17294Comment by Morgoth for <p>You can easily find the list of all predecessors : just call the "distance_all_pairs" method, and you can then get all predecessors of x in a shortest <code>u-v</code> path as the list of all neighbors <code>p</code> of <code>x</code> such that <code>d(u,p)+1+d(x,v)=d(u,v)</code>.</p>
<p>Nathann</p>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17318#post-id-17318That is a good approach. Little more work on my side, but it gets the job done.Tue, 09 Jul 2013 04:19:48 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17318#post-id-17318Answer by tmonteil for <p>I am working with graphs in sage and need a method of finding all shortest paths between some pair (or all pairs) of vertices. </p>
<p>Note that it is important to have all shortest paths registred, not just one, as seen in many Bellman-Ford/Dijkstra implementations (for instance Graph.shortest_path_all_pairs or networkx.algorithms.shortest_paths.all_pairs_shortest_path), and not just a number of those paths. </p>
<p>I am also satisfied with only a list of "optimal" predecessors... as long as the list is complete.</p>
<p>Thank you for answers!</p>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?answer=15210#post-id-15210There seem not to be an existing method in Sage for doing that out of the box, so you should write your own algorithm. If you are lazy, you can still use the following slow brute force method, depending on the size of your graph:
sage: G = graphs.GrotzschGraph()
sage: allp = G.all_paths(1,4)
sage: m = min(len(p) for p in allp) ; m
3
sage: [p for p in allp if len(p) == m]
[[1, 0, 4], [1, 10, 4]]
Tue, 09 Jul 2013 01:47:50 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?answer=15210#post-id-15210Comment by Morgoth for <p>There seem not to be an existing method in Sage for doing that out of the box, so you should write your own algorithm. If you are lazy, you can still use the following slow brute force method, depending on the size of your graph:</p>
<pre><code>sage: G = graphs.GrotzschGraph()
sage: allp = G.all_paths(1,4)
sage: m = min(len(p) for p in allp) ; m
3
sage: [p for p in allp if len(p) == m]
[[1, 0, 4], [1, 10, 4]]
</code></pre>
http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17317#post-id-17317Thank you, but this is too much brute force for me. Anyway, it is good to know all_paths function.Tue, 09 Jul 2013 04:20:39 -0500http://ask.sagemath.org/question/10332/finding-all-shortest-paths-between-given-specific-pair-of-vertices/?comment=17317#post-id-17317