The interval I(u,v) between a pair of vertices u,v in graph

asked 2016-12-03 22:51:31 +0100

Hakeem
13 ●1 ●5

updated 2016-12-05 00:23:10 +0100

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 flag offensive close merge delete

add a comment

3 Answers

Sort by » oldest newest most voted

answered 2016-12-04 03:50:22 +0100

fidbc

2423 ●4 ●26 ●61

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}

edit flag offensive delete link

add a comment

answered 2016-12-04 16:52:46 +0100

David Coudert
766 ●12 ●20 http://www-sop.inria.f...

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

edit flag offensive delete link

Comments

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.

Hakeem ( 2016-12-07 04:05:34 +0100 )edit

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

wonder ( 2017-09-11 21:45:35 +0100 )edit

add a comment

answered 2016-12-04 06:18:41 +0100

Hakeem
13 ●1 ●5

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

edit flag offensive delete link

add a comment

Your Answer

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

Add Answer

The interval I(u,v) between a pair of vertices u,v in graph

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

The interval I(u,v) between a pair of vertices u,v in graph edit

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

The interval I(u,v) between a pair of vertices u,v in graph