{"id":1056,"date":"2013-08-19T17:26:53","date_gmt":"2013-08-20T00:26:53","guid":{"rendered":"http:\/\/zackmdavis.net\/blog\/?p=1056"},"modified":"2013-08-30T11:39:30","modified_gmt":"2013-08-30T18:39:30","slug":"ford-fulkerson","status":"publish","type":"post","link":"http:\/\/zackmdavis.net\/blog\/2013\/08\/ford-fulkerson\/","title":{"rendered":"Ford-Fulkerson"},"content":{"rendered":"

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<\/em>, another is called the sink<\/em>, and the weight of the edge (i<\/em>, j<\/em>) represents the maximum capacity of the pipe which transports fluid from the location i<\/em> to location j<\/em>. The maximum-flow problem is precisely the question of how to transport the maximum possible amount of fluid from<\/em> the source to<\/em> 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<\/em> to each edge, not to exceed that edge's capacity, such that inflow equals outflow for all the intermediate (i.e.<\/em>, non-source, non-sink) nodes, and such that the total flow reaching the sink is maximized.<\/p>\n

<\/p>\n

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<\/code> 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:<\/p>\n

class Edge\r\n  attr_accessor :tail\r\n  attr_accessor :head\r\n  attr_accessor :capacity\r\n\r\n  def initialize(t, h, c)\r\n    @tail = t\r\n    @head = h\r\n    @capacity = c\r\n  end\r\nend<\/code><\/pre>\n
And let's also make a FlowNetwork<\/code> class, defined by the names of its source and sink nodes, and a hash which maps Edge<\/code>s to the amount of flow currently assigned to that Edge<\/code>:<\/p>\n
class FlowNetwork\r\n  attr_accessor :source\r\n  attr_accessor :sink\r\n  attr_accessor :network\r\n  \r\n  def initialize(source, sink, edges)\r\n    @source = source\r\n    @sink = sink\r\n    @network = {}\r\n    edges.each do |e|\r\n      @network[e] = 0\r\n    end\r\n  end<\/code><\/pre>\n
(Note that I haven't yet closed the FlowNetwork<\/code> class definition yet, because we still want to define more methods implementing the Ford-Fulkerson algorithm!)<\/p>\n
So how do<\/em> 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<\/code>.) We then find an augmenting path<\/em> 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<\/em> 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<\/em> 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:<\/p>\n
  def ford_fulkerson\r\n    path = augmenting_path\r\n    while path\r\n      flow_augmentation(path)\r\n      path = augmenting_path\r\n    end\r\n  end<\/code><\/pre>\n
Of course, we need to specify exactly how to find<\/em> 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:<\/p>\n
  def augmenting_path\r\n    labeled = {@source=>nil} # keys are labeled nodes; values, parents thereof\r\n    scanned = {}\r\n    now_scanning = @source\r\n    while not labeled.empty?\r\n      if labeled.include?(@sink) # i.e., we've found an augmenting path\r\n        backtrace = [@sink]\r\n        parent = labeled[@sink]\r\n        while parent != nil # reconstruct the path found\r\n          backtrace.push(parent)\r\n          parent = scanned[parent]\r\n        end\r\n        return backtrace.reverse!\r\n      end\r\n      edges = @network.select do |e, v|\r\n        e.tail == now_scanning or e.head == now_scanning\r\n      end\r\n      edges.each do |e, v|\r\n        if e.tail == now_scanning\r\n          if @network[e] < e.capacity\r\n            if not labeled.merge(scanned).include?(e.head)\r\n              labeled[e.head] = now_scanning\r\n            end\r\n          end\r\n        elsif e.head == now_scanning\r\n          if @network[e] > 0\r\n            if not labeled.merge(scanned).include?(e.tail)\r\n              labeled[e.tail] = now_scanning\r\n            end\r\n          end\r\n        end\r\n      end\r\n      scanned[now_scanning] = labeled[now_scanning]\r\n      labeled.delete(now_scanning)\r\n      now_scanning = labeled.keys[0]\r\n    end\r\n    return nil # no path found\r\n  end<\/code><\/pre>\n
And of course, we also need code to actually augment the flow along the path found\u2014<\/p>\n
  def flow_augmentation(path)\r\n    flow = +1.0\/0 # positive infinity\r\n    edges = []\r\n    def query_edge(tail, head) # select edge given node names\r\n      @network.select{|e, v| e.tail == tail and e.head == head}\r\n    end\r\n    path[0..path.length-2].each_index do |i|\r\n      forward = query_edge(path[i], path[i+1])\r\n      backward = query_edge(path[i+1], path[i])\r\n      if backward.empty?\r\n        edge_flow = forward\r\n        edges.push(edge_flow.keys[0])\r\n        available = edge_flow.keys[0].capacity - edge_flow.values[0]\r\n        if flow > available\r\n          flow = available\r\n        end\r\n      elsif forward.empty?\r\n        edge_flow = backward\r\n        edges.push(edge_flow.keys[0])\r\n        available = edge_flow.values[0]\r\n        if flow > available\r\n          flow = available\r\n        end\r\n      end\r\n    end\r\n    edges.each do |e|\r\n      network[e] += flow\r\n    end\r\n  end<\/code><\/pre>\n
Then throw in a reporting method so we have some way of actually inspecting our network and its completed flow assignment, close the FlowNetwork<\/code> class definition (at long last) ...<\/p>\n
  def report\r\n    print \"Source: \", @source, \"\\n\"\r\n    print \"Sink: \", @sink, \"\\n\"\r\n    @network.each_pair do |e, v|\r\n      print e.tail, ' -> ', e.head, '; capacity: ', e.capacity, ', flow: ', v, \"\\n\"\r\n    end\r\n    puts\r\n  end\r\n\r\nend<\/code><\/pre>\n
\u2014and dear reader, the maximum-flow problem is solved<\/em>! For suppose we are faced with the network depicted in the following diagram:<\/p>\n
\"our<\/a><\/p>\n
We can then (admittedly with some typing) call for a solution like so:<\/p>\n
my_edges = [Edge.new('A', 'B', 12), Edge.new('A', 'E', 15),\r\n  Edge.new('A', 'G', 13), Edge.new('B', 'C', 9), Edge.new('E', 'C', 11),\r\n  Edge.new('G', 'E', 7), Edge.new('C', 'D', 18), Edge.new('C', 'F', 10),\r\n  Edge.new('H', 'E', 8), Edge.new('G', 'H', 12), Edge.new('F', 'D', 6),\r\n  Edge.new('H', 'F', 6), Edge.new('D', 'I', 12), Edge.new('F', 'I', 20),\r\n  Edge.new('H', 'I', 10)]\r\nmy_network = FlowNetwork.new('A', 'I', my_edges)\r\nmy_network.ford_fulkerson\r\nmy_network.report<\/code><\/pre>\n
And receive it like so:<\/p>\n
Source: A\r\nSink: I\r\nA -> B; capacity: 12, flow: 9\r\nA -> E; capacity: 15, flow: 11\r\nA -> G; capacity: 13, flow: 12\r\nB -> C; capacity: 9, flow: 9\r\nE -> C; capacity: 11, flow: 11\r\nG -> E; capacity: 7, flow: 0\r\nC -> D; capacity: 18, flow: 12\r\nC -> F; capacity: 10, flow: 8\r\nH -> E; capacity: 8, flow: 0\r\nG -> H; capacity: 12, flow: 12\r\nF -> D; capacity: 6, flow: 0\r\nH -> F; capacity: 6, flow: 2\r\nD -> I; capacity: 12, flow: 12\r\nF -> I; capacity: 20, flow: 10\r\nH -> I; capacity: 10, flow: 10<\/code><\/pre>\n
Bibliography<\/em><\/strong><\/p>\n
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization<\/em>, \u00a77.5<\/p>\n
Anany Levitin, Introduction to the Design and Analysis of Algorithms<\/em>, \u00a710.2<\/p>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[20],"tags":[42,64],"_links":{"self":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1056"}],"collection":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/comments?post=1056"}],"version-history":[{"count":7,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1056\/revisions"}],"predecessor-version":[{"id":1096,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1056\/revisions\/1096"}],"wp:attachment":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/media?parent=1056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/categories?post=1056"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/tags?post=1056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}