Dear reader, have you ever dreamed of solving instances of the maximum flow problem? Sure you have! Suppose we have a weighted directed graph, which we might imagine as a network of pipes (represented by the edges) between locations (represented by the nodes), pipes through which some sort of fluid might thereby be transported across the network. One node is designated the source, another is called the sink, and the weight of the edge (i, j) represents the maximum capacity of the pipe which transports fluid from the location i to location j. The maximum-flow problem is precisely the question of how to transport the maximum possible amount of fluid from the source to the sink (without any fluid leaking or magically appearing at any of the intermediate nodes). That is, we want to assign an amount of fluid flow to each edge, not to exceed that edge's capacity, such that inflow equals outflow for all the intermediate (i.e., non-source, non-sink) nodes, and such that the total flow reaching the sink is maximized.
It turns out that there's a conceptually straightforward algorithm for solving the maximum flow problem, known as the Ford-Fulkerson method, which we'll implement in Ruby. But first, we'll want to pin down exactly how the flow network will be represented. Let's define an Edge class, each instance of which will be initialized with the names of the nodes at its head and tail, and the edge's maximum capacity:
class Edge
attr_accessor :tail
attr_accessor :head
attr_accessor :capacity
def initialize(t, h, c)
@tail = t
@head = h
@capacity = c
end
end
And let's also make a FlowNetwork class, defined by the names of its source and sink nodes, and a hash which maps Edges to the amount of flow currently assigned to that Edge:
class FlowNetwork
attr_accessor :source
attr_accessor :sink
attr_accessor :network
def initialize(source, sink, edges)
@source = source
@sink = sink
@network = {}
edges.each do |e|
@network[e] = 0
end
end
(Note that I haven't yet closed the FlowNetwork class definition yet, because we still want to define more methods implementing the Ford-Fulkerson algorithm!)
So how do we solve the maximum-flow problem? It's pretty simple! We start with the "zero flow." (In our code above, this is already done when we initialize an instance of FlowNetwork.) We then find an augmenting path from the source to the sink (possibly including edges traversed backwards) such that all the forward-traversed edges along the path have not been assigned their maximum capacity, and all the backward-traversed edges have a nonzero amount of flow. This is path along which we can push more flow from the source to the sink, by increasing the amount of flow along the forward-traversed edges, and decreasing the amount of flow along the backward-traversed edges. (Convince yourself that pushing flow through an edge backwards amounts to decreasing the amount of flow along that edge.) Once we've found such an augmenting path, we push as much flow as we can along it. Then we look for another augmenting path and do the same, until no more augmenting paths can be found. It turns out that the resulting flow assignment solves our problem. So that's the Ford-Fulkerson method:
def ford_fulkerson
path = augmenting_path
while path
flow_augmentation(path)
path = augmenting_path
end
end
Of course, we need to specify exactly how to find these augmenting paths. This is a little bit more involved. It amounts to doing walking through the graph starting at the source, "labeling" nodes that could be part of an augmenting path, and scanning neighbors of labeled nodes looking for more labelable nodes, until we reach the sink (in which case we have found a path) or until we run out of nodes to scan (in which case there are no augmenting paths left). Sort of like this:
def augmenting_path
labeled = {@source=>nil} # keys are labeled nodes; values, parents thereof
scanned = {}
now_scanning = @source
while not labeled.empty?
if labeled.include?(@sink) # i.e., we've found an augmenting path
backtrace = [@sink]
parent = labeled[@sink]
while parent != nil # reconstruct the path found
backtrace.push(parent)
parent = scanned[parent]
end
return backtrace.reverse!
end
edges = @network.select do |e, v|
e.tail == now_scanning or e.head == now_scanning
end
edges.each do |e, v|
if e.tail == now_scanning
if @network[e] < e.capacity
if not labeled.merge(scanned).include?(e.head)
labeled[e.head] = now_scanning
end
end
elsif e.head == now_scanning
if @network[e] > 0
if not labeled.merge(scanned).include?(e.tail)
labeled[e.tail] = now_scanning
end
end
end
end
scanned[now_scanning] = labeled[now_scanning]
labeled.delete(now_scanning)
now_scanning = labeled.keys[0]
end
return nil # no path found
end
And of course, we also need code to actually augment the flow along the path found—
def flow_augmentation(path)
flow = +1.0/0 # positive infinity
edges = []
def query_edge(tail, head) # select edge given node names
@network.select{|e, v| e.tail == tail and e.head == head}
end
path[0..path.length-2].each_index do |i|
forward = query_edge(path[i], path[i+1])
backward = query_edge(path[i+1], path[i])
if backward.empty?
edge_flow = forward
edges.push(edge_flow.keys[0])
available = edge_flow.keys[0].capacity - edge_flow.values[0]
if flow > available
flow = available
end
elsif forward.empty?
edge_flow = backward
edges.push(edge_flow.keys[0])
available = edge_flow.values[0]
if flow > available
flow = available
end
end
end
edges.each do |e|
network[e] += flow
end
end
Then throw in a reporting method so we have some way of actually inspecting our network and its completed flow assignment, close the FlowNetwork class definition (at long last) ...
def report
print "Source: ", @source, "\n"
print "Sink: ", @sink, "\n"
@network.each_pair do |e, v|
print e.tail, ' -> ', e.head, '; capacity: ', e.capacity, ', flow: ', v, "\n"
end
puts
end
end
—and dear reader, the maximum-flow problem is solved! For suppose we are faced with the network depicted in the following diagram:
We can then (admittedly with some typing) call for a solution like so:
my_edges = [Edge.new('A', 'B', 12), Edge.new('A', 'E', 15),
Edge.new('A', 'G', 13), Edge.new('B', 'C', 9), Edge.new('E', 'C', 11),
Edge.new('G', 'E', 7), Edge.new('C', 'D', 18), Edge.new('C', 'F', 10),
Edge.new('H', 'E', 8), Edge.new('G', 'H', 12), Edge.new('F', 'D', 6),
Edge.new('H', 'F', 6), Edge.new('D', 'I', 12), Edge.new('F', 'I', 20),
Edge.new('H', 'I', 10)]
my_network = FlowNetwork.new('A', 'I', my_edges)
my_network.ford_fulkerson
my_network.report
And receive it like so:
Source: A
Sink: I
A -> B; capacity: 12, flow: 9
A -> E; capacity: 15, flow: 11
A -> G; capacity: 13, flow: 12
B -> C; capacity: 9, flow: 9
E -> C; capacity: 11, flow: 11
G -> E; capacity: 7, flow: 0
C -> D; capacity: 18, flow: 12
C -> F; capacity: 10, flow: 8
H -> E; capacity: 8, flow: 0
G -> H; capacity: 12, flow: 12
F -> D; capacity: 6, flow: 0
H -> F; capacity: 6, flow: 2
D -> I; capacity: 12, flow: 12
F -> I; capacity: 20, flow: 10
H -> I; capacity: 10, flow: 10
Bibliography
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, §7.5
Anany Levitin, Introduction to the Design and Analysis of Algorithms, §10.2
