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

Hakeem
13 ●1 ●5

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

add a comment

3 Answers

Sort by » oldest newest most voted

answered 8 years ago

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}

link

add a comment

answered 8 years ago

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

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 ( 8 years ago )

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

wonder ( 7 years ago )

add a comment

answered 8 years ago

Hakeem
13 ●1 ●5

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

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 savecancel

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

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