Ask Your Question
1

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

asked 2016-12-03 15:51:31 -0500

Hakeem gravatar image

updated 2016-12-04 17:23:10 -0500

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

3 answers

Sort by ยป oldest newest most voted
1

answered 2016-12-03 20:50:22 -0500

fidbc gravatar image

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 more
2

answered 2016-12-04 09:52:46 -0500

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 more

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 gravatar imageHakeem ( 2016-12-06 21:05:34 -0500 )edit

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

wonder gravatar imagewonder ( 2017-09-11 14:45:35 -0500 )edit
0

answered 2016-12-03 23:18:41 -0500

Hakeem gravatar image

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

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-12-03 15:44:40 -0500

Seen: 91 times

Last updated: Dec 04 '16