H = DiGraph([('X','A','(3)'), ('X','B','(1)'), ('A','C','(3)'),
('B','C','(5)'), ('B','D','(4)'), ('C','Y','(2)'),
('D','E','(2)'), ('E','Y','(3)')])
H.show()
p = MixedIntegerLinearProgram()
f = p.new_variable(real=True, nonnegative=True)
s, t = 'X', 'Y'
for v in H:
if v != s and v != t:
p.add_constraint(
sum(f[(v,u)] for u in H.neighbors_out(v))
- sum(f[(u,v)] for u in H.neighbors_in(v)) == 0 )
p.set_objective(sum(f[(s,u)] for u in H.neighbors_out(s)) )
p.add_constraint(f[('X','A')] <= 3)
p.add_constraint(f[('X','B')] <= 1)
p.add_constraint(f[('A','C')] <= 3)
p.add_constraint(f[('B','C')] <= 5)
p.add_constraint(f[('B','D')] <= 4)
p.add_constraint(f[('C','Y')] <= 2)
p.add_constraint(f[('D','E')] <= 2)
p.add_constraint(f[('E','Y')] <= 3)
a = p.solve()
print "maximum flow =", a
p.get_values(f)
maximum flow = 3.0
{('B', 'C'): 0.0, ('D', 'E'): 1.0, ('X', 'A'): 2.0, ('E', 'Y'): 1.0, ('C', 'Y'): 2.0, ('X', 'B'): 1.0, ('A', 'C'): 2.0, ('B', 'D'): 1.0}