Python: Issues with Networkx Dijkstra algo

Question

My objective is to do the exact same thing as posted here.

I have a matrix (DataFrame or df) that looks like this:

community A   B   C   D
A         0   3   4   1
B         3   0   2   0
C         4   2   0   1
D         1   0   1   0 

This is a symmetric df and each weight represents the weight or intensity of the connections between each communities. As explained in the link, I want to produce a matrix that shows the shortest distances among all nodes (or communities). I first invert the above matrix and set the G graph network:

G = nx.Graph()
commu = list(df.index)
for i in range(0,len(commu)):
    for j in range(0,len(commu)):
            if i == j:
                pass
            else:
                G.add_edge(str(i),str(j),weight=df.ix[df.index[i], df.columns[j]])

This gives me the following network graph: The different colors of the edges is for different weights. (I changed the letters for numbers in my graph)

Ok, so far so good. Now, I want the shortest distance among all nodes. I was thinking to use this nx.dijkstra_shortest_path_length(G,source,target) and loop over all nodes for source and target and produce a matrix like in the above link with all values of the shortest path across all nodes in each cell of the matrix but for some reason nx.dijkstra_shortest_path_length(G,source,target) does not work for me. If I do nx.dijkstra_shortest_path_length(G,A,B) or any combination of nodes, I always get a value of 0. Why? Is there an efficient way of reproducing a matrix like in the link using Networkx and the nx.dijkstra algo?

Answer 1

You can just use networkx.shortest_path(G) with the weight='weight' keyword. e.g.

In [1]: import networkx as nx

In [2]: G = nx.Graph()

In [3]: G.add_edge(1,2,weight=7)

In [4]: G.add_edge(1,4,weight=3)

In [5]: G.add_edge(2,3,weight=1)

In [6]: G.add_edge(3,4,weight=100)

In [7]: nx.adjacency_matrix(G).todense()
Out[7]: 
matrix([[  0,   7,   0,   3],
        [  7,   0,   1,   0],
        [  0,   1,   0, 100],
        [  3,   0, 100,   0]])

In [8]: nx.shortest_path_length(G)
Out[8]: 
{1: {1: 0, 2: 1, 3: 2, 4: 1},
 2: {1: 1, 2: 0, 3: 1, 4: 2},
 3: {1: 2, 2: 1, 3: 0, 4: 1},
 4: {1: 1, 2: 2, 3: 1, 4: 0}}

In [9]: nx.shortest_path_length(G,weight='weight')
Out[9]: 
{1: {1: 0, 2: 7, 3: 8, 4: 3},
 2: {1: 7, 2: 0, 3: 1, 4: 10},
 3: {1: 8, 2: 1, 3: 0, 4: 11},
 4: {1: 3, 2: 10, 3: 11, 4: 0}}

In [10]: nx.utils.dict_to_numpy_array(nx.shortest_path_length(G,weight='weight'))
Out[10]: 
array([[  0.,   7.,   8.,   3.],
       [  7.,   0.,   1.,  10.],
       [  8.,   1.,   0.,  11.],
       [  3.,  10.,  11.,   0.]])

Answer 2

(Not an answer, just a long comment). If

In [65]: df.values
Out[65]: 
array([[0, 3, 4, 1],
       [3, 0, 2, 0],
       [4, 2, 0, 1],
       [1, 0, 1, 0]], dtype=int64)

then instead of

G = nx.Graph()
commu = list(df.index)
for i in range(0,len(commu)):
    for j in range(0,len(commu)):
            if i == j:
                pass
            else:
                G.add_edge(str(i),str(j),weight=df.ix[df.index[i], df.columns[j]])

you can construct G with

In [66]: G = nx.from_numpy_matrix(df.values)

In [67]: G.edges(data=True)
Out[67]: 
[(0, 1, {'weight': 3}),
 (0, 2, {'weight': 4}),
 (0, 3, {'weight': 1}),
 (1, 2, {'weight': 2}),
 (2, 3, {'weight': 1})]

and if you want to label the nodes ABCD instead of 0123:

In [68]: G = nx.relabel_nodes(G, dict(zip(range(4), 'ABCD')))

In [69]: G.edges(data=True)
Out[69]: 
[('A', 'C', {'weight': 4}),
 ('A', 'B', {'weight': 3}),
 ('A', 'D', {'weight': 1}),
 ('C', 'B', {'weight': 2}),
 ('C', 'D', {'weight': 1})]