DM559/DM545 – Linear and Integer Programming

Max Flow in Networkx

We import the networkx module and check the version. What is described in this document works with version 1.9.1 and above.

In [1]:

import networkx as nx

print "Networkx versions is",nx.__version__

Networkx versions is 1.9.1

Network definition

In [2]:

G = nx.DiGraph()
G.add_edge('s','a', capacity=3.0)
G.add_edge('s','b', capacity=1.0)
G.add_edge('a','c', capacity=3.0)
G.add_edge('b','c', capacity=5.0)
G.add_edge('b','d', capacity=4.0)
G.add_edge('d','e', capacity=2.0)
G.add_edge('c','t', capacity=2.0)
G.add_edge('e','t', capacity=3.0)

Network drawing

In [3]:

%matplotlib inline
pos=nx.spectral_layout(G)
nx.draw(G, pos=pos, with_labels=True)
nx.draw_networkx_edge_labels(G,pos,edge_labels={e:G.edge[e[0]][e[1]]["capacity"] for e in G.edges()})

Out[3]:

{('a', 'c'): <matplotlib.text.Text at 0x10f9d4fd0>,
 ('b', 'c'): <matplotlib.text.Text at 0x10f9cf2d0>,
 ('b', 'd'): <matplotlib.text.Text at 0x10f9d65d0>,
 ('c', 't'): <matplotlib.text.Text at 0x10f9cfe50>,
 ('d', 'e'): <matplotlib.text.Text at 0x10f9d4450>,
 ('e', 't'): <matplotlib.text.Text at 0x10f9d4a10>,
 ('s', 'a'): <matplotlib.text.Text at 0x10f9c52d0>,
 ('s', 'b'): <matplotlib.text.Text at 0x10f9cf890>}

Max flow

In [4]:

flow_value, flow_dict = nx.maximum_flow(G, 's', 't')

print flow_value
print flow_dict

3.0
{'a': {'c': 2.0}, 'c': {'t': 2.0}, 'b': {'c': 0, 'd': 1.0}, 'e': {'t': 1.0}, 'd': {'e': 1.0}, 's': {'a': 2.0, 'b': 1.0}, 't': {}}