All shortest paths for a subset

[Mukund Raj]

Hello,

I just had a graph theoretic question about finding all shortest paths between vertices for a subset of vertices in a graph. Floyd Warshall (also implemented in Networkx) gives this result for all the vertices in a graph but is there an efficient algorithm or way to do this for just a subset of vertices if I am only interested in internode distance for say 1000 nearby vertices out of 1000000 vertices in the whole graph?

Thanks,
M

[Moritz Emanuel Beber]

Hi,

You could first create a subgraph and then use that to find the shortest
paths. Or is there a problem with that approach?

Mock up:
small_net = big_net.subgraph(group_of_nodes)
nx.shortest_paths(small_net)

Best,
Moritz

[Mukund Raj]

Thanks for your reply Moritz.

If I do that however, and if any of the nodes in my set(lets call it set A) of 1000 nearby nodes are not connected directly or via nodes in the set A, then the set of edges between those nodes is not selected. What I am trying to do is get an efficient way to get convex set of a subset of vertices in a graph.

Any node would be in the convex set of a set of nodes=Vsubset if it lies on the shortest path between any two nodes in Vsubset. A node outside Vsubset may also be in the convex set of Vsubset.

[Moritz]

Hey again,

On Wednesday, 12 February 2014 23:10:54 UTC+1, Mukund Raj wrote:

Thanks for your reply Moritz.

If I do that however, and if any of the nodes in my set(lets call it set A) of 1000 nearby nodes are not connected directly or via nodes in the set A, then the set of edges between those nodes is not selected. What I am trying to do is get an efficient way to get convex set of a subset of vertices in a graph.

Any node would be in the convex set of a set of nodes=Vsubset if it lies on the shortest path between any two nodes in Vsubset. A node outside Vsubset may also be in the convex set of Vsubset.

There are some shortest paths algorithms like Dijkstra's
http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.shortest_paths.weighted.dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.dijkstra_path
that allow the specification of a source and target nodes. At the moment I'm can't comment on the efficiency but you could call that function for all pairs of nodes in your set A and then build a set of all nodes found along the paths. Is that what you want? There are also other functions that allow you to provide a cut-off (or you can adapt them to do so, search this list for examples), which could help you to limit the neighbourhood of your set  A that you want to investigate.

HTH,
Moritz