# The interval I(u,v) between a pair of vertices u,v 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,

Hakeem

edit retag close merge delete

Sort by » oldest newest most voted Not 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}

more

This 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 intervals

more

Thank 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.

seems like just removing the u!=w and v!=w conditions would fix that

Thank you very much. That is exactly what I wanted.

more