ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 11 Sep 2017 14:45:35 -0500The interval I(u,v) between a pair of vertices u,v in graphhttps://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/Hello Everyone,
I am really new to the sagemath and I need your help with finding the interval between **all pair of vertices** in a graph.
Def: In graph G, the Interval between a pair of vertices u and v is: I(u,v)={w|d(u,v)=d(u,w)+d(w,v)}
In other words, the interval between a pair of vertices u and v is : all vertices that lies on all shortest paths between them.
I want to find the interval between all pairs of vertices in graph. I do not know if such function already exists in sagemath or I do need to implement my own.
Thanks,
HakeemSat, 03 Dec 2016 15:44:40 -0600https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/Answer by David Coudert for <p>Hello Everyone,</p>
<p>I am really new to the sagemath and I need your help with finding the interval between <strong>all pair of vertices</strong> in a graph.</p>
<p>Def: In graph G, the Interval between a pair of vertices u and v is: I(u,v)={w|d(u,v)=d(u,w)+d(w,v)}</p>
<p>In other words, the interval between a pair of vertices u and v is : all vertices that lies on all shortest paths between them.</p>
<p>I want to find the interval between all pairs of vertices in graph. I do not know if such function already exists in sagemath or I do need to implement my own.</p>
<p>Thanks,</p>
<p>Hakeem</p>
https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?answer=35914#post-id-35914This will be faster to compute all intervals at once.
def intervals(g):
import itertools
dist = g.distance_all_pairs()
intervals = dict()
for u,v in itertools.combinations(g.vertices(), 2):
intervals[u,v] = list()
for w in g.vertices():
if u!=w and v!=w and dist[u][v]==dist[u][w]+dist[w][v]:
intervals[u,v].append(w)
intervals[v,u] = copy(intervals[u,v])
return intervalsSun, 04 Dec 2016 09:52:46 -0600https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?answer=35914#post-id-35914Comment by wonder for <p>This will be faster to compute all intervals at once.</p>
<pre><code>def intervals(g):
import itertools
dist = g.distance_all_pairs()
intervals = dict()
for u,v in itertools.combinations(g.vertices(), 2):
intervals[u,v] = list()
for w in g.vertices():
if u!=w and v!=w and dist[u][v]==dist[u][w]+dist[w][v]:
intervals[u,v].append(w)
intervals[v,u] = copy(intervals[u,v])
return intervals
</code></pre>
https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?comment=38792#post-id-38792seems like just removing the u!=w and v!=w conditions would fix thatMon, 11 Sep 2017 14:45:35 -0500https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?comment=38792#post-id-38792Comment by Hakeem for <p>This will be faster to compute all intervals at once.</p>
<pre><code>def intervals(g):
import itertools
dist = g.distance_all_pairs()
intervals = dict()
for u,v in itertools.combinations(g.vertices(), 2):
intervals[u,v] = list()
for w in g.vertices():
if u!=w and v!=w and dist[u][v]==dist[u][w]+dist[w][v]:
intervals[u,v].append(w)
intervals[v,u] = copy(intervals[u,v])
return intervals
</code></pre>
https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?comment=35937#post-id-35937Thank you. This is really a very good implementation to what I wanted, in addition to the performance. The only problem with this implementation is that u and v should be in the interval between them. The interval between a pair of vertices u and v is: all vertices (including u and v) that lies on all shortest paths between them.
So before "for loop 2" we can append u and then after we done with "for loop 2" we can append v.Tue, 06 Dec 2016 21:05:34 -0600https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?comment=35937#post-id-35937Answer by fidbc for <p>Hello Everyone,</p>
<p>I am really new to the sagemath and I need your help with finding the interval between <strong>all pair of vertices</strong> in a graph.</p>
<p>Def: In graph G, the Interval between a pair of vertices u and v is: I(u,v)={w|d(u,v)=d(u,w)+d(w,v)}</p>
<p>In other words, the interval between a pair of vertices u and v is : all vertices that lies on all shortest paths between them.</p>
<p>I want to find the interval between all pairs of vertices in graph. I do not know if such function already exists in sagemath or I do need to implement my own.</p>
<p>Thanks,</p>
<p>Hakeem</p>
https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?answer=35906#post-id-35906Not quite sure if it is implemented already. However, it is not hard to implement your own. Here is one possible way of implementing it, however there might still be room to improve on performance.
def interval(g,u,v):
duv = g.shortest_path_length(u,v)
interval = []
for w in g:
if g.shortest_path_length(u,w) + g.shortest_path_length(w,v) == duv:
interval.append(w)
return interval
It shouldn't be hard to extend the implementation to compute the intervals between any pair of vertices. One way to achieve it would be:
intervals = {(u,v):interval(g,u,v) for u in g for v in g}Sat, 03 Dec 2016 20:50:22 -0600https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?answer=35906#post-id-35906Answer by Hakeem for <p>Hello Everyone,</p>
<p>I am really new to the sagemath and I need your help with finding the interval between <strong>all pair of vertices</strong> in a graph.</p>
<p>Def: In graph G, the Interval between a pair of vertices u and v is: I(u,v)={w|d(u,v)=d(u,w)+d(w,v)}</p>
<p>In other words, the interval between a pair of vertices u and v is : all vertices that lies on all shortest paths between them.</p>
<p>I want to find the interval between all pairs of vertices in graph. I do not know if such function already exists in sagemath or I do need to implement my own.</p>
<p>Thanks,</p>
<p>Hakeem</p>
https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?answer=35907#post-id-35907Thank you very much. That is exactly what I wanted.Sat, 03 Dec 2016 23:18:41 -0600https://ask.sagemath.org/question/35905/the-interval-iuv-between-a-pair-of-vertices-uv-in-graph/?answer=35907#post-id-35907