Ideal Flow Network Anaysis using Python

Ideal Flow Network is a new concept to analyze transportation and communication networks. In this tutorial, we will use a simple network (visualized using graphiz).

First, you need to download and install graphiz and numpy. The code of IdealFlowNetwork module is available in GitHub.

import graphviz as dg
import numpy as np
import IdealFlowNetwork as ifn

Suppose we have the following strongly connected network

d=dg.Digraph(engine='circo')
d.edge("a","b")
d.edge("a","c")
d.edge("a","d")
d.edge("d","e")
d.edge("e","a")
d.edge("e","d")
d.edge("c","b")
d.edge("b","d")
d.edge("e","c")
d

The capacity matrix is shown as follow. The positive numbers represent the number of lanes in the links. Zero means no links between nodes.

#   a  b  c  d  e 
C=[[0, 1, 1, 1, 0],   # a
   [0, 0, 0, 1, 0],   # b
   [0, 1, 1, 0, 0],   # c
   [0, 0, 0, 0, 2],   # d
   [1, 0, 1, 2, 0]
  ]
C

[[0, 1, 1, 1, 0],
 [0, 0, 0, 1, 0],
 [0, 1, 1, 0, 0],
 [0, 0, 0, 0, 2],
 [1, 0, 1, 2, 0]]

The adjacency matrix of the capacity matrix that is strongly connected is always irreducible matrix. Let us test using the following code.

A=ifn.capacity2adj(C)
ifn.isIrreducible(A)

True

We compute the stochastic matrix as follow

S=ifn.capacity2stochastic(C)
print('stochastic matrix=\n',S)

stochastic matrix=
 [[ 0.          0.33333333  0.33333333  0.33333333  0.        ]
 [ 0.          0.          0.          1.          0.        ]
 [ 0.          0.5         0.5         0.          0.        ]
 [ 0.          0.          0.          0.          1.        ]
 [ 0.25        0.          0.25        0.5         0.        ]]

We can check network efficiency based on the entropy ratio. A network is efficient if it has maximum entropy. Efficient network happens if the outflow probability distribution in each node is uniformly distributed in term of time and space. In this example the network efficiency is 98%.

print('Entropy=', ifn.networkEntropy(S))
print('Entropy ratio=', ifn.entropyRatio(S))

Entropy= 2.83148024007
Entropy ratio= 0.979624933136

Now we can compute flow matrix F that represents the flow in each link.

F=ifn.capacity2idealFlow(C)
print('Ideal Flow matrix=\n', F)

Ideal Flow matrix=
 [[ 0.     0.025  0.025  0.025  0.   ]
 [ 0.     0.     0.     0.125  0.   ]
 [ 0.     0.1    0.1    0.     0.   ]
 [ 0.     0.     0.     0.     0.3  ]
 [ 0.075  0.     0.075  0.15   0.   ]]

Notice that the sum of rows and sum of columns of an ideal flow matrix are always the same.

sR=ifn.sumOfRow(F)
sC=ifn.sumOfCol(F)
print('sum of row=',sR,'\n')
print('sum of columns=',sC,'\n')

sum of row= [[ 0.075]
 [ 0.125]
 [ 0.2  ]
 [ 0.3  ]
 [ 0.3  ]] 

sum of columns= [[ 0.075  0.125  0.2    0.3    0.3  ]]

Premagic matrix means the matrix has exactly the same sum of rows as the sum of columns.

print('isPremagic(F)=',ifn.isPremagic(F),'\n')

isPremagic(F)= True

Ideal flow matrix is defined as premagic (the flow are conserved), strongly connected (irreducible) and non-negative.

print('isIrreducible(F)=', ifn.isIrreducible(F))
print('isNonNegative(F)=', ifn.isNonNegative(F))
print('is Ideal Flow(F)=', ifn.isIdealFlow(F))

isIrreducible(F)= True
isNonNegative(F)= True
is Ideal Flow(F)= True

Example of Efficient Network¶

In the following example, we will examine an efficient network. Let us define an adjacency matrix.

#   a  b  c  d  
A=[[0, 0, 1, 1],   # a
   [1, 0, 0, 0],   # b
   [0, 1, 0, 1],   # c
   [0, 1, 0, 0],   # d
  ]
A=np.asarray(A)
A

array([[0, 0, 1, 1],
       [1, 0, 0, 0],
       [0, 1, 0, 1],
       [0, 1, 0, 0]])

We can draw this network

d1=dg.Digraph(engine='circo')
d1.edge("a","c")
d1.edge("a","d")
d1.edge("b","a")
d1.edge("c","b")
d1.edge("c","d")
d1.edge("d","b")
d1

We can obtain the ideal flow directly from adjacency matrix and the outflow probability distribution of each node would be equal (uniform distribution).

F=ifn.adj2idealFlow(A)
print('F=',F,'\n')

F= [[ 0.          0.          0.15384615  0.15384615]
 [ 0.30769231  0.          0.          0.        ]
 [ 0.          0.07692308  0.          0.07692308]
 [ 0.          0.23076923  0.          0.        ]]

The sum of rows of ideal flow matrix is always equal to the sum of columns. This property is called premagic property.

sR=ifn.sumOfRow(F)
sC=ifn.sumOfCol(F)
print('sum of row=',sR,'\n')
print('sum of columns=',sC,'\n')
print('isPremagic(F)=',ifn.isPremagic(F),'\n')

sum of row= [[ 0.30769231]
 [ 0.30769231]
 [ 0.15384615]
 [ 0.23076923]] 

sum of columns= [[ 0.30769231  0.30769231  0.15384615  0.23076923]] 

isPremagic(F)= True

We can easily scale ideal flow matrix by a scaling factor, kappa, which is the same as the total flow.

kappa=1000
F=ifn.adj2idealFlow(A, kappa)
print('F=',F,'\n')

F= [[   0.            0.          153.84615385  153.84615385]
 [ 307.69230769    0.            0.            0.        ]
 [   0.           76.92307692    0.           76.92307692]
 [   0.          230.76923077    0.            0.        ]]

We can get back the stochastic matrix based on ideal flow matrix.

S=ifn.idealFlow2stochastic(F)
print('S=',S,'\n')

S= [[ 0.   0.   0.5  0.5]
 [ 1.   0.   0.   0. ]
 [ 0.   0.5  0.   0.5]
 [ 0.   1.   0.   0. ]]

Observe that our entropy ratio is 1, that means a network with uniform distribution of outflow is the most efficient network. The proof of this theorem can be found in my paper in EASTS journal.

print('Entropy=', ifn.networkEntropy(S))
print('Entropy ratio=', ifn.entropyRatio(S))

Entropy= 1.38629436112
Entropy ratio= 1.0

last update: Sept 2017

Cite this tutorial as:

Teknomo,K. (2017) Ideal Flow Network Anaysis using Python (http://people.revoledu.com/kardi/tutorial/Python/Ideal+Flow.html)

Visit www.Revoledu.com for more tutorials in Data Science.

Permission is granted to share this notebook as long as the copyright notice is intact.