pythongraphnetworkxconservation-laws

NetworkX: structuring a simple flow study on a graph

If you consider the following graph:

from __future__ import division
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from numpy.linalg import inv

G = nx.Graph()

pos={1:(2,3),2:(0,0),3:(6,0)}
G.add_nodes_from(pos.keys())
nx.set_node_attributes(G, 'coord', pos)

PE={1:0,2:60,3:40}
nx.set_node_attributes(G,'PE',PE)
q={1:100,2:0,3:0}
nx.set_node_attributes(G,'q',q)

G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,3)

import math
lengths={}
inv_lengths={}
for edge in G.edges():
    startnode=edge[0]
    endnode=edge[1]
    lengths[edge]=round(math.sqrt(((pos[endnode][1]-pos[startnode][1])**2)+
                                      ((pos[endnode][0]-pos[startnode][0])**2)),2)
    inv_lengths[edge]=round(1/lengths[edge],3)
nx.set_edge_attributes(G, 'length', lengths)
nx.set_edge_attributes(G, 'inv_length', inv_lengths) 
nx.draw(G,pos,node_size=1000,node_color='r',with_labels=True)
nx.draw_networkx_edge_labels(G,pos)
plt.show()

enter image description here

And the following flow problem:

enter image description here

where 1 is a supply-only node and 2 and 3 are demand-only, how come that the following solution yields weird values of flow through each edge? It seems like q1=100 is not even considered, and I expect L2 to have flow=0.

m=nx.laplacian_matrix(G,weight='inv_length')
a=m.todense()

flow={}
res2=np.dot(a,b) #No inverse is required: x=ab
res2=[round(item,3) for sublist in res2.tolist() for item in sublist]
print res2
for i,e in enumerate(G.edges()):
   flow[e]=res2[i]

b=[]
for i,v in enumerate(PE.values()):
    b.append(v)
res2=np.dot(a,b) #No inverse is required: x=ab
res2=[round(item,3) for sublist in res2.tolist() for item in sublist]
print res2

#res2=[-24.62, 19.96, 4.66]

enter image description here

Solution

  • I have taken the liberty to compute edge lengths in a simpler way:

    from scipy.spatial.distance import euclidean
lengths = {}
inv_lengths = {}
for edge in G.edges():
    startnode = edge[0]
    endnode = edge[1]
    d = euclidean(pos[startnode], pos[endnode])
    lengths[edge] = d
    inv_lengths[edge] = 1/d

    And this is how I implemented the matrix equation   matrix equation:

    E = np.array([[0], 
              [60], 
              [40]], dtype=np.float64)

L1 = lengths[(1, 2)]
L2 = lengths[(2, 3)]
L3 = lengths[(1, 3)]

L = np.array([[1/L1 + 1/L3,       -1/L1,       -1/L3],
              [      -1/L1, 1/L1 + 1/L2,       -1/L2],
              [      -1/L3,       -1/L2, 1/L2 + 1/L3]], dtype=np.float64)

qLE = np.dot(L, E)

    The code above yields the same result (approximately) than yours:

    In [55]: np.set_printoptions(precision=2)

In [56]: qLE
Out[56]: 
array([[-24.64],
       [ 19.97],
       [  4.67]])

    In summary, I think this is not a programming issue. Perhaps you should revise the flow model...