network_flow_test_cases.sagews

# HAAI test case:
# First step is to construct a graph of the channel network.
# The labels show capacities of each edge.
H = DiGraph([(1,2,'(35)'), 
             (2,3,'(20)'), (2,4,'(20)'), 
             (3,5,'(10)'), (4,6,'(20)'), (5,7,'(20)'), 
             (6,7,'(12.5)'), (6,8,'(12.5)'), (7,9,'(25)'), (8,10,'(15)'),
             (9,11,'(100)'), (10,11,'(100)')])
H.show(edge_labels='True', layout='acyclic')
# NOTE: In acyclic layout, all edges point upward. 
# Without that option I seem to get random/weird orientations.

# Next, create linear program object p, and flow function f:

p = MixedIntegerLinearProgram()
f = p.new_variable(real=True, nonnegative=True)

# Define source and sink nodes:
s, t = 1, 11

# Define objective function & constraints:
p.set_objective(sum(f[(s,u)] for u in H.neighbors_out(s)) )

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.add_constraint(f[(1,2)] <= 35)
p.add_constraint(f[(2,3)] <= 20)
p.add_constraint(f[(2,4)] <= 20)
p.add_constraint(f[(3,5)] <= 10)
p.add_constraint(f[(4,6)] <= 20)
p.add_constraint(f[(5,7)] <= 20)
p.add_constraint(f[(6,7)] <= 12.5)
p.add_constraint(f[(6,8)] <= 12.5)
p.add_constraint(f[(7,9)] <= 25)
p.add_constraint(f[(8,10)] <= 15)
p.add_constraint(f[(9,11)] <= 100)
p.add_constraint(f[(10,11)] <= 100)

# solve and print output:
a = p.solve()
print "maximum flow =", a
p.get_values(f)

maximum flow = 30.0 {(1, 2): 30.0, (6, 7): 12.5, (4, 6): 20.0, (5, 7): 10.0, (8, 10): 7.5, (3, 5): 10.0, (9, 11): 22.5, (2, 3): 10.0, (10, 11): 7.5, (7, 9): 22.5, (2, 4): 20.0, (6, 8): 7.5}

# Example 2: Another maximum flow in network problem, with non-numerical node labels.

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}