CODEWITHSUNDEEP
pythongraphgraph-algorithmnetworkxshortest-path
FaCoffee
FaCoffee

Reputation: 7929

Python: how to optimize the count of all possible shortest paths?

In a 3x3 network I want to be able to determine all the shortest paths between any two nodes. Then, for each node in the network, I want to compute how many shortest paths pass through one specific node.

This requires using the nx.all_shortest_paths(G,source,target) function, which returns a generator. This is at variance from using the nx.all_pairs_shortest_path(G), as suggested here. The difference is that in the former case the function computes all the shortest paths between any two nodes, while in the latter case it computes only one shortest path between the same pair of nodes.

Given that I need to consider all shortest paths, I have come up with the following script. This is how I generate the network I am working with:

import networkx as nx
N=3
G=nx.grid_2d_graph(N,N)
pos = dict( (n, n) for n in G.nodes() )
labels = dict( ((i, j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds.sort()
vals.sort()
pos2=dict(zip(vals,inds))
nx.draw_networkx(G, pos=pos2, with_labels=False, node_size = 15)

And this is how I print all the shortest paths between any two nodes:

for n in G.nodes():
    for j in G.nodes():
        if (n!=j): #Self-loops are excluded
            gener=nx.all_shortest_paths(G,source=n,target=j)
            print('From node '+str(n)+' to '+str(j))
            for p in gener:
                print(p) 
            print('------')

The result is a path from node x to node y which only includes the nodes along the way. An excerpt of what I get is:

From node 0 to 2 #Only one path exists
[0, 1, 2] #Node 1 is passed through while going from node 0 to node 2
------
From node 0 to 4 #Two paths exist
[0, 1, 4] #Node 1 is passed through while going from node 0 to node 4
[0, 3, 4] #Node 3 is passed through while going from node 0 to node 4
------
...continues until all pairs of nodes are covered...

My question: how could I amend the last code block to make sure that I know how many shortest paths, in total, pass through each node? According to the excerpt outcome I've provided, node 1 is passed through 2 times, while node 3 is passed through 1 time (starting and ending node are excluded). This calculation needs to be carried out to the end to figure out the final number of paths through each node.

Upvotes: 1

Views: 1405

Answers (2)

Kirell
Kirell

Reputation: 9828

What you seek to compute is the unnormalized betweenness centrality.

From Wikipedia:

The betweenness centrality is an indicator of a node's centrality in a network. It is equal to the number of shortest paths from all vertices to all others that pass through that node.

More generally, I suggest you have a look at all the standard measures of centrality already in Networkx.

Upvotes: 1

Gareth McCaughan
Gareth McCaughan

Reputation: 19981

I would suggest making a dict mapping each node to 0

counts = {}
for n in G.nodes(): counts[n] = 0

and then for each path you find -- you're already finding and printing them all -- iterate through the vertices on the path incrementing the appropriate values in your dict:

# ...
for p in gener:
    print(p)
    for v in p: counts[v] += 1

Upvotes: 2

Related Questions