フォードファルカーソン法をRubyで実装

グラフに対する基本的な問題として

  • 最小全域木
  • 最短路問題
  • 最大フロー

の3つがあると思う。で、最小全域木は離散最適の課題としてPrim法を使って解いてみたし、最短路問題はベルマンフォードのアルゴリズムをRubyC++で解いてみた。となったら、最大フローを実装しないわけにはいかないな、ということでフォードファルカーソン法を実装してみました。上の3つの問題では一番ややこしかった気がする。というわけでコードと実行結果。

繰り返しの中で残余ネットワークを更新していって、残余ネットワークにおいて始点から終点へのパスが存在するかを幅優先探索を使って探索していくという流れ。

# -*- coding: utf-8 -*-

require "pp"

class DirectedGraph
  attr_reader :nodes
  attr_reader :weights
  attr_reader :edges
  attr_reader :flow
  def initialize # initialization
    @nodes = []
    @edges = Hash.new{|h,k| h[k] = []}
    @weights = Hash.new{|h,k| h[k] = {}} 
    @flow = Hash.new{|h,k| h[k] = {}} 
  end

  def add_node(v)
    @nodes.push v unless @nodes.include?(v)
  end
  
  def add_edge(u, v)
    add_node(u)
    add_node(v)
    unless @edges[u].index(v)
      @edges[u].push v
    end
  end

  def [](u, v)
    @weights[{u => v}]
  end

  def []=(u, v, w, f = 0) 
    add_node(u)
    add_node(v)
    add_edge(u, v)
    @weights[{u => v}] = w
    @flow[{u => v}] = f
  end

  def residual_network # グラフに対する残余ネットワーク
    g = DirectedGraph.new
    self.nodes.each{|u|
      self.nodes.each{|v|
        if self.edges[u].include?(v) # (u, v) \in Vかどうか
          if self.flow[{u => v}] == 0 
            g[u, v] = self.weights[{u => v}] 
          elsif self.weights[{u => v}] > self.flow[{u => v}]
            g[v, u] = self.flow[{u => v}]
            g[u, v] = self.weights[{u => v}] - self.flow[{u => v}]
          elsif self.weights[{u => v}] > self.flow[{u => v}]
            g[v, u] = self.flow[{u => v}] 
          else
          end        
        end
      }
    }
    return g
  end
  
  def ford_fulkerson(s ,t)
    # 初期化
    f = Hash.new{|h,k| h[k] = {}}
    self.edges.each_pair{|u, nodes| 
      nodes.each{|v|
        f[{u => v}] = 0; f[{v => u}] = 0
      }
    }
    residual_network = self.residual_network
    r = route(residual_network.bfs(s), s, t) # 残余ネットワークにおいて、sからtへの経路を計算
    min_flow =  r.enum_cons(2).map{|edge| # 残余ネットワークにおけるsからtへの経路の中で最小の容量を求める
      u = edge[0]; v = edge[1]
      residual_network[u, v]
    }.min
    while reachable?(r, s, t) # 残余ネットワークにおいて増加道がある限り繰り返す
      r.enum_cons(2).each{|edges|
        u = edges[0]; v = edges[1]
        if self[u, v] <= min_flow + self.flow[{u => v}] # 容量を越えたら、フローを容量にする
          self[u, v, self[u, v]] = self[u, v]
        else # フローがまだ増やせるんだったら、今のフローに足し込む
          self[u, v, self[u, v]] = self.flow[{u => v}] + min_flow
        end
      }
      residual_network = self.residual_network
      r = route(residual_network.bfs(s), s, t) # 残余ネットワークにおいて、sからtへの経路を計算
      min_flow =  r.enum_cons(2).map{|edge| # 残余ネットワークにおけるsからtへの経路の中で最小の容量を求める
        u = edge[0]; v = edge[1]
        residual_network[u, v]
      }.min
    end
    return self
  end

  def bfs(s) # 幅優先探索。頂点をkeyに、そのparentをvalueにしたハッシュであるpiを返す
    pi = {} # 親の情報を格納
    next_sources = [] # 次の始点となる頂点集合
    q = self.nodes.clone - [s] # 探索されていないもの
    edges = self.edges[s]
    edges.each{|v|
      next_sources.push v
      pi[v] = s
      q -= [v]
    }
    while !q.empty? # Queueが空になるまで繰り返す
      tmp = []
      next_sources.each{|s|
        edges = self.edges[s].reject{|x| # すでに探索されたものは除去
          (pi.keys | pi.values).uniq.include?(x)
        } 
        edges.each{|v|
          tmp.push v
          pi[v] = s
          q -= [v]
        }
      }
      next_sources.clear
      next_sources = tmp
      break if next_sources.empty?
    end
    return pi
  end

  def route(pi, s, t) # sからtへの経路を返す。途中で行けなくなる場合は、行けたところまでの経路を返す
    r = [t]
    while !r.include?(pi[t]) && # また来たことがない
        pi[t] !=s && # 残余ネットワークにおいてはsから出ていく場合がある 
        !pi[t].nil? # 親がいない場合
      r.push pi[t]
      t = pi[t] # 親をたどっていかせる
    end
    r.push s if pi[t] == s # 最後の親がsかどうか
    return r.reverse
  end

  def reachable?(route, s, t) # 経路routeを使って、sからtへ到達可能かどうか
    (route[0] == s) && (route[route.length-1] == t)
  end
end

g = DirectedGraph.new

g["s", "v1"] = 16
g["s", "v2"] = 13
g["v1", "v2"] = 10
g["v2", "v1"] = 4
g["v1", "v3"] = 12
g["v2", "v4"] = 14
g["v3", "v2"] = 9
g["v3", "t"] = 20
g["v4", "v3"] = 7
g["v4", "t"] = 4

pp g.ford_fulkerson("s", "t")

実行結果

/Users/syou6162/ruby% ruby ford_fulkerson.rb
#<DirectedGraph:0x84170
 @edges=
  {"v1"=>["v2", "v3"],
   "v2"=>["v1", "v4"],
   "v3"=>["v2", "t"],
   "v4"=>["v3", "t"],
   "s"=>["v1", "v2"],
   "t"=>[]},
 @flow=
  {{"v4"=>"t"}=>4,
   {"v3"=>"t"}=>19,
   {"v4"=>"v3"}=>7,
   {"v2"=>"v1"}=>0,
   {"v1"=>"v2"}=>0,
   {"s"=>"v1"}=>12,
   {"v2"=>"v4"}=>11,
   {"v1"=>"v3"}=>12,
   {"s"=>"v2"}=>11,
   {"v3"=>"v2"}=>0},
 @nodes=["s", "v1", "v2", "v3", "v4", "t"],
 @weights=
  {{"v4"=>"t"}=>4,
   {"v3"=>"t"}=>20,
   {"v4"=>"v3"}=>7,
   {"v2"=>"v1"}=>4,
   {"v1"=>"v2"}=>10,
   {"s"=>"v1"}=>16,
   {"v2"=>"v4"}=>14,
   {"v1"=>"v3"}=>12,
   {"s"=>"v2"}=>13,
   {"v3"=>"v2"}=>9}>